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

[Stuart Marks]

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. :-)

> 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.

> 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.

> 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.

>   - 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().

> 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.

> 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