[11] RFR: 8193128: Reduce number of implementation classes returned by List/Set/Map.of() (original) (raw)

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