Hi,
The patch for this issue is a result of the following discussion on
mlvm-dev list:
http://mail.openjdk.java.net/pipermail/mlvm-dev/2016-May/006602.html
I propose the following improvement to the implementation of ClassValue
API:
http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.04.3/
This is a re-implementation of ClassValue API that leverages a
ConcurrentMap for storage. ConcurrentHashMap was initially tested, but
using it regressed lookup performance for about ~10%. So a simple
ConcurrentMap implementation (LinearProbeHashtable) was created which
has smaller footprint, better CPU cache locality and consequently faster
lookup performance for the task at hand. The goal of this task was to
shrink the memory footprint of ClassValue API. To see the end effect
let's first look at the results of a benchmark that simulates a
re-deployment of an application in an app server where several apps are
deployed and each uses it's own set of classes and ClassValue(s):
http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/ClassValueExpungeBench.java
Benchmark (classValuesPerPart)
(classesPerPart) (impl) (partitions) Mode Cnt Score Error Units
ClassValueExpungeBench.redeployPartition 8 1024
jdk9 16 ss 16 65.682 ± 1.485 ms/op
ClassValueExpungeBench.redeployPartition 8 4096
jdk9 16 ss 16 247.040 ± 7.684 ms/op
ClassValueExpungeBench.redeployPartition 64 1024
jdk9 16 ss 16 302.536 ± 27.750 ms/op
ClassValueExpungeBench.redeployPartition 64 4096
jdk9 16 ss 16 1174.002 ± 77.183 ms/op
Benchmark (classValuesPerPart) (classesPerPart) (impl) (partitions)
Mode Cnt Score Error Units
ClassValueExpungeBench.redeployPartition 8 1024
pl04.3 16 ss 16 47.179 ± 1.436 ms/op
ClassValueExpungeBench.redeployPartition 8 4096
pl04.3 16 ss 16 163.067 ± 8.118 ms/op
ClassValueExpungeBench.redeployPartition 64 1024
pl04.3 16 ss 16 67.581 ± 1.718 ms/op
ClassValueExpungeBench.redeployPartition 64 4096
pl04.3 16 ss 16 240.458 ± 6.616 ms/op
A by-product of this simulation is a heap dump histogram taken after the
last warmup iteration when all "applications" are deployed:
top-10 classes heap dump for 64 ClassValue(s) x 4096 Class(es) x 16
partitions
jdk9:
num #instances #bytes class name (module)
-------------------------------------------------------
1: 4194309 167772360 java.util.WeakHashMap$Entry
(java.base@9-internal)
2: 4195329 134250528 java.lang.ClassValue$Entry
(java.base@9-internal)
3: 65539 34603248 [Ljava.util.WeakHashMap$Entry;
(java.base@9-internal)
4: 65537 34603032 [Ljava.lang.ClassValue$Entry;
(java.base@9-internal)
5: 67301 7552448 java.lang.Class
(java.base@9-internal)
6: 65536 4194304 java.lang.ClassValue$ClassValueMap
(java.base@9-internal)
7: 65552 2097664 java.lang.ref.ReferenceQueue
(java.base@9-internal)
8: 67736 1676344 [Ljava.lang.Object;
(java.base@9-internal)
9: 66349 1116848 [I (java.base@9-internal)
10: 65554 1048864 java.lang.ref.ReferenceQueue$Lock
(java.base@9-internal)
-------------------------------------------------------
388915640 == 370 MiB
pl04.3:
num #instances #bytes class name (module)
-------------------------------------------------------
1: 133274 69833848 [Ljava.lang.Object;
(java.base@9-internal)
2: 67300 7552376 java.lang.Class
(java.base@9-internal)
3: 65536 2097152 java.lang.ClassValue$ClassValueMap
(java.base@9-internal)
4: 65536 2097152
java.lang.ClassValue$ClassValueMap$WeakNode (java.base@9-internal)
5: 66349 1116848 [I (java.base@9-internal)
6: 65991 1055856 java.lang.Object
(java.base@9-internal)
7: 7434 696584 [B (java.base@9-internal)
8: 1551 299680 [Ljava.lang.Class;
(java.base@9-internal)
9: 2447 176184 java.lang.reflect.Field
(java.base@9-internal)
10: 7154 171696 java.lang.String
(java.base@9-internal)
-------------------------------------------------------
85097376 == 81 MiB
Footprint is reduced for more than 4 times. The main improvement of this
implementation is that to support M Class(es) x N ClassValue(s), the
only part of the data structure that has O(M*N) space footprint are the
backing array(s) of LinearProbeHashtable. No less than 3 and no more
than 6 Object slots are used per Class x ClassValue association (4 in
average). Other supporting parts of the data structure are either O(M),
O(N) or O(1).
The lookup time has improved too with this patch (slightly):
http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/ClassValueBench.java
http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.04.3.bench_results.pdf
As to the LinearProbeHashtable, it has been updated from initial version
to implement the whole ConcurrentMap interface. Not much was needed for
that (~150 lines of heavy commented code) comparing to the
implementation in webrev.04.2
(http://cr.openjdk.java.net/~plevart/misc/ClassValue.Alternative2/webrev.04.2/).
The end effect was that I was able to test the correctness of the
implementation using MOAT tests. Other changes to LinearProbeHashtable
from webrev.04.2 (for those following the discussion on mlvm-dev) are:
- the lookup logic that was repeated in each and every method was
factored-out into a lookup() private method.
- further benchmarking revealed that is was not beneficial to have
a 'skip' field in tombstone objects. Reading this field to optimize
skipping over a consecutive run of tombstones reduces cache-locality of
algorithm. On average it is faster to just skip one tombstone at a time
and use a singleton tombstone object to be able to compare just the
reference.
- The following spin loop was added to get() method (and similar to
some other methods) to preserve SC properties of the methods:
public V get(Object key) {
Object[] tab = table;
int i = lookup(tab, key);
if (i >= 0) {
Object value = getVolatile(tab, i + 1);
if (value != null) {
return (V) value;
}
// possible race with removing an entry can cause oldValue
// to be observed cleared. If this happens, we know the key
// has/will be tombstoned just after that but we must wait
// for that to happen in order to preserve SC properties of
// this method; without this wait one could even observe
the
// following in one thread:
//
// table.get(k) == null && table.containsKey(k);
//
while (getVolatile(tab, i) != TOMBSTONE) {
Thread.onSpinWait();
}
}
return null;
}
...the write this spin-loop is waiting on is in the remove() method(s):
tab[i + 1] = null; // clear the value...
tombstoned++;
putVolatile(tab, i, TOMBSTONE); // ...publish
tombstone
The lookup performance of LinearProbeHashtable was put to test comparing
it with ConcurrentHashMap in the following benchmark:
http://cr.openjdk.java.net/~plevart/misc/LinearProbeHashTable/lpht_src.tgz
Results:
http://cr.openjdk.java.net/~plevart/misc/LinearProbeHashTable/lpht_bench.pdf
In this benchmark, several variations are tested. The one from
webrev.04.2 with stateful tombstones is called LinearProbeHashTable and
the one with singleton stateless tombstone, presented in this RFR as
webrev.04.3 is called LinearProbeHashTable1. The benchmark shows that
even during concurrent removals and insertions, the successful lookup
performance (GetExistent) does not degrade much and is on-par with
ConcurrentHashMap. This benchmark also explores the suitability of using
LinearProbeHashTable for keys derived from MethodType.
A note to reviewers: It is useless to compare the old implementation
with the new one side by side as they have not much in common (just
public API and javadocs). Although the net line count increases with
this patch, the complexity of ClassValue implmenetation is reduced,
because it is a layered implementation. ClassValue API is implemented in
terms of a well-known ConcurrentMap API and correctness of ConcurrentMap
implementation is verified by MOAT tests.
Regards, Peter
