RFR(m): 8139233 add initial compact immutable collection implementations

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Stuart Marks" <stuart.marks at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Jeudi 5 Mai 2016 08:32:08
> Objet: Re: RFR(m): 8139233 add initial compact immutable collection implementations
> 
> On 5/4/16 1:38 AM, Remi Forax wrote:
> > nice work !
> 
> Spoken like a true university professor: "nice work" followed by 100 lines of
> criticism. :-)

professional bias :)

> 
> > first, all classes should be final otherwise, they are not truly immutable
> > and all arrays should be marked as @Stable.
> 
> OK, I'll make the classes final.
> 
> On @Stable, I had a chat with Paul Sandoz about this, and he suggested
> holding
> back from adding this. Its semantics are quite particular and are subject to
> change, and widespread use could easily turn into misuse.

the third item of an immutable list stored in a static final should be a constant, no ?

> 
> > List0, List1,
> >   why not using Collections.emptyList(), Collections.singletonList() here ?
> 
> Serialization compatibility with future versions. I want all of these to
> serialize to the same serial proxy in JDK 9, so that in JDK 9+ they can be
> deserialized to whatever equivalent implementation classes exist in that
> version
> of the JDK. For example, there might be a single field-based implementation
> that
> covers a small range of sizes, or an implementation using value types.

ok !

> 
> > ListN:
> >   - i don't think that extending AbstractList is a good idea here,
> >     AbstractList provide the failfast/modCount mecanism not needed here.
> >     Moreover, i think you should have some overriden methods on par with
> >     Arrays.asList()
> >     (i.e. a custom isEmpty, toArray, indexOf, contains, iterator,
> >     spliterator and forEach)
> >     otherwise people will use Arrays.asList just because it's faster :(
> 
> The implementations all extend AbstractList/Set/Map mainly for implementation
> convenience. This way it makes it easy to add and remove implementations
> tailored for specific sizes, since so much code is shared with the abstract
> superclasses. But they do come with some baggage, as you point out. As the
> set
> of implementation classes settles down, it would make more sense to override
> more methods, and refactor to handle sharing, at which point maybe the
> dependence on the abstract superclasses can be severed.

The problem is that AbstractList is a public class, removing it from the hierarchy is not a backward compatible change,
so it's not something that can be changed as an after through.

> 
> >   - in the constructor, you should use a local variable here,
> >         @SafeVarargs
> >         ListN(E... input) {
> >             // copy and check manually to avoid TOCTOU
> >             @SuppressWarnings("unchecked")
> >             E[] elements = (E[])new Object[input.length]; // implicit
> >             nullcheck of input
> >             for (int i = 0; i < input.length; i++) {
> >                 elements[i] = Objects.requireNonNull(input[i]);
> >             }
> >             this.elements = elements;
> >         }
> 
> Nice. Will fix.
> 
> > List2:
> >   - same as for ListN, should not inherits from AbstractList.
> >   - i wonder why iterator() is not overriden like with Set2.
> 
> Bringing up a List implementation with AbstractList requires only overriding
> get() and size(), but not iterator(). On the other hand, bringing up a Set
> implementation using AbstractSet requires overriding only iterator() and
> size().

I think you will have to override iterator anyway (for the same reason the result of Arrays.asList() override the iterator). 

> 
> > Set2:
> >   - again, here, i don't think that inheriting from AbstractSet is a good
> >   idea.
> >   - in the iterator, pos (position ?) should be private and next() can be
> >   written without the '+=',
> >                 public E next() {
> >                     if (pos == 0) {
> >                         pos = 1;
> >                         return e0;
> >                     } else if (pos == 1) {
> >                         pos = 2;
> >                         return e1;
> >                     } else {
> >                         throw new NoSuchElementException();
> >                     }
> >                 }
> >   - the iterator should not be defined as inner class (with a reference to
> >   Set2) but
> >     be defined as a static class that contains a copy of e1 and e2,
> >     this will save an indirection and avoid to keep a link on the Set if it
> >     is transient.
> 
> Good fixes, thanks. Some of this is stuff left over from when there were
> field-based implementations with larger sizes.
> 
> > SetN:
> >   - in the constructor, use a local variable like for ListN
> >   - the @SuppressWarnings for contains is wrong, probe should take an
> >   Object, not an E.
> 
> Ah, nice cleanup.
> 
> >   - the iterator should not be an inner class like Set2 and take the array
> >   as parameter.
> >     idx should be private. Instead of doing the loop in hasNext and next,
> >     the loop should
> >     be done once in the constructor and in next. So the code of hasNext
> >     will be simple
> >     and the JIT will be able to fold a call to hasNext() followed by a call
> >     to next().
> 
> OK, I'll look at this.
> 
> >    - i don't understand how the serialization can work given that the SALT
> >    may be different between two VMs
> 
> The salt is XORed with the element's hash to determine the position in the
> collection's array. Serializing it writes all the objects in the array from
> left
> to right, but we don't actually care what the order is. Upon deserialization,
> the objects' hash values are XORed with the deserializing JVM's salt and
> (probably) end up in different positions in the array of the newly
> deserialized
> collection. But again we don't care where they end up.
> 
> Same goes for MapN's keys and values.

ok, i will re-review that code later ...

> 
> > MapN:
> >   - see SetN :)
> 
> :-)
> 
> > SerialProxy:
> >   - I believe the class SerialProxy should be public, no ?
> 
> No, the proxy object can and usually should be private. What's missing is a
> doc
> comment specifying the serial format. This should have an "@serial include"
> tag,
> which will cause the doc comment to end up in the serialized-form.html file.
> This works even if the proxy class itself is private.
> 
> This work is tracked by JDK-8133977.
> 
> >   - The constructor should take a Object... to simplify all calls in the
> >   different writeReplace.
> 
> Good idea.
> 
> >   - fields flags and array should be private
> 
> OK.
> 
> Thanks for all the comments! I'll work on an updated webrev and post it soon.
> 
> s'marks
> 
> 

Rémi