On Mar 26, 2014, at 5:21 AM, David Holmes <david.holmes@oracle.com> wrote:

Mike,

On 26/03/2014 6:37 AM, Mike Duigou wrote:

...

Hello all;

Recently HotSpot gained additional support for transactional memory, <https://bugs.openjdk.java.net/browse/JDK-8031320>. This patch is a libraries followon to that change. RTM and other transactional memory implementations benefit from clustering writes towards the end of the transaction whenever possible. This change optimizes the behaviour of two collection classes, Hashtable and Vector by moving several field updates to cluster them together near the end of the transaction. Yes, we know, these are obsolete collections but these two classes were used as the basis for the original benchmarking and evaluation during the development of the transactional memory JVM features. Future changes providing similar optimizations to other collections will be pursued when it can be shown they offer value and don't add a cost to non TM performance (TM is not yet a mainstream feature).

https://bugs.openjdk.java.net/browse/JDK-8020860 http://cr.openjdk.java.net/~mduigou/JDK-8020860/0/webrev/

It is not expected that this change will have any meaningful impact upon performance (either positive or negative) outside of TM-enabled configurations. The main change is to move existing field updates towards the end of the transaction and avoid conditionals between field updates.

There is a slight behaviour change introduced in this changeset. Previously some methods updated the modcount unconditionally updated even when an ArrayIndexOutOfBoundsException was subsequently thrown for an invalid index and the Vector was not modified. With this change the modcount will only be updated if the Vector is actually changed. It is not expected that applications will have relied or should have relied on this behaviour.

I could live with that change in behaviour, but this change completely breaks the fail-fast semantics of the iterators in some cases! If you don't update modCount until after the change is complete, the iterator may access the updated state and not throw CME!.

There is a possibility that a method could barf before the modCount is updated e.g. before the fix the modCount was aggressively updated, but now it is possible to say throw an exception and the modCount will not be updated (see addAll if the collection is null or the index is out of bounds).

I think this change is misguided.

I too share concerns about this. I would have hoped that the compiler (both javac and the runtime) might be able to automatically move code around to group writes. In the interim of getting such good compiler support i can understand the need for certain updates to improve performance. Do we have access to the perf results? Paul.

On Apr 4, 2014, at 1:42 AM, Mike Duigou <mike.duigou@oracle.com> wrote:

...

I could live with that change in behaviour, but this change completely breaks the fail-fast semantics of the iterators in some cases! If you don't update modCount until after the change is complete, the iterator may access the updated state and not throw CME!.

For Vector I don't see this. The Iterator accesses to the data structures is always done with the Vector.this lock held. The re-ordering would only be observable to another thread if it is reading the Vector fields without holding the lock. I am not sure we should worry about that case.

Agreed, i don't see how that can happen.

For Hashtable Iterator there is no synchronization on the owning Hashtable except during the remove() method. It is unclear why the Hashtable iterators were not written in the same way as Vector.

Dunno.

It seems like there would be massive disruption to adding synchronization to Hashtable's itertors. Are the Hashtable iterators actually fast-fail?

They are fail fast only from within the same thread when the control is inverted via iterator (like that for non-synchronized HashMap etc), otherwise it is necessary to explicitly synchronize on the iterator, much like that for Collections.synchronized* methods, see the implementation: public Set<K> keySet() { if (keySet == null) keySet = Collections.synchronizedSet(new KeySet(), this); return keySet; } The documentation for keySet etc. states: * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation), the results of * the iteration are undefined. The set supports element removal, The documentation on the enumeration methods does not say anything. We should probably update the documentation to additionally say something like that on Collections.synchronized* methods.

Without synchronization this is not guaranteed since the writes may not be visible and Hashtable iterator failure behaviour is already likely to vary between platforms/architectures. With RTM it's presumed that the writes will NOT be visible until the transaction completes. This implies that the failure mode from Hashtable iterators is likely to change just by turning RTM locking on whether we make this code change or not. :-(

...

I think this change is misguided.

I think we are fine for Vector, but Hashtable gives me concerns even in it's current state.

I don't think the current situation is made any worse by your changes. The are some subtle changes with regards parameter checking and throwing exceptions, but that does not seems to be very important behaviour to preserve. Paul.

