Asserting and using fast, LARGE arrays in prolog

Question

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

Answer 1

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 dcg), 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:

• it's not portable
• it introduces global state, making your predicate hard to read and debug
• it's not significantly more efficient than simply using additional arguments to carry the array through (implicitly or explicitly)
• it's error prone
• etc.