RFR: 8166365: Small immutable collections should provide optimized implementations when possible

[Stuart Marks]

On 1/10/17 3:50 AM, Claes Redestad wrote:
> please review this change to improve startup/warmup characteristics
> and performance of the immutable collection factories:
>
> Bug: https://bugs.openjdk.java.net/browse/JDK-8166365
> Webrev: http://cr.openjdk.java.net/~redestad/8166365/webrev.01/
>
> While filed as an RFE, and a more thorough examination of the hierarchy
> of the ImmutableCollection classes has been discussed[1], this more
> limited patch resolves some immediate issues related to module system
> bootstrap and is therefore motivated to push to 9.
>
> Thanks!
>
> /Claes
>
> [1] we should likely not inherit Iterator classes that check for
> co-modification etc,

Hi Claes,

Thanks for taking this on.

Interesting that some -- and only some -- of the existing empty and singleton 
collections in Collections.java hadn't overridden hashCode(). Thanks for filling 
these in.

The following comments all apply to ImmutableCollections.java.

-------

Regarding Paul's questions about whether you should override equals() and 
various additional hashCode() methods:

The general rule from "Effective Java" is that equals() and hashCode() both be 
overridden. However, this is mainly directed at classes that are chidren of 
Object and that are providing semantics that differ from Object's equals() and 
hashCode() methods. The more precise rule is that the semantics of equals() and 
hashCode() must match.

It's oddly asymmetric to override hashCode() but not equals(), but that's OK, as 
these implementations all inherit equals() from their superclasses, which 
provide the right semantics. In addition, equals() is a bit complicated and is 
kind of expensive, and it should be relatively infrequent.

The point of hashCode() is to avoid unnecessary calls to equals(), so overriding 
hashCode() to make it go fast is more important than overriding equals(). In 
that light it's a bit odd that hashCode() is overridden in most places here, but

List2.hashCode()
ListN.hashCode()
MapN.hashCode()

aren't overridden.

I'd like to see them added at some point, but if your benchmarks don't justify 
them, maybe they're not necessary right now. If not, we should make a note to 
add them later.

-------

All of List{0,1,2,N}.contains(null) will currently return false. With this 
change, List{0,1,2}.contains(null) will change to throw NPE, but 
ListN.contains(null) will continue to return false.

I actually like the change of throwing NPE on contains(null). Note that all the 
Set and Map implementations here throw NPE when null is passed to 
contains/containsKey/containsValue, so returning false instead of throwing NPE 
from the List.contains() methods might have been an oversight on my part. But 
all the List implementations should be made consistent.

Thus, ListN.contains() should be overridden to provide consistent NPE behavior. 
It could simply be

     return super.contains(Objects.requireNonNull(o));

or maybe just write out the loop in order to avoid Iterator allocation.

Also note that (as Peter Levart mentioned some time ago, in the initial review 
of these implementations) that although it isn't guaranteed by specification, 
the convention in the collections implementations is to compare an argument o to 
a contained element e by calling o.equals(e). Thus List1.contains(o) should 
change to

     return o.equals(e0); // implicit nullcheck of o

and the call to Objects.requireNonNull(o) can be dropped.

-------

  287         @Override
  288         public boolean containsAll(Collection<?> o) {
  289             return o.isEmpty(); // implicit nullcheck
  290         }


  324         @Override
  325         public boolean contains(Object o) {
  326             return o.equals(e0); // implicit nullcheck of o
  327         }

  373         @Override
  374         public boolean contains(Object o) {
  375             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
  376         }

While it does add a bit of clutter, I like the idea of commenting every location 
where an implicit nullcheck is done, as is done here, and in several other 
places you had removed the Objects.requireNonNull() call. Note that some 
implicit nullchecks in the List code aren't commented; comments should be added 
there. Please also add a comment at this code in Set2:

  355             if (e0.equals(Objects.requireNonNull(e1))) {

something like "// implicit nullcheck of e0".

Also please add comments for SetN.probe() and MapN.probe() to indicate that 
callers are relying on them to do implicit nullchecks of their args.

-------

In Set2, SetN, Map1, and MapN, the addition of @Stable also dropped the 
"private" access modifier. Other implementations still have corresponding fields 
as private. Was this intentional? I think they should all remain private.

-------

  664         @Override
  665         public boolean containsKey(Object o) {
  666             return probe(o) >= 0; // probe implicity nullchecks o
  667         }

Typo "implicity".

-------

  669         @Override
  670         public boolean containsValue(Object o) {
  671             for (int i = 1; i < table.length; i += 2) {
  672                 Object v = table[i];
  673                 if (v != null && o.equals(v)) {
  674                     return true;
  675                 }
  676             }
  677             return false;
  678         }

At 673, // implicit nullcheck of o

-------

Thanks!!

s'marks