Trace Compilation and Recursion, Part 1

TraceMonkey does really well at lots of benchmarks. Specifically, it does well at benchmarks that it can trace compile. If for some reason a loop contains a code path that cannot be traced, that path will never run inside the JIT – instead it stays in the interpreter, which is much slower.

There isn’t much left that we can’t trace, but when that happens, it lights up benchmarks in bad ways. One of the areas we don’t trace at all is recursion.

Recursion isn’t too common on the web but it’s still a big hole in our functionality, so I worked on it quite a bit this summer. Unfortunately it’s non-trivial, and still hasn’t landed, but I’d like to talk about what I do have working.

Quick Introduction

TraceMonkey uses trace trees. If some repetitive code is run, like a loop, a trace recorder kicks in. This records the behavior of the code for one iteration. If any behavior could diverge at runtime – such as an if branch – it becomes a “guard”, and we only record the observed path.

We assemble these observations into statically-typed, native CPU code. If a guard is triggered while running this new, faster code, it means the behavior has changed. We start recording a new path, and attach it to the point of divergence. Thus the code is literally a tree of traces.

Recursion is a Loop, Sort Of

Recursion is a loop, so we’d like to compile as such, using the behavior we observe at runtime. Let’s look at a simple recursive function and identify where it loops.

Select All Code:
function factorial(n) {
  if (n == 0)
    return 1;
  return n * factorial(n - 1);
}

What happens when you call factorial(10)? It starts off in the interpreter here:

Select All Code:
  if (n == 0)

n isn’t 0, so the indented path gets skipped.

Select All Code:
  return n * factorial(n - 1);

First n - 1 evaluates to 9. Then factorial() is called again, and we’re back at:

Select All Code:
  if (n == 0)

Bam. We’ve hit the same point, and thus identified a repeating pattern. To make sure it’s hot, the tracer recorder waits for one more iteration. Then it kicks in and starts recording the behavior it sees. Is (n == 0)? No, n is 8, so the tracer records:

Select All Code:
1: guard n != 0

Next, the trace compiler sees the n - 1 and function call and records those.

Select All Code:
2: subtract(n, 0x1)
3: add stack space (frame) for factorial call
4: n = result of instruction #2

Next the trace recorder sees if n == 0, which is where it started recording. It adds a “jump to the beginning” instruction and compiles the trace to native code. Visually it looks something like this:

Down recursion

But wait! That’s only “half” of the function. Specifically, it’s the down-recursive half, which dives deeper and deeper. What happens when we run this? The code will build a bunch of stack frames that look like this:

frame # variables
9 n = 0
8 n = 1
7 n = 2
6 n = 3
5 n = 4
4 n = 5
3 n = 6
2 n = 7
1 n = 8

When n == 0, the guard fails. This is really nasty. It turns out the JIT and interpreter have completely different ways of representing stack frames, and when transferring control the frames must be converted from one to the other. Locally, this process is really expensive. As you can imagine it is disastrous for deeply recursive functions. The only way to fully mitigate this is to make sure we spend more time in the JIT. Ideally, we never want to reconstruct any frames.

Upwards Recursion

But back to what happens. n == 0, the guard has triggered, and we’re back in the interpreter. The recorder only wants to observe hot code, so it doesn’t record the path from the guard yet. Now we see this get executed:

Select All Code:
  if (n == 0)
    return 1;

Remember, we’re at frame #9 from the diagram above. The “return” instruction pops us to frame #8, and now we’re at:

Select All Code:
  return n * (result of factorial(n - 1));

This returns 1 * 1 to the calling function, and now we’re at:

Select All Code:
  return n * (result of factorial(n - 1));

We’re back at the same place! That’s a loop. This time 2 * 1 is multiplied to return 2. The trace recorder kicks in and starts recording from frame #6, but hits a snag: it sees a return, but hasn’t recorded a matching function call for this trace. This is where things get weird. How can it observe a return if it doesn’t know anything about frame #5?

It can’t. That’s sad, but we really want to solve this. If the JIT can unwind its own recursive frames, we won’t hit that expensive synthesizing path. The trick is to infer some uniquely identifying information about frame 5: its variable’s types and program counter. We guard on that identity. If that guard fails at runtime, we know that it is illegal to keep popping frames.

The resulting trace looks like this:

Upwards recursion

Linking the Two Halves

Hopefully, the down-recursive side will be run again. When the n == 0 guard hits, it will be “hot”, and the recorder starts up. This time it notices the “return”, looks at the above frame, and recognizes that recursion is unwinding. It links the two traces together like so:

