[Openmcl-devel] Address-based hashing considered harmful. Maybe.

[Stonewall Ballard]

On 3/1/03 8:06 AM, "Gary Byers" <gb at clozure.com> wrote:

>...
> That seems to leave arrays and cons cells as objects without handy
> immutable attributes that can be used to derive good hash values.
> If we were to get rid of the concept of address-based hashing
> in OpenMCL and chose not to add "unique ID" fields to cons cells
> and arrays, EQ-based hash lookup on those types of keys would
> degenerate to linear search.

At least in the case of cons cells, how hard would it be to allocate them in
their own zone and never move them? Since they're fixed-size, the only
reason to move them is so that a scavenger can work uniformly on all
objects.

Arrays could have the extra ID field without that much overhead, I expect.

What if you marked hash tables that contain cons cells or arrays, and
rehashed them as you do now only in those cases? "Pay as you go".

 - Stoney


_______________________________________________
Openmcl-devel mailing list
Openmcl-devel at clozure.com
http://clozure.com/cgi-bin/mailman/listinfo/openmcl-devel