ImmutableCollections.MapN optimisation ?

[John Rose]

On Jun 30, 2018, at 8:39 AM, Martin Buchholz <martinrb at google.com> wrote:
> 
>> On Sat, Jun 30, 2018 at 3:54 AM, Remi Forax <forax at univ-mlv.fr> wrote:
>> 
>> 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.
>> 
> 
> In ArrayDeque we had success transforming loops into 2 nested loops, the
> inner one being hotspot friendly, and it seems like the same approach would
> work for probe().
> E.g. look at ArrayDeque#contains

That was my thought too. Best case is that the JIT unrolls both levels of loop.  Test it though; YMMV.  

I like to make the outer loop iterate from false to true, as a style thing. When it unrolls you get two customized inner loops.

– John