This is the mail archive of the
java@gcc.gnu.org
mailing list for the Java project.
Re: 4.0.0 JNI/reflection invocation 2/4/8 times as slow as in 3.3.3
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