String hashCode

Thu Feb 1 07:40:00 GMT 2001

Tom Tromey wrote:
> The new data structure is an STL map<> (a red-black tree). I chose
> this because it has better worst-case performance than the existing
> hash table and is therefore better for real-time usage. The hash
> table is bad because rehashing makes the worst case expensive.

Some thoughts:
- Your performance scenario may not take cache behavior into consideration. A
binary tree can exhibit terrible spatial locality, causing several cache misses
or even TLB misses in the during lookups, because nodes may not be allocated
consecutively, or even close. That may end up more expensive than rehashing in
the worst case.
- It sounds as though you are targetting some sort of hard real-time with this
decision. Is this feasible at all, given the current state of our GC?
- What do you think about preserving both a hashtable and map implementation in
the source, so that one could be chosen at configure time?
--
Jeff Sturm
jeff.sturm@commerceone.com