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

[Remi Forax]

Hi Stuart,
nice work !

first, all classes should be final otherwise, they are not truly immutable and all arrays should be marked as @Stable.

List0, List1, 
  why not using Collections.emptyList(), Collections.singletonList() here ?
  
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 :(

  - 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;
        }
   - 

List2:
  - same as for ListN, should not inherits from AbstractList.
  - i wonder why iterator() is not overriden like with Set2.

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.

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

        final static class SetNIterator implements Iterator {
          private final E[] elements;
          private int index = nextIndex(0);

          SetNIterator(E[] elements) {
            this.elements = elements;
          }

          private static int nextIndex(int index) {
            for(; index < elements.length; index++) {
              if (elements[index] != null) {
                return index;
              }
            }
            return -1;
          } 

          @Override
          public boolean hasNext() {
            return index != -1;
          }

          @Override
          public E next() {
            if (index == -1) {
              throw new NoSuchElementException();
            }
            E element = elements[index];
            index = nextIndex(index + 1);
            return element;
          }
        }

   - i don't understand how the serialization can work given that the SALT may be different between two VMs
  
MapN:
  - see SetN :)   

SerialProxy:
  - I believe the class SerialProxy should be public, no ?
  - The constructor should take a Object... to simplify all calls in the different writeReplace.
  - fields flags and array should be private
   
regards,
Rémi

----- Mail original -----
> De: "Stuart Marks" <stuart.marks at oracle.com>
> À: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Mercredi 4 Mai 2016 06:55:35
> Objet: RFR(m): 8139233 add initial compact immutable collection	implementations
> 
> Hi all,
> 
> This is a reimplementation of collections created by the JEP 269 convenience
> factory methods. These implementations are overall quite a bit smaller than
> their conventional collections counterparts, particularly at small sizes.
> Lookup
> performance for the hash-based structures (Set and Map) is not particularly
> fast, though in most cases it's comparable to TreeSet/TreeMap. Further
> improvements are likely possible.
> 
> There are no API changes in this changeset.
> 
> Please review:
> 
>      http://cr.openjdk.java.net/~smarks/reviews/8139233/webrev.0/
> 
> JEP link:
> 
>      http://openjdk.java.net/jeps/269
> 
> Thanks,
> 
> s'marks
>