Re: [Chicken-users] Error with large lists, (apply) and (string-append)

[Peter Bex]

On Thu, Aug 11, 2016 at 10:08:57PM +0100, Samadi van Koten wrote:
> When I run the attached code using `csi -s apply-error.scm`, I get this
> error (no newline, Thunderbird is forcibly wrapping it :-/):
> 
> csi: runtime.c:2802: C_save_and_reclaim: Assertion `C_temporary_stack >=
> C_temporary_stack_limit' failed.
> 
> Notice that the first line, using (+) with (apply) works fine, while
> (string-append) doesn't.
> 
> I'm using CHICKEN version 4.11.0 on Arch Linux.

Hello Samadi,

Thanks for reporting this bug.  I've had a look and at least I can
supply an analysis why this is behaving differently.

The reason behind the difference is that + maps directly to C_plus, which
takes its arguments straight from the argument vector that's built up
from the list.

string-append, on the other hand, is a pure Scheme procedure with a rest
argument.  The generated C code for argument list handling first converts
the procedure's argvector to a Scheme list, thereby "reifying" it to make
it accessible to code for manipulation.

The generated C code starts out like this:

-----------------------------------------------------------------
/* string-append in k7882 in k7879 */
static void C_ccall f_9808(C_word c,C_word *av){
C_word tmp;
C_word t0=av[0];
C_word t1=av[1];
C_word t2;
C_word *a;
if(!C_demand(C_calculate_demand((c-2)*C_SIZEOF_PAIR +13,c,4))){
C_save_and_reclaim((void*)f_9808,c,av);}
a=C_alloc((c-2)*C_SIZEOF_PAIR+13);
t2=C_build_rest(&a,c,2,av);
... more code ...
-----------------------------------------------------------------

With "c" being the argument count (100002), I'm sure you can imagine
that the C_demand check will _always_ fail (the stack simply isn't
so large), so it'll try to reclaim some memory through a minor GC.
C_save_and_reclaim() will set aside the argvector on the temporary
stack, which can't hold 100000 items, so it aborts, at which point
it triggers the error you've seen.

In January, I sent a patch to the mailing list which got rid of the
argvector limit (see bug #1098).  With this patch, C_save_and_reclaim
won't simply abort, but resize the temporary stack's size.

I updated the patch and tested with that version, but there it initially
seemed to behave worse: instead of complaining that the argvector was
too large, it simply kept looping on the C_demand/save_and_reclaim part
of the generated code, because the C stack isn't large enough (like I
explained above).  If I resize the stack limit using -:s4M, it works
without a hitch.

Note that the current releases of CHICKEN will also seem to work if you
increase the stack size to be large enough, but it may still fail if by
chance a minor GC needs to happen right the moment the string-append is
called because the argvector isn't big enough.

I'm not sure if this really classifies as a bug, since you are running
into a limitation.  If you're using this in production code, you should
know that applying string-append with large lists is not guaranteed to
work in general.  As srfi-13 states:

  (string-concatenate string-list) -> string

    Append the elements of string-list together into a single string.
    Guaranteed to return a freshly allocated string.

    Note that the (apply string-append STRING-LIST) idiom is not robust
    for long lists of strings, as some Scheme implementations limit the
    number of arguments that may be passed to an n-ary procedure.

And this was written before CHICKEN even existed.  In Gamnbit, we get:

*** ERROR IN "test.scm"@6.1 -- Number of arguments exceeds implementation limit
(string-append "1" "1" "1" "1" "1" "1" "1" "1" "1" "1" "1" "1" "1" "1" "1" ...)

In Guile 2.0, we get quite a stack trace ending with:

ice-9/boot-9.scm:65:2: Throw to key `vm-error' with args `(vm-run "VM: Stack 
overflow" ())'.

Racket, Gauche and Scheme48 deal with this code just fine.  Chibi takes
a long time, but also seems to work.  So I do think my patch for #1098 is
worthwhile (even though it will loop forever with the default settings).
I'll send an updated version to chicken-hackers (the one I originally
sent didn't apply anymore).

In CHICKEN 4.10, this code would trigger a nicer Scheme-level exception
though, which is catchable rather than the uncatchable abort from 4.11,
so I do think it's a regression.

Cheers,
Peter

signature.asc
Description: Digital signature