Subject: Re: Strange behaviour with large lists

From: Jan Wielemaker <[email-masked]>
Date: Mon, 16 Oct 2000 16:59:54 +0200

On Mon, 16 Oct 2000, Luis Iraola wrote:

>Version 3.4.0 on Windows NT and 98 behaves funny when managing large lists
>(10^5 elements) and the same goal is repeated several times.
>
>The first time the goal is asked the systems answers quickly:
>
>Welcome to SWI-Prolog (Version 3.4.0)
>Copyright (c) 1990-2000 University of Amsterdam. 
>Copy policy: GPL-2 (see www.gnu.org)
>
>For help, use ?- help(Topic). or ?- apropos(Word).
>
>?- findall(N,between(1,100000,N),L), findall(N,select(N,L,_),L).
>
>N = _G5
>L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] 
>
>Yes
>
>--------------- 0 -----------------
>Second time, a couple of errors are raised immediately:
>
>?- findall(N,between(1,100000,N),L), findall(N,select(N,L,_),L).
>ERROR: Out of global stack
>ERROR: Out of global stack

Interesting problem.  The trick is that the system remembers how
big the stacks were after the last garbage collect.  Now, using
your values, it turns out the system nearly runs out of stack
after the 2nd garbage collect it performs when running this
goal.

It uses this value to decide when the next garbage collect
call makes sence.  In this case it thinks ``the previous GC took
the stack down to 3.6 MB (default limit 4MB), it doesn't seem to make
much sense to run another''.  If you just blindly keep running GC at
any possible opportunity if the stacks are low, the system will get
extremely slow before running out of stack in cases where the stack
limit really won't do the trick.

Now, it is easy to fix your problem by resetting the remembered
stack-size-after-gc in the toplevel's call to trim_stacks/0, returning
unused stack to the OS.

This however won't solve the whole problem.  Consider

t :- findall(N,between(1,100000,N),L), findall(N,select(N,L,_),L).

?- t,t.

This situation gives the same problem.  The first t succeeds, turning
all data into garbage.  The second t makes the system run out of stack.
If you do

?- t, garbage_collect, t.

all is fine: the garbage_collect in the middle collects the entire
stacks (except a few hundred bytes used by the system).

Second problem is that it runs out of stack while running foreign code
(collecting the solutions of findall) and that doesn't work very
elegantly.

Summarising
===========

For the moment, the simplest solution is to raise the stack limits a
bit, ensuring enough space after a GC to expand the stacks.  Using
-G0 -T0 sets the relevant limits to the maximum allowed on your
system (128MB on 32-bit machines).

On the longer run, it seems the policy for GC should be improved.

	Regards --- Jan