[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:38:20 UTC 2018
Also, I don't think that ClassCastException should be caught here. It
should never be thrown by containsAll(c) anyway.
On 01/08/18 20:09, Peter Levart wrote:
> 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