Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

This finally got committed, after a lot of performance and testing rework,
and discovering plenty of opportunity for future performance, scalability
and testing improvements.  Thanks to reviewers for performance push back,
leading especially to a better ArrayDeque.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Mon, Nov 21, 2016 at 8:47 AM, Paul Sandoz  wrote:

>
> On 21 Nov 2016, at 07:29, Martin Buchholz  wrote:
>
> Un-OK. Sometimes when microbenchmarking, we stumble upon a code sequence
> that hotspot likes.   I observed 20% improvement with the below, so
> switching to that:
>
> public boolean tryAdvance(Consumer action) {
> Objects.requireNonNull(action);
> final Object[] es = elements;
> if (fence < 0) { fence = tail; cursor = head; } // late-binding
> final int i;
> if ((i = cursor) == fence)
> return false;
> E e = nonNullElementAt(es, i);
> cursor = inc(i, es.length);
> action.accept(e);
> return true;
> }
>
>
> Ok.
>
> I suppose i should stop being surprised at these kind of things, but would
> like to know, if you happen to, why such an improvement was gained for
> explicitly inlining the getFence call. Were you reaching some inlining
> thresholds in hotspot?
>

It's worse than that.  I had to un-inline AND move the cursor increment
into the "middle" of the call to accept.

Regarding getFence() - I'm not convinced having a separate method here is
ever good for humans or machines, especially when the inlined version is
one readable line of code, whereas getFence() has a non-obvious side effect.

Regarding moving array access before cursor increment: this makes it easier
for hotspot to do the array access checks and cursor increment in parallel;
otherwise hotspot (thinks it) needs to defer array access until after
cursor is written because it might be out of bounds?!

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 21 Nov 2016, at 07:29, Martin Buchholz  wrote:
> 
> Un-OK. Sometimes when microbenchmarking, we stumble upon a code sequence that 
> hotspot likes.   I observed 20% improvement with the below, so switching to 
> that:
> 
> public boolean tryAdvance(Consumer action) {
> Objects.requireNonNull(action);
> final Object[] es = elements;
> if (fence < 0) { fence = tail; cursor = head; } // late-binding
> final int i;
> if ((i = cursor) == fence)
> return false;
> E e = nonNullElementAt(es, i);
> cursor = inc(i, es.length);
> action.accept(e);
> return true;
> }
> 

Ok.

I suppose i should stop being surprised at these kind of things, but would like 
to know, if you happen to, why such an improvement was gained for explicitly 
inlining the getFence call. Were you reaching some inlining thresholds in 
hotspot?

Paul.

> 
> On Thu, Nov 17, 2016 at 7:41 PM, Martin Buchholz  > wrote:
> 
> 
> On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz  > wrote:
> 
>  843 public boolean tryAdvance(Consumer action) {
>  844 if (action == null)
>  845 throw new NullPointerException();
>  846 int t, i;
>  847 if ((t = fence) < 0) t = getFence();
> 
> Is that for optimisation purposes, since the same check is also performed in 
> getFence? If so that seems like overkill
> 
> 
> OK:
> 
> --- src/main/java/util/ArrayDeque.java18 Nov 2016 03:22:20 -  
> 1.114
> +++ src/main/java/util/ArrayDeque.java18 Nov 2016 03:38:23 -
> @@ -866,9 +866,8 @@
>  public boolean tryAdvance(Consumer action) {
>  if (action == null)
>  throw new NullPointerException();
> -int t, i;
> -if ((t = fence) < 0) t = getFence();
> -if (t == (i = cursor))
> +final int t, i;
> +if ((t = getFence()) == (i = cursor))
>  return false;
>  final Object[] es = elements;
>  cursor = inc(i, es.length);
> 
> 
> 
>  848 if (t == (i = cursor))
>  849 return false;
>  850 final Object[] es;
>  851 action.accept(nonNullElementAt(es = elements, i));
>  852 cursor = inc(i, es.length);
> 

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Un-OK. Sometimes when microbenchmarking, we stumble upon a code sequence
that hotspot likes.   I observed 20% improvement with the below, so
switching to that:

public boolean tryAdvance(Consumer action) {
Objects.requireNonNull(action);
final Object[] es = elements;
if (fence < 0) { fence = tail; cursor = head; } // late-binding
final int i;
if ((i = cursor) == fence)
return false;
E e = nonNullElementAt(es, i);
cursor = inc(i, es.length);
action.accept(e);
return true;
}


On Thu, Nov 17, 2016 at 7:41 PM, Martin Buchholz 
wrote:

>
>
> On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz 
> wrote:
>
>>
>>  843 public boolean tryAdvance(Consumer action) {
>>  844 if (action == null)
>>  845 throw new NullPointerException();
>>  846 int t, i;
>>  847 if ((t = fence) < 0) t = getFence();
>>
>> Is that for optimisation purposes, since the same check is also performed
>> in getFence? If so that seems like overkill
>>
>>
> OK:
>
> --- src/main/java/util/ArrayDeque.java 18 Nov 2016 03:22:20 - 1.114
> +++ src/main/java/util/ArrayDeque.java 18 Nov 2016 03:38:23 -
> @@ -866,9 +866,8 @@
>  public boolean tryAdvance(Consumer action) {
>  if (action == null)
>  throw new NullPointerException();
> -int t, i;
> -if ((t = fence) < 0) t = getFence();
> -if (t == (i = cursor))
> +final int t, i;
> +if ((t = getFence()) == (i = cursor))
>  return false;
>  final Object[] es = elements;
>  cursor = inc(i, es.length);
>
>
>
>>
>>  848 if (t == (i = cursor))
>>  849 return false;
>>  850 final Object[] es;
>>  851 action.accept(nonNullElementAt(es = elements, i));
>>  852 cursor = inc(i, es.length);
>>
>

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

No more rework is planned!

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Regarding the testing mess:

I think there should be a project to use Junit 5 features to create
interface based tests.  Then a BlockingDeque implementation could easily
pull in all the tests already written for BlockingDeque and its
superinterfaces.  Tests for interfaces would be found in a predictable
location, e.g. test/j/u/c/BlockingDeque/.  jtreg probably needs to have
junit 5 support added.  There should be testing folk excited about doing
this!  (The historic preference to have such tests in the JCK is an
impediment ... )

On Wed, Oct 19, 2016 at 12:19 PM, Stuart Marks 
wrote:

>
>
> On 10/18/16 11:00 AM, Martin Buchholz wrote:
>
>> There's already a certain amount of mixing, e.g. stream tests sometimes
>> test
>> j.u.c. and Queue tests sometimes test all the Queue implementations.
>> Unlike
>> non-test code, some redundancy and divergence of testing frameworks and
>> styles
>> is fine.  I still haven't found a way of writing shared tests for
>> implementations of an interface that I really like.
>>
>
> It's probably the case that divergence of testing frameworks is
> unavoidable, or at least it's impractical. I doubt that it's worthwhile to
> rewrite all the straight jtreg tests into TestNG, or JUnit, or whatever.
> But I'd draw the line before saying this is "fine." [1]
>
> Maintaining the tests' organization is pretty important. Most of the
> collections tests are in jdk/test/java/util though they're spread around a
> bit uncomfortably even here. But now it's, oh, ArrayDeque and
> ArrayList.removeIf tests are over *here* instead. Having things spread
> around increases the likelihood of cases being missed or being tested
> redundantly.
>
> The test groups have to be maintained as well. I know I've been bitten by
> problems (not in collections) where I *thought* I had run the right set of
> tests, but it ended up that I hadn't, resulting in me breaking the build.
> As it turns out, jdk_collections_core doesn't include any ArrayDeque tests.
> Hmmm. Well, maybe jdk_collections_core isn't useful. It would have been
> nice to know this when I added it last year. :-/ [2]
>
> As things stand, I'm basically OK with this changeset going in. But it
> does seem to highlight some areas that need some future cleanup,
> particularly in the tests and the test group declarations.
>
> s'marks
>
> [1] http://knowyourmeme.com/memes/this-is-fine
>
> [2] http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/7a0c06013ae6
>
>

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

I encourage you to look at the experiments in the valhalla repository.

Such as:

  
http://hg.openjdk.java.net/valhalla/valhalla/jdk/file/780c8eba356a/src/java.base/share/classes/java/anyutil/ArrayDeque.java
 


I have no objections to the current change but i expect it to change back at 
some point, and there will be other changes needed as you point out, but 
perhaps not as major as you think in some cases, and others perhaps more so, 
especially to take advantage of value-type optimized data structures.

Paul.

> On 18 Nov 2016, at 08:57, Martin Buchholz  wrote:
> 
> 
> 
> On Fri, Nov 18, 2016 at 5:02 AM, Doug Lea  > wrote:
> On 11/18/2016 02:28 AM, Remi Forax wrote:
> Martin,
> for ArrayDeque, when you start to have methods like
>   @SuppressWarnings("unchecked")
>static final  E elementAt(Object[] es, int i) {
>return (E) es[i];
>}
> 
> I think it's a better idea to type the field elements as a E[] instead of 
> Object[].
> Historically, using Object(] instead of E[] was preferred because it's a kind 
> of 'more true' at runtime,
> but it will be less true with anyfied generics and as we can see if it leads 
> to introduce method like elementAt, using E[] will make the code more 
> readable.
> 
> 
> We always use Object[] in cases where anyfication isn't possible
> (without further code rework) because we rely on null as a distinct
> value. Elsewhere we do use E[].
> 
> I've always considered using E[] a bigger cheat than the elementAt method, 
> due to the expectation that if reification was ever implemented, then E[] 
> would simply be wrong in a ClassCastException sort of way.
> 
> I will be surprised if anyfication can be made to work on collection classes 
> without major rewrites.  When working with elements that are references, 
> there is a need to null out slots that are no longer used for the benefit of 
> the GC, as well as a special value to mark the slot as free.  Sometimes 
> logically removing an element means CASing the reference to null.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Here's a few more places to apply Remi's rule:

--- src/test/tck/Collection8Test.java 15 Nov 2016 23:08:30 - 1.27
+++ src/test/tck/Collection8Test.java 18 Nov 2016 17:21:19 -
@@ -304,7 +304,7 @@
 switch (rnd.nextInt(4)) {
 case 0: survivors.addAll(c); break;
 case 1: survivors.addAll(Arrays.asList(c.toArray())); break;
-case 2: c.forEach(e -> survivors.add(e)); break;
+case 2: c.forEach(survivors::add); break;
 case 3: for (Object e : c) survivors.add(e); break;
 }
 assertTrue(orig.containsAll(accepts));
@@ -355,11 +355,11 @@
 ArrayList forEached = new ArrayList();
 ArrayList removeIfed = new ArrayList();
 for (Object x : c) iterated.add(x);
-c.iterator().forEachRemaining(e ->
iteratedForEachRemaining.add(e));
+c.iterator().forEachRemaining(iteratedForEachRemaining::add);
 for (Spliterator s = c.spliterator();
- s.tryAdvance(e -> tryAdvanced.add(e)); ) {}
-c.spliterator().forEachRemaining(e -> spliterated.add(e));
-c.forEach(e -> forEached.add(e));
+ s.tryAdvance(tryAdvanced::add); ) {}
+c.spliterator().forEachRemaining(spliterated::add);
+c.forEach(forEached::add);
 c.removeIf(e -> { removeIfed.add(e); return false; });
 boolean ordered =
 c.spliterator().hasCharacteristics(Spliterator.ORDERED);
@@ -589,7 +589,7 @@
 try (PoolCleaner cleaner = cleaner(pool, done)) {
 threadsStarted.bulkRegister(tasks.size());
 futures = tasks.stream()
-.map(task -> pool.submit(task))
+.map(pool::submit)
 .collect(Collectors.toList());
 threadsStarted.arriveAndDeregister();
 Thread.sleep(testDurationMillis);

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 18 Nov 2016, at 08:46, Martin Buchholz <marti...@google.com> wrote:
> 
> 
> 
> On Thu, Nov 17, 2016 at 11:17 PM, Remi Forax <fo...@univ-mlv.fr 
> <mailto:fo...@univ-mlv.fr>> wrote:
> - Mail original -
> > De: "Martin Buchholz" <marti...@google.com <mailto:marti...@google.com>>
> > À: "Paul Sandoz" <paul.san...@oracle.com <mailto:paul.san...@oracle.com>>
> > Cc: "core-libs-dev" <core-libs-dev@openjdk.java.net 
> > <mailto:core-libs-dev@openjdk.java.net>>
> > Envoyé: Vendredi 18 Novembre 2016 05:29:12
> > Objet: Re: RFR: jsr166 jdk9 integration wave 12
> 
> [..]
> 
> 
> >>  317 c.forEach(e -> addLast(e));
> >>
> >> this::addLast, up to you which you prefer
> >>
> >>
> > Meh.  Left as is; another vote could tip to the other side.
> >
> >
> 
> I like the rule that says, use a method reference if you can and a lambda 
> otherwise.
> so i vote for this::addLast :)
> 
> 
> Done!  Seems like a good rule to adopt.
> 

And FWIW you will get slightly less byte code in the compiled class, because 
there is no lambda body to de-sugar.

Paul.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Fri, Nov 18, 2016 at 5:02 AM, Doug Lea  wrote:

> On 11/18/2016 02:28 AM, Remi Forax wrote:
>
>> Martin,
>> for ArrayDeque, when you start to have methods like
>>   @SuppressWarnings("unchecked")
>>static final  E elementAt(Object[] es, int i) {
>>return (E) es[i];
>>}
>>
>> I think it's a better idea to type the field elements as a E[] instead of
>> Object[].
>> Historically, using Object(] instead of E[] was preferred because it's a
>> kind of 'more true' at runtime,
>> but it will be less true with anyfied generics and as we can see if it
>> leads to introduce method like elementAt, using E[] will make the code more
>> readable.
>>
>>
> We always use Object[] in cases where anyfication isn't possible
> (without further code rework) because we rely on null as a distinct
> value. Elsewhere we do use E[].


I've always considered using E[] a bigger cheat than the elementAt method,
due to the expectation that if reification was ever implemented, then E[]
would simply be wrong in a ClassCastException sort of way.

I will be surprised if anyfication can be made to work on collection
classes without major rewrites.  When working with elements that are
references, there is a need to null out slots that are no longer used for
the benefit of the GC, as well as a special value to mark the slot as
free.  Sometimes logically removing an element means CASing the reference
to null.

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 18 Nov 2016, at 04:52, Doug Lea  wrote:
> 
> 
>> On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz > > wrote:
>> 
>> 
>>Semaphore
>>—
>> 
>> 633 /**
>> 634  * Acquires and returns all permits that are immediately
>>available.
>> 635  * Upon return, zero permits are available.
>> 636  *
>> 637  * @return the number of permits acquired
>> 638  */
>> 639 public int drainPermits() {
>> 640 return sync.drainPermits();
>> 641 }
>> 
>>Arguably, if positive acquires all permits, otherwise releases all
>>permits. Perhaps:
> 
> Thank! That's a better way to phrase intent. Reworded to:
> 
>/**
> * Acquires and returns all permits that are immediately
> * available, or if negative permits are available, releases them.
> * Upon return, zero permits are available.
> *
> * @return the number of permits acquired or, if negative, the
> * number released
> */
> 

Looks good to me.


>> 
>>Probably requires a CCC which i can manage.
>> 
> 
> Really?

Hmm… i don’t really wanna do it :-) but i suppose from the current 
specification it could be interpreted that no action is taken if there are 
negative permits. I believe submitter of the associated bug interpreted it that 
way.

> If so, please do.
> 

I’ll take the pain :-)

Paul.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Thu, Nov 17, 2016 at 11:17 PM, Remi Forax <fo...@univ-mlv.fr> wrote:

> - Mail original -
> > De: "Martin Buchholz" <marti...@google.com>
> > À: "Paul Sandoz" <paul.san...@oracle.com>
> > Cc: "core-libs-dev" <core-libs-dev@openjdk.java.net>
> > Envoyé: Vendredi 18 Novembre 2016 05:29:12
> > Objet: Re: RFR: jsr166 jdk9 integration wave 12
>
> [..]
>
>
> >>  317 c.forEach(e -> addLast(e));
> >>
> >> this::addLast, up to you which you prefer
> >>
> >>
> > Meh.  Left as is; another vote could tip to the other side.
> >
> >
>
> I like the rule that says, use a method reference if you can and a lambda
> otherwise.
> so i vote for this::addLast :)
>
>
Done!  Seems like a good rule to adopt.


