[OPTIMIZATION] Objects from methods that return 3 or more possible runtime-types optimize very poorly

[techsy730]

Something discovered when optimizing Guava is that Hotspot (OpenJDK's virtual machine) optimizes megamorphic variables/returns (those that could be 3 or more different runtime types) far worse then it does mono or dimorphic ones (1 or 2 different implementations). Sometimes by factors in the double digits. (https://github.com/google/guava/issues/1268)

As such, we should avoid static utility methods that can return potentially 3 or more different implementations.

This may (or may not) be better in newer JVMs, but in Java 8, the one we are targeting, it is absolutely an issue.

[vigna]

Mmmmhhh... I think there are a lot of those. Like, the various .of() methods which optimize for an empty set, a singleton, etc.

[techsy730]

There are two offenders that immediately come to mind

• The of static factories from the root interfaces (List.of(...), etc) (Ninja'd!)
• The wrappers of Iterator/Spliterator in Iterators/Spliterators converting to primitive ones from object based ones (e.g. asIntIterator)

[techsy730]

The of methods can be resolved by having the empty case return a "well known" empty instance of the kind the varargs one returns. Such as ImmutableList.EMPTY instead of Lists.EMPTY for List.of().

The Iterators case will probably require me to flatten the class hierarchy, pulling the instanceof into IteratorWrapper instead of having a subclass of it. (would want to measure this impact)

[vigna]

Yeah, I thought about that. We can have an immutable empty list exposed directly by ImmutableList. I'm writing that.

[techsy730]

I've already done that in https://github.com/vigna/fastutil/pull/180 https://github.com/vigna/fastutil/pull/180/commits/27882c39c44ae46f4aad193a0cf6eaec55ceae34

[vigna]

Great! :) I'm still finding unused classes like

PrimitiveSpliteratorWrapperWithComparator

in ByteSpliterators.

[techsy730]

Oops, I missed those. Forgot to check the shorter types' warnings. I'll fix those

[techsy730]

List.of and Set.of are the most important.

Iterators.asXIterator and its cousin Spliterators.asXSpliterator are still an issue. However, the performance loss only happens if three or more returns of different types actually happen in a program run, not by merely being possible in the bytecode. And I can't imagine that many programs will trigger all three paths. Still should be looked at but less important.

[techsy730]

Specifically, the problem is the method that takes an Object based iterator and wraps it as a Fastutil primitive iterator (same for spliterator)

I should try to measure which of these harms performance the least:

1. The current status quo (megamorphic return)
2. Moving the instanceof check into the nextInt() method
3. Not trying to handle a JDK PrimitiveIterator at all and just have that go through that box/unbox process as well even though we could avoid it
4. Removing the API assurance that a Fastutil PrimitiveIterator goes through unchanged, and wrap it (with an instanceof check in next, forwarding if it is a fastutil one)

[vigna]

I think we can consider this done, right?

[techsy730]

Not quite. There is still the case.

• The wrappers of Iterator/Spliterator in Iterators/Spliterators converting to primitive ones from object based ones (e.g. asIntIterator).

But that is a pretty niche usage and I don't think it is worth blocking 8.5.0 over.

[vigna]

OK, I'll leave this open then.