[11] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of()
Claes Redestad
claes.redestad at oracle.com
Mon Jan 8 11:37:10 UTC 2018
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