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

[Claes Redestad]

Hi Paul,

On 2017-01-10 17:32, Paul Sandoz wrote:
> Hi,
>
> ImmutableCollections
> —
>
> Did you forget or intentionally omit overriding the hashCode for List2 and ListN?

Intentionally omitted: since List2 and ListN have O(1) get performance,
the Iterator provided by AbstractList seems good enough for now.

>
>
>  481         @Override
>  482         public int hashCode() {
>  483             int h = 0;
>  484             for (E e : elements) {
>  485                 if (e != null) {
>  486                     h += e.hashCode();
>  487                 }
>  488             }
>  489             return h;
>  490         }
>
> No need for the null check of e.

Actually null checks are needed: SetN elements is a sparse array with
null at indexes where there is no actual entry.

Or are you suggesting we do the following?

for (E e : elements) {
     h += Objects.hashCode(e);
}

> If you override hashCode should you override equals as well?

I need to look into this one and get back to you, might be
unintentionally left out.

>
>
>  617         @Override
>  618         public int hashCode() {
>  619             return k0.hashCode() ^ v0.hashCode();
>  620         }
>
> That does not conform to the specification of Map.hashCode:
>
> /**
>  * Returns the hash code value for this map.  The hash code of a map is
>  * defined to be the sum of the hash codes of each entry in the map's
>  * {@code entrySet()} view.  This ensures that {@code m1.equals(m2)}
>
> (Your tests might be lucky with the summing of hash codes with distinct ranges of bits set?)

I think you're mistaken: k0 and v0 constitute the sole entry of Map1,
and k0.hashCode() ^ v0.hashCode() is the hash code for said entry;
compare HashMap.Node.hashCode().

>
>
>  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         }
>
> No need for the null check for v, can pass table[i] directly to o.equals

Again, table is sparse and contain null entries when there's no map
entry at that index in the table.  In this case o.equals(null) would
likely return the right thing (false) for all objects, but seems a bit
odd to me.

Thanks!

/Claes

>
> Paul.
>
>> On 10 Jan 2017, at 03:50, Claes Redestad <claes.redestad at oracle.com> wrote:
>>
>> Hi,
>>
>> 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,
>