[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;
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