[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: weak hash tables
From: |
Andy Wingo |
Subject: |
Re: weak hash tables |
Date: |
Fri, 28 Oct 2011 11:02:01 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) |
Hi,
A follow-up to the weak table work.
On Mon 24 Oct 2011 19:19, Andy Wingo <address@hidden> writes:
> I [reimplemented weak hash tables] as open-addressed hash tables, with
> robin hood linear probing on collision
The tables work well. There are a couple of drawbacks currently:
(1) Moving weak references (disappearing links) is expensive for
libgc, because it has to free then allocate a new entry in the
disappearing links table. I have a patch to add an API to fix
this, and I think it will probably be accepted.
(2) You still have to run over the whole table after GC to update the
occupancy count of the table. I'm trying to fix that in libgc as
well, to add a variant of the disappearing link API that
increments a counter somewhere in memory.
> (However I don't think our current hash functions are very good.)
They were *terrible*. Replacing them with hash functions from the
internet improved the performace of compiling psyntax.scm by about 25 or
30%. It's not often you get to do that!
Currently, for me, compiling psyntax takes 1.4 seconds on master whereas
it takes 1.2 seconds on stable-2.0. This bothered me for a while, until
I realized that it's actually compiling different things.
psyntax-pp.scm on master (representing the expanded, optimized form of
psyntax.scm) is different from its counterpart on stable-2.0, though in
the end the compiled psyntax-pp.go on master is actually larger than the
stable-2.0 counterpart. For the moment I'm not worried, as there will
be many changes in 2.2 that should favor a more agressive inliner.
Andy
--
http://wingolog.org/