Prolog, testing labeling heuristics

Question

I'm working on some experiments for comparing different labeling heuristics in Sicstus Prolog.

But I keep getting into 'Resource error: insufficient memory'.

I'm pretty sure I'm doing something wrong in my testcode.

The following code will replicate my problem:

:- use_module(library(clpfd)).
:- use_module(library(lists)).

atest( R, C ):-
    X is R * C,
    length( M, X),
    domain( M, 0, X),
    all_distinct( M ),

    statistics(walltime, [_,_SinceLast]),
    labeling( [],M ),
    statistics(walltime, [_,SinceLast]),

    write('Labeling time: '), write(SinceLast),write('ms'),nl.


% Testcode for looping through alot of variations and run one test for each variant
t1:-
    Cm = 1000,
    Cr = 1000,
    (
    for(C,0, Cm),
    param([Cm,Cr])
    do
        (
        for(R, 0, Cr ),
        param([C])
        do
            atest( C, R )
        )
    ).      

A short time after I call the t1 predicate, I get a 'Resource error: insufficient memory' exception.

I guess I should do something after I call atest to release resources?

Also: Is this the correct way to measure labeling-time? Any better way to do this?

Answer 1

You are not doing anything strictly wrong, but you are trying to run

length(Xs,N), domain(Xs,0,N), all_distinct(Xs), labeling([],Xs).

for N up to 1000000. The system constructs a search tree with depth N, and has to store intermediate states of the variables and the constraint system for each level. This takes a lot of memory for large N, and it is quite possible that you get a memory overflow already for a single run with large N.

The second issue is that you are running your benchmarks in a recursive loop, i.e. you are effectively creating a conjunction

atest(0,0), ..., atest(1000,1000)

and since each call to atest/2 succeeds with its first solution and keeps its search state around, this means you are trying to create a search tree with 250500250000 levels...

The simplest improvement is to cut each search after the first solution by changing your code to once(atest(C,R)). A further improvement is to run the benchmarks in a failure-driven loop

(
    between(0,Cm,C),
    between(0,Cr,R), 
    once(atest(C,R)),
    fail
;
    true
)

which will free memory sooner and faster, and reduce distortion of your measurements due to garbage collection.

Answer 2

Toplevel hides alternate answers

If you are testing t1 on SICStus' toplevel shell with some smaller values you might get the wrong impression that t1 has exactly one answer/solution. However, this is not the case! So the toplevel hides from you the other answers. This is a special behavior in the SICStus toplevel which does not show further answers if the query does not contain variables. But there is a total of x! many solutions for your labeling, x! for each test case and the timing for the other solutions is some random value. You are out of memory because for each test case, Prolog keeps a record to continue producing the next solution for each test case.

Looping

I do not recommend using a failure driven loop for testing, instead, use the following loop which is very similar but much safer:

\+ (
      between(0, Cm, C),
      between(0, Cr, R),
      \+ atest(C, R)
   ).

The big difference to a failure driven loop is when atest/2 accidentally fails for some C and R. In a failure driven loop this will go essentially unnoticed, whereas above construct will fail.

Some systems provide a predicate forall/2 for this purpose.

Timing

If you do timing, better only use the first element of the list and compute the difference:

statistics(walltime, [T0|_]),
Goal,
statistics(walltime, [T1|_]),
D is T1 - T0.

In this manner alternate answers to Goal will give you a more meaningful value.