[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: 26 Sep 2005 12:51:34 -0400
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2


Robert Boyer <address@hidden> writes:

> > 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.
> I'm not prepared to make any claims or assertions in this vicinity!  I'm just
> feeling my way.  But I will point out that:
>   (a) an sxhash computation, which is necessary to do an equal hash, is an
>       unknown that might be somewhat expensive in comparison to an eq gethash.
>       How deep does it descend?  Who knows?
>   (b) in addition to the sxhash-like computation, at least one full equal
>       comparison (and possibly several) may be necessary to check that an
>       equal hash lookup hit has been found.  If the structures being tested
>       for equal are really, really huge (as they often are in our case, being
>       bdds or biological trees), that full equal test can take a long time!

OK, this all makes sense -- its a question of list size and
complexity, which would appear to argue in favor of an equal strategy
for types, though it might be nice to get a sense on where the
transition point is someday.

Just committed a first stab at type memoization (based on equal
hashing) in the compiler together with a few other type fixes.  I
think you should see some performance gains should you be interested.

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]