<html>
  <head>
    <meta content="text/html; charset=windows-1252"
      http-equiv="Content-Type">
  </head>
  <body style="background-color: rgb(255, 255, 255); color: rgb(0, 0,
    0);" text="#000000" bgcolor="#FFFFFF">
    Hi David,<br>
    <br>
    I played a little with the idea of having a hash table instead of
    packed sorted array for interning. Using ConcurrentHashMap would
    present quite some memory overhead. A more compact representation is
    possible in the form of a linear-scan hash table where elements of
    array are MemberNames themselves:<br>
    <br>
<a class="moz-txt-link-freetext" href="http://cr.openjdk.java.net/~plevart/misc/MemberName.intern/jdk.06.diff/">http://cr.openjdk.java.net/~plevart/misc/MemberName.intern/jdk.06.diff/</a><br>
    <br>
    This is a drop-in replacement for MemberName on top of your jdk.06
    patch. If you have some time, you can run this with your performance
    tests to see if it presents any difference. If not, then perhaps
    this interning is not so performance critical after all.<br>
    <br>
    Regards, Peter<br>
    <br>
    <div class="moz-cite-prefix">On 11/07/2014 10:14 PM, David Chase
      wrote:<br>
    </div>
    <blockquote
      cite="mid:39826508-110B-4FCE-9A58-8C3D1B9FC7DE@oracle.com"
      type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
      <pre wrap="">New webrev:

bug: <a class="moz-txt-link-freetext" href="https://bugs.openjdk.java.net/browse/JDK-8013267">https://bugs.openjdk.java.net/browse/JDK-8013267</a>

webrevs:
<a class="moz-txt-link-freetext" href="http://cr.openjdk.java.net/~drchase/8013267/jdk.06/">http://cr.openjdk.java.net/~drchase/8013267/jdk.06/</a>
<a class="moz-txt-link-freetext" href="http://cr.openjdk.java.net/~drchase/8013267/hotspot.06/">http://cr.openjdk.java.net/~drchase/8013267/hotspot.06/</a>

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 (see <a class="moz-txt-link-freetext" href="https://bugs.openjdk.java.net/browse/JDK-8014288">https://bugs.openjdk.java.net/browse/JDK-8014288</a> )
  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 <a class="moz-txt-link-rfc2396E" href="mailto:david.r.chase@oracle.com"><david.r.chase@oracle.com></a> wrote:

</pre>
      <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
        <pre wrap="">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 <a class="moz-txt-link-rfc2396E" href="mailto:peter.levart@gmail.com"><peter.levart@gmail.com></a> wrote:

</pre>
        <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
          <pre wrap="">On 11/04/2014 04:19 PM, David Chase wrote:
</pre>
          <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
            <pre wrap="">On 2014-11-04, at 5:07 AM, Peter Levart <a class="moz-txt-link-rfc2396E" href="mailto:peter.levart@gmail.com"><peter.levart@gmail.com></a> wrote:
</pre>
            <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
              <pre wrap="">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?
</pre>
              <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
            <pre wrap="">It canít be an identityHashMap, because we are interning member names.
</pre>
            <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
          <pre wrap="">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.

</pre>
          <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
            <pre wrap="">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).
</pre>
            <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
          <pre wrap="">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

</pre>
          <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
            <pre wrap="">David

</pre>
            <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
              <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
                <pre wrap="">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.
</pre>
                <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
              <pre wrap="">Perhaps, yes. But note that questions about JMM and ordering of writes to array elements are about correctness, not performance.

Regards, Peter

</pre>
              <blockquote type="cite"><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]--><!--[if !IE]><DIV style="border-left: 2px solid #009900; border-right: 2px solid #009900;  padding: 0px 15px; margin: 2px 0px;"><![endif]-->
                <pre wrap="">David
</pre>
                <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
              <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
            <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
          <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
        <pre wrap=""></pre>
        <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
      <pre wrap=""></pre>
      <!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--><!--[if !IE]></DIV><![endif]--></blockquote>
    <br>
  </body>
</html>