Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 22, 2017, at 11:57 AM, John Rose  wrote:
> 
> On Dec 21, 2017, at 5:31 PM, Stuart Marks  wrote:
>> 
>> I'd like a blanket assertion that view collections are not serializable.
>> 
>> Now this should be considered distinct from whether view collections are 
>> value-based; I'm fine with considering view collections to be value-based. 
>> It's just that some value-based collections are serializable and others 
>> aren't. In particular, given a serializable, value-based list, a sublist 
>> should not be serializable but it can be value-based. A sublist of a sublist 
>> should also not be serializable and can be value-based, and in this case we 
>> can do short-circuiting such as 'return this' if we like.
> 
> The two concerns can be separated, but they necessarily
> have a priority, and I think you have got the priority backward.
> Here's the way I see it:
> 
> 1. Value-based aggregates are inherently lossless when
> serialized, and so should (in general) be made serializable.
> 
> 2. Views are generally lossy when serialized, *if the backing
> store has a significant identity*, and should (in general) not
> be made serializable.
> 
> If we are going to make blanket statements, I claim the first
> is more fundamental than the second.  The second has
> priority only in history, since serialization was invented before
> the value-based distinction.
> 
> I think we should apply the rules in logical order 1, then 2,
> not historical order 2, then 1.
> 

P.S. I am talking about serialization as a general thing with
a future.  If you are talking only about legacy serialization,
then I can see there might be historical influences that would
invert the flow of the above logic.  Still, I'd like to tweak
legacy serialization in better directions AFAP, even if its
ultimately futile, so that when we come up with something
better we will have relatively more good precedents to
preserve.

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 21, 2017, at 5:31 PM, Stuart Marks  wrote:
> 
> I'd like a blanket assertion that view collections are not serializable.
> 
> Now this should be considered distinct from whether view collections are 
> value-based; I'm fine with considering view collections to be value-based. 
> It's just that some value-based collections are serializable and others 
> aren't. In particular, given a serializable, value-based list, a sublist 
> should not be serializable but it can be value-based. A sublist of a sublist 
> should also not be serializable and can be value-based, and in this case we 
> can do short-circuiting such as 'return this' if we like.

The two concerns can be separated, but they necessarily
have a priority, and I think you have got the priority backward.
Here's the way I see it:

1. Value-based aggregates are inherently lossless when
serialized, and so should (in general) be made serializable.

2. Views are generally lossy when serialized, *if the backing
store has a significant identity*, and should (in general) not
be made serializable.

If we are going to make blanket statements, I claim the first
is more fundamental than the second.  The second has
priority only in history, since serialization was invented before
the value-based distinction.

I think we should apply the rules in logical order 1, then 2,
not historical order 2, then 1.

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Jason Mehrens]

What are your thoughts on pushing the static EMPTY_XXX declarations from 
ImmutableCollections down in to each respective inner class?  Doing that should 
allow for on demand class loading instead of getting everything when any 
factory is used.

>http://cr.openjdk.java.net/~redestad/8193128/open.04/

Jason

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Stuart Marks]

John Rose wrote:


Can anyone point out a reason why the value based
lists of List.of() should serialize while the value based
lists of List.of().subList() should not?  Or is there some
reason we should not allow subList to produce value
based lists?



I think one can interpret the @implSpec in AbstracList::subList to suggest
that the implementation retrieved will subclass AbstractList, which implies
it's*not*  Serializable. As we move away from AbstractList then we can of
course choose our own spec, but since it's established behavior I tried as
best I could to retrofit behavior…



Maybe you are right about that, but AbstractList is*not*  part of the API
of the List returned by List.of, so you are free to do whatever is right
for the value-based list, ignoring all parts of AbstractList that are not
immediately valuable to you.

(Yes, someone could "notice" that the result of List.of seems to be
castable to AbstractList, and*then*  lodge a complaint that its sublist
is serializable, but that's a forced scenario; if we deem it is a real
bug to fix, at some date far in the future, we can fix it by removing
AbstractList from the supers of the List.of result.)


Right, there is no requirement that subList() return an instance of 
AbstractList.

We have a blanket value-based statement over all these implementations. Anybody 
who cares whether subList() returns the same or a different instance, for 
example using References on them, is performing an identity-sensitive operation, 
which violates the value-based admonition.


(Should use of References be added to the list of identity-sensitive operations 
in ValueBased.html?)


I do have a bit of an issue with something like List.of().subList(0,0) returning 
'this', since in this case the sublist will be serializable. This is an outlier, 
because, most existing sublists of the conventional collections aren't 
serializable. And in JDK 9 (and probably JDK 10) sublists of immutable lists 
aren't serializable, since the immutables' sublist implementation is inherited 
from AbstractList.


Now suppose that we proceed with something similar to Claes' sublist 
implementation from webrev open.04, [1] except that if the requested sublist 
matches the bounds of the list, it simply returns 'this'. We'd then have a case 
where


List.of().subList(0, 0) is serializable
List.of(1).subList(0, 0) is not serializable
List.of(1).subList(0, 1) is serializable

and in general

Object[] a = ...
List.of(a).subList(m, n) ??? serializable ???

I'd like to avoid situations like this, where a sublist (and in general, view 
collections) are sometimes serializable and sometimes not, depending upon the 
input data. Instead, I'd like a blanket assertion that view collections are not 
serializable.


Now this should be considered distinct from whether view collections are 
value-based; I'm fine with considering view collections to be value-based. It's 
just that some value-based collections are serializable and others aren't. In 
particular, given a serializable, value-based list, a sublist should not be 
serializable but it can be value-based. A sublist of a sublist should also not 
be serializable and can be value-based, and in this case we can do 
short-circuiting such as 'return this' if we like.


s'marks


[1] http://cr.openjdk.java.net/~redestad/8193128/open.04/

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Stuart Marks]

Finally catching up with this thread

Yes, there should be some additional test cases added. When I added the 
immutable collection classes in JDK 9, I did modify MOAT.java so that its test 
cases would apply to the new implementations.


A few more cases could be added that apply not only to the immutable lists but 
also to lists in general.


I think the bugs mentioned here are with indexOf() and lastIndexOf(), with the 
latter accidentally being a copy of the former. Later in the thread John pointed 
out an off-by-one error with lastIndexOf(), so edge cases should be added as 
well. These would apply to all lists, not just the immutable ones.


There is also the issue mentioned in

JDK-8191418 List.of().indexOf(null) doesn't throw NullPointerException

Tests should be added for that and related methods. Since many collections 
permit null, and I suspect some that disallow null might permit indexOf(null) 
and related, it's not clear to me these belong in MOAT.java.


