Re: [PATCH] Efficient Gensym Hack

[Mark H Weaver <mhw@netris.org>]

Hi Andy, thanks for the quick response! :)

Andy Wingo <wingo@pobox.com> writes:

> On Mon 05 Mar 2012 18:17, Mark H Weaver <mhw@netris.org> writes:
>
>> It makes 'gensym' about 4.7 times faster on my Yeeloong.  Gensyms are
>> not given names or even numbers until they are asked for their names or
>> hash values (for 'equal?' hash tables only).
>
> Ah, interesting :)  I had always thought that you would need to number
> them first, but I see that you found a way to avoid that.

I got the idea from http://icfp06.cs.uchicago.edu/dybvig-talk.pdf

Anyway, in retrospect, I don't even see how I could make it work
otherwise.  The problem is that with lazy gensyms, the name you
ultimately assign to the gensym _must_ not already be interned.  Think
about it.  Suppose you assign a gensym with prefix "foo" the number 6,
and that there's another symbol already interned with the name "foo6".
Now you have two distinct symbols (in the sense of 'eq?'), both
semantically interned, with the same name.  There's no way to recover
from this.

The only solution I could find is to give the gensym a name that has not
already been interned.  In my implementation, I don't increment the
counter at all until the lazy gensym is "forced".  If that name is
already interned, and I just keep incrementing the counter until I find
a unique symbol.  Only after it has been successfully interned do I
_commit_ to the new name by clearing the "lazy gensym flag".

>> 1. The implementation of symbols is split between symbols.c and
>> strings.c, and the gensym hack needs the internals of both.  I had to
>> add some new internal functions, including one to make a stringbuf from
>> a string and one to make a string from a stringbuf.
>
> Yeah, this is not good.  With my dynstack work I found that functions
> that are internal but not static can prevent some important inlining.

That's definitely true, but fortunately these new internal functions are
used only by the gensym code.  Anyway, if you're concerned about this,
one option would be to combine string.c and symbol.c into a single file.

> Your thoughts on that weak set mechanism would be appreciated.

Everything I know about weak storage mechanisms I learned from Bruno
Haible.  Highly recommended reading:

  http://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html

I'll explore issues regarding the symbol table in another email.

    Thanks!
      Mark