ImmutableCollections.MapN optimisation ?

Remi Forax forax at univ-mlv.fr
Sat Jun 30 10:54:37 UTC 2018


Playing with the value types,
i've remarked that ImmutableCollections.MapN is missing an override for getOrDefault which making get() 2 times faster than getOrDefault on my test.

The other problem is more subtle, get() uses probe() and probe() uses an infinite loop and not a counted loop, the result is that c2 generates  lot of assembly codes for probe() as a consequence it doesn't inline probe() in get() making get() really slow compared to HashMap.get() which is fully inlined.
There are several wys to fix that:
- you can try to transform the while(true) loop in probe into 2 subsequents loops from idx to length + from 0 to idx.
- you can inline the code of probe() into get() and even peel the first loop body evaluation as HashMap.get() does.
- you can do both.
- your idea here :)

Also, i wonder if it's not better to make Map1 to also take cares of the zero case instead of making MapN to manage that case, because it's trading a size check with a null check and usually nullcheck can be removed by the VM.

regards,
Rémi



More information about the core-libs-dev mailing list