[11] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()
Peter Levart
peter.levart at gmail.com
Mon Jan 8 19:09:02 UTC 2018
Hi Claes,
Are you sure that AbstractImmutableSet.equals(Object) is correct?
@Override
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection<?> c = (Collection<?>) o;
try {
return containsAll(c);
} catch (ClassCastException | NullPointerException unused) {
return false;
}
}
It seems to me that this implementation returns true when passing in a
sub-set of this. Should the method also check that the size(s) of both
sets are the same?
Regards, Peter
On 01/08/18 12:37, Claes Redestad wrote:
> Hi Stuart et al,
>
> I've gone through the feedback (thanks, everyone!) and made the
> following adjustments which I
> hope covers most, if not all, concerns:
>
> - Per John's suggestion I've moved most of the methods in List12/ListN
> to AbstractImmutableList,
> using for-loops rather than iterators etc. I've not found evidence
> that the suggested
> @ForceInline + trivial @Override trick is necessary for the methods
> implemented here to match
> ArrayList, so left this out for now (examining this in-depth might be
> a good follow-up).
>
> - Extracted common code between immutable List and Set implementations to
> AbstractImmutableCollection and addedAbstractImmutableSet (the only
> method that was pulled
> in and not overridden from AbstractSet was equals, so this seems like
> a cleaner abstraction with
> minimal copy-paste)
>
> - Rolled up the changes requested by JDK-8191418 into this patch,
> i.e., the following calls
> now throw a NPE as expected:
>
> List.of(..).subList(..).indexOf(null);
> List.of(..).subList(..).lastIndexOf(null);
> List.of(..).subList(..).contains(null);
>
> Additionally Set.of(..).contains(null) and
> Map.of(..).containsValue/-Key(null) had an inconsistency
> discovered when adding tests to this.
>
> This is going against offline suggestions to break this patch into
> smaller parts, e.g. implement
> JDK-8191418[1] separately, merge List0 into ListN in a standalone
> patch etc.. I agree, but
> think teasing the constituent pieces at play *now* would be a large
> effort for small gain.
>
> If faced with another round of overwhelming feedback/criticism I'm
> open to but not enthusiastic
> about splitting this apart. :-)
>
> - Per Jason Mehren's suggestion, I've moved EMPTY_* static finals to
> their respective
> ListN/SetN/MapN class. I think they might all be initialized early in
> the bootstrap, but felt
> cleaner regardless.
>
> - I've NOT changed the subList() to return a Serializable view for now.
>
> Experimentally verified that having List.of().subList() return a
> List12 or ListN as appropriate
> *could* give a speedup at call-sites that observe List12, ListN and
> SubList, but to achieve this
> we would either have to redesign ListN to keep track of an offset +
> size (which has a small
> performance and footprint cost), or have subList() actually copy the
> backing array.
>
> Either alternative seems somewhat unappealing, and take the
> conservative approach for now. And
> making SubList Serializable would be a simple change at a later date
> if deemed appropriate..
>
> - Added a set of indexOf / lastIndexOf sanity tests for all(?) List
> implementations in java.util to
> MOAT
>
> - Added tests to ListFactories ensuring indexOf(null) /
> lastIndexOf(null) / contains(null) are
> consistent across immutable list and subList implementations
>
> - Added a test to SetFactories ensuring contains(null) throw NPE for
> all implementations
>
> - Added tests to MapFactories ensuring
> containsKey(null)/containsValue(null) consistently throw
> NPE for all implementations
>
> - Verified micro performance numbers hold up, and added micros for
> hashCode, indexOf.. [2]
>
> http://cr.openjdk.java.net/~redestad/8193128/open.05/
>
> Regards
>
> /Claes
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8191418
> [2]
>
> http://cr.openjdk.java.net/~redestad/8193128/ListMorphism.java
>
> Baseline:
> Benchmark Mode Cnt Score Error Units
> ListMorphism.finalGetFromArrayList avgt 25 37.985 ± 0.550 ns/op
> ListMorphism.finalGetFromList avgt 25 15.081 ± 0.016 ns/op
> ListMorphism.finalSumSizesArrayList avgt 25 16.474 ± 0.343 ns/op
> ListMorphism.finalSumSizesList avgt 25 13.817 ± 0.009 ns/op
> ListMorphism.getFromArrayList avgt 25 46.473 ± 0.049 ns/op
> ListMorphism.getFromArrayList12 avgt 25 34.711 ± 1.680 ns/op
> ListMorphism.getFromList avgt 25 88.202 ± 0.500 ns/op
> ListMorphism.getFromList12 avgt 25 28.904 ± 0.041 ns/op
> ListMorphism.sumSizesArrayList avgt 25 22.603 ± 0.012 ns/op
> ListMorphism.sumSizesArrayList12 avgt 25 17.584 ± 0.019 ns/op
> ListMorphism.sumSizesList avgt 25 59.781 ± 2.666 ns/op
> ListMorphism.sumSizesList12 avgt 25 17.589 ± 0.036 ns/op
> ListMorphism.arrayListHash avgt 25 121.163 ± 7.160 ns/op
> ListMorphism.listHash avgt 25 104.532 ± 0.783 ns/op
> ListMorphism.arrayListIndexOf avgt 25 74.204 ± 0.515 ns/op
> ListMorphism.listIndexOf avgt 25 529.105 ± 8.281 ns/op
>
> Patch:
> Benchmark Mode Cnt Score Error Units
> ListMorphism.finalGetFromArrayList avgt 25 37.744 ± 0.110 ns/op
> ListMorphism.finalGetFromList avgt 25 13.862 ± 0.085 ns/op
> ListMorphism.finalSumSizesArrayList avgt 25 16.326 ± 0.012 ns/op
> ListMorphism.finalSumSizesList avgt 25 15.249 ± 0.658 ns/op
> ListMorphism.getFromArrayList avgt 25 46.520 ± 0.220 ns/op
> ListMorphism.getFromArrayList12 avgt 25 33.922 ± 0.051 ns/op
> ListMorphism.getFromList avgt 25 40.186 ± 0.019 ns/op
> ListMorphism.getFromList12 avgt 25 27.741 ± 0.241 ns/op
> ListMorphism.sumSizesArrayList avgt 25 22.908 ± 1.051 ns/op
> ListMorphism.sumSizesArrayList12 avgt 25 17.656 ± 0.121 ns/op
> ListMorphism.sumSizesList avgt 25 29.342 ± 1.410 ns/op
> ListMorphism.sumSizesList12 avgt 25 20.180 ± 0.148 ns/op
> ListMorphism.arrayListHash avgt 25 117.427 ± 7.805 ns/op
> ListMorphism.listHash avgt 25 110.268 ± 7.485 ns/op
> ListMorphism.arrayListIndexOf avgt 25 75.051 ± 2.539 ns/op
> ListMorphism.listIndexOf avgt 25 76.609 ± 0.121 ns/op
>
> The arrayListHash/listHash results are inconclusive due to a bimodal
> run-to-run
> distribution in my micro but are close enough for comfort. The ~7x
> listIndexOf improvement is large and stable, and stem mainly from moving
> from the inefficient use of iterators previously inherited from
> AbstractList.
>
> On 2017-12-22 02:04, Stuart Marks wrote:
>> 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
>>> <claes.redestad at oracle.com <mailto:claes.redestad at oracle.com>> wrote:
>>>
>>> Hi,
>>>
>>> On 2017-12-08 07:54, Andrej Golovnin wrote:
>>>
>>> Hi Claes,
>>>
>>> http://cr.openjdk.java.net/~redestad/8193128/open.02/
>>> <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/
>>> <http://cr.openjdk.java.net/~redestad/8193128/open.03/>
>>>
>>> Thanks!
>>>
>>> /Claes
>>>
>>> [1] https://bugs.openjdk.java.net/browse/JDK-8191442
>>> <https://bugs.openjdk.java.net/browse/JDK-8191442>
>>>
>>>
>
More information about the core-libs-dev
mailing list