Tuesday, March 10, 2009

How Firefox 3.1 Uses Trace Trees to Optimize Javascript Runtimes

Version 3.1 of Firefox should be a pretty marked improvement for Javascript performance because of a compilation optimization that the Firefox team is putting in place for that release. Trace-based compilation identifies loops, and records frequently visited paths within those loops to determine what needs to be compiled.

Traditional Just-In-Time compilation usually happens at the method/function level, where the need for compilation is simply determined by whether or not the function/method has been visited. When a function is visited for the first time, the control flow graph for the entire function is created, then compiled into the proper instruction set. This could cause quite a bit of unnecessary overhead given the way that Javascript applications are delivered via the internets.

With trace compilation, the compiler first determines the loop headers, since most frequently called code usually exists within a loop. To determine loop headers, the compiler keeps a counter of back branches (ones that send control back to a previous location), and once that counter hits a certain threshold, that is identified as a "hot" trace. Subsequent paths starting at that loop header are then recorded and compiled.

In this scheme, the interpreter and the compiler are handing control back and forth to each other, which itself can be somewhat expensive. However, all along the way, whenever interpretation of a branch is occurring within these "hot" traces, the recorder is keeping track and compiling the alternate paths.

There's a bunch more information on this method of compilation, including information that's specific to TraceMonkey implementation.