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

[Stuart Marks]

Hi Stephen,

On 5/4/16 8:25 AM, Stephen Colebourne wrote:
> A new instance is being created each time for size-zero
> lists/sets/maps. This should return a singleton.

Yes, this is a fairly obvious optimization. It's been on my personal to-do list, 
but I've moved this to a sub-task in JIRA: JDK-8156079.

On the other hand, the tradeoff isn't so obvious. By analogy, we cache the 
small, integral boxed values. This saves memory but reduces locality.

Still, this ought to be considered.

> The serialization proxy is reminiscent of those in JSR-310 but less
> space efficient. Once per stream, the proxy will write
> "java.util.ImmutableCollections.SerialProxy", whereas the JSR-310 one
> is "java.time.Ser". Thats about 29 bytes more than it needs too. ie. a
> package-scoped java.util.Ser would be more efficient.

Good point. I'll refactor this to a top-level, private class with a shorter name.

> There are no messages for IndexOutOfBoundsException.

Will fix to use Objects.checkIndex().

> Like Peter, I'm not convinced that extending AbstractList is the way
> to go, although I can see arguments both ways.

(I think this was Rémi.) Extending AbstractList makes it convenient to have a 
bunch of different variations, but it does come with some baggage. More 
discussion in my (forthcoming) reply to Rémi.

> equals() and hashCode() could be optimized on the size 0, 1 and 2
> classes, as probably can some other methods.
>
> Should spliterator() should be overridden to add the IMMUTABLE flag?

Yes, there are a bunch of methods that can and should be overridden in order to 
improve things. As you point out, spliterator() is one of them. This is already 
tracked by JDK-8133978, still future work.

> For maps, I implemented this years ago which may be of interest:
> http://commons.apache.org/proper/commons-collections/xref/org/apache/commons/collections4/map/Flat3Map.html#L72

Interesting. Thanks for the link.

> I disagree with altering the iteration order. Guava's ImmutableSet and
> ImmutableMap have reliable iteration specified to match creation
> order. This aspect of the design is very useful.

I think this is a reasonable thing to want, but it would be a different API. The 
current Set.of() and Map.of() APIs have unspecified iteration order, and I want 
to "enforce" that via randomizing the iteration order. Having unspecified 
iteration order, but with the implementation giving a stable order, is the worst 
of both worlds. It lets clients bake in inadvertent order dependencies, and then 
when we do change it, it breaks them. (This seems to happen every couple years 
with HashMap.) Randomizing iteration order helps preserve implementation freedom.

That said, it's a fine thing to have a different API that gives a Set or Map 
with a stable iteration order. Several people have asked for this. I've filed 
JDK-8156070 to track this.

s'marks