> Rémi
>

Re: RFR: jsr166 jdk9 integration wave 12

[Doug Lea]

On 11/18/2016 02:28 AM, Remi Forax wrote:

Martin,
for ArrayDeque, when you start to have methods like
  @SuppressWarnings("unchecked")
   static final  E elementAt(Object[] es, int i) {
   return (E) es[i];
   }

I think it's a better idea to type the field elements as a E[] instead of 
Object[].
Historically, using Object(] instead of E[] was preferred because it's a kind 
of 'more true' at runtime,
but it will be less true with anyfied generics and as we can see if it leads to 
introduce method like elementAt, using E[] will make the code more readable.



We always use Object[] in cases where anyfication isn't possible
(without further code rework) because we rely on null as a distinct
value. Elsewhere we do use E[].

-Doug



so the constructors should be:
  @SuppressWarnings("unchecked")
  public ArrayDeque() {
elements = (E[])new Object[16];
  }

(same transformation for ArrayDeque(int)).

And you can remove all the casts to E and the corresponnding SuppressWarnings 
and remove the method elementAt.

Rémi

- Mail original -

De: "Martin Buchholz" 
À: "core-libs-dev" , "Doug Lea" , 
"Stuart Marks"
, "Paul Sandoz" 
Envoyé: Mardi 18 Octobre 2016 03:34:34
Objet: RFR: jsr166 jdk9 integration wave 12



Most of this is for Stuart - very collection-y.

http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/

This includes a rewrite of ArrayDeque to bring it to parity with ArrayList
(except for List features).
The patch includes public methods ensureCapacity, trimToSize, replaceAll as
in ArrayList, but we can defer making them public to a later change (or a
later release), since new public methods are always controversial.  But I'd
really like to get the performance/scalability changes in for jdk 9.

It also includes a redo of ArrayList#removeIf to make it more efficient and
consistent with behavior of other implementations, including ArrayDeque.

The patches are a little tangled because they step on each other's toes.
File CollectionTest is in "miscellaneous", but it tests both the ArrayDeque
and ArrayList changes.

Re: RFR: jsr166 jdk9 integration wave 12

[Doug Lea]

On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz > wrote:


Semaphore
—

 633 /**
 634  * Acquires and returns all permits that are immediately
available.
 635  * Upon return, zero permits are available.
 636  *
 637  * @return the number of permits acquired
 638  */
 639 public int drainPermits() {
 640 return sync.drainPermits();
 641 }

Arguably, if positive acquires all permits, otherwise releases all
permits. Perhaps:


Thank! That's a better way to phrase intent. Reworded to:

/**
 * Acquires and returns all permits that are immediately
 * available, or if negative permits are available, releases them.
 * Upon return, zero permits are available.
 *
 * @return the number of permits acquired or, if negative, the
 * number released
 */



Probably requires a CCC which i can manage.



Really? If so, please do.

-Doug

Re: RFR: jsr166 jdk9 integration wave 12

[Remi Forax]

Martin,
for ArrayDeque, when you start to have methods like
  @SuppressWarnings("unchecked")
   static final  E elementAt(Object[] es, int i) {
   return (E) es[i];
   }

I think it's a better idea to type the field elements as a E[] instead of 
Object[].
Historically, using Object(] instead of E[] was preferred because it's a kind 
of 'more true' at runtime,
but it will be less true with anyfied generics and as we can see if it leads to 
introduce method like elementAt, using E[] will make the code more readable.

so the constructors should be:
  @SuppressWarnings("unchecked")
  public ArrayDeque() {
elements = (E[])new Object[16];
  }

(same transformation for ArrayDeque(int)).

And you can remove all the casts to E and the corresponnding SuppressWarnings 
and remove the method elementAt.

Rémi

- Mail original -
> De: "Martin Buchholz" 
> À: "core-libs-dev" , "Doug Lea" 
> , "Stuart Marks"
> , "Paul Sandoz" 
> Envoyé: Mardi 18 Octobre 2016 03:34:34
> Objet: RFR: jsr166 jdk9 integration wave 12

> Most of this is for Stuart - very collection-y.
> 
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/
> 
> This includes a rewrite of ArrayDeque to bring it to parity with ArrayList
> (except for List features).
> The patch includes public methods ensureCapacity, trimToSize, replaceAll as
> in ArrayList, but we can defer making them public to a later change (or a
> later release), since new public methods are always controversial.  But I'd
> really like to get the performance/scalability changes in for jdk 9.
> 
> It also includes a redo of ArrayList#removeIf to make it more efficient and
> consistent with behavior of other implementations, including ArrayDeque.
> 
> The patches are a little tangled because they step on each other's toes.
> File CollectionTest is in "miscellaneous", but it tests both the ArrayDeque
> and ArrayList changes.

Re: RFR: jsr166 jdk9 integration wave 12

[Remi Forax]