But if List.of().indexOf(null) were to throw NPE, I'd expect 
List.of().subList(...).indexOf(null) also to throw NPE.


s'marks


On 12/8/17 9:44 AM, Martin Buchholz wrote:

Should there be changes to general purpose collection testing classes like
test/jdk/java/util/concurrent/tck/CollectionTest.java
test/jdk/java/util/Collection/MOAT.java
that would have caught this bug?
(although those are mostly designed for mutable collections, but I think some 
immutable collections (nCopies?) get tested somewhere.


On Fri, Dec 8, 2017 at 7:13 AM, Claes Redestad > wrote:


Hi,

On 2017-12-08 07:54, Andrej Golovnin wrote:

Hi Claes,

http://cr.openjdk.java.net/~redestad/8193128/open.02/


I think you should provide specialised implementations of the
#indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
Using an iterator in List12 is an overkill. But even in ListN using a
simple for loop would be much better.


it's somewhat ironic that I started looking at this *because*
indexOf was slow due use of iterators[1], but then never got
around to specialize them in this patch.

In any case please take look at
the implementation of the #lastIndexOf() method in the
AbstractImmutableList class. It looks like a copy of
AbstractImmutableList#indexOf() and this is wrong.


Nice catch! Quite the embarrassing copy-paste that...

- Specialized the index/lastIndexOf methods for List12, ListN
- Fixed implementation of lastIndexOf in AbstractImmutableList.
- As AbstractImmutableList.indexOf/lastIndexOf are now only used
by AbstractImmutableList.SubList, I moved them there with some
commentary since it's not clear JDK-8191418 should add null
checkson the input for SubList or not.
- Added sanity tests of indexOf/lastIndexOf that touches all
the new implementations:

http://cr.openjdk.java.net/~redestad/8193128/open.03/


Thanks!

/Claes

[1] https://bugs.openjdk.java.net/browse/JDK-8191442

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Peter Levart]

Peter Levart je 09. 12. 2017 ob 21:01 napisal:

Hi Claes,

Claes Redestad je 09. 12. 2017 ob 03:19 napisal:

Hi John,

On 2017-12-09 02:20, John Rose wrote:
On Dec 8, 2017, at 4:45 PM, John Rose > wrote:


Can anyone point out a reason why the value based
lists of List.of() should serialize while the value based
lists of List.of().subList() should not?  Or is there some
reason we should not allow subList to produce value
based lists?


One thing that might be implied from the specification that talks 
about "...a view of the portion of this list between the specified 
indexes..." is that the view keeps a reference to the original list. 
This is observable if combined with Reference object(s). But I don't 
know if this is an important behavioral detail that any code depends on.


Regards, Peter


BTW, ImmutableCollections.AbstractImmutableList.SubList already violates 
that assumption and nobody is complaining.


Peter

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Peter Levart]

Hi Claes,

Claes Redestad je 09. 12. 2017 ob 03:19 napisal:

Hi John,

On 2017-12-09 02:20, John Rose wrote:
On Dec 8, 2017, at 4:45 PM, John Rose > wrote:


Can anyone point out a reason why the value based
lists of List.of() should serialize while the value based
lists of List.of().subList() should not?  Or is there some
reason we should not allow subList to produce value
based lists?


One thing that might be implied from the specification that talks about 
"...a view of the portion of this list between the specified indexes..." 
is that the view keeps a reference to the original list. This is 
observable if combined with Reference object(s). But I don't know if 
this is an important behavioral detail that any code depends on.


Regards, Peter

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Andrej Golovnin]

Hi Claes,

> For example, returning Spliterators.emptySpliterator() and
> Collections.singletonSpliterator when appropriate *sounds* like nice little
> optimizations, but Arrays.spliterator(T[]) with an empty or single-element 
> array
> appears to be relatively cheap operations, whereas mixing implementation could
> make call-sites accepting List.of(foo).spliterator() become megamorphic.
> 
> Thus I think these should be done independently as a follow-up, along with
> tests and microbenchmarks.

I’m fine with it. The most important part is that you now aware of this problem
and I’m sure that you would provide the best possible solution. :-)

Best regards,
Andrej Golovnin

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

Hi Andrej,

forEach seems like a no-brainer, but spliterator might require some 
extra care.


For example, returning Spliterators.emptySpliterator() and
Collections.singletonSpliterator when appropriate *sounds* like nice little
optimizations, but Arrays.spliterator(T[]) with an empty or 
single-element array
appears to be relatively cheap operations, whereas mixing implementation 
could

make call-sites accepting List.of(foo).spliterator() become megamorphic.

Thus I think these should be done independently as a follow-up, along with
tests and microbenchmarks.

Thanks!

/Claes

On 2017-12-09 11:43, Andrej Golovnin wrote:

Hi Claes,


One more thing: Could you please add specialised implementations also
for the following methods:

List.forEach(Consumer)

List.spliterator()
  For List12 when List12.size() == 1 please use 
Collections.singletonSpliterator()
  (this method should be moved to the Spliterators class and be public).
  For List12 when List12.size() == 2 please use Arrays.spliterator().

  For ListN when List.isEmpty() == true please use 
Spliterators.emptySpliterator​()
  and otherwise use Arrays.spliterator().


I’m sorry I forgot to mention, that Set12, SetN, Map12 and MapN should also
have specialised implementations for the #forEach-methods and for
the #spliterator()-methods in Set12, SetN.

Thanks!

Best regards,
Andrej Golovnin

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Andrej Golovnin]

Hi Claes,

> One more thing: Could you please add specialised implementations also
> for the following methods:
> 
> List.forEach(Consumer)
> 
> List.spliterator()
>  For List12 when List12.size() == 1 please use 
> Collections.singletonSpliterator()
>  (this method should be moved to the Spliterators class and be public).
>  For List12 when List12.size() == 2 please use Arrays.spliterator().
> 
>  For ListN when List.isEmpty() == true please use 
> Spliterators.emptySpliterator​()
>  and otherwise use Arrays.spliterator().
> 

I’m sorry I forgot to mention, that Set12, SetN, Map12 and MapN should also
have specialised implementations for the #forEach-methods and for
the #spliterator()-methods in Set12, SetN.

Thanks!

Best regards,
Andrej Golovnin

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Andrej Golovnin]

Hi Claes,

> I think one can interpret the @implSpec in AbstracList::subList to suggest
> that the implementation retrieved will subclass AbstractList, which implies
> it's *not* Serializable.

Not for me. java.util.ArrayList is a subclass of AbstractList and is 
serializable.
And you can use j.u.ArrayList to implement the #subList-method in a subclass of
AbstractList without violating the @implSpec in AbstractList#subList.

