4.0.0 JNI/reflection invocation 2/4/8 times as slow as in 3.3.3

Mon Jan 24 12:11:00 GMT 2005

On Sun, 2005年01月23日 at 23:00, Tom Tromey wrote:
> Keeping the number of slots odd is an attempt to make the entries
> spread out better over the array. I don't know whether this is
> successful or not.

Imagine a program which allocates and immediately removes a key. If you
let the hash() distribute the keys all over the table, your table gets
filled with tombstones. And since a tombstone prevents a key to be
entered immediately, our hash table has degenerated into a linear list
which could have a length of up to 75% of it. What would help is to
change the implementation to allow more than one key at a location, for
example by storing the additional keys in a separate list or by building
clusters.
> The change from "* 2" to "<< 1", way back when, was an erroneous
> attempt at optimization. 

It worked, but is was bogus. Multiplying by 8 creates clusters of 8
elements, see hash(). Usually each cluster gets filled with not much
more than 6 elements (75%) until the hashtable grows. Since the last
element of each cluster is never touched, it is used as a "stop marker"
for the linear search. Even if one cluster accidently overflows, the
"stop marker" in the next cluster will prevent searching most of the
hash table.
Jost