Re: [eclipse-clp-users] Trail stack overflow

Hi Matthew,

On 08/07/2013 16:26, mskala_at_ansuz.sooke.bc.ca wrote:
> Please note that I am not asking how to increase the size of the trail stack.
>
> What pattern of use could cause excessive consumption of the trail, not
> global, stack?  I have a piece of code that involves nested (for() do ())
> loops containing code that is supposed to be deterministic, and it's
> causing the trail stack to overflow - even when enlarged to as much as 3
> gigabytes.  Global stack consumption is only a couple hundred K.
>
> My understanding is that the trail stack records unifications, in order,
> so that they can be undone in reverse order on backtracking.  Stray choice
> points inside the loops might cause it to overflow, but then I would
> expect the global stack to also become large, and probably overflow first,
> and that's not happening.  I'll experiment with adding some cuts and
> once() calls but I don't have high hopes for this.

If your code is deterministic, then the trail will not record anything.
Even if the code is made deterministic (e.g. with a cut) _after_ something
has been trailed, this should be cleaned up by the garbage collector.

The first thing I would do is to trace through a few iterations of your
loop with the tracer, looking for *EXIT ports, which indicate that the
exited predicate left a choicepoint behind.

Generally, you are correct to expect a certain global stack consumption
to accompany the trail consumption, although the local stack also
gets trailed.


>
> My next guess is that because my loop is computing a cumulative sum using
> fromto(), there's always a new unification that will be visible in the
> next iteration added to the trail stack on each iteration; as a result,
> the many unifications of local variables, which should be removable
> because they are no longer visible once the iteration terminates, are
> stuck below the non-removable cumulative sum variable, and can't be
> removed.  If that's it, is there anything I can do about it?  One
> possibility that occurred to me might be to use a non-logical variable to
> store my cumulative sum, to keep it off the trail stack and avoid
> fromto().  However, I'm updating a bunch of variables from iteration to
> iteration using fromto() at the moment, and they won't all be easy to
> switch to non-logical variables, so this might slow rather than stopping
> the accumulation of trail stack entries, and I'm not sure I want to put
> effort into it until I have more evidence that that's even a correct
> diagnosis of the problem to begin with.

No, if your code is deterministic, there is no such piling-up effect.
Logical variables and last-call optimizations make such loops (and
equivalent tail-recursive predicates) constant in space consumption.
I'm pretty sure there is no need to resort to nonlogical hacks.


Anyway, if you get stuck, send me some code and I can look into it.

Cheers,
Joachim