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

[Tom Tromey <tromey at redhat dot com>]

>>>>> "Jost" == Jost Boekemeier <jost2345@yahoo.de> writes:

>> The new implementation is really just the original
>> reimplementation resurrected.

Jost> Umm, no.  The original implementation is this: double
Jost> the size of the table and add 4 empty slots per
Jost> bucket.

Sorry, I really meant the *original* implementation.  Take a look at
the diff between revisions 1.8 and 1.9.

Jost> The new implementation just adds an empty slot at the
Jost> end, essentially creating a linear list with the empty
Jost> slot as the stop marker.

The way I understand IdentityHashMap to work is that it keeps both the
keys and values in a single array.  For any even 'i', table[i] is the
key and table[i+1] is the value.  So, the number of usable slots in
the array is "table.length / 2".

So this line in put():

        table = new Object[(old.length * 2) + 2];

is changing a table with N slots into one with 2N + 1 slots.  Once we
have made a new array, we proceed to put all the old values into the
new array (implicitly removing tombstones).

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.

Jost> The comment is correct
Jost> (the last entry is used to separate the buckets), but
Jost> maybe it should mention how the entries are layed out.

The last entry does not separate buckets.  It can be used just like
any other entry.  It just depends on the particular hash value.

Jost> Probably the original author wrote 1 + 2 to emphasize
Jost> that the size of the hash gets doubled and we add 4
Jost> slots per bucket. 

I know that this is not the case, as I was the original author.  But
it is possible the above would be better... I just don't understand
why.  That is what I would like to figure out.

The change from "* 2" to "<< 1", way back when, was an erroneous
attempt at optimization.  We chose to revert it completely instead of
adding parens, since the "* 2" is somewhat clearer and the speed
improvement, if it exists, is probably not very important anyway.

Tom