And as John already mentioned AbstractList is not a part of the Public API of
the lists returned by the List#of()-methods. So the only spec you should care
about is the one defined in List#subList(). And this spec says nothing about
whether the returned instance should be searializable or not.

> As time is likely up for getting this into 10 then I guess we might as well
> take a step back and do this right for 11. I suspect we'll need a CSR for
> this RFE regardless.
> 
> Keeping it all down to two classes as you suggest allows any mixed usage to
> stay in the realm of bimorphism which might bring a considerable speedup
> in some cases, and the reduction in number of implementation classes
> loaded is a boon. Having all methods in ListN account for the offset might
> cost us a few percent here and there, though.
> 
> An int offset on ListN would actually be footprint neutral compared to the
> pre-existing implementation which pulls in the int modCount from AbstractList.

I really like the idea from John to use List12 and ListN for sublists as it 
would give
us for free the fast implementations for the methods like indexOf, lastIndexOf, 
etc. even
for sublists. But I would not use offset. Do you remember the problem with 
String#substring()
when the #substring()-method has returned a view over very huge String object
which then could not be garbage collected due to a reference from the substring?

I would just add a new constructor to ListN:

ListN(E[] elements, int fromIndex, int toIndex)

to copy elements from the parent list. And this would allow us to keep 
the implementation of the ListN class as is.

One more thing: Could you please add specialised implementations also
for the following methods:

List.forEach(Consumer)

List.spliterator()
  For List12 when List12.size() == 1 please use 
Collections.singletonSpliterator()
  (this method should be moved to the Spliterators class and be public).
  For List12 when List12.size() == 2 please use Arrays.spliterator().
 
  For ListN when List.isEmpty() == true please use 
Spliterators.emptySpliterator​()
  and otherwise use Arrays.spliterator().


> http://cr.openjdk.java.net/~redestad/8193128/open.04/

In case you still would like to use the SubList class:

115 int size;

The size field should be final.

Thanks!

Best regards,
Andrej Golovnin

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 8, 2017, at 6:19 PM, Claes Redestad  wrote:
> 
> I think one can interpret the @implSpec in AbstracList::subList to suggest
> that the implementation retrieved will subclass AbstractList, which implies
> it's *not* Serializable. As we move away from AbstractList then we can of
> course choose our own spec, but since it's established behavior I tried as
> best I could to retrofit behavior…

Maybe you are right about that, but AbstractList is *not* part of the API
of the List returned by List.of, so you are free to do whatever is right
for the value-based list, ignoring all parts of AbstractList that are not
immediately valuable to you.

(Yes, someone could "notice" that the result of List.of seems to be
castable to AbstractList, and *then* lodge a complaint that its sublist
is serializable, but that's a forced scenario; if we deem it is a real
bug to fix, at some date far in the future, we can fix it by removing
AbstractList from the supers of the List.of result.)

> As time is likely up for getting this into 10 then I guess we might as well
> take a step back and do this right for 11. I suspect we'll need a CSR for
> this RFE regardless.

No, we don't need a CSR.  It's unspecified behavior.  And in a brand new
API.  This is a valid refinement from murky to clear, not a change in spec.
(Because it's brand new, there's not even a de facto spec. to worry about.)

> Keeping it all down to two classes as you suggest allows any mixed usage to
> stay in the realm of bimorphism which might bring a considerable speedup
> in some cases, and the reduction in number of implementation classes
> loaded is a boon. Having all methods in ListN account for the offset might
> cost us a few percent here and there, though.

I don't think it will.  It's a fetch of an addend (usually zero) from a cache 
line
that is already hot.  Hot fetches and extra addends are usually in the noise.

> An int offset on ListN would actually be footprint neutral compared to the
> pre-existing implementation which pulls in the int modCount from AbstractList.

Yep.  And it will be an improvement to the number of classes loaded, both in
the status quo and in your current version (with bespoke sublists and their
iterators).

— John

P.S.  The extra cut-n-paste of the helper classes was bothering me, enough
to consider asking for new API points for sublist views.  But if you do the
ListN with an offset, those problems can be pushed off for another day.

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

On 2017-12-09 02:09, John Rose wrote:

On Dec 8, 2017, at 7:13 AM, Claes Redestad  wrote:

http://cr.openjdk.java.net/~redestad/8193128/open.03/


