arraysprologswi-prologprolog-directive-dynamic

Asserting and using fast, LARGE arrays in prolog

I'm using functors to get random-access arrays using arg/3 in SWI-Prolog. What i'm doing is loading values from a sample into a functor I create and asserting the array for future use.

Once loaded, Random access is indeed O(1) as I've verified using time/1. The issue is loading the functor from the assertion takes a lot of time ( time/1 suggests it's linear in the size of the array ). Is there any way i can speed this up to constant time?

Minimal code for reproduction:

:- dynamic
    current_sample/1.

xrange(L,R,X):-
    L < R,
    ( X = L;
    X1 is L+1, xrange(X1,R,X)
    ).


arraybase_from_list__set_arg_from_list([], _, _).
arraybase_from_list__set_arg_from_list([Head|Tail], I, ResArray):-
    I1 is I+1,
    nb_setarg(I1, ResArray, Head),
    arraybase_from_list__set_arg_from_list(Tail, I1, ResArray).

arraybase_from_list(List, ResArray):-
    length(List, L),
    functor(ResArray, custom_array_data, L),
    arraybase_from_list__set_arg_from_list(List, 0, ResArray ).


test_array_create( N ):- % Creates a dummy array of squares of numbers fromo [0,N)
    findall( X2, (xrange( 0,N,X), X2 is X*X), XList ),
    arraybase_from_list( XList, Arr ),
    assert( current_sample(Arr) ).

test_array_get(I,V):- % Unifies V with Ith element of Current sample
    I0 is I+1,
    current_sample(Arr), % Take turns timing this
    arg( I0, Arr, V ).   % And then timing this
Solution

  • You are seeing linear overhead when using current_sample/1 because the arguments of predicates are copied from the database when a predicate is called.

    There are several ways to get rid of this linear overhead, turning it into 𝒪(1).

    A good way

    A good way to do it is to carry around the whole array, either explicitly or implicitly, throghout all predicates that need to access it.

    You can use semicontext notation to do it implicitly (see ), or write your own custom expansion rules. This is similar to monads in Haskell.

    Consider doing this!

    A much worse way

    A much worse and only on the surface easier way is to use global variables instead of the the global database to store the term.

    Avoid this!

    Some reasons: