[Top][All Lists]

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

[Gcl-devel] Re: hashing and memoizing

From: Camm Maguire
Subject: [Gcl-devel] Re: hashing and memoizing
Date: 24 Sep 2005 21:07:44 -0400
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2


Robert Boyer <address@hidden> writes:

> Here may be the numb of the problem as I see it with any proposed use of
> hashing and memoizing or any general facility for supporting same.  When to
> flush?  These hash/memo techniques tend to gradually fill up memory and
> someone has to decide when to "forget" or death from memory exhaustion will
> ensue.  But it's not very clear in general when to flush.  compile-file might
> provide a good beginning/end pair for the forgetting process.

My thoughts exactly as well.  I have here locally now an equal hashing
memoization to normalize-type and type-and for the compiler which is
apparently reducing compile time on sone files by a bit more that
50%, even flushing on each compile-file, so this looks promising.

My real question here was equal hashing vs. eq "hash-consing" you guys
use, which I understand to be effectively a three eq gethash lookup.
I.e. for a pair of unique objects, lookup a hash table pertaining to
the first one alone in a specific global hash table, then lookup the
second one in the new table which returns a unique cons of the pair,
then lookup this pair in a type-and hash table.

This appears to save only one cons per lookup over the equal hash
strategy, so the main benefit must be speed, which is remarkable,
i.e. that three eq lookups are faster than one equal lookup.  Are
these assumptions of mine misguided?

Take care,

> Bob

Camm Maguire                                            address@hidden
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah

reply via email to

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