RFR: 8166365: Small immutable collections should provide optimized implementations when possible
Claes Redestad
claes.redestad at oracle.com
Wed Jan 11 13:43:28 UTC 2017
Hi Stuart,
On 01/11/2017 04:10 AM, Stuart Marks wrote:
> 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.
As they are all rather simple and straightforward I've added them for
consistency.
>
> -------
>
> 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.
Done.
>
> 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.
Done.
>
> -------
>
> 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.
Done.
>
> -------
>
> 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.
This was intentional: for those implementations where I dropped private
there are inner
classes which access the fields directly. This leads to synthetic
accessors, which shows up
as JIT compilation overhead during module bootstrap profiling.
This is what made me look at this in the first place, and a large part
of the reason why I
believe that it's motivated to fast-track this enhancement as a means to
improve JDK 9
startup metrics. If you have a strong preference against them being
made package-private
there's a similar gain to be had by passing them as arguments to
concrete inner classes,
e.g., for Set2:
static class Itr<E> implements Iterator<E> {
private final E e0;
private final E e1;
private int idx = 0;
Itr(E e0, E e1) {
this.e0 = e0;
this.e1 = e1;
}
@Override
public boolean hasNext() {
return idx < 2;
}
@Override
public E next() {
if (idx == 0) {
idx = 1;
return e0;
} else if (idx == 1) {
idx = 2;
return e1;
} else {
throw new NoSuchElementException();
}
}
}
@Override
public Iterator<E> iterator() {
return new Itr<E>(e0, e1);
}
>
> -------
>
> 664 @Override
> 665 public boolean containsKey(Object o) {
> 666 return probe(o) >= 0; // probe implicity nullchecks o
> 667 }
>
> Typo "implicity".
Fixed.
>
> -------
>
> 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
All done:
http://cr.openjdk.java.net/~redestad/8166365/webrev.02/
Thanks for the thorough review!
/Claes
>
> -------
>
> Thanks!!
>
> s'marks
More information about the core-libs-dev
mailing list