The dynamic stack

The dynamic stack

[Andy Wingo]

Hi,

I have pushed a patch to master that changes the implementation of the
dynamic stack from being a linked list on the heap to being an actual
stack.  This allows us to push items on the stack in many cases without
allocating memory at all.

This has become particularly important in `master', because ports in
master have a similar locking discipline as stdio ports in glibc.  (See
"Streams and Threads" in the libc manual, for more.)  The upshot is that
there's a lot more scm_dynwind_pthread_mutex_lock in master, and that
was slowing things down noticeably.

This patch makes a simple "guile examples/web/debug-sxml.scm" server go
from serving 3215 reqs/s to 3830 reqs/s.  (Using "ab -n 100000 -c100
http://localhost:8080/" on the same machine to test; the machine is my
laptop.  By way of comparison, stable-2.0 does 3225 reqs/s on that
benchmark.)

Still, there are some things we can do to improve matters, especially
with regards to prompts.  If instead of storing a cookie, the VM did a
setjmp() on entry, we could avoid allocating a jmpbuf for each prompt.
This could bring some other code simplifications, notably, the cleanup
of partial_cont_call.

Anyway, these are disconnected ramblings.  Review is welcome; I'll try
to incorporate any feedback.  Cheers!

Andy
-- 
http://wingolog.org/

Re: The dynamic stack

[Ludovic Courtès]

Hi,

Andy Wingo <wingo@pobox.com> skribis:

> I have pushed a patch to master that changes the implementation of the
> dynamic stack

The “dynwind stack” actually (I misread it the first time.)

> from being a linked list on the heap to being an actual stack.  This
> allows us to push items on the stack in many cases without allocating
> memory at all.

Sounds great!

Could you please add comments in dynstack.c (above each function), and
make sure to follow GCS-style (no hanging brace, for example)?

Regarding comments, I see that <https://www.ohloh.net/p/guile> now ranks
Guile as one of the least commented source code bases.  There are many
good reasons why we ought to do better here, IMO.

WDYT?

> This patch makes a simple "guile examples/web/debug-sxml.scm" server go
> from serving 3215 reqs/s to 3830 reqs/s.  (Using "ab -n 100000 -c100
> http://localhost:8080/" on the same machine to test; the machine is my
> laptop.  By way of comparison, stable-2.0 does 3225 reqs/s on that
> benchmark.)

Nice!

Did you try a micro-benchmark that would ‘dynamic-wind’ repeatedly?

Thanks,
Ludo’.

Re: The dynamic stack

[Andy Wingo]

Greets :)

On Tue 06 Mar 2012 18:20, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> skribis:
>
>> I have pushed a patch to master that changes the implementation of the
>> dynamic stack
>
> The “dynwind stack” actually (I misread it the first time.)

Yes, it did have this name before.  (More often, "the wind list".)  But
since "dynwind" is overloaded so much (dynamic-wind operator, <dynwind>,
scm_dynwind_*), and the dynamic stack can have other things on it like
prompts, I thought it best to give it a new name.

> Could you please add comments in dynstack.c (above each function), and
> make sure to follow GCS-style (no hanging brace, for example)?

What do you mean by "no hanging brace"?  To my knowledge^Wignorance this
file does have the right style.

What sorts of comments would you like to see?  I have been working with
this code a lot, so perhaps some things which are obvious to me from
names, types, assertions, etc that might not actually be obvious.  I
don't see what I can write that isn't wholly redundant.  Perhaps you
will let me know :-)

Regards,

Andy
-- 
http://wingolog.org/

Re: The dynamic stack

[Noah Lavine]

Hello,

>> The “dynwind stack” actually (I misread it the first time.)
>
> Yes, it did have this name before.  (More often, "the wind list".)  But
> since "dynwind" is overloaded so much (dynamic-wind operator, <dynwind>,
> scm_dynwind_*), and the dynamic stack can have other things on it like
> prompts, I thought it best to give it a new name.

I see your point about the old name, but I find the new name
confusing. What about the stack that holds regular program variables
and temporaries? That is also dynamic, so at first I thought you were
referring to that. I didn't know what was going on until this email.

I thought of "control stack", since the things on it deal with control
flow. But that is also confusing, because it doesn't include return
addresses and frame pointers.

Noah

Re: The dynamic stack

[Andy Wingo]

Hi Noah,

On Wed 07 Mar 2012 07:05, Noah Lavine <noah.b.lavine@gmail.com> writes:

>>> The “dynwind stack” actually (I misread it the first time.)
>>
>> Yes, it did have this name before.  (More often, "the wind list".)  But
>> since "dynwind" is overloaded so much (dynamic-wind operator, <dynwind>,
>> scm_dynwind_*), and the dynamic stack can have other things on it like
>> prompts, I thought it best to give it a new name.
>
> I see your point about the old name, but I find the new name
> confusing. What about the stack that holds regular program variables
> and temporaries?  That is also dynamic, so at first I thought you were
> referring to that. I didn't know what was going on until this email.

It's a good question!

The essential difference is that lookup on the VM stack is static --
things are always at known locations.  That's what lexical scoping gives
us.  Lookup on the dynamic stack is dynamic: e.g. "what's the nearest
prompt with tag FOO", "what are the dynamic-wind expressions within that
extent", etc.

In an ideal world, we'd probably use the same stack for both purposes,
as C++ does (AFAIU).  The reason that we don't is that the scm_dynwind_*
API manipulates the dynwind stack from outside of the VM.

Cheers,

Andy
-- 
http://wingolog.org/

Re: The dynamic stack

[Ludovic Courtès]

Hi!

Andy Wingo <wingo@pobox.com> skribis:

> On Tue 06 Mar 2012 18:20, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> skribis:
>>
>>> I have pushed a patch to master that changes the implementation of the
>>> dynamic stack
>>
>> The “dynwind stack” actually (I misread it the first time.)
>
> Yes, it did have this name before.  (More often, "the wind list".)  But
> since "dynwind" is overloaded so much (dynamic-wind operator, <dynwind>,
> scm_dynwind_*), and the dynamic stack can have other things on it like
> prompts, I thought it best to give it a new name.

Indeed, very good point.

That said, when I first saw the topic, I was expecting something about
the VM stack, which could now be grown dynamically upon stack overflow.
:-)

Now, what would be a better name?  As you say, in an ideal world,
there’d be only one stack so...

>> Could you please add comments in dynstack.c (above each function), and
>> make sure to follow GCS-style (no hanging brace, for example)?
>
> What do you mean by "no hanging brace"?

Anything reported by:

  grep -nH -e '[[:graph:]]\+[[:blank:]]*{$' *.[ch]

such as:

  typedef enum {
    SCM_DYNSTACK_TYPE_NONE = 0,
    SCM_DYNSTACK_TYPE_FRAME,
    SCM_DYNSTACK_TYPE_UNWINDER,
    SCM_DYNSTACK_TYPE_REWINDER,
    SCM_DYNSTACK_TYPE_WITH_FLUIDS,
    SCM_DYNSTACK_TYPE_PROMPT,
    SCM_DYNSTACK_TYPE_DYNWIND,
  } scm_t_dynstack_item_type;

Also, “Don't declare both a structure tag and variables or typedefs in
the same declaration” (info "(standards) Syntactic Conventions").

> What sorts of comments would you like to see?  I have been working with
> this code a lot, so perhaps some things which are obvious to me from
> names, types, assertions, etc that might not actually be obvious.  I
> don't see what I can write that isn't wholly redundant.  Perhaps you
> will let me know :-)

Comments above functions would be nice.  For instance, I can’t tell what
this does:

  scm_t_dynstack *
  scm_dynstack_capture (scm_t_dynstack *dynstack, scm_t_bits *item)

A two-line comment above mentioning DYNSTACK and ITEM would be great
(info "(standards) Comments").  (And we could use the neat
M-x semantic-ia-show-doc, which gives a Geiser feel to this dull C
world.  ;-))

And I think it wouldn’t be redundant for many/most of the functions in
that file.

Thanks,
Ludo’.