RFR: 8166365: Small immutable collections should provide optimized implementations when possible

[Stuart Marks]

On 1/11/17 2:30 PM, Louis Wasserman wrote:
> I haven't followed this much, but an observation: in Guava, we avoided
> creating lots of specialized implementations for small collections, because
> the JVM, at least at the time, had a sweet spot for bimorphic dispatch:
> method calls where the real implementation would be one of two options, and
> that the cost blew up after you hit three, and we considered hitting that
> sweet spot more worthwhile than the slightly smaller overhead for
> collections that were already small.
>
> As a result, many of our immutable collection implementations converged on
> having two implementations: one single-element implementation, and one
> implementation for everything else (0, 2, 3... but not 1), and then we had
> a singleton static constant object for the 0-element case.
>
> I don't know if that calculus has changed, but it seemed worth mentioning.

It seems worth keeping an eye on this. I'll let the Hotspot performance guys say 
whether megamorphic calls become an issue. At this point it seems like we're 
working on more fundamental optimizations, such as the stuff that Claes just pushed.

There is also some excess array copying that needs to be cleaned up, and the 
spliterators still need to be optimized....

If we were to try to reduce the implementations down to two, I'd say that we'd 
want a field-based implementation and an array-based implementation. Having a 
field-based implementation avoids a dependent load and a separate object header 
for the array. But the space savings of 0-field and 1-field classes over a 
2-field class aren't so large, so maybe these could be consolidated if warranted.

Fortunately :-) the APIs are designed so that we have complete freedom to 
rearrange the implementations compatibly in the future, as we get more 
information, or as the various space/performance tradeoffs change.

s'marks