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.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.
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
_______________________________________________
mlvm-dev mailing list
mlvm-dev@openjdk.java.net
http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