Recursion, linked together

Beautiful! Except for…

Next Time

There are still problems with this approach. The major one is that by the time the up-recursive frame is built, all of the frames exist on the interpreter – not the JIT. When control transfers from the interpreter to the JIT, only one frame is converted because the process is very expensive.

That means the first up-recursive guard will hit, since there are no more JIT frames. We’ll do the expensive reconstruction process on the same frame, transfer it back to the interpreter, then re-enter the interpreter. This will happen for each frame until the recursion is unwound, all to execute a few multiplies!

That’s REALLY bad. To make things worse, this whole process will happen at least twice. The first time is to unwind the initial down recursion. The next time is because the n == 0 guard fails, and all the frames are popped off the JIT and transferred to the interpreter again. Everything only runs smoothly on the third invocation of the recursion function.

Next time I’ll discuss approaches to solving that situation.

23 thoughts on “Trace Compilation and Recursion, Part 1

  1. Valery

    “Next time I’ll discuss approaches to solving that situation.”

    could you tell a post number, please? :)
    PyPy guys might want to look into it

    Reply
    1. dvander Post author

      Hi Valery,

      I never managed to write that post, unfortunately. For what it’s worth, all the trace recursion code has since been deleted (by my own hands) from TraceMonkey. It was a difficult problem to solve in our engine and whole-method JITing was both faster and much simpler.

      I have talked to the PyPy guys about it and they told me it wasn’t a big concern since Python programs tend to not be recursive. If people are really interested though, I can brain dump into a new article :)

      Reply
  2. Tresa Wempe

    My husband and i were really fulfilled Louis could carry out his homework via the precious recommendations he acquired from your own weblog. It’s not at all simplistic just to always be giving out key points which often some others might have been selling. We really see we have got the writer to thank because of that. Those illustrations you have made, the simple blog navigation, the relationships you aid to instill – it is many spectacular, and it’s leading our son in addition to our family know that that content is entertaining, and that is rather indispensable. Thanks for all the pieces!

    Reply
  3. Porsche Interiano

    What i really don’t understood is basically how you’re going to be not actually way more nicely-liked than you could be now. You happen to be so intelligent. You realize therefore considerably relating to this topic, created me personally consider it from a good deal of varied angles. Its like women and men aren’t fascinated until it’s 1 point to do with Lady gaga! Your individual stuffs wonderful. Continually keep it up!

    Reply
  4. Buford Warholic

    erfahrungen mit apcalis oral jelly kamagra oral jelly 100mg forum kamagra oral jelly cvs kamagra oral jelly effects kamagra oral jelly auf rechnung kaufen kamagra oral jelly tadalafil apcalis sx review

    Reply
  5. Jimmy

    Gracias por poner a nuestra disposición este material. Voy a utilizarlo para mi aprendizaje porque me ha parecido de muy buen nivel.

    Reply
  6. Vince

    Después de ver este post, lo recomendaré, porque es coherente y muy informativo. Ojalá continues escribiendo más material relacionado con este tema.

    Reply
  7. Troy Bristow

    I’ve been exploring for a little bit for any high quality articles or weblog posts on this kind of house . Exploring in Yahoo I at last stumbled upon this web site. Reading this information So i’m glad to express that I have an incredibly excellent uncanny feeling I found out exactly what I needed. I such a lot indubitably will make certain to don’t disregard this web site and give it a glance regularly.

    Reply
  8. Entertainer eCommerce

    Hey very nice site!! Man .. Excellent .. Amazing .. I’ll bookmark your website and take the feeds also…I am happy to find a lot of useful information here in the post, we need develop more techniques in this regard, thanks for sharing. . . . . .

    Reply
  9. Martha Gramling

    Quite wonderful short article, precisely just what I required. Quite useful post i really be conscious of thanks for sharing such a wonderful post. I wan na because of a great extent for providing such useful and also qualitative material for that reason commonly.

    Reply
  10. Britany Hurta

    First You obtained a excellent blog.I will definitely have an interest in additional identical subject matters. i see you received truly very helpful subjects, i will be constantly examining your blog many thanks.

    Reply
  11. Laronda Laehn

    It is terrific to have the opportunity to check out a good quality post with beneficial info on subjects that plenty are interested on.I concur with your conclusions and will eagerly anticipate your future updates.

    Reply
  12. website

    You could certainly see your enthusiasm in the work you
    write. The arena hopes for more passionate writers such as you who are not afraid to mention how they
    believe. Always go after your heart.

    Reply

Leave a Reply

Your email address will not be published.