I'll retreat to being neutral on the overall idea. In general, it *is* a best software engineering practice to do all the reading and computing before doing all the writing at the end. You'll break anyone who does the crazy thing of intentionally calling add(null, Integer.MAX_VALUE) just for the side effect of incrementing modCount. How would _you_ increment modCount without doing any modding?! You could make a real improvement (more concurrency) for addAll, by moving the call to toArray out of the synchronized block. public synchronized boolean addAll(Collection<? extends E> c) { - modCount++; Object[] a = c.toArray(); It's hardly worth it for e.g. clear, where you are doing nothing but writes in the loop as well. public synchronized void clear() { Entry<?,?> tab[] = table; - modCount++; for (int index = tab.length; --index >= 0; ) tab[index] = null; + modCount++; count = 0; } On Mon, Apr 14, 2014 at 3:54 PM, Mike Duigou <mike.duigou@oracle.com> wrote:

Hello all;

Sorry for the delay in following up on this issue. I have collected responses to the various comments and will provide responses here.

- Regarding the performance impact of the changes and of RTM. Valdimir Kozlov provided the following results from a run on a Haswell CPU system:

...

threads=4 Interval=10000 CPUs=4 MapSize=2048 Population=1024 P10G80R10

Without RTM locking, without Hashtable changes:

2080 iterations/msec

Without RTM locking, with Hashtable changes (-Xbootclasspath/p:Hashtable124.jar):

2140 iterations/msec

With RTM locking (-XX:+UseRTMLocking), without Hashtable changes:

23500 iterations/ms

With RTM locking, with Hashtable changes:

33100 iterations/ms

Numbers are average from 3 runs. They v[a]ry about 6-8%.

The benchmark is a slightly adapted version of the Hashtable benchmark used in Dave Dice's ASPLOS 2009 "Rock" paper [1]

- Regarding hotspot or javac doing the desired code movements. Neither compiler will currently move assignments past conditional logic and it isn't likely this will change in the near future. While it would be foolish to restructure all of our code for "compiler behaviour of the week" it does seem prudent to do so very selectively when we know that the behaviour is not going to soon change and the benefits are significant.

- Regarding potential loss of fast-fail behaviour. Vector is unaffected because reads and co-mod checks are always done under synchronization. Enumerations from Hashtable elements() and keys() methods offer no fast-fail behaviour though they may see different behaviour as a result of this change. The Hashtable entrySet().iterator(), keySet().iterator() and values().iterator() will have the existing behaviour when the illegal modification occurs on the same thread as iteration. When the modification occurs on a different thread then it is possible that different behaviour may be observed. Since the Hashtable Iterator modCount check occurs without synchronization the ordering of visible writes is unspecified until the lock on Hashtable is released. In the meantime neither, either or both writes may be visible. In RTM, updates to modCount would not be visible to unsynchronized readers regardless of placement within the synchronized block. We may just have to accept this limitation of Hashtable Iterators--they should really be holding the lock during next() if the fast-fail is to be reliable.

Should we proceed forward despite these understood limitations? My vote is a very soft "Yes".

Mike

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.143.8940&rep=rep1&t...

On Apr 4 2014, at 02:07 , Paul Sandoz <paul.sandoz@oracle.com> wrote:

...

On Apr 4, 2014, at 1:42 AM, Mike Duigou <mike.duigou@oracle.com> wrote:

...

...

I could live with that change in behaviour, but this change completely

breaks the fail-fast semantics of the iterators in some cases! If you don't update modCount until after the change is complete, the iterator may access the updated state and not throw CME!.

For Vector I don't see this. The Iterator accesses to the data structures is always done with the Vector.this lock held. The re-ordering would only be observable to another thread if it is reading the Vector fields without holding the lock. I am not sure we should worry about that case.

Agreed, i don't see how that can happen.

...

For Hashtable Iterator there is no synchronization on the owning Hashtable except during the remove() method. It is unclear why the Hashtable iterators were not written in the same way as Vector.

Dunno.

...

It seems like there would be massive disruption to adding synchronization to Hashtable's itertors. Are the Hashtable iterators actually fast-fail?

They are fail fast only from within the same thread when the control is inverted via iterator (like that for non-synchronized HashMap etc), otherwise it is necessary to explicitly synchronize on the iterator, much like that for Collections.synchronized* methods, see the implementation:

public Set<K> keySet() { if (keySet == null) keySet = Collections.synchronizedSet(new KeySet(), this); return keySet; }

The documentation for keySet etc. states:

* reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation), the results of * the iteration are undefined. The set supports element removal,

The documentation on the enumeration methods does not say anything.

We should probably update the documentation to additionally say something like that on Collections.synchronized* methods.

...

Without synchronization this is not guaranteed since the writes may not be visible and Hashtable iterator failure behaviour is already likely to vary between platforms/architectures. With RTM it's presumed that the writes will NOT be visible until the transaction completes. This implies that the failure mode from Hashtable iterators is likely to change just by turning RTM locking on whether we make this code change or not. :-(

...

...

I think this change is misguided.

I think we are fine for Vector, but Hashtable gives me concerns even in it's current state.

I don't think the current situation is made any worse by your changes.

The are some subtle changes with regards parameter checking and throwing exceptions, but that does not seems to be very important behaviour to preserve.

Paul.

Did you mean s/code/link/ ? + * The Enumerations returned by Hashtable's {@code #keys keys} and + * {@code #elements elements} methods are <em>not</em> fail-fast. On Tue, Apr 15, 2014 at 3:14 PM, Mike Duigou <mike.duigou@oracle.com> wrote:

On Apr 14 2014, at 18:25 , Martin Buchholz <martinrb@google.com> wrote:

...

I'll retreat to being neutral on the overall idea.

In general, it *is* a best software engineering practice to do all the reading and computing before doing all the writing at the end.

You'll break anyone who does the crazy thing of intentionally calling add(null, Integer.MAX_VALUE) just for the side effect of incrementing modCount. How would _you_ increment modCount without doing any modding?!

