[9] RFR(L) 8013267 : move MemberNameTable from native code to Java heap, use to intern MemberNames
Peter Levart
peter.levart at gmail.com
Sat Nov 8 15:07:38 UTC 2014
Hi David,
As previously, I feel competent to comment only the Java side of the patch.
Using linked list to publish to VM is a safer and easier way for the
desired purpose and using a separate data structure for interning makes
it easier to change it in the future should need arise. That need may
just be around the corner as there are people (Martin Buchholz, Duncan
MacGregor, for example) that use classes with huge number of methods...
Here are few comments for the new webrev (MemberName):
78 @SuppressWarnings("rawtypes") //Comparable in next line
79 /*non-public*/ final class MemberName implements Member, Comparable, Cloneable {
Since MemberName is final and can only be compared to itself, you could
make it implement Comparable<MemberName> and eliminate the @SuppressWarnings
more MemberName:
84 private volatile MemberName next; // used for a linked list of MemberNames known to VM
...
1375 private static class ClassData {
1376 /**
1377 * This needs to be a simple data structure because we need to access
1378 * and update its elements from the JVM. Note that the Java side controls
1379 * the allocation and order of elements in the array; the JVM modifies
1380 * fields of those elements during class redefinition.
1381 */
1382 private volatile MemberName[] elementData;
1383 private volatile MemberName publishedToVM;
1384 private volatile int size;
1385
1386 /**
1387 * Interns a member name in the member name table.
1388 * Returns null if a race with the jvm occurred. Races are detected
1389 * by checking for changes in the class redefinition count that occur
1390 * before an intern is complete.
1391 *
1392 * @param klass class whose redefinition count is checked.
1393 * @param memberName member name to be interned
1394 * @param redefined_count the value of classRedefinedCount() observed before
1395 * creation of the MemberName that is being interned.
1396 * @return null if a race occurred, otherwise the interned MemberName.
1397 */
1398 @SuppressWarnings({"unchecked","rawtypes"})
1399 public MemberName intern(Class<?> klass, MemberName memberName, int redefined_count) {
1400 if (elementData == null) {
1401 synchronized (this) {
1402 if (elementData == null) {
1403 elementData = new MemberName[1];
1404 }
1405 }
1406 }
1407 synchronized (this) { // this == ClassData
1408 final int index = Arrays.binarySearch(elementData, 0, size, memberName);
1409 if (index >= 0) {
1410 return elementData[index];
1411 }
1412 // Not found, add carefully.
1413 return add(klass, ~index, memberName, redefined_count);
1414 }
1415 }
...
1426 private MemberName add(Class<?> klass, int index, MemberName e, int redefined_count) {
1427 // First attempt publication to JVM, if that succeeds,
1428 // then record internally.
1429 e.next = publishedToVM;
1430 publishedToVM = e;
1431 storeFence();
1432 if (redefined_count != jla.getClassRedefinedCount(klass)) {
1433 // Lost a race, back out publication and report failure.
1434 publishedToVM = e.next;
1435 return null;
1436 }
Since you now synchronize lookup/add *and* lazy elementData construction
on the same object (the ClassData instance), you can merge two
synchronized blocks and simplify code. You can make MemberName.next,
ClassData.elementData and ClassData.size be non-volatile (just
ClassData.publishedToVM needs to be volatile) and ClassData.intern() can
look something like that:
public synchronized MemberName intern(Class<?> klass, MemberName
memberName, int redefined_count) {
final int index;
if (elementData == null) {
elementData = new MemberName[1];
index = ~0;
} else {
index = Arrays.binarySearch(elementData, 0, size, memberName);
if (index >= 0) return elementData[index];
}
// Not found, add carefully.
return add(klass, ~index, memberName, redefined_count);
}
// Note: no need for additional storeFence() in add()...
private MemberName add(Class<?> klass, int index, MemberName e, int
redefined_count) {
// First attempt publication to JVM, if that succeeds,
// then record internally.
e.next = publishedToVM; // volatile read of publishedToVM,
followed by normal write of e.next...
publishedToVM = e; // ...which is ordered before
volatile write of publishedToVM...
if (redefined_count != jla.getClassRedefinedCount(klass)) { //
...which is ordered before volatile read of klass.classRedefinedCount.
// Lost a race, back out publication and report failure.
publishedToVM = e.next;
return null;
}
...
Now let's take for example one of the MemberName.make() methods that
return interned MemberNames:
206 public static MemberName make(Method m, boolean wantSpecial) {
207 // Unreflected member names are resolved so intern them here.
208 MemberName tmp0 = null;
209 InternTransaction tx = new InternTransaction(m.getDeclaringClass());
210 while (tmp0 == null) {
211 MemberName tmp = new MemberName(m, wantSpecial);
212 tmp0 = tx.tryIntern(tmp);
213 }
214 return tmp0;
215 }
I'm trying to understand the workings of InternTransaction helper class
(and find an example that breaks it). You create an instance of it,
passing Method's declaringClass. You then (in retry loop) create a
resolved MemberName from the Method and wantSpecial flag. This
MemberName's clazz can apparently differ from Method's declaringClass. I
don't know when and why this happens, but apparently it can (super
method?), so in InternTransaction.tryIntern() you do...
363 if (member_name.isResolved()) {
364 if (member_name.clazz != tx_class) {
365 Class prev_tx_class = tx_class;
366 int prev_txn_token = txn_token;
367 tx_class = member_name.clazz;
368 txn_token = internTxnToken(tx_class);
369 // Zero is a special case.
370 if (txn_token != 0 ||
371 prev_txn_token != internTxnToken(prev_tx_class)) {
372 // Resolved class is different and at least one
373 // redef of it occurred, therefore repeat with
374 // proper class for race consistency checking.
375 return null;
376 }
377 }
378 member_name = member_name.intern(txn_token);
379 if (member_name == null) {
380 // Update the token for the next try.
381 txn_token = internTxnToken(tx_class);
382 }
383 }
Now let's assume that the resolved member_name.clazz differs from
Method's declaringClass. Let's assume also that either member_name.clazz
has had at least one redefinition or Method's declaringClass has been
redefined between creating InternTransaction and reading
member_name.clazz's txn_token. You return 'null' in such case,
concluding that not only the resolved member_name.clazz redefinition
matters, but Method's declaringClass redefinition can also invalidate
resolved MemberName am I right? It would be helpful if I could
understand when and how Method's declaringClass redefinition can affect
member_name. Can it affect which clazz is resolved for member_name?
Anyway, you return null in such case from an updated InternTransaction
(tx_class and txn_token are now updated to have values for resolved
member_name.clazz). In next round the checks of newly constructed and
resolved member_name are not performed against Method's declaringClass
but against previous round's member_name.clazz. Is this what is
intended? I can see there has to be a stop condition for loop to end,
but shouldn't checks for Method's declaringClass redefinition be
performed in every iteration (in addition to the check for
member_name.clazz redefinition if it differs from Method's declaringClass)?
Regards, Peter
On 11/07/2014 10:14 PM, David Chase wrote:
> New webrev:
>
> bug:https://bugs.openjdk.java.net/browse/JDK-8013267
>
> webrevs:
> http://cr.openjdk.java.net/~drchase/8013267/jdk.06/
> http://cr.openjdk.java.net/~drchase/8013267/hotspot.06/
>
> Changes since last:
>
> 1) refactored to put ClassData under java.lang.invoke.MemberName
>
> 2) split the data structure into two parts; handshake with JVM uses a linked list,
> which makes for a simpler backout-if-race, and Java side continues to use the
> simple sorted array. This should allow easier use of (for example) fancier
> data structures (like ConcurrentHashMap) if this later proves necessary.
>
> 3) Cleaned up symbol references in the new hotspot code to go through vmSymbols.
>
> 4) renamed oldCapacity to oldSize
>
> 5) ran two different benchmarks and saw no change in performance.
> a) nashorn ScriptTest (seehttps://bugs.openjdk.java.net/browse/JDK-8014288 )
> b) JMH microbenchmarks
> (see bug comments for details)
>
> And it continues to pass the previously-failing tests, as well as the new test
> which has been added to hotspot/test/compiler/jsr292 .
>
> David
>
> On 2014-11-04, at 3:54 PM, David Chase<david.r.chase at oracle.com> wrote:
>
>> I’m working on the initial benchmarking, and so far this arrangement (with synchronization
>> and binary search for lookup, lots of barriers and linear cost insertion) has not yet been any
>> slower.
>>
>> I am nonetheless tempted by the 2-tables solution, because I think the simpler JVM-side
>> interface that it allows is desirable.
>>
>> David
>>
>> On 2014-11-04, at 11:48 AM, Peter Levart<peter.levart at gmail.com> wrote:
>>
>>> On 11/04/2014 04:19 PM, David Chase wrote:
>>>> On 2014-11-04, at 5:07 AM, Peter Levart<peter.levart at gmail.com> wrote:
>>>>> Are you thinking of an IdentityHashMap type of hash table (no linked-list of elements for same bucket, just search for 1st free slot on insert)? The problem would be how to pre-size the array. Count declared members?
>>>> It can’t be an identityHashMap, because we are interning member names.
>>> I know it can't be IdentityHashMap - I just wondered if you were thinking of an IdentityHashMap-like data structure in contrast to standard HashMap-like. Not in terms of equality/hashCode used, but in terms of internal data structure. IdentityHashMap is just an array of elements (well pairs of them - key, value are placed in two consecutive array slots). Lookup searches for element linearly in the array starting from hashCode based index to the element if found or 1st empty array slot. It's very easy to implement if the only operations are get() and put() and could be used for interning and as a shared structure for VM to scan, but array has to be sized to at least 3/2 the number of elements for performance to not degrade.
>>>
>>>> In spite of my grumbling about benchmarking, I’m inclined to do that and try a couple of experiments.
>>>> One possibility would be to use two data structures, one for interning, the other for communication with the VM.
>>>> Because there’s no lookup in the VM data stucture it can just be an array that gets elements appended,
>>>> and the synchronization dance is much simpler.
>>>>
>>>> For interning, maybe I use a ConcurrentHashMap, and I try the following idiom:
>>>>
>>>> mn = resolve(args)
>>>> // deal with any errors
>>>> mn’ = chm.get(mn)
>>>> if (mn’ != null) return mn’ // hoped-for-common-case
>>>>
>>>> synchronized (something) {
>>>> mn’ = chm.get(mn)
>>>> if (mn’ != null) return mn’
>>>> txn_class = mn.getDeclaringClass()
>>>>
>>>> while (true) {
>>>> redef_count = txn_class.redefCount()
>>>> mn = resolve(args)
>>>>
>>>> shared_array.add(mn);
>>>> // barrier, because we are a paranoid
>>>> if (redef_count = redef_count.redefCount()) {
>>>> chm.add(mn); // safe to publish to other Java threads.
>>>> return mn;
>>>> }
>>>> shared_array.drop_last(); // Try again
>>>> }
>>>> }
>>>>
>>>> (Idiom gets slightly revised for the one or two other intern use cases, but this is the basic idea).
>>> Yes, that's similar to what I suggested by using a linked-list of MemberName(s) instead of the "shared_array" (easier to reason about ordering of writes) and a sorted array of MemberName(s) instead of the "chm" in your scheme above. ConcurrentHashMap would certainly be the most performant solution in terms of lookup/insertion-time and concurrent throughput, but it will use more heap than a simple packed array of MemberNames. CHM is much better now in JDK8 though regarding heap use.
>>>
>>> A combination of the two approaches is also possible:
>>>
>>> - instead of maintaining a "shared_array" of MemberName(s), have them form a linked-list (you trade a slot in array for 'next' pointer in MemberName)
>>> - use ConcurrentHashMap for interning.
>>>
>>> Regards, Peter
>>>
>>>> David
>>>>
>>>>>> And another way to view this is that we’re now quibbling about performance, when we still
>>>>>> have an existing correctness problem that this patch solves, so maybe we should just get this
>>>>>> done and then file an RFE.
>>>>> Perhaps, yes. But note that questions about JMM and ordering of writes to array elements are about correctness, not performance.
>>>>>
>>>>> Regards, Peter
>>>>>
>>>>>> David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141108/aa25deee/attachment-0001.html>
More information about the hotspot-compiler-dev
mailing list