- Mail original -
> De: "Martin Buchholz" <marti...@google.com>
> À: "Paul Sandoz" <paul.san...@oracle.com>
> Cc: "core-libs-dev" <core-libs-dev@openjdk.java.net>
> Envoyé: Vendredi 18 Novembre 2016 05:29:12
> Objet: Re: RFR: jsr166 jdk9 integration wave 12

[..]


>>  317 c.forEach(e -> addLast(e));
>>
>> this::addLast, up to you which you prefer
>>
>>
> Meh.  Left as is; another vote could tip to the other side.
> 
> 

I like the rule that says, use a method reference if you can and a lambda 
otherwise.
so i vote for this::addLast :)

Rémi

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz 
wrote:

>
> Semaphore
> —
>
>  633 /**
>  634  * Acquires and returns all permits that are immediately
> available.
>  635  * Upon return, zero permits are available.
>  636  *
>  637  * @return the number of permits acquired
>  638  */
>  639 public int drainPermits() {
>  640 return sync.drainPermits();
>  641 }
>
> Arguably, if positive acquires all permits, otherwise releases all
> permits. Perhaps:
>
>   Acquires and returns all permits that are immediately available,
> otherwise releases all permits (if negative).
>   Upton return, zero permits are available.
>
>   @return the number of permits acquired, or the number of permits release
> (a negative value)
>
> Probably requires a CCC which i can manage.
>

I agree we can do better along the lines you suggest.  I'm hesitant since I
don't understand the intended use for  drainPermits.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz 
wrote:

>
> Perhaps consolidate the repeated mini bit set methods as package private
> static methods on AbstractCollection? Unclear where the j.u.concurrent ones
> should go though...
>

Deferred.


> It’s purely a subjective thing but i would be inclined to change the
> variable name “deathRow" to something more neutral such as “removedBitSet”.
>

It's certainly evocative!  Especially given that they may get a reprieve
from a following predicate!


> The 2 layer nested loop is quite clever, certainly twists the mind when
> first encountered. It’s arguably more readable if there are two separate,
> (not-nested) loops, but that also requires two explicit invocations of the
> action, which may perturb the performance characteristics.
>

After you've written a hundred of these loops, they start to look rather
natural/idiomatic.  I think these nested loops should be the canonical way
to implement traversals of circular buffers in any programming language.
The inner loops seem optimal.  It seems unlikely we've invented something
new here, but maybe...


> ArrayDeque
> —
>
>  188 public ArrayDeque(int numElements) {
>  189 elements = new Object[Math.max(1, numElements + 1)];
>  190 }
>
> What if Integer.MAX_VALUE is passed?
>

Now tries (and fails!) to allocate a maximal array.


>  202 public ArrayDeque(Collection c) {
>  203 elements = new Object[c.size() + 1];
>  204 addAll(c);
>  205 }
>
> What if c.size() returns Integer.MAX_VALUE?
>
>
Now delegates to the other constructor.