Assuming you meant Vector::put(Integer.MAX_VALUE, null). You could use synchronized(vector) { vector.removeRange(vector.size(), vector.size()) } with slight higher cost.

...

You could make a real improvement (more concurrency) for addAll, by moving the call to toArray out of the synchronized block. public synchronized boolean addAll(Collection<? extends E> c) { - modCount++; Object[] a = c.toArray();

Done!

...

It's hardly worth it for e.g. clear, where you are doing nothing but

writes in the loop as well.

...

public synchronized void clear() { Entry<?,?> tab[] = table; - modCount++; for (int index = tab.length; --index >= 0; ) tab[index] = null; + modCount++; count = 0; }

For consistency with other methods I retained the movement of modCount.

I have updated the webrev with what I hope is the final form:

http://cr.openjdk.java.net/~mduigou/JDK-8020860/1/webrev/

Good to go?

Mike

PS:- I would have liked to rewritten Hashtable::putAll(Map<> t)

as :

{ t.forEach(this::put) }

but decided against this since it may change the synchronization on t which seems risky. ie. some Thread could hold a lock on t which would now deadlock where the current implementation does not. The forEach() implementation would have advantages as for some cases it would avoid the need to create Map.Entry objects in the iterator.

Yes. This has been corrected. Mike On Apr 16 2014, at 08:19 , Martin Desruisseaux <martin.desruisseaux@geomatys.fr> wrote:

Hello all

Le 15/04/14 18:14, Mike Duigou a écrit :

...

I have updated the webrev with what I hope is the final form:

http://cr.openjdk.java.net/~mduigou/JDK-8020860/1/webrev/

The first changes in the javadoc contains "{@code #keys keys}" and "{@code #elements elements}". I presume that you mean {@link} instead of {@code}?

Martin

Thanks Martin and Martin; I have corrected this along with some additional documentation updates: http://cr.openjdk.java.net/~mduigou/JDK-8020860/3/webrev/ Mike On Apr 16 2014, at 10:47 , Martin Buchholz <martinrb@google.com> wrote:

Here you access elementCount outside the synchronized block, which is a data race + public boolean addAll(int index, Collection<? extends E> c) { if (index < 0 || index > elementCount) throw new ArrayIndexOutOfBoundsException(index);

On Wed, Apr 16, 2014 at 10:30 AM, Mike Duigou <mike.duigou@oracle.com> wrote: Yes. This has been corrected.

Mike

On Apr 16 2014, at 08:19 , Martin Desruisseaux <martin.desruisseaux@geomatys.fr> wrote:

...

Hello all

Le 15/04/14 18:14, Mike Duigou a écrit :

...

I have updated the webrev with what I hope is the final form:

http://cr.openjdk.java.net/~mduigou/JDK-8020860/1/webrev/

The first changes in the javadoc contains "{@code #keys keys}" and "{@code #elements elements}". I presume that you mean {@link} instead of {@code}?

Martin

I would prefer having separate changes that address different concerns. Here's a spec update that is not quite correct because the ArrayStoreException depends on the runtime types (i.e. the Class objects available at runtime), but these may be different from the compile-time type parameters T and E. The fact that arrays are incorrectly covariant at compile time adds to the confusion. There's also a confusion between the type of a and the component type of a. You could improve matters by introducing the word "component type" in these sorts of specs. I again think this kind of change should be done across all the jdk classes. http://docs.oracle.com/javase/specs/jls/se7/html/jls-10.html All the components of an array have the same type, called the*component type* of the array. - * @throws ArrayStoreException if the runtime type of a is not a supertype - * of the runtime type of every element in this Vector + * @throws ArrayStoreException if the runtime type of a, {@code <T>}, is not + * a supertype of the runtime type, {@code <E>}, of every element in this + * Vector On Fri, May 2, 2014 at 12:22 PM, Mike Duigou <mike.duigou@oracle.com> wrote:

Thanks Martin and Martin;

I have corrected this along with some additional documentation updates:

http://cr.openjdk.java.net/~mduigou/JDK-8020860/3/webrev/

Mike

On Apr 16 2014, at 10:47 , Martin Buchholz <martinrb@google.com> wrote:

Here you access elementCount outside the synchronized block, which is a data race

+ public boolean addAll(int index, Collection<? extends E> c) { if (index < 0 || index > elementCount) throw new ArrayIndexOutOfBoundsException(index);

On Wed, Apr 16, 2014 at 10:30 AM, Mike Duigou <mike.duigou@oracle.com>wrote:

...

Yes. This has been corrected.

Mike

On Apr 16 2014, at 08:19 , Martin Desruisseaux < martin.desruisseaux@geomatys.fr> wrote:

...

Hello all

Le 15/04/14 18:14, Mike Duigou a écrit :

...

I have updated the webrev with what I hope is the final form:

http://cr.openjdk.java.net/~mduigou/JDK-8020860/1/webrev/

The first changes in the javadoc contains "{@code #keys keys}" and "{@code #elements elements}". I presume that you mean {@link} instead of {@code}?

Martin