[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:46:36 UTC 2018
On 01/08/18 20:09, Peter Levart wrote:
>
> Should the method also check that the size(s) of both sets are the same?
Or better yet, compute the size of the other set as you iterate the
elements. Like this:
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
int osize = 0;
for (Object e : (Iterable<?>) o) {
if (!contains(e)) {
return false;
}
osize++;
}
return size() == osize;
}
...since calling .size() on the passed-in Set might not be free.
Regards, Peter
>
> 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