[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 1 16:40:02 UTC 2014
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 --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141101/ab49ac1a/attachment.html>
More information about the hotspot-compiler-dev
mailing list