[Truffle] Loop count propagation

[Chris Seaton]

On 28 May 2014, at 14:21, Stefan Marr <java at stefan-marr.de> wrote:
> While skimming through your JRuby changes I saw something I haven’t noticed before:
> 
> Pass loop counts up to the first call target for a method that is not a block.
> https://github.com/jruby/jruby/commit/74934f06299f896170e37cd538c594f6dd27fb35
> 
> What’s the idea behind that change? I don’t know enough about the corresponding compiler heuristics, so, it is not directly obvious to me why you propagate the loop count up to the enclosing methods.

This change greatly improved warmup time and generated fewer compiled methods. I’ll illustrate using JavaScript, to avoid any confusion about Ruby or SmallTalk syntax and to make it more accessible to other people reading this:

The loop construct in Ruby is a method call that you pass a block to. It’s implemented like this:

function loop(body) {
    while (true) {
      body();
    }
}

And used like this:

function foo() {
  loop(function() {
    ...
  })
}

Normally Truffle would compile the function that I pass to loop after enough iterations, and then compile loop separately. It won’t compile foo unless that is called enough times. I’d prefer that it just compile foo straight away - if you had a JS-style while loop you wouldn’t just compile the body of the while loop, you’d compile the function that contained it, and this achieves the same thing, even though we have extra functions instead of statement blocks.

To achieve that I pass the loop count to the first root node that isn’t a block (an anonymous function, in JS terms). I also pass it to all blocks in between, in case they can be compiled but the outer function can’t.

> If a method has a high loop count, does it mean it gets more attention by the optimizer?
> Or is the idea to move the start point, for where and when to optimizer stars optimizing, up to the outer lexical scope to avoid optimizing only inner blocks? I guess, if that would happen, these inner blocks would access the outer lexical scope and thereby crossing the boundary between units of optimisation?

The idea is to move the starting point, as you say. There’s no tiered compilation in Graal (I believe) so it’s not about getting more attention, it’s just about what gets compiled.

Also, creating the block object to pass to loop involves allocating an object and often materialising a frame. If I start compilation at a point earlier on the call stack I’m likely to inline both loop and the anonymous function, optimising away the allocation of the object and the materialisation of the frame.

I don’t know how well this will apply to you, as you convert a call to while into a special while node, don’t you? So that means the loop count would already count for foo in your case I think? I don’t do that, so my call to loop and my call to the anonymous function are just normal calls for me and I need this special mechanism to pass the loop count up.

> Also, you added branch probability to your while nodes and if nodes, what kind of impact do you see for that?
> (one of the relevant commits was: Using CompilerDirectives.injectBranchProbability in the DoWhile nodes
> https://github.com/jruby/jruby/commit/3845bbb106313bf7c4b0624a7fe8ac71940708b4)

I can’t quantify any performance difference, but I just noticed they could be in there and put them in. At some point it might be a nice idea to turn off features and see what difference it makes. But I can tell you that when we wrote the DYLA paper we had to turn off BranchProfiles in IfNode because it was optimising away the breakpoint on our never-taken branch. You probably won’t find a benchmark that has dead code like that, so might be hard to illustrate.

A more important use is in core library methods. Here in the Array#[]= method (assigning to an index in an array) I have branch profiles for the cases where the index is at the end, or beyond the end. This is almost always not needed, so we can usually remove it via a BranchProfile.

https://github.com/jruby/jruby/blob/master/core/src/main/java/org/jruby/truffle/nodes/core/ArrayNodes.java#L616

Chris

> Thanks
> Stefan
> 
> -- 
> Stefan Marr
> INRIA Lille - Nord Europe
> http://stefan-marr.de/research/
> 
> 
>