CODEWITHSUNDEEP
listprologout-of-memoryswi-prologclpfd
Carles Araguz
Carles Araguz

Reputation: 1177

How can I avoid an "out of global stack" error in SWI-Prolog?

I have a (SWI-)Prolog program that uses CLP(FD) variables in an utterly massive way (²). I am moving lists of CLP(FD) items in and out of several predicates (¹), and their constraints grow exponentially. My code works for small lists, but when I try to use it for long lists of elements (where the amount of constraints for each element becomes enormous) I end up with an Out of global stack error.

My point is whether I can use a different method for passing such huge arguments without using the stack. My first thought was to use asserta to store the intermediate results in the dynamic database but I'm not sure if I'll be able to store uninstantiated variables or CLP(FD) constraints that way. And I don't know if this is an optimal solution either...

¹ MORE DETAILS: What I need is an overlap of N lists of length L where the first elements are offseted. However, the offsets are not bound but are CLP(FD) variables.

² EVEN MORE DETAILS: Basically, I have a number of lists where each element has thousands of constraints. Each element constraints are basically holding information about its value, which is linked to a "master-variable" value. Depending on the master-variable's value, each list item will have a value or another.

Since I already had problems with the implementation of such list generator and I asked here for some advice, you can see the actual list-maker predicate, overlap_at/5, here.

overlap_lists/4 is the predicate which is issuing the error (it does work fine for Rs's lengths of less than 140 elements AND less than 10 Cs elements):

% Cs -> lists that have to be overlapped. Their items are integers.
% Ss -> Offsets per each list. They are CLP(FD) variables.
% Rs -> (not important here)
% Os -> List of overlapped elements.

overlap_lists(Cs,Ss,Rs,Os) :-
    length(Rs,L),
    zeros(Zs,L), % The initial list to overlap with is a list filled with zeros.
    overlap(Cs,Ss,Zs,Os),
    list_limit(Os,Rs). % Constrains the consumptions

overlap([],[],Fs,Fs) :- !.
overlap([C|Cs],[S|Ss],Os,Fs) :-
    fd_inf(S,Inf),
    overlap_at(Os,C,S,Inf,Os2),!,
    overlap(Cs,Ss,Os2,Fs).

overlap_at([], _, _, _, []).
overlap_at([A|As], Bs, S, N0, [AB|ABs]) :-
    overlap_here(Bs, [A|As], [AB|ABs], Conj),
    S #= N0 #==> Conj,
    S #> N0 #==> AB #= A,
    N1 #= N0 + 1,
    overlap_at(As, Bs, S, N1, ABs).

overlap_here(_, [], _, 1) :- !.
overlap_here([], [A|As], [AB|ABs], (AB #= A #/\ Rest)) :-
    overlap_here([], As, ABs, Rest).    
overlap_here([B|Bs], [A|As], [AB|ABs], (AB #= A + B #/\ Rest)) :-
    overlap_here(Bs, As, ABs, Rest).

Upvotes: 4

Views: 2542

Answers (1)

mat
mat

Reputation: 40768

The first thing that comes to mind: Increase the global stack that SWI-Prolog allocates via

swipl -G128M ...

It may help you to read more about the Prolog stacks: For example, the global stack is not to be confused with the local stack. Passing arguments differently will typically not help you to decrease the global stack usage. Richard O'Keefes The Craft of Prolog contains a good discussion on where the space goes.

On 64-bit processors, the global stack can be larger than 128MB with SWI-Prolog, so for serious computations, you may need a 64-bit machine with a lot of RAM.

That being said, the code I posted uses only a polynomial, not exponential, amount of memory. If you are formulating the problem in such a way that it needs exponential space, you may first try to find a more (memory-)efficient formulation. The problem does not seem to require exponential space intrinsically.

If you need to preserve constraints over assertz/1, use copy_term/3 to obtain the constraints as residual goals, and assert these residual goals along with the variables so that you can later reinstate the goals via maplist(call, Gs).

Upvotes: 4

Related Questions