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.redes...@oracle.com <mailto:claes.redes...@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>
