[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 |
Greetings!
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