[Gcl-devel] Re: hashing and memoizing

[Camm Maguire]

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