[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)


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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]