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):


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


...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!



Am 26.05.2016 um 14:42 schrieb Michael Haupt <michael.ha...@oracle.com <mailto:michael.ha...@oracle.com>>:

Hi Peter,

thank you for this wonderful piece of work.

Am 26.05.2016 um 10:59 schrieb Peter Levart <peter.lev...@gmail.com <mailto:peter.lev...@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.




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

mlvm-dev mailing list

Reply via email to