Geek Answers Handbook

Prolog Checking Label Heuristics

I am working on some experiments to compare different heuristic labels in Sicstus Prolog.

But I continue to go into Resource Error: Out of Memory.

I'm sure something is wrong in my test code.

The following code will repeat 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 calling the predicate t1, I get the exception "Resource error: insufficient memory".

I think I should do something after I call atest to release the resources?

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

+1
source share
2 answers

You are doing nothing wrong, but trying to run

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

for N up to 1,000,000. The system creates a search tree with depth N and must store intermediate states of variables and a constraint system for each level. It takes up a lot of memory for large N, and it is quite possible that you get memory overflow for one run with large N.

The second problem is that you use your tests in a recursive loop, i.e. effectively create a connection

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

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

The simplest improvement is to reduce each search after the first solution by changing the code to once(atest(C,R)) . A further improvement is to run tests in a failover cycle.

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

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

+3
source

Toplevel hides alternative answers

If you test t1 on a SICStus top-level shell with lower values, you may get the false impression that t1 has exactly one answer / solution. However, it is not! So, the top layer hides other answers from you. This is a special behavior in SICStus toplevel, which does not show further answers if the request does not contain variables. But there is only x! many solutions for your marking, x! for each test case, and time for other solutions is a random value. You have lost memory because for each test case, Prolog saves a record to continue releasing the next solution for each test case.

Cyclic

I do not recommend using a fail 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 with the loop caused by the failure is when atest/2 accidentally fails for some C and R In a fail-safe cycle, this will be almost imperceptible, while it will not succeed above the structure.

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

Timing

If you make a timing, it’s better to use only the first element of the list and calculate the difference:

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

Thus, alternative answers to the goal will give you more meaningful value.

+1
source

More articles:


All Articles