>
>  226  * Adds i and j, mod modulus.
>  227  * Precondition and postcondition: 0 <= i < modulus, 0 <= j <=
> modulus.
>  228  */
>  229 static final int add(int i, int j, int modulus) {
>
> Is that upper bound correct for j? 0 <= j < modulus
>

j renamed to distance, to emphasize asymmetry.
Although in this file, distance will never equal modulus.


>
>  317 c.forEach(e -> addLast(e));
>
> this::addLast, up to you which you prefer
>
>
Meh.  Left as is; another vote could tip to the other side.


>
>  843 public boolean tryAdvance(Consumer action) {
>  844 if (action == null)
>  845 throw new NullPointerException();
>  846 int t, i;
>  847 if ((t = fence) < 0) t = getFence();
>
> Is that for optimisation purposes, since the same check is also performed
> in getFence? If so that seems like overkill
>
>
done.


>
>  848 if (t == (i = cursor))
>  849 return false;
>  850 final Object[] es;
>  851 action.accept(nonNullElementAt(es = elements, i));
>  852 cursor = inc(i, es.length);
>
> Recommend updating cursor before the action
>
>
done.


>
>  853 return true;
>  854 }
>
>
>
> Collection8Test
> —
>
>  429 public void testRemoveAfterForEachRemaining() {
>
> Are tests run by default with testImplementationDetails == true? I am
> guessing so.
>
>
We run various combinations in jtreg mode.

 * @run junit/othervm/timeout=1000 -Djsr166.testImplementationDetails=true
JSR166TestCase
 * @run junit/othervm/timeout=1000
-Djava.util.concurrent.ForkJoinPool.common.parallelism=0
-Djsr166.testImplementationDetails=true JSR166TestCase
 * @run junit/othervm/timeout=1000
-Djava.util.concurrent.ForkJoinPool.common.parallelism=1
-Djava.util.secureRandomSeed=true JSR166TestCase

The original target for these tests are the jck, and that is expected to
run with the default testImplementationDetails=false

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz 
wrote:

>
>  843 public boolean tryAdvance(Consumer action) {
>  844 if (action == null)
>  845 throw new NullPointerException();
>  846 int t, i;
>  847 if ((t = fence) < 0) t = getFence();
>
> Is that for optimisation purposes, since the same check is also performed
> in getFence? If so that seems like overkill
>
>
OK:

--- src/main/java/util/ArrayDeque.java 18 Nov 2016 03:22:20 - 1.114
+++ src/main/java/util/ArrayDeque.java 18 Nov 2016 03:38:23 -
@@ -866,9 +866,8 @@
 public boolean tryAdvance(Consumer action) {
 if (action == null)
 throw new NullPointerException();
-int t, i;
-if ((t = fence) < 0) t = getFence();
-if (t == (i = cursor))
+final int t, i;
+if ((t = getFence()) == (i = cursor))
 return false;
 final Object[] es = elements;
 cursor = inc(i, es.length);



>
>  848 if (t == (i = cursor))
>  849 return false;
>  850 final Object[] es;
>  851 action.accept(nonNullElementAt(es = elements, i));
>  852 cursor = inc(i, es.length);
>

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Here's an update that adds some explanations, addresses some of Paul's
comments, and improves handling of capacities near 2**31.

Coincidentally, today I got access to a machine with enough memory to run
testHugeCapacity without dying, so that test gets fixed.  Previous
iterations tried to get rid of the spare slot, and there may be some other
lingering vestige of that, as with this test.

Index: src/main/java/util/ArrayDeque.java
===
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/ArrayDeque.java,v
retrieving revision 1.113
diff -u -r1.113 ArrayDeque.java
--- src/main/java/util/ArrayDeque.java 13 Nov 2016 02:10:09 - 1.113
+++ src/main/java/util/ArrayDeque.java 18 Nov 2016 03:09:50 -
@@ -68,13 +68,15 @@
  *
  * Because in a circular array, elements are in general stored in
  * two disjoint such slices, we help the VM by writing unusual
- * nested loops for all traversals over the elements.
+ * nested loops for all traversals over the elements.  Having only
+ * one hot inner loop body instead of two or three eases human
+ * maintenance and encourages VM loop inlining into the caller.
  */

 /**
  * The array in which the elements of the deque are stored.
- * We guarantee that all array cells not holding deque elements
- * are always null.
+ * All array cells not holding deque elements are always null.
+ * The array always has at least one null slot (at tail).
  */
 transient Object[] elements;

@@ -88,7 +90,8 @@

 /**
  * The index at which the next element would be added to the tail
- * of the deque (via addLast(E), add(E), or push(E)).
+ * of the deque (via addLast(E), add(E), or push(E));
+ * elements[tail] is always null.
  */
 transient int tail;

@@ -187,7 +190,10 @@
  * @param numElements lower bound on initial capacity of the deque
  */
 public ArrayDeque(int numElements) {
-elements = new Object[Math.max(1, numElements + 1)];
+elements =
+new Object[(numElements < 1) ? 1 :
+   (numElements == Integer.MAX_VALUE) ?
Integer.MAX_VALUE :
+   numElements + 1];
 }

 /**
@@ -201,7 +207,7 @@
  * @throws NullPointerException if the specified collection is null
  */
 public ArrayDeque(Collection c) {
-elements = new Object[c.size() + 1];
+this(c.size());
 addAll(c);
 }

@@ -224,19 +230,21 @@
 }

 /**
- * Adds i and j, mod modulus.
- * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
+ * Circularly adds the given distance to index i, mod modulus.
+ * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.
+ * @return index 0 <= i < modulus
  */
-static final int add(int i, int j, int modulus) {
-if ((i += j) - modulus >= 0) i -= modulus;
+static final int add(int i, int distance, int modulus) {
+if ((i += distance) - modulus >= 0) distance -= modulus;
 return i;
 }

 /**
  * Subtracts j from i, mod modulus.
- * Index i must be logically ahead of j.
- * Returns the "circular distance" from j to i.
- * Precondition and postcondition: 0 <= i < modulus, 0 <= j < modulus.
+ * Index i must be logically ahead of index j.
+ * Precondition: 0 <= i < modulus, 0 <= j < modulus.
+ * @return the "circular distance" from j to i; corner case i == j
+ * is diambiguated to "empty", returning 0.
  */
 static final int sub(int i, int j, int modulus) {
 if ((i -= j) < 0) i += modulus;
@@ -862,9 +870,9 @@
 if ((t = fence) < 0) t = getFence();
 if (t == (i = cursor))
 return false;
-final Object[] es;
-action.accept(nonNullElementAt(es = elements, i));
+final Object[] es = elements;
 cursor = inc(i, es.length);
+action.accept(nonNullElementAt(es, i));
 return true;
 }

@@ -1232,6 +1240,8 @@

 /** debugging */
 void checkInvariants() {
+// Use head and tail fields with empty slot at tail strategy.
+// head == tail disambiguates to "empty".
 try {
 int capacity = elements.length;
 // assert head >= 0 && head < capacity;
Index: src/main/java/util/concurrent/ArrayBlockingQueue.java
===
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/concurrent/ArrayBlockingQueue.java,v
retrieving revision 1.137
diff -u -r1.137 ArrayBlockingQueue.java
--- src/main/java/util/concurrent/ArrayBlockingQueue.java 13 Nov 2016
02:10:09 - 1.137
+++ src/main/java/util/concurrent/ArrayBlockingQueue.java 18 Nov 2016
03:09:50 -
@@ -58,6 +58,11 @@
 public class ArrayBlockingQueue extends AbstractQueue
 implements BlockingQueue, java.io.Serializable {

+/*

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 17 Nov 2016, at 13:58, Martin Buchholz  wrote:
> 
> 
> 
> On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz  > wrote:
> 
> ForkJoin
> —
> 
>   69  * tasks that are never joined. All worker threads are initialized
>   70  * with {@link Thread#isDaemon} set {@code true}.
> 
> CCC?
> 
> JDK 7 had
> """Because ForkJoinPool uses threads in daemon mode, there is typically no 
> need to explicitly shutdown such a pool upon program exit."""
>  
> https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html
>  
> 
> 
> but that was inadvertently dropped.
> 

Ah, i see, ok, no need.

Thanks,
Paul.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz 
wrote:

>
>
> SplittableRandom
> —
>
>  533 /**
>  534  * Generates a pseudorandom number with the indicated number of
>  535  * low-order bits.  Because this class has no subclasses, this
>  536  * method cannot be invoked or overridden.
>  537  *
>  538  * @param  bits random bits
>  539  * @return the next pseudorandom value from this random number
>  540  * generator's sequence
>  541  */
>  542 protected int next(int bits) {
>  543 return nextInt() >>> (32 - bits);
>  544 }
>  545
>
> Unless i am missing something really subtle, I don’t think this is
> required since SplittableRandom does not extend from Random (unlike in
> ThreadLocalRandom), and no associated reflective test is required.
>

Thanks! I completely missed that SplittableRandom doesn't extend Random!
Reverted changes to SplittableRandom and SplittableRandomTest.

I'm regenerating
http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/
but Paul's review version is available at
http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration.2016-11-17/

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Thu, Nov 17, 2016 at 12:03 PM, Paul Sandoz 
wrote:

>
> ForkJoin
> —
>
>   69  * tasks that are never joined. All worker threads are initialized
>   70  * with {@link Thread#isDaemon} set {@code true}.
>
> CCC?
>

JDK 7 had
"""Because ForkJoinPool uses threads in daemon mode, there is typically no
need to explicitly shutdown such a pool upon program exit."""

https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html

but that was inadvertently dropped.

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 16 Nov 2016, at 16:03, Martin Buchholz  wrote:
> 
> Apologies for having this wave turn into a tsunami.
> 
> CopyOnWriteArrayList was rewritten due to finding 
> https://bugs.openjdk.java.net/browse/JDK-8169738
> ArrayDeque and ArrayBlockingQueue now both use efficient nested loop idiom 
> for all traversals.
> Most bulk remove methods in all collection classes were rewritten for 
> efficiency, using similar code.
> Lots of tests and benchmarks added.

Ok, i will just go through all of it.


Collection-optimization
—

Perhaps consolidate the repeated mini bit set methods as package private static 
methods on AbstractCollection? Unclear where the j.u.concurrent ones should go 
though...

It’s purely a subjective thing but i would be inclined to change the variable 
name “deathRow" to something more neutral such as “removedBitSet”.

The 2 layer nested loop is quite clever, certainly twists the mind when first 
encountered. It’s arguably more readable if there are two separate, 
(not-nested) loops, but that also requires two explicit invocations of the 
action, which may perturb the performance characteristics.


ArrayDeque
—

 188 public ArrayDeque(int numElements) {
 189 elements = new Object[Math.max(1, numElements + 1)];
 190 }

What if Integer.MAX_VALUE is passed?


 202 public ArrayDeque(Collection c) {
 203 elements = new Object[c.size() + 1];
 204 addAll(c);
 205 }

What if c.size() returns Integer.MAX_VALUE?


 226  * Adds i and j, mod modulus.
 227  * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
 228  */
 229 static final int add(int i, int j, int modulus) {

Is that upper bound correct for j? 0 <= j < modulus ?


 317 c.forEach(e -> addLast(e));

this::addLast, up to you which you prefer


 843 public boolean tryAdvance(Consumer action) {
 844 if (action == null)
 845 throw new NullPointerException();
 846 int t, i;
 847 if ((t = fence) < 0) t = getFence();

Is that for optimisation purposes, since the same check is also performed in 
getFence? If so that seems like overkill


 848 if (t == (i = cursor))
 849 return false;
 850 final Object[] es;
 851 action.accept(nonNullElementAt(es = elements, i));
 852 cursor = inc(i, es.length);

Recommend updating cursor before the action


 853 return true;
 854 }



Collection8Test
—

 429 public void testRemoveAfterForEachRemaining() {

Are tests run by default with testImplementationDetails == true? I am guessing 
so.


Semaphore
—

 633 /**
 634  * Acquires and returns all permits that are immediately available.
 635  * Upon return, zero permits are available.
 636  *
 637  * @return the number of permits acquired
 638  */
 639 public int drainPermits() {
 640 return sync.drainPermits();
 641 }

Arguably, if positive acquires all permits, otherwise releases all permits. 
Perhaps:

  Acquires and returns all permits that are immediately available, otherwise 
releases all permits (if negative).
  Upton return, zero permits are available.

  @return the number of permits acquired, or the number of permits release (a 
negative value)

Probably requires a CCC which i can manage.



SplittableRandom
—

 533 /**
 534  * Generates a pseudorandom number with the indicated number of
 535  * low-order bits.  Because this class has no subclasses, this
 536  * method cannot be invoked or overridden.
 537  *
 538  * @param  bits random bits
 539  * @return the next pseudorandom value from this random number
 540  * generator's sequence
 541  */
 542 protected int next(int bits) {
 543 return nextInt() >>> (32 - bits);
 544 }
 545

Unless i am missing something really subtle, I don’t think this is required 
since SplittableRandom does not extend from Random (unlike in 
ThreadLocalRandom), and no associated reflective test is required.


ForkJoin
—

  69  * tasks that are never joined. All worker threads are initialized
  70  * with {@link Thread#isDaemon} set {@code true}.

CCC?


Thanks,
Paul.



> 
> 
> On Wed, Nov 16, 2016 at 3:34 PM, Paul Sandoz  wrote:
> Hi Martin,
> 
> Glad you looked more closely at the perf aspects of ArrayDeque.
> 
> I am struggling to determine what has changed since the last revision. Apart 
> from ArrayDeque what files should i be looking at?
> 
> Thanks,
> Paul.
> 
> > On 16 Nov 2016, at 12:14, Martin Buchholz  wrote:
> >
> > Thanks to Vitaly and Doug for being more concerned about offer/poll
> > performance than I was initially.  ArrayDeque is now back to using the head
> > + tail + spare slot strategy, which keeps optimal performance for non-bulk
> > operations, while everything else gets faster.  We have new tests and new
> > 

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Apologies for having this wave turn into a tsunami.

CopyOnWriteArrayList was rewritten due to finding
https://bugs.openjdk.java.net/browse/JDK-8169738
ArrayDeque and ArrayBlockingQueue now both use efficient nested loop idiom
for all traversals.
Most bulk remove methods in all collection classes were rewritten for
efficiency, using similar code.
Lots of tests and benchmarks added.


On Wed, Nov 16, 2016 at 3:34 PM, Paul Sandoz  wrote:

> Hi Martin,
>
> Glad you looked more closely at the perf aspects of ArrayDeque.
>
> I am struggling to determine what has changed since the last revision.
> Apart from ArrayDeque what files should i be looking at?
>
> Thanks,
> Paul.
>
> > On 16 Nov 2016, at 12:14, Martin Buchholz  wrote:
> >
> > Thanks to Vitaly and Doug for being more concerned about offer/poll
> > performance than I was initially.  ArrayDeque is now back to using the
> head
> > + tail + spare slot strategy, which keeps optimal performance for
> non-bulk
> > operations, while everything else gets faster.  We have new tests and new
> > benchmarks, as a result of which new bugs were found and fixed, and this
> > integration wave has grown rather larger than originally intended.
> >
> > The JIT-friendly nested loop strategy was successful for making bulk
> > operations on circular arrays faster, and this is used for both
> ArrayDeque
> > and ArrayBlockingQueue.
> >
> > +/*
> > + * VMs excel at optimizing simple array loops where indices are
> > + * incrementing or decrementing over a valid slice, e.g.
> > + *
> > + * for (int i = start; i < end; i++) ... elements[i]
> > + *
> > + * Because in a circular array, elements are in general stored in
> > + * two disjoint such slices, we help the VM by writing unusual
> > + * nested loops for all traversals over the elements.
> > + */
> >
> >
> > Bulk removal operations on array-based collections retreat to a two-pass
> > algorithm, which is slightly slower (but still O(n)), but continues to
> > support (questionable) predicates that reentrantly access the collection
> in
> > read mode.
> >
> > http://cr.openjdk.java.net/~martin/webrevs/openjdk9/
> jsr166-jdk9-integration/
> >
> > On Fri, Oct 21, 2016 at 12:32 PM, Martin Buchholz 
> > wrote:
> >
> >>
> >>
> >> On Tue, Oct 18, 2016 at 4:18 PM, Martin Buchholz 
> >> wrote:
> >>
> >>>
> >>>
> >>> On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich 
> >>> wrote:
> >>>
> 
> >> * Change in allocation/capacity policy.
> >>
> >> The removal of the power-of-two restriction, and applying a 1.5x
> > growth
> >> factor (same as ArrayList) seems sensible. Does this mean that the
> > ability
> >> to compute the proper array index by using x & (length-1) wasn't
> > worth it?
> >> Or at least not worth the extra tail wastage?
> >>
> >
> > There's no integer division to optimize, as with hash tables.
> 
>  But it does add some new branches, doesn't it? Potentially branches
> that
>  aren't taken prior to JIT compilation, but taken later = deopt.
> 
> >>>
> >>> If it's a smidgeon slower, I don't care that much; improvement in
> >>> flexibility and scalability are more important.
> >>>
> >>> Of course, I do care about algorithmic improvements to e.g. removeIf
> >>>
> >>>
>  Curious if you ran some benchmarks on ArrayDeque.
> 
> >>>
> >>> Not yet.  Who would like to show how slow the code is?
> >>>
> >>
> >> I revived my ancient IteratorMicroBenchmark for the latest webrev, made
> it
> >> a proper jtreg test, added ArrayDeque Jobs, and verified that the new
> code
> >> is measurably faster than the old code, at least for the mundane job of
> >> iterating.
> >> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/
> >> jsr166-jdk9-integration/ArrayList/
> >>
> >>
>
>

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

Hi Martin,

Glad you looked more closely at the perf aspects of ArrayDeque.

I am struggling to determine what has changed since the last revision. Apart 
from ArrayDeque what files should i be looking at?

Thanks,
Paul.

> On 16 Nov 2016, at 12:14, Martin Buchholz  wrote:
> 
> Thanks to Vitaly and Doug for being more concerned about offer/poll
> performance than I was initially.  ArrayDeque is now back to using the head
> + tail + spare slot strategy, which keeps optimal performance for non-bulk
> operations, while everything else gets faster.  We have new tests and new
> benchmarks, as a result of which new bugs were found and fixed, and this
> integration wave has grown rather larger than originally intended.
> 
> The JIT-friendly nested loop strategy was successful for making bulk
> operations on circular arrays faster, and this is used for both ArrayDeque
> and ArrayBlockingQueue.
> 
> +/*
> + * VMs excel at optimizing simple array loops where indices are
> + * incrementing or decrementing over a valid slice, e.g.
> + *
> + * for (int i = start; i < end; i++) ... elements[i]
> + *
> + * Because in a circular array, elements are in general stored in
> + * two disjoint such slices, we help the VM by writing unusual
> + * nested loops for all traversals over the elements.
> + */
> 
> 
> Bulk removal operations on array-based collections retreat to a two-pass
> algorithm, which is slightly slower (but still O(n)), but continues to
> support (questionable) predicates that reentrantly access the collection in
> read mode.
> 
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/
> 
> On Fri, Oct 21, 2016 at 12:32 PM, Martin Buchholz 
> wrote:
> 
>> 
>> 
>> On Tue, Oct 18, 2016 at 4:18 PM, Martin Buchholz 
>> wrote:
>> 
>>> 
>>> 
>>> On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich 
>>> wrote:
>>> 
 
>> * Change in allocation/capacity policy.
>> 
>> The removal of the power-of-two restriction, and applying a 1.5x
> growth
>> factor (same as ArrayList) seems sensible. Does this mean that the
> ability
>> to compute the proper array index by using x & (length-1) wasn't
> worth it?
>> Or at least not worth the extra tail wastage?
>> 
> 
> There's no integer division to optimize, as with hash tables.
 
 But it does add some new branches, doesn't it? Potentially branches that
 aren't taken prior to JIT compilation, but taken later = deopt.
 
>>> 
>>> If it's a smidgeon slower, I don't care that much; improvement in
>>> flexibility and scalability are more important.
>>> 
>>> Of course, I do care about algorithmic improvements to e.g. removeIf
>>> 
>>> 
 Curious if you ran some benchmarks on ArrayDeque.
 
>>> 
>>> Not yet.  Who would like to show how slow the code is?
>>> 
>> 
>> I revived my ancient IteratorMicroBenchmark for the latest webrev, made it
>> a proper jtreg test, added ArrayDeque Jobs, and verified that the new code
>> is measurably faster than the old code, at least for the mundane job of
>> iterating.
>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/
>> jsr166-jdk9-integration/ArrayList/
>> 
>> 

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Thanks to Vitaly and Doug for being more concerned about offer/poll
performance than I was initially.  ArrayDeque is now back to using the head
+ tail + spare slot strategy, which keeps optimal performance for non-bulk
operations, while everything else gets faster.  We have new tests and new
benchmarks, as a result of which new bugs were found and fixed, and this
integration wave has grown rather larger than originally intended.

The JIT-friendly nested loop strategy was successful for making bulk
operations on circular arrays faster, and this is used for both ArrayDeque
and ArrayBlockingQueue.

+/*
+ * VMs excel at optimizing simple array loops where indices are
+ * incrementing or decrementing over a valid slice, e.g.
+ *
+ * for (int i = start; i < end; i++) ... elements[i]
+ *
+ * Because in a circular array, elements are in general stored in
+ * two disjoint such slices, we help the VM by writing unusual
+ * nested loops for all traversals over the elements.
+ */


Bulk removal operations on array-based collections retreat to a two-pass
algorithm, which is slightly slower (but still O(n)), but continues to
support (questionable) predicates that reentrantly access the collection in
read mode.

http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/

On Fri, Oct 21, 2016 at 12:32 PM, Martin Buchholz 
wrote:

>
>
> On Tue, Oct 18, 2016 at 4:18 PM, Martin Buchholz 
> wrote:
>
>>
>>
>> On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich 
>> wrote:
>>
>>>
 > * Change in allocation/capacity policy.
 >
 > The removal of the power-of-two restriction, and applying a 1.5x
 growth
 > factor (same as ArrayList) seems sensible. Does this mean that the
 ability
 > to compute the proper array index by using x & (length-1) wasn't
 worth it?
 > Or at least not worth the extra tail wastage?
 >

 There's no integer division to optimize, as with hash tables.
>>>
>>> But it does add some new branches, doesn't it? Potentially branches that
>>> aren't taken prior to JIT compilation, but taken later = deopt.
>>>
>>
>> If it's a smidgeon slower, I don't care that much; improvement in
>> flexibility and scalability are more important.
>>
>> Of course, I do care about algorithmic improvements to e.g. removeIf
>>
>>
>>> Curious if you ran some benchmarks on ArrayDeque.
>>>
>>
>> Not yet.  Who would like to show how slow the code is?
>>
>
> I revived my ancient IteratorMicroBenchmark for the latest webrev, made it
> a proper jtreg test, added ArrayDeque Jobs, and verified that the new code
> is measurably faster than the old code, at least for the mundane job of
> iterating.
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/
> jsr166-jdk9-integration/ArrayList/
>
>

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Tue, Oct 18, 2016 at 4:18 PM, Martin Buchholz 
wrote:

>
>
> On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich 
> wrote:
>
>>
>>> > * Change in allocation/capacity policy.
>>> >
>>> > The removal of the power-of-two restriction, and applying a 1.5x growth
>>> > factor (same as ArrayList) seems sensible. Does this mean that the
>>> ability
>>> > to compute the proper array index by using x & (length-1) wasn't worth
>>> it?
>>> > Or at least not worth the extra tail wastage?
>>> >
>>>
>>> There's no integer division to optimize, as with hash tables.
>>
>> But it does add some new branches, doesn't it? Potentially branches that
>> aren't taken prior to JIT compilation, but taken later = deopt.
>>
>
> If it's a smidgeon slower, I don't care that much; improvement in
> flexibility and scalability are more important.
>
> Of course, I do care about algorithmic improvements to e.g. removeIf
>
>
>> Curious if you ran some benchmarks on ArrayDeque.
>>
>
> Not yet.  Who would like to show how slow the code is?
>

I revived my ancient IteratorMicroBenchmark for the latest webrev, made it
a proper jtreg test, added ArrayDeque Jobs, and verified that the new code
is measurably faster than the old code, at least for the mundane job of
iterating.
http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/ArrayList/

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 19 Oct 2016, at 19:33, Martin Buchholz  wrote:
> 
> 
> 
> On Wed, Oct 19, 2016 at 3:44 PM, Paul Sandoz  > wrote:
> 
>> On 18 Oct 2016, at 13:58, Martin Buchholz > > wrote:
>> 
>> Latest webrev defers potential new methods:
>>/* TODO: public */ private void trimToSize()
> 
> Sorry to push back, i know it’s a hassle, but i think such features should be 
> retained in a separate proposed patch.
> 
> OK.  These methods can still be found in jsr166 CVS, but are now filtered out 
> during upstreaming.


Thanks for being flexible. Looks good to me (i did not look in detail at the 
impl improvements on ArrayDeque, i think Stuart has that one amply covered).

Paul.

Re: RFR: jsr166 jdk9 integration wave 12

[Jonathan Bluett-Duncan]

Ah, I see. Thanks for answering my questions Martin.

Sounds like there's no real benefit then to using guava-testlib in this
changeset instead of CollectionTest. And even if the benefit of using it
was considered to be high enough in the future, it would probably need its
own JSR, since I presume it would be applicable to a number of places in
the jdk, making it a humongous change.

Overall, it seems sensible to wait until e.g. JUnit 5 develops a worthwhile
solution to the dynamic test generation problem, at which point we could
then consider it for writing exhaustive tests for the jdk collections.

Thanks again,
Jonathan


On 20 October 2016 at 04:45, Martin Buchholz  wrote:

>
>
> On Wed, Oct 19, 2016 at 4:40 PM, Jonathan Bluett-Duncan <
> jbluettdun...@gmail.com> wrote:
>
>> Hi Martin,
>>
>> By collections infrastructure, do you mean something like the collection
>> testers in guava-testlib?
>>
>> If so, I agree that JUnit 5's dynamic tests look promising for
>> implementing such an infrastructure. I admit I don't have all the context
>> here, but would using guava-testlib in the meantime be a viable medium- or
>> short-term solution? Or would its dependence on JUnit 3/4 make switching
>> impractical? Or, perhaps, has development into CollectionTest gone so far
>> that, for that reason instead, it would be impractical until switch, at
>> least until something superior using e.g. JUnit 5's dynamic tests is made?
>>
>
> I'm embarrassed to say I'm not familiar enough with guava's testlib.
> Guava does have generic collection oriented tests, and even runs them on
> jdk classes. (Someone on the jdk quality team should be running the guava
> tests using development jdks!).  I'm not familiar enough with the tools to
> work on this myself, but I encourage someone who is to do that.
>
> I see that guava testlib does have:
>
> TestsForQueuesInJavaUtil.java
> TestsForSetsInJavaUtil.java
> TestsForListsInJavaUtil.java
> TestsForMapsInJavaUtil.java
>
> and that the infrastructure there is vaguely similar to what I ended up
> doing.  JDK version skew is a problem, because openjdk development is
> focused on jdk9, while guava is still trying to digest jdk8.
>

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Wed, Oct 19, 2016 at 4:40 PM, Jonathan Bluett-Duncan <
jbluettdun...@gmail.com> wrote:

> Hi Martin,
>
> By collections infrastructure, do you mean something like the collection
> testers in guava-testlib?
>
> If so, I agree that JUnit 5's dynamic tests look promising for
> implementing such an infrastructure. I admit I don't have all the context
> here, but would using guava-testlib in the meantime be a viable medium- or
> short-term solution? Or would its dependence on JUnit 3/4 make switching
> impractical? Or, perhaps, has development into CollectionTest gone so far
> that, for that reason instead, it would be impractical until switch, at
> least until something superior using e.g. JUnit 5's dynamic tests is made?
>

I'm embarrassed to say I'm not familiar enough with guava's testlib.  Guava
does have generic collection oriented tests, and even runs them on jdk
classes. (Someone on the jdk quality team should be running the guava tests
using development jdks!).  I'm not familiar enough with the tools to work
on this myself, but I encourage someone who is to do that.

I see that guava testlib does have:

TestsForQueuesInJavaUtil.java
TestsForSetsInJavaUtil.java
TestsForListsInJavaUtil.java
TestsForMapsInJavaUtil.java

and that the infrastructure there is vaguely similar to what I ended up
doing.  JDK version skew is a problem, because openjdk development is
focused on jdk9, while guava is still trying to digest jdk8.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Wed, Oct 19, 2016 at 3:44 PM, Paul Sandoz  wrote:

>
> On 18 Oct 2016, at 13:58, Martin Buchholz  wrote:
>
> Latest webrev defers potential new methods:
>
>/* TODO: public */ private void trimToSize()
>
> Sorry to push back, i know it’s a hassle, but i think such features should
> be retained in a separate proposed patch.
>

OK.  These methods can still be found in jsr166 CVS, but are now filtered
out during upstreaming.

Re: RFR: jsr166 jdk9 integration wave 12

[Jonathan Bluett-Duncan]

Hi Martin,

By collections infrastructure, do you mean something like the collection
testers in guava-testlib?

If so, I agree that JUnit 5's dynamic tests look promising for implementing
such an infrastructure. I admit I don't have all the context here, but
would using guava-testlib in the meantime be a viable medium- or short-term
solution? Or would its dependence on JUnit 3/4 make switching impractical?
Or, perhaps, has development into CollectionTest gone so far that, for that
reason instead, it would be impractical until switch, at least until
something superior using e.g. JUnit 5's dynamic tests is made?

Kind regards,
Jonathan

On 19 October 2016 at 23:21, Martin Buchholz  wrote:

> These tests are maintained outside of openjdk and have only recently been
> made available within openjdk.
>
> There may be a future where all the consumers of these tests are willing to
> accept a good test framework.  Junit 5 dynamic tests look promising
> http://junit.org/junit5/docs/current/user-guide/#writing-
> tests-dynamic-tests
> but it may be a decade before we can use it.
>
> Probably code bases that include interfaces (e.g. Collection) should
> provide infrastructure to test those interfaces for any implementation, but
> openjdk does not try to do so.  CollectionTest is an experimental step in
> that direction, but it looks we could do better with Junit 5 some day.  The
> openjdk and jtreg projects can try to help by supporting junit 5 earlier
> rather than later.
>
> On Wed, Oct 19, 2016 at 12:19 PM, Stuart Marks 
> wrote:
>
> >
> >
> > On 10/18/16 11:00 AM, Martin Buchholz wrote:
> >
> >> There's already a certain amount of mixing, e.g. stream tests sometimes
> >> test
> >> j.u.c. and Queue tests sometimes test all the Queue implementations.
> >> Unlike
> >> non-test code, some redundancy and divergence of testing frameworks and
> >> styles
> >> is fine.  I still haven't found a way of writing shared tests for
> >> implementations of an interface that I really like.
> >>
> >
> > It's probably the case that divergence of testing frameworks is
> > unavoidable, or at least it's impractical. I doubt that it's worthwhile
> to
> > rewrite all the straight jtreg tests into TestNG, or JUnit, or whatever.
> > But I'd draw the line before saying this is "fine." [1]
> >
> > Maintaining the tests' organization is pretty important. Most of the
> > collections tests are in jdk/test/java/util though they're spread around
> a
> > bit uncomfortably even here. But now it's, oh, ArrayDeque and
> > ArrayList.removeIf tests are over *here* instead. Having things spread
> > around increases the likelihood of cases being missed or being tested
> > redundantly.
> >
> > The test groups have to be maintained as well. I know I've been bitten by
> > problems (not in collections) where I *thought* I had run the right set
> of
> > tests, but it ended up that I hadn't, resulting in me breaking the build.
> > As it turns out, jdk_collections_core doesn't include any ArrayDeque
> tests.
> > Hmmm. Well, maybe jdk_collections_core isn't useful. It would have been
> > nice to know this when I added it last year. :-/ [2]
> >
> > As things stand, I'm basically OK with this changeset going in. But it
> > does seem to highlight some areas that need some future cleanup,
> > particularly in the tests and the test group declarations.
> >
> > s'marks
> >
> > [1] http://knowyourmeme.com/memes/this-is-fine
> >
> > [2] http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/7a0c06013ae6
> >
> >
>

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 18 Oct 2016, at 13:58, Martin Buchholz  wrote:
> 
> Latest webrev defers potential new methods:
>/* TODO: public */ private void trimToSize()

Sorry to push back, i know it’s a hassle, but i think such features should be 
retained in a separate proposed patch.

Paul.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

These tests are maintained outside of openjdk and have only recently been
made available within openjdk.

There may be a future where all the consumers of these tests are willing to
accept a good test framework.  Junit 5 dynamic tests look promising
http://junit.org/junit5/docs/current/user-guide/#writing-tests-dynamic-tests
but it may be a decade before we can use it.

Probably code bases that include interfaces (e.g. Collection) should
provide infrastructure to test those interfaces for any implementation, but
openjdk does not try to do so.  CollectionTest is an experimental step in
that direction, but it looks we could do better with Junit 5 some day.  The
openjdk and jtreg projects can try to help by supporting junit 5 earlier
rather than later.

On Wed, Oct 19, 2016 at 12:19 PM, Stuart Marks 
wrote:

>
>
> On 10/18/16 11:00 AM, Martin Buchholz wrote:
>
>> There's already a certain amount of mixing, e.g. stream tests sometimes
>> test
>> j.u.c. and Queue tests sometimes test all the Queue implementations.
>> Unlike
>> non-test code, some redundancy and divergence of testing frameworks and
>> styles
>> is fine.  I still haven't found a way of writing shared tests for
>> implementations of an interface that I really like.
>>
>
> It's probably the case that divergence of testing frameworks is
> unavoidable, or at least it's impractical. I doubt that it's worthwhile to
> rewrite all the straight jtreg tests into TestNG, or JUnit, or whatever.
> But I'd draw the line before saying this is "fine." [1]
>
> Maintaining the tests' organization is pretty important. Most of the
> collections tests are in jdk/test/java/util though they're spread around a
> bit uncomfortably even here. But now it's, oh, ArrayDeque and
> ArrayList.removeIf tests are over *here* instead. Having things spread
> around increases the likelihood of cases being missed or being tested
> redundantly.
>
> The test groups have to be maintained as well. I know I've been bitten by
> problems (not in collections) where I *thought* I had run the right set of
> tests, but it ended up that I hadn't, resulting in me breaking the build.
> As it turns out, jdk_collections_core doesn't include any ArrayDeque tests.
> Hmmm. Well, maybe jdk_collections_core isn't useful. It would have been
> nice to know this when I added it last year. :-/ [2]
>
> As things stand, I'm basically OK with this changeset going in. But it
> does seem to highlight some areas that need some future cleanup,
> particularly in the tests and the test group declarations.
>
> s'marks
>
> [1] http://knowyourmeme.com/memes/this-is-fine
>
> [2] http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/7a0c06013ae6
>
>

Re: RFR: jsr166 jdk9 integration wave 12

[Stuart Marks]

On 10/18/16 11:00 AM, Martin Buchholz wrote:

There's already a certain amount of mixing, e.g. stream tests sometimes test
j.u.c. and Queue tests sometimes test all the Queue implementations. Unlike
non-test code, some redundancy and divergence of testing frameworks and styles
is fine.  I still haven't found a way of writing shared tests for
implementations of an interface that I really like.


It's probably the case that divergence of testing frameworks is unavoidable, or 
at least it's impractical. I doubt that it's worthwhile to rewrite all the 
straight jtreg tests into TestNG, or JUnit, or whatever. But I'd draw the line 
before saying this is "fine." [1]


Maintaining the tests' organization is pretty important. Most of the collections 
tests are in jdk/test/java/util though they're spread around a bit uncomfortably 
even here. But now it's, oh, ArrayDeque and ArrayList.removeIf tests are over 
*here* instead. Having things spread around increases the likelihood of cases 
being missed or being tested redundantly.


The test groups have to be maintained as well. I know I've been bitten by 
problems (not in collections) where I *thought* I had run the right set of 
tests, but it ended up that I hadn't, resulting in me breaking the build. As it 
turns out, jdk_collections_core doesn't include any ArrayDeque tests. Hmmm. 
Well, maybe jdk_collections_core isn't useful. It would have been nice to know 
this when I added it last year. :-/ [2]


As things stand, I'm basically OK with this changeset going in. But it does seem 
to highlight some areas that need some future cleanup, particularly in the tests 
and the test group declarations.


s'marks

[1] http://knowyourmeme.com/memes/this-is-fine

[2] http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/7a0c06013ae6

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Tue, Oct 18, 2016 at 6:33 PM, Vitaly Davidovich 
wrote:

>
> Indeed - the whole inlining based on simple bytecode size is a big problem
> (I've brought this up in various contexts several times on the compiler
> list, but this is a known issue).  But, some of the methods using the jsr
> style look to already be >35 bytes.  I've seen this style in other places
> in the JDK where the method is definitely above 35.
>

- 35 is not a universal physical constant!
- maybe the same style is used in a similar method where it did cross the
35 byte threshold
- elsewhere in jsr166 we deal with concurrency, where copying fields into
locals is a good reflex for correctness

Re: RFR: jsr166 jdk9 integration wave 12

[Vitaly Davidovich]

On Tuesday, October 18, 2016, Martin Buchholz  wrote:

>
>
> On Tue, Oct 18, 2016 at 4:26 PM, Vitaly Davidovich  > wrote:
>
>> "jsr166 style" - makes it easy on javac and the JIT, if not for humans.
>>>
>> In some of the cases here, I'd consider it a significant JIT failure if
>> the "jsr166 style" makes a difference (I'm not sure how this makes a
>> difference to javac - did you mean interpreter?).  Is this jsr style a
>> carryover from long ago? Maybe it needs to be reconsidered.  The code
>> clarity isn't terrible, but it would be unfortunate to do this in simple
>> cases where the compiler ought to handle it just fine - does it not?
>>
>
> I consider it a significant failure that
>
>1. JDK-6445664 
>
> Eliminate remaining performance penalty for using assert
>
> still hasn't been fixed.
>
Indeed - the whole inlining based on simple bytecode size is a big problem
(I've brought this up in various contexts several times on the compiler
list, but this is a known issue).  But, some of the methods using the jsr
style look to already be >35 bytes.  I've seen this style in other places
in the JDK where the method is definitely above 35.  My thinking was this
must be some manual attempt to force the compiler to put the value in a
register or stack slot, for fear that it wouldn't do it on its own because
it can't prove it's safe, rather than inlining.

Anyway, the style is odd, perhaps outdated to some degree, but not that big
of a deal in the grand scheme of things (IMO).

I mostly wanted to know of impact on ArrayDeque performance due to the code
restructuring.


-- 
Sent from my phone

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Tue, Oct 18, 2016 at 4:26 PM, Vitaly Davidovich 
wrote:

> "jsr166 style" - makes it easy on javac and the JIT, if not for humans.
>>
> In some of the cases here, I'd consider it a significant JIT failure if
> the "jsr166 style" makes a difference (I'm not sure how this makes a
> difference to javac - did you mean interpreter?).  Is this jsr style a
> carryover from long ago? Maybe it needs to be reconsidered.  The code
> clarity isn't terrible, but it would be unfortunate to do this in simple
> cases where the compiler ought to handle it just fine - does it not?
>

I consider it a significant failure that

   1. JDK-6445664 

Eliminate remaining performance penalty for using assert

still hasn't been fixed.

Re: RFR: jsr166 jdk9 integration wave 12

[Vitaly Davidovich]

On Tuesday, October 18, 2016, Martin Buchholz  wrote:

>
>
> On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich  > wrote:
>
>>
>>> > * Change in allocation/capacity policy.
>>> >
>>> > The removal of the power-of-two restriction, and applying a 1.5x growth
>>> > factor (same as ArrayList) seems sensible. Does this mean that the
>>> ability
>>> > to compute the proper array index by using x & (length-1) wasn't worth
>>> it?
>>> > Or at least not worth the extra tail wastage?
>>> >
>>>
>>> There's no integer division to optimize, as with hash tables.
>>
>> But it does add some new branches, doesn't it? Potentially branches that
>> aren't taken prior to JIT compilation, but taken later = deopt.
>>
>
> If it's a smidgeon slower, I don't care that much; improvement in
> flexibility and scalability are more important.
>
Well, others may :).  I'm not saying it's slower, I don't know, but you're
dismissing that possibility a bit too quickly, methinks.

>
> Of course, I do care about algorithmic improvements to e.g. removeIf
>
Sure, no debate.

>
>
>> Curious if you ran some benchmarks on ArrayDeque.
>>
>
> Not yet.  Who would like to show how slow the code is?
>
>
>> Also, some odd stylistic things, such as:
>>
>> while (s == (capacity = (elements = this.elements).length))
>>
>> Is this an attempt to help the JIT or something?
>>
>> "jsr166 style" - makes it easy on javac and the JIT, if not for humans.
>
In some of the cases here, I'd consider it a significant JIT failure if the
"jsr166 style" makes a difference (I'm not sure how this makes a difference
to javac - did you mean interpreter?).  Is this jsr style a carryover from
long ago? Maybe it needs to be reconsidered.  The code clarity isn't
terrible, but it would be unfortunate to do this in simple cases where the
compiler ought to handle it just fine - does it not?


-- 
Sent from my phone

Re: RFR: jsr166 jdk9 integration wave 12

[Vitaly Davidovich]

On Tuesday, October 18, 2016, Martin Buchholz  wrote:

> On Tue, Oct 18, 2016 at 10:15 AM, Stuart Marks  >
> wrote:
>
> >
> >
> > On 10/17/16 6:34 PM, Martin Buchholz wrote:
> >
> >> Most of this is for Stuart - very collection-y.
> >>
> >> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-
> >> jdk9-integration/
> >>
> >> This includes a rewrite of ArrayDeque to bring it to parity with
> ArrayList
> >> (except for List features).
> >> The patch includes public methods ensureCapacity, trimToSize, replaceAll
> >> as in
> >> ArrayList, but we can defer making them public to a later change (or a
> >> later
> >> release), since new public methods are always controversial.  But I'd
> >> really
> >> like to get the performance/scalability changes in for jdk 9.
> >>
> >> It also includes a redo of ArrayList#removeIf to make it more efficient
> >> and
> >> consistent with behavior of other implementations, including ArrayDeque.
> >>
> >> The patches are a little tangled because they step on each other's toes.
> >> File
> >> CollectionTest is in "miscellaneous", but it tests both the ArrayDeque
> and
> >> ArrayList changes.
> >>
> >
> > Hi Martin,
> >
> > ArrayList.removeIf() is nice. I like the way it recovers from the
> > predicate having thrown an exception. I note that it uselessly copies the
> > tail of the array to itself, if the predicate throws an exception and
> > nothing has been deleted yet. You could add a r != w check, or possibly
> > deleted > 0 if you prefer, or maybe we don't care because this is a rare
> > (we hope) error recovery case.
> >
> >
> I had the same thoughts... I added checks for deleted > 0
>
>
> > ***
> >
> > I have some comments on ArrayDeque:
> >
> > * Change in allocation/capacity policy.
> >
> > The removal of the power-of-two restriction, and applying a 1.5x growth
> > factor (same as ArrayList) seems sensible. Does this mean that the
> ability
> > to compute the proper array index by using x & (length-1) wasn't worth
> it?
> > Or at least not worth the extra tail wastage?
> >
>
> There's no integer division to optimize, as with hash tables.

But it does add some new branches, doesn't it? Potentially branches that
aren't taken prior to JIT compilation, but taken later = deopt.

Curious if you ran some benchmarks on ArrayDeque.

Also, some odd stylistic things, such as:

while (s == (capacity = (elements = this.elements).length))

Is this an attempt to help the JIT or something?


> It was the horror of user discovering that ArrayDeque(2^n) allocated
> 2^(n+1) that persuaded me to go down this road.
> It's also very useful to allocate exactly the requested size on
> ArrayDeque(m) or be precise with trimToSize or allow growth up to (almost)
> Integer.MAX_VALUE.
> A circular buffer is a very simple data structure - our implementation
> should be a model!
>
>
> > (Potential future enhancement: allocate the array lazily, like ArrayList)
> >
> > Note, I haven't digested all the changes yet.
> >
> > * API additions
> >
> > I'm somewhat undecided about these.
> >
> > I've always felt that the ensureCapacity() and trimToSize() methods were
> a
> > sop added to ArrayList aimed at people converting from Vector. The
> > ArrayList.ensureCapacity() method seems to be used a lot, but probably
> not
> > to great effect, since addAll() gives exact sizing anyway. The
> trimToSize()
> > method could be useful in some cases, but should we hold out for a
> > generalized one, as requested by JDK-4619094?
> >
>
> ensureCapacity is the least useful - just saving less than a factor of 2
> allocation on growth.  trimToSize seems more important, since it saves
> memory "permanently".
>
>
> > On the other hand, ArrayDeque is modeling an array, so providing some
> size
> > control seems mostly harmless.
> >
> > The replaceAll() method is a bit oddly placed here. It's a default method
> > on List (which ArrayDeque doesn't, and can't implement) so it's a bit
> > strange to have a special method here with the same name and semantics as
> > the one on List, but with a "fork" of the specification.
> >
> >
> yeah, it's adding a List method even though the mega-feature of List view
> is deferred.
>
>
> > Maybe if JDK-8143850 is implemented to give a list view of an ArrayDeque,
> > the replaceAll() method could be implemented on that:
> >
> > arrayDeque.asList().replaceAll(clazz::method);
> >
>
> yeah, the idea might be that we add List methods like get(i) and replaceAll
> directly on ArrayDeque, but only when you call asList do you get something
> that implements List ... which is ... odd.
>
>
> ***
> >
> > I'm not sure what to think of the arrangement of the tests. The "core"
> > collections, that is, collections in java.util, exclusive of
> > java.util.concurrent, are mostly tested by tests in jdk/test/java/util.
> > This patch adds tests for ArrayList and ArrayDeque inside of
> > jdk/test/java/util/concurrent/tck. There's a test group
> > 

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

Latest webrev defers potential new methods:

   /* TODO: public */ private void trimToSize()

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

> On 18 Oct 2016, at 12:07, Martin Buchholz  wrote:
> 
> 
> 
> On Tue, Oct 18, 2016 at 10:55 AM, Paul Sandoz  wrote:
> 
> Testing-wise there is always gonna be some overlap. It would be nice to 
> consolidate, although arguably in principle TCK has a slightly different 
> focus. Now that the tck is in the OpenJDK repo perhaps we should add that to 
> the jdk_collections_core?
> 

Ah, i see they are already implicitly included under the jdk_concurrent group.

# All collections, core and concurrent
jdk_collections = \
:jdk_collections_core \
:jdk_concurrent

# java.util.concurrent
# Includes concurrent collections plus other stuff
# Maintained by JSR-166 EG (Doug Lea et al)
jdk_concurrent = \
java/util/concurrent

Hmm… not sure i have a strong opinion here regarding the removal of the core 
group. I think the comment should be updated to state tck tests are included.


> I don't think the distinction between  jdk_collections_core and 
> jdk_collections is useful.  Too many tests test both kinds of collections, 
> and there's  inheritance.  Just get rid of jdk_collections_core, and add:
> 
> test/java/util/Spliterator

Yes, that’s useful to add to the collection group.


> test/java/util/stream/test/org/openjdk/tests/java/util/stream/CollectorsTest.java

The above tests j.u.s.Collector implementations rather than collections 
themselves (even thought it produces collections), so i think it should not be 
added.


> test/java/util/stream/test/org/openjdk/tests/java/util/stream/CollectionAndMapModifyStreamTest.java

Ok.

Paul.

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Tue, Oct 18, 2016 at 10:55 AM, Paul Sandoz 
wrote:

>
> Testing-wise there is always gonna be some overlap. It would be nice to
> consolidate, although arguably in principle TCK has a slightly different
> focus. Now that the tck is in the OpenJDK repo perhaps we should add that
> to the jdk_collections_core?
>

I don't think the distinction between  jdk_collections_core and
jdk_collections is useful.  Too many tests test both kinds of collections,
and there's  inheritance.  Just get rid of jdk_collections_core, and add:

test/java/util/Spliterator
test/java/util/stream/test/org/openjdk/tests/java/util/stream/CollectorsTest.java
test/java/util/stream/test/org/openjdk/tests/java/util/stream/CollectionAndMapModifyStreamTest.java

Re: RFR: jsr166 jdk9 integration wave 12

[Martin Buchholz]

On Tue, Oct 18, 2016 at 10:15 AM, Stuart Marks 
wrote:

>
>
> On 10/17/16 6:34 PM, Martin Buchholz wrote:
>
>> Most of this is for Stuart - very collection-y.
>>
>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-
>> jdk9-integration/
>>
>> This includes a rewrite of ArrayDeque to bring it to parity with ArrayList
>> (except for List features).
>> The patch includes public methods ensureCapacity, trimToSize, replaceAll
>> as in
>> ArrayList, but we can defer making them public to a later change (or a
>> later
>> release), since new public methods are always controversial.  But I'd
>> really
>> like to get the performance/scalability changes in for jdk 9.
>>
>> It also includes a redo of ArrayList#removeIf to make it more efficient
>> and
>> consistent with behavior of other implementations, including ArrayDeque.
>>
>> The patches are a little tangled because they step on each other's toes.
>> File
>> CollectionTest is in "miscellaneous", but it tests both the ArrayDeque and
>> ArrayList changes.
>>
>
> Hi Martin,
>
> ArrayList.removeIf() is nice. I like the way it recovers from the
> predicate having thrown an exception. I note that it uselessly copies the
> tail of the array to itself, if the predicate throws an exception and
> nothing has been deleted yet. You could add a r != w check, or possibly
> deleted > 0 if you prefer, or maybe we don't care because this is a rare
> (we hope) error recovery case.
>
>
I had the same thoughts... I added checks for deleted > 0


> ***
>
> I have some comments on ArrayDeque:
>
> * Change in allocation/capacity policy.
>
> The removal of the power-of-two restriction, and applying a 1.5x growth
> factor (same as ArrayList) seems sensible. Does this mean that the ability
> to compute the proper array index by using x & (length-1) wasn't worth it?
> Or at least not worth the extra tail wastage?
>

There's no integer division to optimize, as with hash tables.

It was the horror of user discovering that ArrayDeque(2^n) allocated
2^(n+1) that persuaded me to go down this road.
It's also very useful to allocate exactly the requested size on
ArrayDeque(m) or be precise with trimToSize or allow growth up to (almost)
Integer.MAX_VALUE.
A circular buffer is a very simple data structure - our implementation
should be a model!


> (Potential future enhancement: allocate the array lazily, like ArrayList)
>
> Note, I haven't digested all the changes yet.
>
> * API additions
>
> I'm somewhat undecided about these.
>
> I've always felt that the ensureCapacity() and trimToSize() methods were a
> sop added to ArrayList aimed at people converting from Vector. The
> ArrayList.ensureCapacity() method seems to be used a lot, but probably not
> to great effect, since addAll() gives exact sizing anyway. The trimToSize()
> method could be useful in some cases, but should we hold out for a
> generalized one, as requested by JDK-4619094?
>

ensureCapacity is the least useful - just saving less than a factor of 2
allocation on growth.  trimToSize seems more important, since it saves
memory "permanently".


> On the other hand, ArrayDeque is modeling an array, so providing some size
> control seems mostly harmless.
>
> The replaceAll() method is a bit oddly placed here. It's a default method
> on List (which ArrayDeque doesn't, and can't implement) so it's a bit
> strange to have a special method here with the same name and semantics as
> the one on List, but with a "fork" of the specification.
>
>
yeah, it's adding a List method even though the mega-feature of List view
is deferred.


> Maybe if JDK-8143850 is implemented to give a list view of an ArrayDeque,
> the replaceAll() method could be implemented on that:
>
> arrayDeque.asList().replaceAll(clazz::method);
>

yeah, the idea might be that we add List methods like get(i) and replaceAll
directly on ArrayDeque, but only when you call asList do you get something
that implements List ... which is ... odd.


***
>
> I'm not sure what to think of the arrangement of the tests. The "core"
> collections, that is, collections in java.util, exclusive of
> java.util.concurrent, are mostly tested by tests in jdk/test/java/util.
> This patch adds tests for ArrayList and ArrayDeque inside of
> jdk/test/java/util/concurrent/tck. There's a test group
> jdk_collections_core that's intended to test the core collections, so it'll
> miss the new tests being added here.
>
> I'm not sure what to suggest. The new tests use the JSR166TestCase
> framework, which is probably useful, and probably can't be used if the
> tests are moved elsewhere. I don't know what it would take to convert this
> to jtreg or testng. Or, the core test group could be modified to run
> selected JSR166 test cases, which doesn't seem quite right either.
> Suggestions?
>
>
There's already a certain amount of mixing, e.g. stream tests sometimes
test j.u.c. and Queue tests sometimes test all the Queue implementations.
Unlike non-test code, some redundancy 

Re: RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

Hi,

The j.u.c. changes look ok to me as do the misc changes.

The ArrayDeque changes may also change the performance characteristics, a 
space/time trade-off e.g. in current version array bounds checks are strength 
reduced to a zero-based test of the array length. Unsure in practice if this 
really matters.

At this stage in Java 9 i would be inclined not to make ArrayDeque more 
ArrayList-like with new public methods ensureCapacity/trimToSize/replaceAll. Do 
you mind if we hold off an that for now and think more about that?

Testing-wise there is always gonna be some overlap. It would be nice to 
consolidate, although arguably in principle TCK has a slightly different focus. 
Now that the tck is in the OpenJDK repo perhaps we should add that to the 
jdk_collections_core?

Paul.

> On 18 Oct 2016, at 10:15, Stuart Marks  wrote:
> 
> 
> 
> On 10/17/16 6:34 PM, Martin Buchholz wrote:
>> Most of this is for Stuart - very collection-y.
>> 
>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/
>> 
>> This includes a rewrite of ArrayDeque to bring it to parity with ArrayList
>> (except for List features).
>> The patch includes public methods ensureCapacity, trimToSize, replaceAll as 
>> in
>> ArrayList, but we can defer making them public to a later change (or a later
>> release), since new public methods are always controversial.  But I'd really
>> like to get the performance/scalability changes in for jdk 9.
>> 
>> It also includes a redo of ArrayList#removeIf to make it more efficient and
>> consistent with behavior of other implementations, including ArrayDeque.
>> 
>> The patches are a little tangled because they step on each other's toes.  
>> File
>> CollectionTest is in "miscellaneous", but it tests both the ArrayDeque and
>> ArrayList changes.
> 
> Hi Martin,
> 
> ArrayList.removeIf() is nice. I like the way it recovers from the predicate 
> having thrown an exception. I note that it uselessly copies the tail of the 
> array to itself, if the predicate throws an exception and nothing has been 
> deleted yet. You could add a r != w check, or possibly deleted > 0 if you 
> prefer, or maybe we don't care because this is a rare (we hope) error 
> recovery case.
> 
> ***
> 
> I have some comments on ArrayDeque:
> 
> * Change in allocation/capacity policy.
> 
> The removal of the power-of-two restriction, and applying a 1.5x growth 
> factor (same as ArrayList) seems sensible. Does this mean that the ability to 
> compute the proper array index by using x & (length-1) wasn't worth it? Or at 
> least not worth the extra tail wastage?
> 
> (Potential future enhancement: allocate the array lazily, like ArrayList)
> 
> Note, I haven't digested all the changes yet.
> 
> * API additions
> 
> I'm somewhat undecided about these.
> 
> I've always felt that the ensureCapacity() and trimToSize() methods were a 
> sop added to ArrayList aimed at people converting from Vector. The 
> ArrayList.ensureCapacity() method seems to be used a lot, but probably not to 
> great effect, since addAll() gives exact sizing anyway. The trimToSize() 
> method could be useful in some cases, but should we hold out for a 
> generalized one, as requested by JDK-4619094?
> 
> On the other hand, ArrayDeque is modeling an array, so providing some size 
> control seems mostly harmless.
> 
> The replaceAll() method is a bit oddly placed here. It's a default method on 
> List (which ArrayDeque doesn't, and can't implement) so it's a bit strange to 
> have a special method here with the same name and semantics as the one on 
> List, but with a "fork" of the specification.
> 
> Maybe if JDK-8143850 is implemented to give a list view of an ArrayDeque, the 
> replaceAll() method could be implemented on that:
> 
>arrayDeque.asList().replaceAll(clazz::method);
> 
> ***
> 
> I'm not sure what to think of the arrangement of the tests. The "core" 
> collections, that is, collections in java.util, exclusive of 
> java.util.concurrent, are mostly tested by tests in jdk/test/java/util. This 
> patch adds tests for ArrayList and ArrayDeque inside of 
> jdk/test/java/util/concurrent/tck. There's a test group jdk_collections_core 
> that's intended to test the core collections, so it'll miss the new tests 
> being added here.
> 
> I'm not sure what to suggest. The new tests use the JSR166TestCase framework, 
> which is probably useful, and probably can't be used if the tests are moved 
> elsewhere. I don't know what it would take to convert this to jtreg or 
> testng. Or, the core test group could be modified to run selected JSR166 test 
> cases, which doesn't seem quite right either. Suggestions?
> 
> ***
> 
> I haven't looked at the other j.u.c changes. I haven't done so historically, 
> but I can if you need a reviewer.
> 
> s'marks
> 

Re: RFR: jsr166 jdk9 integration wave 12

[Stuart Marks]

On 10/17/16 6:34 PM, Martin Buchholz wrote:

Most of this is for Stuart - very collection-y.

http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/

This includes a rewrite of ArrayDeque to bring it to parity with ArrayList
(except for List features).
The patch includes public methods ensureCapacity, trimToSize, replaceAll as in
ArrayList, but we can defer making them public to a later change (or a later
release), since new public methods are always controversial.  But I'd really
like to get the performance/scalability changes in for jdk 9.

It also includes a redo of ArrayList#removeIf to make it more efficient and
consistent with behavior of other implementations, including ArrayDeque.

The patches are a little tangled because they step on each other's toes.  File
CollectionTest is in "miscellaneous", but it tests both the ArrayDeque and
ArrayList changes.


Hi Martin,

ArrayList.removeIf() is nice. I like the way it recovers from the predicate 
having thrown an exception. I note that it uselessly copies the tail of the 
array to itself, if the predicate throws an exception and nothing has been 
deleted yet. You could add a r != w check, or possibly deleted > 0 if you 
prefer, or maybe we don't care because this is a rare (we hope) error recovery case.


***

I have some comments on ArrayDeque:

* Change in allocation/capacity policy.

The removal of the power-of-two restriction, and applying a 1.5x growth factor 
(same as ArrayList) seems sensible. Does this mean that the ability to compute 
the proper array index by using x & (length-1) wasn't worth it? Or at least not 
worth the extra tail wastage?


(Potential future enhancement: allocate the array lazily, like ArrayList)

Note, I haven't digested all the changes yet.

* API additions

I'm somewhat undecided about these.

I've always felt that the ensureCapacity() and trimToSize() methods were a sop 
added to ArrayList aimed at people converting from Vector. The 
ArrayList.ensureCapacity() method seems to be used a lot, but probably not to 
great effect, since addAll() gives exact sizing anyway. The trimToSize() method 
could be useful in some cases, but should we hold out for a generalized one, as 
requested by JDK-4619094?


On the other hand, ArrayDeque is modeling an array, so providing some size 
control seems mostly harmless.


The replaceAll() method is a bit oddly placed here. It's a default method on 
List (which ArrayDeque doesn't, and can't implement) so it's a bit strange to 
have a special method here with the same name and semantics as the one on List, 
but with a "fork" of the specification.


Maybe if JDK-8143850 is implemented to give a list view of an ArrayDeque, the 
replaceAll() method could be implemented on that:


arrayDeque.asList().replaceAll(clazz::method);

***

I'm not sure what to think of the arrangement of the tests. The "core" 
collections, that is, collections in java.util, exclusive of 
java.util.concurrent, are mostly tested by tests in jdk/test/java/util. This 
patch adds tests for ArrayList and ArrayDeque inside of 
jdk/test/java/util/concurrent/tck. There's a test group jdk_collections_core 
that's intended to test the core collections, so it'll miss the new tests being 
added here.


I'm not sure what to suggest. The new tests use the JSR166TestCase framework, 
which is probably useful, and probably can't be used if the tests are moved 
elsewhere. I don't know what it would take to convert this to jtreg or testng. 
Or, the core test group could be modified to run selected JSR166 test cases, 
which doesn't seem quite right either. Suggestions?


***

I haven't looked at the other j.u.c changes. I haven't done so historically, but 
I can if you need a reviewer.


s'marks