[9] RFR(L) 8013267 : move MemberNameTable from native code to Java heap, use to intern MemberNames
David Chase
david.r.chase at oracle.com
Sat Nov 1 17:03:28 UTC 2014
Hello Peter,
I think it is expected that inserting-interns will be asymptotically rare — classes
have a finite number of methods, after all. I’m not sure if that is worth doing right
now, since this is also a bug fix — maybe the performance enhancements go
in as an RFE.
Maybe other reviewers will have an opinion?
David
On 2014-11-01, at 12:40 PM, Peter Levart <peter.levart at gmail.com> wrote:
>
> On 10/31/2014 11:59 PM, David Chase wrote:
>> Thanks very much, I shall attend to these irregularities.
>>
>> David
>>
>
> Hi David,
>
> Just a nit (in Class.ClassData):
>
> 2537 if (oldCapacity > 0) {
> 2538 element_data[oldCapacity] = element_data[oldCapacity - 1];
> 2539 // all array elements are non-null and sorted, increase size.
> 2540 // if store to element_data above floats below
> 2541 // store to size on the next line, that will be
> 2542 // inconsistent to the VM if a safepoint occurs here.
> 2543 size += 1;
> 2544 for (int i = oldCapacity; i > index; i--) {
> 2545 // pre: element_data[i] is duplicated at [i+1]
> 2546 element_data[i] = element_data[i - 1];
> 2547 // post: element_data[i-1] is duplicated at [i]
> 2548 }
> 2549 // element_data[index] is duplicated at [index+1]
> 2550 element_data[index] = (Comparable<?>) e;
> 2551 } else {
>
> In line 2544, you could start the for loop with (int i = oldCapacity - 1; ...), since you have already moved the last element before incrementing the size. Also, I would more quickly grasp the code if "oldCapacity" was called "oldSize".
>
> Now just a though...
>
> What is the expected ratio of intern() calls that insert new element to those that just return existing interned element? If those that return existing element are frequent and since you already carefully arrange insertion so that VM can at any safepoint see the "consistent" state without null elements, I wonder if intern() could itself perform an optimistic search without holding an exclusive lock.
>
> This is just a speculation, but would the following code work?
>
> private Comparable<?>[] elementData() {
> Comparable<?>[] elementData = this.elementData;
> if (elementData == null) {
> synchronized (this) {
> elementData = this.elementData;
> if (elementData == null) {
> this.elementData = elementData = new Comparable[1];
> }
> }
> }
> return elementData;
> }
>
> private final StampedLock lock = new StampedLock();
>
> public <E extends Comparable<? super E>> E intern(Class<?> klass, E memberName, int redefined_count) {
> int size, index = 0;
> Comparable<?>[] elementData;
> // try to take an optimistic-read stamp
> long rstamp = lock.tryOptimisticRead();
> long wstamp = 0L;
>
> if (rstamp != 0L) { // successfull
> // 1st read size so that it doesn't overshoot the actual elementData.length
> size = this.size;
> // 2nd read elementData
> elementData = elementData();
>
> index = Arrays.binarySearch(elementData, 0, size, memberName);
> if (index >= 0) {
> E element = (E) elementData[index];
> // validate that our reads were not disturbed by any writes
> if (lock.validate(rstamp)) {
> return element;
> }
> }
>
> // try to convert to write lock
> wstamp = lock.tryConvertToWriteLock(rstamp);
> }
>
> if (wstamp == 0L) {
> // either tryOptimisticRead or tryConvertToWriteLock failed -
> // must acquire write lock and re-read/re-try search
> wstamp = lock.writeLock();
> size = this.size;
> elementData = elementData();
> index = Arrays.binarySearch(elementData, 0, size, memberName);
> if (index >= 0) {
> E element = (E) elementData[index];
> lock.unlockWrite(wstamp);
> return element;
> }
> }
>
> // we have a write lock and are sure there was no element found
> E element = add(klass, ~index, memberName, redefined_count);
>
> lock.unlockWrite(wstamp);
> return element;
> }
>
>
>
> The only thing that will have to be done to add() method is to publish new elements safely. Code doing binary-search under optimistic read could observe an unsafely published MemberName and comparing with such instance could lead to a NPE for example. To remedy this, the newly inserted MemberName would have to be published using a volatile write to the array slot (using Unsafe) - moving existing elements up and down the array does not have to be performed with volatile writes, since they have already been published.
>
> Do you think this would be worth the effort?
>
> Regards, Peter
>
>
>> On 2014-10-31, at 6:01 PM, Peter Levart <peter.levart at gmail.com>
>> wrote:
>>
>>
>>> On 10/31/2014 07:11 PM, David Chase wrote:
>>>
>>>> I found a lurking bug and updated the webrevs — I was mistaken
>>>> about this version having passed the ute tests (but now, for real, it does).
>>>>
>>>> I also added converted Christian’s test code into a jtreg test (which passes):
>>>>
>>>>
>>>>
>>>> http://cr.openjdk.java.net/~drchase/8013267/hotspot.05/
>>>> http://cr.openjdk.java.net/~drchase/8013267/jdk.05/
>>> Hi David,
>>>
>>> I'll just comment on the JDK side of things.
>>>
>>> In Class.ClassData.intern(), ther is a part that synchronizes on the elementData (volatile field holding array of Comparable(s)):
>>>
>>> 2500 synchronized (elementData) {
>>> 2501 final int index = Arrays.binarySearch(elementData, 0, size, memberName);
>>> 2502 if (index >= 0) {
>>> 2503 return (E) elementData[index];
>>> 2504 }
>>> 2505 // Not found, add carefully.
>>> 2506 return add(klass, ~index, memberName, redefined_count);
>>> 2507 }
>>>
>>> Inside this synchronized block, add() method is called, which can call grow() method:
>>>
>>> 2522 if (oldCapacity + 1 > element_data.length ) {
>>> 2523 // Replacing array with a copy is safe; elements are identical.
>>> 2524 grow(oldCapacity + 1);
>>> 2525 element_data = elementData;
>>> 2526 }
>>>
>>> grow() method creates a copy of elementData array and replaces it on this volatile field (line 2584):
>>>
>>> 2577 private void grow(int minCapacity) {
>>> 2578 // overflow-conscious code
>>> 2579 int oldCapacity = elementData.length;
>>> 2580 int newCapacity = oldCapacity + (oldCapacity >> 1);
>>> 2581 if (newCapacity - minCapacity < 0)
>>> 2582 newCapacity = minCapacity;
>>> 2583 // minCapacity is usually close to size, so this is a win:
>>> 2584 elementData = Arrays.copyOf(elementData, newCapacity);
>>> 2585 }
>>>
>>> A concurrent call to intern() can therefore synchronize on a different monitor, so two threads will be inserting the element into the same array at the same time, Auch!
>>>
>>>
>>>
>>> Also, lazy construction of ClassData instance:
>>>
>>> 2593 private ClassData<T> classData() {
>>> 2594 if (this.classData != null) {
>>> 2595 return this.classData;
>>> 2596 }
>>> 2597 synchronized (this) {
>>> 2598 if (this.classData == null) {
>>> 2599 this.classData = new ClassData<>();
>>> 2600 }
>>> 2601 }
>>> 2602 return this.classData;
>>> 2603 }
>>>
>>> Synchronizes on the j.l.Class instance, which can interfere with user synchronization (think synchronized static methods). This dangerous.
>>>
>>> Theres an inner class Class.Atomic which is a home for Unsafe machinery in j.l.Class. You can add a casClassData method to it and use it to atomically install the ClassData instance without synchronized blocks.
>>>
>>>
>>>
>>> Regards, Peter
>>>
>>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141101/72a51e6f/signature.asc>
More information about the hotspot-compiler-dev
mailing list