Re: [PATCH] Efficient Gensym Hack

[Andy Wingo]

Hi Mark,

A quick reaction to your summary; I'll look at the patches shortly.

On Mon 05 Mar 2012 18:17, Mark H Weaver <address@hidden> writes:

> Here's an implementation of the efficient gensym hack for stable-2.0.

Excellent!

> 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.

> 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.
(I found the performance impact using "perf record", and valgrind
--tool=callgrind).  It's good that we have internal functions to avoid
bloating our public API, but they do seem to prevent optimization.  I
wonder if LTO could help here.

> 2. The symbol table uses the symbols themselves as the keys.  This was
> already hairy and inefficient: take a look at symbol_lookup_assoc_fn,
> which has to convert symbols to strings (which involves allocation) to
> implement the hash lookup!

It uses the symbols as keys, but it uses the string hash value (not the
symbol hashq value) as the hash.  There are some important cases in
which no string need be allocated: scm_from_utf8_symbol and
scm_from_latin1_symbol.  But yes, it's hairy.

Note also that this has changed significantly in master.  Your thoughts
on that weak set mechanism would be appreciated.

> IMHO, it would be much better to use a weak-value hash table, with
> strings as the keys and symbols as the values.  Maybe we can do that
> for 2.2.

Interesting idea.  It's not clear to me how this would solve this
problem though; but perhaps that will be clear when I read the patches.

Anyway, to keep this short, I'll look at the patches in another mail.

Cheers!

Andy

ps. An interesting benchmark (before and after) would be to time the
execution of (compile-file "module/ice-9/psyntax.scm").
-- 
http://wingolog.org/