Re: String interning

[Bryce McKinlay <bryce at albatross dot co dot nz>]

Tom Tromey wrote:

> What if we make each slot in the hash table a linked list of interned
> strings instead?  Then when we delete a string it will always be safe
> to simply reuse a deleted slot.  This is bad in its own way, which is
> that the lists could get very long.

Yeah, that and its difficult to implement a linked list here. We can't
justify adding an extra 32 bits to every String just for the sake of a
'next' pointer for interning. We could use pointers to arrays or a
special struct as entries in the hash table, but both of those solutions
add more overhead and complexity.

I'm thinking of going with the solution where rehash() allways rehashes
the table, flushing out the DELETED_STRINGs, even if an increase in the
table size turns out to be not required because alot of the
strhash_count consists of deleted strings. This seems to work reasonably
well, and its only slower when there are a lot of collectable strings in
the table. Even then, it still runs the InternHog test about 4X or more
faster than the linux JDK 1.2.2 implementation, and scales well.

regards

  [ bryce ]