GNU bug report logs - #13088
stack overflow while compiling

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 13088 in the body.
You can then email your comments to 13088 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: rixed <at> happyleptic.org
To: bug-guile <at> gnu.org
Subject: stack overflow while compiling
Date: Wed, 5 Dec 2012 17:31:30 +0100

[Message part 1 (text/plain, inline)]

This program tries to compile a long cond expression and fails quickly with
a stack overflow.

Of course this procedure was generated and a user is unlikely to write such a
long cond, but considering the simplicity of the expression I'm surprised that
the stack is so solicited.

Note that I tested with guile 2.0.6 and not the fresh new 2.0.7 but I haven't
noticed anything in the changelog regarding memory consumption.

[stack-overflow.scm (text/plain, attachment)]

Message #8 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: rixed <at> happyleptic.org
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Thu, 6 Dec 2012 17:01:24 +0100

[Message part 1 (text/plain, inline)]

Some findings!

1. The problems probably originates in the translation to tree-il.
2. Using something like
(define-syntax my-cond
   (syntax-rule ()
      ((_ (p x ...)    )  (if p (begin x ...)))
      ((_ (p x ...) . l)  (if p (begin x ...) (my-cond . l))))

Makes the compilation to progress further but fails at a later with,
scheme@(guile-user)> (compile program #:to 'value)
language/assembly/compile-bytecode.scm:150:39: In procedure #<procedure
2be2a20 at language/assembly/compile-bytecode.scm:150:27 (x)>:
language/assembly/compile-bytecode.scm:150:39: In procedure
bytevector-u8-set!: Value out of range: 2070

I quick look at the cond clause in boot.scm does not show any evidence that
it will blow the stack. In my view the
suspect is any code in psyntax.scm that does a tree walk of the finished
code the cond clause is a really deep tree!
because that cond clause produces a already expanded large codeblock that
psyntax has to chew on while  the my-cond
clause above produces the tree-il incrementally in smaller steps.

/Stefan


On Wed, Dec 5, 2012 at 5:31 PM, <rixed <at> happyleptic.org> wrote:

> This program tries to compile a long cond expression and fails quickly with
> a stack overflow.
>
> Of course this procedure was generated and a user is unlikely to write
> such a
> long cond, but considering the simplicity of the expression I'm surprised
> that
> the stack is so solicited.
>
> Note that I tested with guile 2.0.6 and not the fresh new 2.0.7 but I
> haven't
> noticed anything in the changelog regarding memory consumption.
>
>

[Message part 2 (text/html, inline)]

Message #11 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: Chapi Chapo <rixed <at> happyleptic.org>
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Sat, 8 Dec 2012 22:44:15 +0100

[Message part 1 (text/plain, inline)]

Some further findings,

The whole macro-expansion to tree-il in psyntax is not done in a tail call
manner which limits the sizes
of code tree's that we can compile. Although it would be interesting to
know how to code the
psyntax expand algorithm in such a way that we don't risk blowing the
stack, I think we
will be better served by waiting for better stack algorithm that implement
growing stacks.

For the second bug above, it's not a bug, it's my-cond syntax not being
recognized and it tries
to tail-call 2000+ argument function which is not supported in guile :-)

In view of this I suggest that we close this bug or perhaps add a feature
request for growing stacks.
An alternate feature request is to have some way to tell guile the size of
the stack at start up.

For now anyone that need to compile large functions the only option, I
believe, is to change the stack size in the code
and recompile.

WDYT
/Stefan

On Thu, Dec 6, 2012 at 5:01 PM, Stefan Israelsson Tampe <
stefan.itampe <at> gmail.com> wrote:

> Some findings!
>
> 1. The problems probably originates in the translation to tree-il.
> 2. Using something like
> (define-syntax my-cond
>    (syntax-rule ()
>       ((_ (p x ...)    )  (if p (begin x ...)))
>       ((_ (p x ...) . l)  (if p (begin x ...) (my-cond . l))))
>
> Makes the compilation to progress further but fails at a later with,
> scheme@(guile-user)> (compile program #:to 'value)
> language/assembly/compile-bytecode.scm:150:39: In procedure #<procedure
> 2be2a20 at language/assembly/compile-bytecode.scm:150:27 (x)>:
> language/assembly/compile-bytecode.scm:150:39: In procedure
> bytevector-u8-set!: Value out of range: 2070
>
> I quick look at the cond clause in boot.scm does not show any evidence
> that it will blow the stack. In my view the
> suspect is any code in psyntax.scm that does a tree walk of the finished
> code the cond clause is a really deep tree!
> because that cond clause produces a already expanded large codeblock that
> psyntax has to chew on while  the my-cond
> clause above produces the tree-il incrementally in smaller steps.
>
> /Stefan
>
>
>
> On Wed, Dec 5, 2012 at 5:31 PM, <rixed <at> happyleptic.org> wrote:
>
>> This program tries to compile a long cond expression and fails quickly
>> with
>> a stack overflow.
>>
>> Of course this procedure was generated and a user is unlikely to write
>> such a
>> long cond, but considering the simplicity of the expression I'm surprised
>> that
>> the stack is so solicited.
>>
>> Note that I tested with guile 2.0.6 and not the fresh new 2.0.7 but I
>> haven't
>> noticed anything in the changelog regarding memory consumption.
>>
>>
>

[Message part 2 (text/html, inline)]

Message #14 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: rixed <at> happyleptic.org
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Mon, 10 Dec 2012 13:16:09 +0100

-[ Sat, Dec 08, 2012 at 10:44:15PM +0100, Stefan Israelsson Tampe ]----
> The whole macro-expansion to tree-il in psyntax is not done in a tail call
> manner which limits the sizes
> of code tree's that we can compile. Although it would be interesting to
> know how to code the
> psyntax expand algorithm in such a way that we don't risk blowing the
> stack, I think we
> will be better served by waiting for better stack algorithm that implement
> growing stacks.

If it was not obvious already I must confess I'm ignorant about the internals
of guile (and of any other scheme compiler), so what I will say is probably
irrelevant. but I changed the cond into the equivalent if forms, which
I believe are not macros, but the result is the same (stack overflow).

> An alternate feature request is to have some way to tell guile the size of
> the stack at start up.

If though that was what '(debug-set! stack x)' was for, but this does not
seams to change anything. I also tried changing stack limits with ulimit
to no avail.

> For now anyone that need to compile large functions the only option, I
> believe, is to change the stack size in the code
> and recompile.

Any hint on how to do that specifically for guile, beyond the above
ulimit/setrlimit?

Message #17 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: Chapi Chapo <rixed <at> happyleptic.org>
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Tue, 11 Dec 2012 23:29:31 +0100

[Message part 1 (text/plain, inline)]

Hi,

I did some effort into getting this working. but first you could try to use
an
or-map to get what you want in stead if compiling everything into code. but
it's probably
faster what you are doing.

Anyway in vm.c I changed the
#define VM_DEFAULT_STACK_SIZE (64 * 1024)

to
#define VM_DEFAULT_STACK_SIZE (64 * 1024 * 64)

and recompiled!

Then I can compile to tree-il. Compiling all the way does not work well,
But if you enter
scheme@(guile-user)> (compile program #:to 'value #:opts '(#:partial-eval?
#f #:cse? #f))  ;;NO OPTIMIZATION PASSES

It will compile to.

$7 = #<procedure 3708400 (proto server-port client-zone server-zone
signature-id)>


In all this emphasizes what I said in earlier and I would still ask for a
sane way to change the stack size for guile
and document it well.

Cheers!
/Stefan




On Mon, Dec 10, 2012 at 1:16 PM, <rixed <at> happyleptic.org> wrote:

> -[ Sat, Dec 08, 2012 at 10:44:15PM +0100, Stefan Israelsson Tampe ]----
> > The whole macro-expansion to tree-il in psyntax is not done in a tail
> call
> > manner which limits the sizes
> > of code tree's that we can compile. Although it would be interesting to
> > know how to code the
> > psyntax expand algorithm in such a way that we don't risk blowing the
> > stack, I think we
> > will be better served by waiting for better stack algorithm that
> implement
> > growing stacks.
>
> If it was not obvious already I must confess I'm ignorant about the
> internals
> of guile (and of any other scheme compiler), so what I will say is probably
> irrelevant. but I changed the cond into the equivalent if forms, which
> I believe are not macros, but the result is the same (stack overflow).
>
> > An alternate feature request is to have some way to tell guile the size
> of
> > the stack at start up.
>
> If though that was what '(debug-set! stack x)' was for, but this does not
> seams to change anything. I also tried changing stack limits with ulimit
> to no avail.
>
> > For now anyone that need to compile large functions the only option, I
> > believe, is to change the stack size in the code
> > and recompile.
>
> Any hint on how to do that specifically for guile, beyond the above
> ulimit/setrlimit?
>
>

[Message part 2 (text/html, inline)]

Message #20 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: rixed <at> happyleptic.org
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Wed, 12 Dec 2012 09:33:35 +0100

-[ Tue, Dec 11, 2012 at 11:29:31PM +0100, Stefan Israelsson Tampe ]----
> Anyway in vm.c I changed the
> #define VM_DEFAULT_STACK_SIZE (64 * 1024)
> 
> to
> #define VM_DEFAULT_STACK_SIZE (64 * 1024 * 64)
> 
> and recompiled!

Oh, I hadn't realized you were speaking about the VM's stack. It all makes
sense now.
Any inconvenient to set this stack even bigger ? How many such stacks do we
have in a running environment ? One per thread ?

> Then I can compile to tree-il. Compiling all the way does not work well,
> But if you enter
> scheme@(guile-user)> (compile program #:to 'value #:opts '(#:partial-eval?
> #f #:cse? #f))  ;;NO OPTIMIZATION PASSES
> 
> It will compile to.
> 
> $7 = #<procedure 3708400 (proto server-port client-zone server-zone
> signature-id)>

Yes, I did this and as a result the compiled function was... 20% faster !?
(note that my bench exclude the compilation time, and uses get-internal-run-time
as a clock source).

Thank you very much for all these advices.
As usual, support from free software community is much better than it is from
any business I've seen :-)

Message #23 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: Chapi Chapo <rixed <at> happyleptic.org>
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Wed, 12 Dec 2012 18:13:39 +0100

[Message part 1 (text/plain, inline)]

Hi,

I added a patch to suggest a new environment variable.

   GUILE_STACK_SIZE_NSCM

If this is defined and setted to a reasonable number then this will be the
number
of SCM (8 byte on a 64bit arch or 4 on a 32 bit arch) to allocate to the VM
stack.

The naming might not be the best, we might want to name it VM_STACK in
stead of stack.

anyway here is a patch. I tested it to the example in the beginning of this
thread and it seams
to work just fine.

The intention is for this to be enough to close the bug.

/Stefan





On Wed, Dec 12, 2012 at 9:33 AM, <rixed <at> happyleptic.org> wrote:

> -[ Tue, Dec 11, 2012 at 11:29:31PM +0100, Stefan Israelsson Tampe ]----
> > Anyway in vm.c I changed the
> > #define VM_DEFAULT_STACK_SIZE (64 * 1024)
> >
> > to
> > #define VM_DEFAULT_STACK_SIZE (64 * 1024 * 64)
> >
> > and recompiled!
>
> Oh, I hadn't realized you were speaking about the VM's stack. It all makes
> sense now.
> Any inconvenient to set this stack even bigger ? How many such stacks do we
> have in a running environment ? One per thread ?
>
> > Then I can compile to tree-il. Compiling all the way does not work well,
> > But if you enter
> > scheme@(guile-user)> (compile program #:to 'value #:opts
> '(#:partial-eval?
> > #f #:cse? #f))  ;;NO OPTIMIZATION PASSES
> >
> > It will compile to.
> >
> > $7 = #<procedure 3708400 (proto server-port client-zone server-zone
> > signature-id)>
>
> Yes, I did this and as a result the compiled function was... 20% faster !?
> (note that my bench exclude the compilation time, and uses
> get-internal-run-time
> as a clock source).
>
> Thank you very much for all these advices.
> As usual, support from free software community is much better than it is
> from
> any business I've seen :-)
>
>

[Message part 2 (text/html, inline)]

[stack-size.patch (application/octet-stream, attachment)]

Message #26 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: rixed <at> happyleptic.org
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Fri, 14 Dec 2012 13:46:51 +0100

> I added a patch to suggest a new environment variable.

I applied your patch locally and am satisfied so far.
I let you know is I run into troubles.

Message #29 received at 13088 <at> debbugs.gnu.org (full text, mbox):

From: Andy Wingo <wingo <at> pobox.com>
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: Chapi Chapo <rixed <at> happyleptic.org>, 13088 <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Thu, 07 Mar 2013 14:26:51 +0100

On Sat 08 Dec 2012 22:44, Stefan Israelsson Tampe <stefan.itampe <at> gmail.com> writes:

> tail-call 2000+ argument function which is not supported in guile :-)

This should be supported.  Just fixed this in stable-2.0.

> I suggest that we close this bug or perhaps add a feature request for
> growing stacks.
>
> An alternate feature request is to have some way to tell guile the size
> of the stack at start up.

In this case I agree, there is no bug in the expander or in the
compiler.  We should be able to grow stacks, but that is tricky with
stable-2.0.  Ideally we would be able to link different stack segments
together with overflow/underflow handlers, as in the Dybvig paper, but
that would require some experimentation that would best be done on
master.

I pushed a patch based on yours to add a GUILE_STACK_SIZE environment
variable.  I hate environment variables but hopefully we can remove it
in 2.2.

Thanks for looking into this!

Andy
-- 
http://wingolog.org/

Message #34 received at 13088-done <at> debbugs.gnu.org (full text, mbox):

From: Andy Wingo <wingo <at> pobox.com>
To: 13088-done <at> debbugs.gnu.org
Subject: Re: bug#13088: stack overflow while compiling
Date: Thu, 07 Mar 2013 14:27:13 +0100

Marking as done.
-- 
http://wingolog.org/

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.