ClassValue perf?

Mon May 30 15:59:54 UTC 2016

Hi Michael,

In the meantime I improved LinearProbeHashtable as I identified a 
weakness in its implementation. In general, if an entry for the same key 
was inserted and removed repeatably, then each such repetition planted a 
"tombstone" at a position of inserted key which means that lookup 
performance for such key deteriorated with each such 
removal/re-insertion until the table was rehashed.

The main trick with LinearProbeHashtable to be able to have lock-free 
lookups is in entries (key/value pairs) that don't move when other 
entries are added or removed from the table. Normally (for example in 
IdentityHashMap that is a similar structure) when an entry is removed 
from linear-probe hash table, entries following it that have their hash 
code point to a point preceeding their position in table, are moved up 
to fill the gap. But such movement is not possible to achieve in 
multithreaded operation without disturbing the lock-free lookup in a way 
that makes it non-functional. So instead of moving the following entries 
up, my implementation plants a "tombstone" key and clears the associated 
value. Such tombstone keys are skipped in lookups, but consider the 
following situation:

hashtable.put(keyX, value1); hastable.remove(keyX);
hashtable.put(keyX, value2); hastable.remove(keyX);
hashtable.put(keyX, value3); hastable.remove(keyX);
hashtable.put(keyX, value4);

// after above modifications and in case they didn't trigger rehashing,
// hashtable.get(keyX) encounters the following state:

i = firstIndex(keyX, table.length);
table[i+0] == Tombstone
table[i+1] == null
table[i+2] == Tombstone
table[i+3] == null
table[i+4] == Tombstone
table[i+5] == null
table[i+6] == keyX
table[i+7] == value4

...so the lookup for keyX must probe 3 tombstones before reaching to the 
matched key. ClassValue usage does not encounter such situations as 
ClassValue.remove actually maps to LinearProbeHashtable.replace(key, 
oldValue, new Removed()) because ClassValue must also track "versions" 
of removals. Where ClassValue calls LinearProbeHashtable.remove is when 
expunging stale keys and each such removed key is never inserted again.

But if LinearProbeHashtable is to be used elsewhere too, we must not 
allow periodic removal/reinsertion of the same key to affect performance 
of lookups.

The solution I discovered was for tombstones to maintain the number of 
consecutive tombstones following the one, so probing can skip an entire 
run of consecutive tombstones in one go. Te above example of repeated 
modifications results in the following state:

i = firstIndex(keyX, table.length);
table[i+0] == Tombstone(skip=3)
table[i+1] == null
table[i+2] == Tombstone(skip=2)
table[i+3] == null
table[i+4] == Tombstone(skip=1)
table[i+5] == null
table[i+6] == keyX
table[i+7] == value4

When lookup encounters a tombstone it can read from it the number of key 
slots to skip. Simple.

Another improvement is in the policy of rehashing. Rehashing is 
triggered just before a new entry is inserted into the table that would 
violate the maximum load factor of 2/3. Tombstones also count as 
occupying the slots, of course, but are removed in rehashing. Rehashing 
can therefore also shrink the table depending on how many tombstones it 
contains. But shrinking it to the minimum length that still satisfies 
the maximum load factor of 2/3 is not the best policy as it can result 
in frequent oscillations around the tipping point that result in 
repeated rehashing. So current strategy reallocates a table in a way 
that guarantees, in worst case, that at least size()/2 entries can get 
inserted into the table before it needs another rehashing, but at the 
same time does not force table to grow any faster when entries are 
inserted only.

I also employed get-acquire/put-release memory ordering semantics 
instead of SC (volatile) in hope that it might improve a bit the 
performance on platforms such as PowerPC or ARM, but this can be changed 
back to SC if anyone gets scared of it :-)

Here's the improved code (only LinearProbeHashtable changed compared to 
webrev.04):

http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.04.1/

Here are the benchmark results comparing original JDK9 ClassValue with 
this patch:

http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.04.1.bench_results.txt

...which show that it still has a slight (performance of lookup) to big 
(footprint and expunging) advantage over present ClassValue in this 
incarnation too.

Michael, could you re-submit this version into internal testing too? I 
think this modification is essential.

Regards, Peter

On 05/30/2016 10:00 AM, Michael Haupt wrote:
> Hi Peter,
>
> the internal tests look good. I'll assign the issue over to you. Thanks!
>
> Best,
>
> Michael
>
>> Am 26.05.2016 um 14:42 schrieb Michael Haupt 
>> <michael.haupt at oracle.com <mailto:michael.haupt at oracle.com>>:
>>
>> Hi Peter,
>>
>> thank you for this wonderful piece of work.
>>
>>> Am 26.05.2016 um 10:59 schrieb Peter Levart <peter.levart at gmail.com 
>>> <mailto:peter.levart at gmail.com>>:
>>> How does this implementation compare on your hardware, Michael?
>>
>> Results attached. It improves on the unpatched version in all cases, 
>> is in most cases even faster than the "simple solution" (reduce 
>> initial size to 1), and reduces complexity of ClassValue. It passes 
>> all open and closed jli-related tests as well as the Nashorn tests. 
>> Looking really good.
>>
>> Let me run the full internal test suite across platforms.
>>
>> Best,
>>
>> Michael
>
>
> -- 
>
> Oracle <http://www.oracle.com/>
> Dr. Michael Haupt | Principal Member of Technical Staff
> Phone: +49 331 200 7277 | Fax: +49 331 200 7561
> OracleJava Platform Group | LangTools Team | Nashorn
> Oracle Deutschland B.V. & Co. KG | Schiffbauergasse 14 | 14467 
> Potsdam, Germany
>
> ORACLE Deutschland B.V. & Co. KG | Hauptverwaltung: Riesstraße 25, 
> D-80992 München
> Registergericht: Amtsgericht München, HRA 95603
>
> Komplementärin: ORACLE Deutschland Verwaltung B.V. | Hertogswetering 
> 163/167, 3543 AS Utrecht, Niederlande
> Handelsregister der Handelskammer Midden-Nederland, Nr. 30143697
> Geschäftsführer: Alexander van der Ven, Jan Schultheiss, Val Maher
> Green Oracle <http://www.oracle.com/commitment> 	Oracle is committed 
> to developing practices and products that help protect the environment
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20160530/5a29df42/attachment.html>