+for (int i = elements.length - 1; i > 0; i--) {

There's an OBOE in this line; should be i >= 0.


I thought I tested the lastIndexOf(..) == 0 cases, but obviously only
for the List12 case...



Errors like this are a risk of hand-specializing code.
It's probably worth it here, but it's still a risk.

For immutable lists, it would be reasonable to recode
the generic algorithms to use for-loops with integer
indexes and get(int) access.  That will remove
the unused generality of iterators, and keep only
the abstraction across get().  The benefits of customized
inlining (to fold up the funny specialized get methods)
can probably be obtained like this:

class AbsImmList {
   @ForceInline int indexOf(Object x) {
 for (int i = 0, s = size(); i < s; i++)  if (x.equals(this.get(i))) return 
i;
   }
}
final class List12 {
   int indexOf(Object x) { return super.indexOf(x); }  // specialize size/get
}
final class ListN {
   int indexOf(Object x) { return super.indexOf(x); }  // specialize size/get
}

The optimization of the funny 1/2 loop for List12 should
unfold into the same code you'd write by hand; if not it's
a bug to fix in C2.  Likewise for the loop in ListN.


I agree, but left this as is for now. If we go the route of re-specifying
behavior of subList we'll want to make sure we get the NPE behavior
of indexOf/lastIndexOf right, too.



— John

P.S. If you are going to hand-specialize, it might be
easier on the optimizer if you would add in this line
as needed:

   final E[] elements = this.elements;  // cache field

Usually C2 gets the same answer, but not always,
since final fields are not fully trustable, and "might"
(in some hypothetical system which C2 can't rule out)
change over a call to Object::equals.  OTOH, generic
coding as above is preferable, and we can fix C2
to hoist the @Stable elements field if it doesn't already.


Ok.



P.P.S. Why does ListN have arity 1 and arity 2 constructors?


Another left-over from my earlier experiments, removed:

http://cr.openjdk.java.net/~redestad/8193128/open.04/

/Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

Hi John,

On 2017-12-09 02:20, John Rose wrote:
On Dec 8, 2017, at 4:45 PM, John Rose > wrote:


Can anyone point out a reason why the value based
lists of List.of() should serialize while the value based
lists of List.of().subList() should not?  Or is there some
reason we should not allow subList to produce value
based lists?


This gets to the heart of a question about how thoroughly we are going
to adopt the concept of value-based.  I think we want to accept that a
sub-collection derived from a value-based collection is itself
value-based, whether or not the API point (designed *before* value
based data structures) is supposed to deliver a “view” or not.  I.e.,
a view of a value-based collection is indistinguishable from a
non-view, and there are performance costs to maintaining a pretended
distinction, so let’s tune our spec. to avoid those costs.

If I'm right about this, perhaps the most natural way to balance Claes's
design is to add an offset field to ListN, and allow ListN to project 
arbitrary

slices out of a backing array.

Then we have only two classes (ListN, List12) even when folks are
slicing all around their lists.  That strikes me as (in terms of number
of loaded classes) much more economical than the stuff with a new
bespoke SubList class, with it's own new bespoke iterator class.
And I think the extra int field (in ListN) will melt into the noise.

— John


I think one can interpret the @implSpec in AbstracList::subList to suggest
that the implementation retrieved will subclass AbstractList, which implies
it's *not* Serializable. As we move away from AbstractList then we can of
course choose our own spec, but since it's established behavior I tried as
best I could to retrofit behavior...

As time is likely up for getting this into 10 then I guess we might as well
take a step back and do this right for 11. I suspect we'll need a CSR for
this RFE regardless.

Keeping it all down to two classes as you suggest allows any mixed usage to
stay in the realm of bimorphism which might bring a considerable speedup
in some cases, and the reduction in number of implementation classes
loaded is a boon. Having all methods in ListN account for the offset might
cost us a few percent here and there, though.

An int offset on ListN would actually be footprint neutral compared to the
pre-existing implementation which pulls in the int modCount from 
AbstractList.


Thanks!

/Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 8, 2017, at 4:45 PM, John Rose  wrote:
> 
> Can anyone point out a reason why the value based
> lists of List.of() should serialize while the value based
> lists of List.of().subList() should not?  Or is there some
> reason we should not allow subList to produce value
> based lists?

This gets to the heart of a question about how thoroughly we are going
to adopt the concept of value-based.  I think we want to accept that a
sub-collection derived from a value-based collection is itself
value-based, whether or not the API point (designed *before* value
based data structures) is supposed to deliver a “view” or not.  I.e.,
a view of a value-based collection is indistinguishable from a
non-view, and there are performance costs to maintaining a pretended
distinction, so let’s tune our spec. to avoid those costs.

If I'm right about this, perhaps the most natural way to balance Claes's
design is to add an offset field to ListN, and allow ListN to project arbitrary
slices out of a backing array.

Then we have only two classes (ListN, List12) even when folks are
slicing all around their lists.  That strikes me as (in terms of number
of loaded classes) much more economical than the stuff with a new
bespoke SubList class, with it's own new bespoke iterator class.
And I think the extra int field (in ListN) will melt into the noise.

— John

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

+1 (there should)

On Dec 8, 2017, at 9:44 AM, Martin Buchholz  wrote:
> 
> Should there be changes to general purpose collection testing classes like
> test/jdk/java/util/concurrent/tck/CollectionTest.java
> test/jdk/java/util/Collection/MOAT.java
> that would have caught this bug?
> (although those are mostly designed for mutable collections, but I think
> some immutable collections (nCopies?) get tested somewhere.

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 8, 2017, at 7:13 AM, Claes Redestad  wrote:
> 
> http://cr.openjdk.java.net/~redestad/8193128/open.03/
> 
+for (int i = elements.length - 1; i > 0; i--) {

There's an OBOE in this line; should be i >= 0.

Errors like this are a risk of hand-specializing code.
It's probably worth it here, but it's still a risk.

For immutable lists, it would be reasonable to recode
the generic algorithms to use for-loops with integer
indexes and get(int) access.  That will remove
the unused generality of iterators, and keep only
the abstraction across get().  The benefits of customized
inlining (to fold up the funny specialized get methods)
can probably be obtained like this:

class AbsImmList {
  @ForceInline int indexOf(Object x) {
for (int i = 0, s = size(); i < s; i++)  if (x.equals(this.get(i))) return 
i;
  }
}
final class List12 {
  int indexOf(Object x) { return super.indexOf(x); }  // specialize size/get
}
final class ListN {
  int indexOf(Object x) { return super.indexOf(x); }  // specialize size/get
}

The optimization of the funny 1/2 loop for List12 should
unfold into the same code you'd write by hand; if not it's
a bug to fix in C2.  Likewise for the loop in ListN.

— John

P.S. If you are going to hand-specialize, it might be
easier on the optimizer if you would add in this line
as needed:

  final E[] elements = this.elements;  // cache field

Usually C2 gets the same answer, but not always,
since final fields are not fully trustable, and "might"
(in some hypothetical system which C2 can't rule out)
change over a call to Object::equals.  OTOH, generic
coding as above is preferable, and we can fix C2
to hoist the @Stable elements field if it doesn't already.

P.P.S. Why does ListN have arity 1 and arity 2 constructors?

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 7, 2017, at 3:41 PM, Claes Redestad  wrote:
> 
> - the ListFactories test didn't explicitly verify that sublists retrieved 
> from various List.of() impls aren't Serializable. Added tests to check no 
> sub-list is Serializable,
> and as a bonus this test now verifies that List.of(...).subList(...) behave 
> like their List.of(..) counterparts in most other ways.

List::subList is a view into a backing list.  But the
story is different for the value-based lists produced
by List.of.

If L is a value-based class, then it seems to me
a meaningless (therefore useless) distinction to
call L::subList a "view".  A slice of a value-based list
can only be another value-based list, because there
is nothing else to slice, besides the component values
of the original list.

So I think we should move forward more confidently
with subList here, and say that List.of(a,b,c).subList(1,2)
is equivalent in all ways to List.of(b,c), and so on.

Can anyone point out a reason why the value based
lists of List.of() should serialize while the value based
lists of List.of().subList() should not?  Or is there some
reason we should not allow subList to produce value
based lists?

— John

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Martin Buchholz]

Should there be changes to general purpose collection testing classes like
test/jdk/java/util/concurrent/tck/CollectionTest.java
test/jdk/java/util/Collection/MOAT.java
that would have caught this bug?
(although those are mostly designed for mutable collections, but I think
some immutable collections (nCopies?) get tested somewhere.

On Fri, Dec 8, 2017 at 7:13 AM, Claes Redestad 
wrote:

> Hi,
>
> On 2017-12-08 07:54, Andrej Golovnin wrote:
>
>> Hi Claes,
>>
>> http://cr.openjdk.java.net/~redestad/8193128/open.02/
>>>
>> I think you should provide specialised implementations of the
>> #indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
>> Using an iterator in List12 is an overkill. But even in ListN using a
>> simple for loop would be much better.
>>
>
> it's somewhat ironic that I started looking at this *because*
> indexOf was slow due use of iterators[1], but then never got
> around to specialize them in this patch.
>
> In any case please take look at
>> the implementation of the #lastIndexOf() method in the
>> AbstractImmutableList class. It looks like a copy of
>> AbstractImmutableList#indexOf() and this is wrong.
>>
>
> Nice catch! Quite the embarrassing copy-paste that...
>
> - Specialized the index/lastIndexOf methods for List12, ListN
> - Fixed implementation of lastIndexOf in AbstractImmutableList.
> - As AbstractImmutableList.indexOf/lastIndexOf are now only used
> by AbstractImmutableList.SubList, I moved them there with some
> commentary since it's not clear JDK-8191418 should add null
> checkson the input for SubList or not.
> - Added sanity tests of indexOf/lastIndexOf that touches all
> the new implementations:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.03/
>
> Thanks!
>
> /Claes
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8191442
>

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

Hi,

On 2017-12-08 07:54, Andrej Golovnin wrote:

Hi Claes,


http://cr.openjdk.java.net/~redestad/8193128/open.02/

I think you should provide specialised implementations of the
#indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
Using an iterator in List12 is an overkill. But even in ListN using a
simple for loop would be much better.


it's somewhat ironic that I started looking at this *because*
indexOf was slow due use of iterators[1], but then never got
around to specialize them in this patch.


In any case please take look at
the implementation of the #lastIndexOf() method in the
AbstractImmutableList class. It looks like a copy of
AbstractImmutableList#indexOf() and this is wrong.


Nice catch! Quite the embarrassing copy-paste that...

- Specialized the index/lastIndexOf methods for List12, ListN
- Fixed implementation of lastIndexOf in AbstractImmutableList.
- As AbstractImmutableList.indexOf/lastIndexOf are now only used
by AbstractImmutableList.SubList, I moved them there with some
commentary since it's not clear JDK-8191418 should add null
checkson the input for SubList or not.
- Added sanity tests of indexOf/lastIndexOf that touches all
the new implementations:

http://cr.openjdk.java.net/~redestad/8193128/open.03/

Thanks!

/Claes

[1] https://bugs.openjdk.java.net/browse/JDK-8191442

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Andrej Golovnin]

Hi Claes,

> http://cr.openjdk.java.net/~redestad/8193128/open.02/

I think you should provide specialised implementations of the
#indexOf() and #lastIndexOf() methods in the classes List12 and ListN.
Using an iterator in List12 is an overkill. But even in ListN using a
simple for loop would be much better. In any case please take look at
the implementation of the #lastIndexOf() method in the
AbstractImmutableList class. It looks like a copy of
AbstractImmutableList#indexOf() and this is wrong.

Best regards,
Andrej Golovnin

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

On 2017-12-07 01:12, Claes Redestad wrote:
SubList is now final, inherits from AbstractImmutableList instead of 
AbstractList and reuses more of the shared code.


I also moved 'implements Serializable' from AbstractImmutableList to 
List12 and ListN respectively to not
change the behavior that List.of(0,1) is serializable while 
List.of(0,1).subList(0,1) isn't.


While doing this, I realized a few issues with my patch around the 
subList mechanics:


- I had "optimized" AbstractImmutable::subList to return self or 
emptyList if appropriate, which sounded nice, but is in fact an 
incompatible change (some subLists become Serializable).
- the ListFactories test didn't explicitly verify that sublists 
retrieved from various List.of() impls aren't Serializable. Added tests 
to check no sub-list is Serializable,
and as a bonus this test now verifies that List.of(...).subList(...) 
behave like their List.of(..) counterparts in most other ways.
- fixed range check in AbstractImmutableList.listIterator(0) to not 
throw IOOBE if the list is empty


http://cr.openjdk.java.net/~redestad/8193128/open.02/

Thanks!

/Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

On Dec 7, 2017, at 12:05 PM, Remi Forax  wrote:
> 
> have a bit saying if an object is fully initialized or not, this bit will be 
> true at the end of the constructor and can be set for the de-serialization too

Yes, that's the hard part of fixing final.  Sometimes we call this the "slushy 
bit".
It would almost always be false, but would be true for those unusual objects
which are in the process of deserialization, and also (perhaps) objects which
may escape into the optimizer while undergoing normal construction. The
latter version of "slushy" is probably a statically computable condition,
unlike "slushy during deserialization".

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Remi Forax]

You have also the problem of people doing a lot of things in the constructor, 
by example

class Foo {
  @Stable final int x;

  Foo() {
m();
x = 3;
m();
  }

  void m() {
for(...) {
  // use x here
}
  }
}

here, m() can be JITed with x equals to 0 as a constant and the code of m() be 
re-use for the second call even if the value of x has changed in the middle.
in that case, either you need to maintain dependency between the JITed code and 
the field 'x' or have a bit saying if an object is fully initialized or not, 
this bit will be true at the end of the constructor and can be set for the 
de-serialization too.

Rémi

- Mail original -
> De: "John Rose" <john.r.r...@oracle.com>
> À: "Paul Sandoz" <paul.san...@oracle.com>
> Cc: "core-libs-dev" <core-libs-dev@openjdk.java.net>
> Envoyé: Jeudi 7 Décembre 2017 20:50:01
> Objet: Re: [10?] RFR: 8193128: Reduce number of implementation classes 
> returned by List/Set/Map.of()

>> On Dec 6, 2017, at 5:16 PM, Paul Sandoz <paul.san...@oracle.com> wrote:
>> 
>> It can, since final fields are not treated as really final (unless in
>> java.lang.invoke package, where it’s as if all such fields are annotated with
>> @Stable). C2 will treat the field value a constant value if the collection is
>> held in a static final field.
> 
> We could tweak the semantics of @Stable to omit the zero corner case for a 
> final
> field. Then the annotation on a non-array field would mean “trust this final”.
> 
> It would be yet another stop gap before that far-off day when we fix finals 
> (and
> arrays). Such new uses of @Stable would have to be evaluated for any
> interaction with deserialization, so it’s not a simple decision.

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[John Rose]

> On Dec 6, 2017, at 5:16 PM, Paul Sandoz  wrote:
> 
> It can, since final fields are not treated as really final (unless in 
> java.lang.invoke package, where it’s as if all such fields are annotated with 
> @Stable). C2 will treat the field value a constant value if the collection is 
> held in a static final field.

We could tweak the semantics of @Stable to omit the zero corner case for a 
final field. Then the annotation on a non-array field would mean “trust this 
final”.

It would be yet another stop gap before that far-off day when we fix finals 
(and arrays). Such new uses of @Stable would have to be evaluated for any 
interaction with deserialization, so it’s not a simple decision. 

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Paul Sandoz]

> On 6 Dec 2017, at 16:12, Claes Redestad  wrote:
>> 
>>   and i do not understand why the field size is not declared @Stable anymore,
>>   ok, it can be equals to zero, but in that case the JIT will emit a move
>>   so it's better than always asking for a move (or i do not understand the 
>> semantics of @Stable ?)
> 
> Hmm, I'm under the impression @Stable brings no additional value to a final 
> non-array fields (definitely important for arrays).
> 

It can, since final fields are not treated as really final (unless in 
java.lang.invoke package, where it’s as if all such fields are annotated with 
@Stable). C2 will treat the field value a constant value if the collection is 
held in a static final field.

Paul.

> I might have been guilty of adding @Stable to more fields than necessary in 
> these implementations in the first place. I've
> reverted this removal and will add a note to investigate separately if we can 
> more systematically clean them up.
> 
> http://cr.openjdk.java.net/~redestad/8193128/open.01/
> 
> Thanks!
> 
> /Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

Hi Rémi,

On 2017-12-06 23:57, Remi Forax wrote:

Hi Claes,
- both constructors of SubList should be package private,


deal!


- in listIterator, i can be declared outside of the ListIterator as a local 
variable that would be captured by the anonymous class,
   so index is not used inside the anonymous class. Also you can use the 
diamond syntax for anonymous class now.

   public ListIterator listIterator(int index) {
 rangeCheck(index);
 ListIterator i = root.listIterator(offset + index);
 return new ListIterator<>() {
   ...


Sure.


- you can move "new IndexOutOfBoundsException" out of rangeCheck into 
outOfBoundsMsg, so the bytecode size of rangeCheck() will be smaller.


I had already done so for the outer class, and realized I had forgotten 
to clean this part up:


SubList is now final, inherits from AbstractImmutableList instead of 
AbstractList and reuses more of the shared code.


I also moved 'implements Serializable' from AbstractImmutableList to 
List12 and ListN respectively to not
change the behavior that List.of(0,1) is serializable while 
List.of(0,1).subList(0,1) isn't.



- in Itr, please declare the constructor after the declaration of the fields,
   and assigning the cursor to zero is useless.


Done.



- in equals, the code is weirdly asymmetric because e1 is typed as an Iterator, 
declaring it as an Iterator will make the code more symmetric.


I also realized I had missed an opportunity to take advantage of the 
fact that elements returned from e1 are guaranteed to

be non-null. Might as well.



- in List12, you have a lot of useless @SuppressWarnings("unchecked") ??
   in size(), get(), contains(), hashCode(), writeReplace().

- in ListN, again some useless @SuppressWarnings("unchecked") ??
   in  size(), get(), contains(), hashCode(), writeReplace()


I don't know how these snuck in, but my IDE was pleasantly hiding these 
away. I think I cleaned out all the useless ones.



- the constructor of MapN(K,V) can be made a little more efficient (less 
getfield opcodes) if written like this

   MapN(K key, V value) {

   table = new Object[] { key, value };
   size = 1;
   }


Oops, this was a leftover from my experiment where I adapted MapN to 
implement Map1 when setting specializers=0. Removed.




   and i do not understand why the field size is not declared @Stable anymore,
   ok, it can be equals to zero, but in that case the JIT will emit a move
   so it's better than always asking for a move (or i do not understand the 
semantics of @Stable ?)


Hmm, I'm under the impression @Stable brings no additional value to a 
final non-array fields (definitely important for arrays).


I might have been guilty of adding @Stable to more fields than necessary 
in these implementations in the first place. I've
reverted this removal and will add a note to investigate separately if 
we can more systematically clean them up.


http://cr.openjdk.java.net/~redestad/8193128/open.01/

Thanks!

/Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

Hi,

On 2017-12-06 22:20, Martin Buchholz wrote:
Guava struggled with this as well with their immutable collections.  
You could look at their revision history (I haven't). Maybe they got 
rid of SingletonImmutableList for the same reason?


I've not looked at guava sources, but I've seen comments alluding to 
similar issues there, yes.


There's definitely different trade-offs here, and I'm making the 
conservative choice of taking the one that is in effect and trying to 
make it just a bit better.


/Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Remi Forax]

Hi Claes,
- both constructors of SubList should be package private,
- in listIterator, i can be declared outside of the ListIterator as a local 
variable that would be captured by the anonymous class,
  so index is not used inside the anonymous class. Also you can use the diamond 
syntax for anonymous class now.

  public ListIterator listIterator(int index) {
rangeCheck(index);
ListIterator i = root.listIterator(offset + index);
return new ListIterator<>() {
  ...

- you can move "new IndexOutOfBoundsException" out of rangeCheck into 
outOfBoundsMsg, so the bytecode size of rangeCheck() will be smaller.

- in Itr, please declare the constructor after the declaration of the fields,
  and assigning the cursor to zero is useless.

- in equals, the code is weirdly asymmetric because e1 is typed as an 
Iterator, declaring it as an Iterator will make the code more symmetric.

- in List12, you have a lot of useless @SuppressWarnings("unchecked") ??
  in size(), get(), contains(), hashCode(), writeReplace().

- in ListN, again some useless @SuppressWarnings("unchecked") ??
  in  size(), get(), contains(), hashCode(), writeReplace()

- the constructor of MapN(K,V) can be made a little more efficient (less 
getfield opcodes) if written like this
   
  MapN(K key, V value) {
  table = new Object[] { key, value };
  size = 1;
  }

  and i do not understand why the field size is not declared @Stable anymore,
  ok, it can be equals to zero, but in that case the JIT will emit a move
  so it's better than always asking for a move (or i do not understand the 
semantics of @Stable ?)

cheers,
Rémi


- Mail original -
> De: "Claes Redestad" 
> À: "core-libs-dev" , "Stuart Marks" 
> 
> Envoyé: Mercredi 6 Décembre 2017 21:21:55
> Objet: [10?] RFR: 8193128: Reduce number of implementation classes returned 
> by List/Set/Map.of()

> Hi,
> 
> please help review this patch to consolidate the number of
> implementation classes returned by the static collection factories:
> 
> http://cr.openjdk.java.net/~redestad/8193128/open.00/
> 
> I set out to explore options for addressing small inefficiencies we've
> been running into, the latest after replacing use of @Stable arrays in
> java.lang.invoke with List.of() (JDK-8184777):
> 
> - List.indexOf deferred to the iterator in AbstractList, which check for
> concurrent modification
> - Warmup takes a bit longer due to having to warm up four different
> classes and associated methods
> - Slowdowns in certain code paths attributable to certain calls becoming
> megamorphic
> 
> Microbenchmark:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/ListMorphism.java
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/benchmarks.jar
> 
> The benchmark explores how call-sites behave when performing some naive
> operations on a few different Lists.
> 
> For every benchmark using List.of() there's a variant using ArrayList
> for comparison:
> 
> Baseline:
> 
> Benchmark Mode  Cnt    Score Error   Units
> ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
> ListMorphism.finalGetFromList    thrpt   25  335.245 ±  0.244 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
> ListMorphism.finalSumSizesList   thrpt   25  335.107 ±  0.439 ops/us
> # 1.4x
> ListMorphism.getFromArrayList    thrpt   25   70.343 ±  0.972 ops/us
> ListMorphism.getFromList thrpt   25   37.121 ±  0.135 ops/us
> # 0.53x
> ListMorphism.getFromArrayList12  thrpt   25 109.890 ±  0.286  ops/us
> ListMorphism.getFromList12   thrpt   25  109.552 ± 6.972  ops/us
> # 1.0x
> ListMorphism.sumSizesArrayList   thrpt   25  131.467 ±  4.672 ops/us
> ListMorphism.sumSizesList    thrpt   25   57.877 ±  0.102 ops/us
> # 0.45x
> ListMorphism.sumSizesArrayList12 thrpt   25 208.652 ± 11.294  ops/us
> ListMorphism.sumSizesList12  thrpt   25  227.269 ± 0.961  ops/us
> # 1.1x
> 
> The good: When dealing with List literals (the final* benchmarks),
> List.of() allows really nice speed-ups compared to ArrayList.
> 
> The bad: When not used as a literal, List.of() implementations at
> call-sites can cause a substantial slowdown (megamorphic dispatch)
> 
> The ugly:
> 
> After some explorations[1], I narrowed in on the following experiment:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/
> 
> Basically: Merge List1 and List2 into a single class, List12, merge
> List0 into ListN (List0 has a singleton instance, so might as well be an
> instance of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.
> 
> This strikes a balance between throughput, footprint and slightly better
> startup/warmup behavior.
> 
> According to jol estimates[2] the size of List12 is the same as both
> List1 and List2 in the current JDK implementation. Set12 is footprint
> 

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Claes Redestad]

Hi Jonathan,

On 2017-12-06 21:58, Jonathan Bluett-Duncan wrote:

Hi Claes,

Looking at 
http://cr.openjdk.java.net/~redestad/8193128/open.00/src/java.base/share/classes/java/util/ImmutableCollections.java.cdiff.html 
, 
there are sections labelled --- 646,657  and --- 834,845 
 where lines like `Objects.requireNonNull(0 /* zero */);` are 
written. I believe that they were supposed to be either removed or 
made to be written like `Objects.requireNonNull(o /* lowercase o */)`. 
Is my belief/understanding correct?


nice catch! That was two fun little typos on my part (now why did we 
ever make 0 box to an Object...). Fixing in-place.


Thanks!

/Claes

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Martin Buchholz]

Guava struggled with this as well with their immutable collections.  You
could look at their revision history (I haven't). Maybe they got rid of
SingletonImmutableList for the same reason?

On Wed, Dec 6, 2017 at 12:21 PM, Claes Redestad 
wrote:

> Hi,
>
> please help review this patch to consolidate the number of implementation
> classes returned by the static collection factories:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.00/
>
> I set out to explore options for addressing small inefficiencies we've
> been running into, the latest after replacing use of @Stable arrays in
> java.lang.invoke with List.of() (JDK-8184777):
>
> - List.indexOf deferred to the iterator in AbstractList, which check for
> concurrent modification
> - Warmup takes a bit longer due to having to warm up four different
> classes and associated methods
> - Slowdowns in certain code paths attributable to certain calls becoming
> megamorphic
>
> Microbenchmark: http://cr.openjdk.java.net/~re
> destad/scratch/less_immutables/ListMorphism.java
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables
> /benchmarks.jar
>
> The benchmark explores how call-sites behave when performing some naive
> operations on a few different Lists.
>
> For every benchmark using List.of() there's a variant using ArrayList for
> comparison:
>
> Baseline:
>
> Benchmark Mode  CntScore Error   Units
> ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
> ListMorphism.finalGetFromListthrpt   25  335.245 ±  0.244 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
> ListMorphism.finalSumSizesList   thrpt   25  335.107 ±  0.439 ops/us
> # 1.4x
> ListMorphism.getFromArrayListthrpt   25   70.343 ±  0.972 ops/us
> ListMorphism.getFromList thrpt   25   37.121 ±  0.135 ops/us
> # 0.53x
> ListMorphism.getFromArrayList12  thrpt   25 109.890 ±  0.286  ops/us
> ListMorphism.getFromList12   thrpt   25  109.552 ± 6.972  ops/us
> # 1.0x
> ListMorphism.sumSizesArrayList   thrpt   25  131.467 ±  4.672 ops/us
> ListMorphism.sumSizesListthrpt   25   57.877 ±  0.102 ops/us
> # 0.45x
> ListMorphism.sumSizesArrayList12 thrpt   25 208.652 ± 11.294  ops/us
> ListMorphism.sumSizesList12  thrpt   25  227.269 ± 0.961  ops/us
> # 1.1x
>
> The good: When dealing with List literals (the final* benchmarks),
> List.of() allows really nice speed-ups compared to ArrayList.
>
> The bad: When not used as a literal, List.of() implementations at
> call-sites can cause a substantial slowdown (megamorphic dispatch)
>
> The ugly:
>
> After some explorations[1], I narrowed in on the following experiment:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/
>
> Basically: Merge List1 and List2 into a single class, List12, merge List0
> into ListN (List0 has a singleton instance, so might as well be an instance
> of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.
>
> This strikes a balance between throughput, footprint and slightly better
> startup/warmup behavior.
>
> According to jol estimates[2] the size of List12 is the same as both List1
> and List2 in the current JDK implementation. Set12 is footprint neutral
> compared to Set2 on all platforms but lose a few bytes on 64-bit VMs
> compared to Set1.
>
> Benchmark Mode  CntScore   Error Units
> ListMorphism.finalGetFromArrayList   thrpt   25   93.046 ± 0.569 ops/us
> ListMorphism.finalGetFromListthrpt   25  335.280 ± 0.154 ops/us #
> 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  244.595 ± 1.085 ops/us
> ListMorphism.finalSumSizesList   thrpt   25  303.351 ± 0.182 ops/us #
> 1.2x
> ListMorphism.getFromArrayListthrpt   25   70.631 ± 0.070 ops/us
> ListMorphism.getFromList thrpt   25   73.258 ± 2.955 ops/us #
> 1.04x
> ListMorphism.getFromArrayList12  thrpt   25 109.921 ± 0.096  ops/us
> ListMorphism.getFromList12   thrpt   25  127.392 ± 0.088  ops/us
> # 1.16x
> ListMorphism.sumSizesArrayList   thrpt   25  131.393 ± 4.882 ops/us
> ListMorphism.sumSizesListthrpt   25  107.686 ± 5.286 ops/us #
> 0.82x
> ListMorphism.sumSizesArrayList12 thrpt   25  212.350 ± 0.134  ops/us
> ListMorphism.sumSizesList12  thrpt   25  198.778 ± 0.479  ops/us
> # 0.94x
>
> The experiment has a flag to change number of specialized List/Set/Map
> classes (-Djdk.ImmutableCollections.specializations=0|1|2, default=2).
>
> 1 specialization (List1 + ListN, Set1 + SetN) is more or less the same as
> 2, some ~1-2% improvements, mainly in sumSizes micros.
>
> 0 specializations (List-, Set, MapN only) achieves a small increase in
> throughput on some micros by ensuring callsites stay monomorphic, but it's
> not very substantial by my measures (~5%, but mostly in sumSizes micros).
>
> Keeping the footprint more or less the same, while evening out 

Re: [10?] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()

[Jonathan Bluett-Duncan]

Hi Claes,

Looking at
http://cr.openjdk.java.net/~redestad/8193128/open.00/src/java.base/share/classes/java/util/ImmutableCollections.java.cdiff.html,
there are sections labelled --- 646,657  and --- 834,845  where
lines like `Objects.requireNonNull(0 /* zero */);` are written. I believe
that they were supposed to be either removed or made to be written like
`Objects.requireNonNull(o /* lowercase o */)`. Is my belief/understanding
correct?

Cheers,
Jonathan

On 6 December 2017 at 20:21, Claes Redestad 
wrote:

> Hi,
>
> please help review this patch to consolidate the number of implementation
> classes returned by the static collection factories:
>
> http://cr.openjdk.java.net/~redestad/8193128/open.00/
>
> I set out to explore options for addressing small inefficiencies we've
> been running into, the latest after replacing use of @Stable arrays in
> java.lang.invoke with List.of() (JDK-8184777):
>
> - List.indexOf deferred to the iterator in AbstractList, which check for
> concurrent modification
> - Warmup takes a bit longer due to having to warm up four different
> classes and associated methods
> - Slowdowns in certain code paths attributable to certain calls becoming
> megamorphic
>
> Microbenchmark: http://cr.openjdk.java.net/~re
> destad/scratch/less_immutables/ListMorphism.java
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables
> /benchmarks.jar
>
> The benchmark explores how call-sites behave when performing some naive
> operations on a few different Lists.
>
> For every benchmark using List.of() there's a variant using ArrayList for
> comparison:
>
> Baseline:
>
> Benchmark Mode  CntScore Error   Units
> ListMorphism.finalGetFromArrayList   thrpt   25   92.659 ±  3.058 ops/us
> ListMorphism.finalGetFromListthrpt   25  335.245 ±  0.244 ops/us
> # 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  245.020 ±  0.106 ops/us
> ListMorphism.finalSumSizesList   thrpt   25  335.107 ±  0.439 ops/us
> # 1.4x
> ListMorphism.getFromArrayListthrpt   25   70.343 ±  0.972 ops/us
> ListMorphism.getFromList thrpt   25   37.121 ±  0.135 ops/us
> # 0.53x
> ListMorphism.getFromArrayList12  thrpt   25 109.890 ±  0.286  ops/us
> ListMorphism.getFromList12   thrpt   25  109.552 ± 6.972  ops/us
> # 1.0x
> ListMorphism.sumSizesArrayList   thrpt   25  131.467 ±  4.672 ops/us
> ListMorphism.sumSizesListthrpt   25   57.877 ±  0.102 ops/us
> # 0.45x
> ListMorphism.sumSizesArrayList12 thrpt   25 208.652 ± 11.294  ops/us
> ListMorphism.sumSizesList12  thrpt   25  227.269 ± 0.961  ops/us
> # 1.1x
>
> The good: When dealing with List literals (the final* benchmarks),
> List.of() allows really nice speed-ups compared to ArrayList.
>
> The bad: When not used as a literal, List.of() implementations at
> call-sites can cause a substantial slowdown (megamorphic dispatch)
>
> The ugly:
>
> After some explorations[1], I narrowed in on the following experiment:
> http://cr.openjdk.java.net/~redestad/scratch/less_immutables/webrev/
>
> Basically: Merge List1 and List2 into a single class, List12, merge List0
> into ListN (List0 has a singleton instance, so might as well be an instance
> of ListN). Same for Set0,1,2,N. Map0 is merged into MapN.
>
> This strikes a balance between throughput, footprint and slightly better
> startup/warmup behavior.
>
> According to jol estimates[2] the size of List12 is the same as both List1
> and List2 in the current JDK implementation. Set12 is footprint neutral
> compared to Set2 on all platforms but lose a few bytes on 64-bit VMs
> compared to Set1.
>
> Benchmark Mode  CntScore   Error Units
> ListMorphism.finalGetFromArrayList   thrpt   25   93.046 ± 0.569 ops/us
> ListMorphism.finalGetFromListthrpt   25  335.280 ± 0.154 ops/us #
> 3.6x
> ListMorphism.finalSumSizesArrayList  thrpt   25  244.595 ± 1.085 ops/us
> ListMorphism.finalSumSizesList   thrpt   25  303.351 ± 0.182 ops/us #
> 1.2x
> ListMorphism.getFromArrayListthrpt   25   70.631 ± 0.070 ops/us
> ListMorphism.getFromList thrpt   25   73.258 ± 2.955 ops/us #
> 1.04x
> ListMorphism.getFromArrayList12  thrpt   25 109.921 ± 0.096  ops/us
> ListMorphism.getFromList12   thrpt   25  127.392 ± 0.088  ops/us
> # 1.16x
> ListMorphism.sumSizesArrayList   thrpt   25  131.393 ± 4.882 ops/us
> ListMorphism.sumSizesListthrpt   25  107.686 ± 5.286 ops/us #
> 0.82x
> ListMorphism.sumSizesArrayList12 thrpt   25  212.350 ± 0.134  ops/us
> ListMorphism.sumSizesList12  thrpt   25  198.778 ± 0.479  ops/us
> # 0.94x
>
> The experiment has a flag to change number of specialized List/Set/Map
> classes (-Djdk.ImmutableCollections.specializations=0|1|2, default=2).
>
> 1 specialization (List1 + ListN, Set1 + SetN) is more or less the same as
> 2, some ~1-2% improvements, mainly in sumSizes micros.
>
> 0