mit-scheme-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[MIT-Scheme-devel] hash tables with ephemerons


From: Taylor R Campbell
Subject: [MIT-Scheme-devel] hash tables with ephemerons
Date: Fri, 20 Aug 2010 22:41:02 +0000
User-agent: IMAIL/1.21; Edwin/3.116; MIT-Scheme/9.0.1

At <http://mumble.net/~campbell/tmp/mit-scheme-patches/hasheph.patch>
is an implementation of hash tables with entries built out of
ephemerons, to be applied from the top level of a Git checkout with
`patch -p1 < hasheph.patch'.  The general interface to making hash
tables is

((HASH-TABLE/CONSTRUCTOR <key-hash-mod>
                         <key=?>
                         <rehash-after-gc?>
                         <entry-type>)
 #!optional <initial-size>)

The seven entry types are:

HASH-TABLE-ENTRY-TYPE:STRONG
HASH-TABLE-ENTRY-TYPE:KEY-WEAK
HASH-TABLE-ENTRY-TYPE:DATUM-WEAK
HASH-TABLE-ENTRY-TYPE:KEY/DATUM-WEAK
HASH-TABLE-ENTRY-TYPE:KEY-EPHEMERAL
HASH-TABLE-ENTRY-TYPE:DATUM-EPHEMERAL
HASH-TABLE-ENTRY-TYPE:KEY&DATUM-EPHEMERAL

Hash table types are memoized, and open-coded/partially evaluated for
certain sets of parameters.  For example, if you pass EQ-HASH-MOD,
EQ?, #T, and HASH-TABLE-ENTRY-TYPE:STRONG, you get a hash table on
which HASH-TABLE/GET has a tight inner loop, just like you would get
from MAKE-STRONG-EQ-HASH-TABLE before (which is still there).

This implementation passes all tests (of which the patch adds some),
and doesn't seem to crash Scheme, but the tests are not very
extensive, and I haven't yet written any tests that verify the
important properties of weak and ephemeral hash tables.

If you'd like just to browse the source, full copies of the new
hashtb.scm and test-hash-table.scm are in

<http://mumble.net/~campbell/tmp/mit-scheme-patches/hasheph/>.



reply via email to

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