[Openmcl-devel] Address-based hashing considered harmful. Maybe.
sb.list at sb.org
Sat Mar 1 10:53:20 EST 2003
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
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".
Openmcl-devel mailing list
Openmcl-devel at clozure.com
More information about the Openmcl-devel