TraceMonkey概要
この記事は、http://hacks.mozilla.org/2009/07/tracemonkey-overview/の無許可日本語訳です。
Firefox 3.5 has a new JavaScript engine, TraceMonkey, that runs many JavaScript programs 3-4x faster than Firefox 3, speeding up existing web apps and enabling new ones. This article gives a peek under the hood at the major parts of TraceMonkey and how they speed up JS. This will also explain what kinds of programs get the best speedup from TraceMonkey and what kinds of things you can do to get your program to run faster.
Firefox 3.5は新しいJavaScriptエンジン、TraceMonkeyを持っています。これは多くのJavaScriptのプログラムをFirefox 3よりも3倍から4倍速く実行します。既存のウェブアプリケーションを高速にし、新しいウェブアプリケーションを可能にします。この記事は、TraceMonkeyの主要なパーツにある目隠しの下を覗き見し、どうやってJavaScriptの速度を速めているのかをみます。また、TraceMonkeyによってどのようなプログラムがもっとも速度を速められ、プログラムをより速くするために何ができるのか説明します。
JavaScriptを速くするのはなぜ難しいのか: 動的型付け
High-level dynamic languages such as JavaScript and Python make programming more productive, but they have always been slow compared to statically typed languages like Java or C. A typical rule of thumb was that a JS program might be 10x slower than an equivalent Java program.
JavaScriptやPythonのような高レベル動的言語はプログラムをより生産性の高いものにしますが、これらはJavaやCのような静的型付け言語と比較して常に遅いです。典型的には、経験的に、JavaScriptのプログラムは同等のJavaのプログラムより10倍遅いです。
There are two main reasons JS and other dynamic scripting languages usually run slower than Java or C. The first reason is that in dynamic languages it is generally not possible to determine the types of values ahead of time. Because of this, the language must store all values in a generic format and process values using generic operations.
JavaScriptやその他の動的型付けスクリプト言語が通常、JavaやCより遅いことには、2つの理由があります。ひとつ目は、動的型付け言語では一般的に事前に値の型を決定することができないためです。これにより、言語はすべての値を一般的な形式で保存し、一般的な命令で値を処理しなければなりません。
In Java, by contrast, the programmer declares types for variables and methods, so the compiler can determine the types of values ahead of time. The compiler can then generate code that uses specialized formats and operations that run much faster than generic operations. I will call these type-specialized operations.
対照的にJavaでは、プログラマは変数とメソッドの型を宣言するので、コンパイラは事前に値の型を決定できます。コンパイラは、一般的な命令よりとても速く動作する、特化した形式と命令を使用するコードを生成できます。私はこれらを「型に特化した」命令と呼びます。
The second main reason that dynamic languages run slower is that scripting languages are usually implemented with interpreters, while statically typed languages are compiled to native code. Interpreters are easier to create, but they incur extra runtime overhead for tracking their internal state. Languages like Java compile to machine language, which requires almost no state tracking overhead.
動的言語が遅く動作するふたつ目の主な理由は、静的型付け言語がネイティブコードにコンパイルされるのに対し、スクリプト言語が通常インタプリタとして実装される、という点にあります。インタプリタはつくるのが簡単ですが、内部の状態を追跡するために実行時に余計なオーバーヘッドがかかります。Javaのような言語は機械語にコンパイルされますが、これは状態を追跡するオーバーヘッドがほとんど必要ありません。
Let’s make this concrete with a picture. Here are the slowdowns in picture form for a simple numeric add operation: a + b, where a and b are integers. For now, ignore the rightmost bar and focus on the comparison of the Firefox 3 JavaScript interpreter vs. a Java JIT. Each column shows the steps that have to be done to complete the add operation in each programming language. Time goes downward, and the height of each box is proportional to the time it takes to finish the steps in the box.
これを絵で具体的にしましょう。簡単な数値の加算命令: a + b（ここでaとbは整数です）の速度低下を示します。いま、 右端の棒は無視し、Firefox 3 JavaScriptインタプリタとJava JITの比較に注目します。各カラムは、各言語で加算命令を完了するのに必要なステップです。時間は下に向かって流れており、それぞれの箱の高さは、各項目のステップを完了するのに必要な時間に比例します。
In the middle, Java simply runs one machine language add instruction, which runs in time T (one processor cycle). Because the Java compiler knows that the operands are standard machine integers, it can use a standard integer add machine language instruction. That’s it.
真ん中では、Javaは単純にひとつの機械語の加算命令を実行し、これは時間T（1プロセッササイクル）で完了します。Javaのコンパイラはオペランドが標準的な機械の整数であることを知っているので、標準的な整数の加算の機械語を使用できます。
On the left, SpiderMonkey (the JS interpreter in FF3) takes about 40 times as long. The brown boxes are interpreter overhead: the interpreter must read the add operation and jump to the interpreter’s code for a generic add. The orange boxes represent extra work that has to be done because the interpreter doesn’t know the operand types. The interpreter has to unpack the generic representations of a and i, figure out their types, select the specific addition operation, convert the values to the right types, and at the end, convert the result back to a generic format.
図の左では、Firefox 3のJavaScriptインタプリタであるSpiderMonkeyが40倍の時間を要しています。茶色の四角は、インタプリタのオーバーヘッドです。インタプリタは加算命令を読み込み、一般的な加算のコードにジャンプする必要があります。橙色の四角は、インタプリタがオペランドの型を知らないために必要になる余計な仕事です。インタプリタはaとbの一般的な表現をアンパックし、その型を調べ、ふさわしい加算命令を選択し、正しい型に値を変換し、最後に計算結果を一般的な型に戻さなければなりません。
The diagram shows that using an interpreter instead of a compiler is slowing things down a little bit, but not having type information is slowing things down a lot. If we want JS to run more than a little faster than in FF3, by Amdahl’s law, we need to do something about types.
この図は、コンパイラの代わりにインタプリタを使うだけでなく、型情報を持つことで遅くなることを示しています。もしFirefox 3よりもJavaScriptを速くしようと思ったら、Amdahlの法則により、型をなんとかする必要があります。
トラッキングによって型を得る
Our goal in TraceMonkey is to compile type-specialized code. To do that, TraceMonkey needs to know the types of variables. But JavaScript doesn’t have type declarations, and we also said that it’s practically impossible for a JS engine to figure out the types ahead of time. So if we want to just compile everything ahead of time, we’re stuck.
TraceMonkeyにおける我々のゴールは、型に特化したコードにコンパイルすることです。このため、TraceMonkeyは変数の型を知る必要があります。しかしJavaScriptは型宣言を持たないため、型を事前に調べることは実際は不可能です。そのため、すべてを事前にコンパイルしようとしたら、はまります。
So let’s turn the problem around. If we let the program run for a bit in an interpreter, the engine can directly observe the types of values. Then, the engine can use those types to compile fast type-specialized code. Finally, the engine can start running the type-specialized code, and it will run much faster.
そこで問題を逆さにしてみましょう。もしプログラムが一度インタプリタで実行されたら、エンジンは値の型を直接観察できます。そして、エンジンはその型を使って型に特化した速いコードをコンパイルできます。最後にエンジンは型に特化したコードを実行し始め、より速くなります。
There are a few key details about this idea. First, when the program runs, even if there are many if statements and other branches, the program always goes only one way. So the engine doesn’t get to observe types for a whole method — the engine observes types through the paths, which we call traces, that the program actually takes. Thus, while standard compilers compile methods, TraceMonkey compiles traces. One side benefit of trace-at-a-time compilation is that function calls that happen on a trace are inlined, making traced function calls very fast.
このアイデアには、細かい点がいくつかあります。まず、プログラムが実行されたとき、そこに多数のif文やその他の分岐があったとしても、プログラムはたった一通りしか実行されません。そのため、エンジンはメソッド全体に対して型を観察できません -- プログラムが実際に通るパス（これをトレースと呼んでいます）を通して、エンジンは型を観察します。このため、標準的なコンパイラはメソッドをコンパイルしますが、TraceMonkeyはトレースをコンパイルします。トレースしてコンパイルする利点は、トレース中の関数呼び出しをインライン化でき、関数呼び出しをとても高速にできることです。
Second, compiling type-specialized code takes time. If a piece of code is going to run only one or a few times, which is common with web code, it can easily take more time to compile and run the code than it would take to simply run the code in an interpreter. So it only pays to compile hot code (code that is executed many times). In TraceMonkey, we arrange this by tracing only loops. TraceMonkey initially runs everything in the interpreter, and starts recording traces through a loop once it gets hot (runs more than a few times).
ふたつ目として、型に特化したコードをコンパイルするのには時間がかかるという点です。コードが1回か数回しか実行されないと（ウェブではよくあります）、コードをコンパイルして実行するのは、単純にインタプリタが実行するよりも、多くの時間が必要になることでしょう。そのため、採算が取れるのは、ホットなコード（たくさん実行されるコード）をコンパイルすることだけです。TraceMonkeyでは、繰り返しのみをトレースすることで調節しました。TraceMonkeyは最初はインタプリタで実行しますが、ループが一旦ホットになったら（数回実行されたたら）、トレースを記録し始めます。
Tracing only hot loops has an important consequence: code that runs only a few times won’t speed up in TraceMonkey. Note that this usually doesn’t matter in practice, because code that runs only a few times usually runs too fast to be noticeable. Another consequence is that paths through a loop that are not taken at all never need to be compiled, saving compile time.
ホットなループをトレースするのは、重要な結論です: TraceMonkeyでは数回しか実行されないコードは、速くなりません。実際にはこれは問題になりません。なぜならば、数回しか実行されないコードは速くて目立たないからです。また、コンパイルする時間を節約するため、1回のループで通るパスはまったくコンパイルされません。
Finally, above we said that TraceMonkey figures out the types of values by observing execution, but as we all know, past performance does not guarantee future results: the types might be different the next time the code is run, or the 500th next time. And if we try to run code that was compiled for numbers when the values are actually strings, very bad things will happen. So TraceMonkey must insert type checks into the compiled code. If a check doesn’t pass, TraceMonkey must leave the current trace and compile a new trace for the new types. This means that code with many branches or type changes tends to run a little slower in TraceMonkey, because it takes time to compile the extra traces and jump from one to another.
最後に、TraceMonkeyは実行を観察することで値の型を調査しますが、以前のパフォーマンスを将来も保証しません: 次に、あるいは500回あとでコードが実行されるとき、型は違っているかもしれないからです。そして数値用にコンパイルされたコードを実行するとき、実際の値が文字列だったら、とても悪いことが起こります。そのためTraceMonkeyはコンパイルしたコードに型検査を挿入しなければなりません。もし型検査に合格しなかったら、TraceMonkeyは現在のトレースを無視し、新しい型の新しいトレースをコンパイルしなければなりません。これは、たくさんの分岐や型の変更があるコードは、TraceMonkeyでは遅くなるということです。なぜならば、別のトレースをコンパイルして、もう一方にジャンプするのに時間が必要だからです。
実際のTraceMonkey
Now, we’ll show tracing in action by example on this sample program, which adds the first N whole numbers to a starting value:
では、簡単なプログラムで実際のトレースの例をお見せします。このプログラムは、最初のN個の番号を最初の値に加算します。
function addTo(a, n) { for (var i = 0; i < n; ++i) a = a + i; return a; } var t0 = new Date(); var n = addTo(0, 10000000); print(n); print(new Date() - t0);
TraceMonkey always starts running the program in the interpreter. Every time the program starts a loop iteration, TraceMonkey briefly enters monitoring mode to increment a counter for that loop. In FF3.5, when the counter reaches 2, the loop is considered hot and it’s time to trace.
TraceMonkeyはまずインタプリタで実行します。プログラムがループの繰り返しを始めるとき、TraceMonkeyはこのループのカウンタを増やすモニタリングモードに、少しの間だけ入ります。Firefox 3.5では、このカウンタが2になったら、このループはホットであり、トレースするときであるとみなされます。
Now TraceMonkey continues running in the interpreter but starts recording a trace as the code runs. The trace is simply the code that runs up to the end of the loop, along with the types used. The types are determined by looking at the actual values. In our example, the loop executes this sequence of JavaScript statements, which becomes our trace:
いまTraceMonkeyはインタプリタで実行しつづけますが、トレースを記録し始めます。このトレースは単純に、ループの最後で終了する使用された型の情報を持つコードです。型は実際の値を調査して決定されます。我々の例では、このループはJavaScriptの文を実行し、以下のようになります:
a = a + i; // a is an integer number (0 before, 1 after) ++i; // i is an integer number (1 before, 2 after) if (!(i < n)) // n is an integer number (10000000) break;
That’s what the trace looks like in a JavaScript-like notation. But TraceMonkey needs more information in order to compile the trace. The real trace looks more like this:
トレースはJavaScriptのような注意書きに見えます。しかしTraceMonkeyはトレースをコンパイルするのにもっと情報が必要です。実際のトレースは以下のようになります:
trace_1_start:
++i; // i is an integer number (0 before, 1 after)
temp = a + i; // a is an integer number (1 before, 2 after)
if (lastOperationOverflowed())
exit_trace(OVERFLOWED);
a = temp;
if (!(i < n)) // n is an integer number (10000000)
exit_trace(BRANCHED);
goto trace_1_start;
This trace represents a loop, and it should be compiled as a loop, so we express that directly using a goto. Also, integer addition can overflow, which requires special handling (for example, redoing with floating-point addition), which in turn requires exiting the trace. So the trace must include an overflow check. Finally, the trace exits in the same way if the loop condition is false. The exit codes tell TraceMonkey why the trace was exited, so that TraceMonkey can decide what to do next (such as whether to redo the add or exit the loop). Note that traces are recorded in a special internal format that is never exposed to the programmer — the notation used above is just for expository purposes.
このトレースはループを表しており、ループとしてコンパイルされなければならず、そのためgotoを直接使ってこれを表現します。また、整数の加算はオーバーフローするかもしれないので、これに対処するために特別な処理が必要で（たとえば、浮動小数点の加算を再実行する）、このときトレースを終了する必要があります。そのためトレースにはオーバーフローチェックが含まれます。最後に、ループの条件がfalseになったときと同じ方法でトレースは終了します。終了コードによって、TraceMonkeyはトレースがなぜ終了したかが分かります。そのためTraceMonkeyは次に何をするのか決定できます（加算をもう一度実行するのか、ループを終了するのか）。トレースは、特殊な内部形式で記録され、プログラマには公開されません -- 上の注意書きは単に説明のためです。
After recording, the trace is ready to be compiled to type-specialized machine code. This compilation is performed by a tiny JIT compiler (named, appropriately enough, nanojit) and the results are stored in memory, ready to be executed by the CPU.
記録した後、トレースは型に特化された機械語にコンパイルされることができます。このコンパイルは小さいJITコンパイラ（nanojitという名前です）が実行します。そして結果はメモリの保存され、CPUが実行できるようになります。
The next time the interpreter passes the loop header, TraceMonkey will start executing the compiled trace. The program now runs very fast.
インタプリタが次にループの先頭を通過するとき、TraceMonkeyがコンパイルされたトレースを実行するようになります。今度は、プログラムはとても速く実行されます。
On iteration 65537, the integer addition will overflow. (2147450880 + 65537 = 2147516417, which is greater than 2^31-1 = 2147483647, the largest signed 32-bit integer.) At this point, the trace exits with an OVERFLOWED code. Seeing this, TraceMonkey will return to interpreter mode and redo the addition. Because the interpreter does everything generically, the addition overflow is handled and everything works as normal. TraceMonkey will also start monitoring this exit point, and if the overflow exit point ever becomes hot, a new trace will be started from that point.
65537回目の繰り返しのとき、整数の加算はオーバーフローします（2147450880 + 65537 = 2147516417, これは32ビット整数の最大値の2^31-1 = 2147483647より大きいです）。このとき、トレースはOVERFLOWEDで終了します。これを見ると、TraceMonkeyはインタプリタに戻り、加算を再実行します。インタプリタはすべてを一般的に実行するため、加算におけるオーバーフローは適切に扱われ、すべては通常と同様に動作します。TraceMonkeyはこの終了した時点でモニタリングモードを開始し、もしオーバーフローで終了した個所がホットになったら、新しいトレースが開始されます。
But in this particular program, what happens instead is that the program passes the loop header again. TraceMonkey knows it has a trace for this point, but TraceMonkey also knows it can’t use that trace because that trace was for integer values, but a is now in a floating-point format. So TraceMonkey records a new trace:
しかしこのプログラムでは、代わりに起きるのはプログラムがループの先頭を実行することです。TraceMonkeyは、この点のトレースを持っていることを知っていますが、このトレースが整数のためのものであるものの、aが現在は不動小数点数であるため、このトレースは使用できないことも知っています。そのためTraceMonkeyは新しいトレースを記録します:
trace_2_start:
++i; // i is an integer number
a = a + i; // a is a floating-point number
if (!(i < n)) // n is an integer number (10000000)
exit_trace(BRANCHED);
goto trace_2_start;
TraceMonkey then compiles the new trace, and on the next loop iteration, starts executing it. In this way, TraceMonkey keeps the JavaScript running as machine code, even when types change. Eventually the trace will exit with a BRANCHED code. At this point, TraceMonkey will return to the interpreter, which takes over and finishes running the program.
TraceMonkeyはそして新しいトレースをコンパイルし、次のループの繰り返しではこれを実行します。この方法では、TraceMonkeyは、型が変わった場合でも、JavaScriptが機械語を実行できるようにします。最終的には、このトレースはBRANCHEDで終了します。この時点において、TraceMonkeyはインタプリタに戻り、プログラムは終了します。
Here are the run times for this program on my laptop (2.2GHz MacBook Pro):
私のラップトップ (2.2GHz MacBook Pro) における、このプログラムの実行時間は、以下の通りです。
| System | Run Time (ms) |
|---|---|
| SpiderMonkey (FF3) | 990 |
| TraceMonkey (FF3.5) | 45 |
| Java (using int) | 25 |
| Java (using double) | 74 |
| C (using int) | 5 |
| C (using double) | 15 |
This program gets a huge 22x speedup from tracing and runs about as fast as Java! Functions that do simple arithmetic inside loops usually get big speedups from tracing. Many of the bit operation and math SunSpider benchmarks, such bitops-3bit-bits-in-byte, ctrypto-sha1, and math-spectral-norm get 6x-22x speedups.
このプログラムは22倍速くなり、Javaとだいたい同じくらい速いです! 内部のループで単純に計算する関数は、とても速くなります。多くのビット演算と、bitops-3bit-bits-in-byte, ctrypto-sha1とmath-spectral-normのような数学のSunSpiderベンチマークは、6倍から22倍ほど速くなります。
Functions that use more complex operations, such as object manipulation, get a smaller speedup, usually 2-5x. This follows mathematically from Amdahl’s law and the fact that complex operations take longer. Looking back at the time diagram, consider a more complex operation that takes time 30T for the green part. The orange and brown parts will still be about 30T together, so eliminating them gives a 2x speedup. The SunSpider benchmark string-fasta is an example of this kind of program: most of the time is taken by string operations that have a relatively long time for the green box.
オブジェクトの操作といったもっと複雑な命令を使用する関数は、より控えめに速くなり、2倍から5倍です。これは、Amdahlの法則と、複雑な命令は長くかかるという事実に数学的に従います。時間の図に戻ると、緑の部分で30Tかかるもっと複雑な命令を考えて下さい。オレンジと茶色の部分は依然ともに30Tですので、これらをなくすと2倍のスピードアップになります。SunSpiderベンチマークのstring-fastaはこういった種類のプログラムの例です: 時間のほとんどは文字列の操作で取られ、文字列の操作というのは緑の四角で比較的長時間かかります。
Here is a version of our example program you can try in the browser:
ウェブブラウザで試せるプログラムの例がここにあります:
（省略）
性能の問題を理解し、解決する
Our goal is to make TraceMonkey reliably fast enough that you can write your code in the way that best expresses your ideas, without worrying about performance. If TraceMonkey isn’t speeding up your program, we hope you’ll report it as a bug so we can improve the engine. That said, of course, you may need your program to run faster in today’s FF3.5. In this section, we’ll explain some tools and techniques for fixing performance of a program that doesn’t get a good (2x or more) speedup with the tracing JIT enabled. (You can disable the jit by going to about:config and setting the pref javascript.options.jit.content to false.)
我々のゴールは、TraceMonkeyを、性能に関して心配することなく、あなたのアイデアを最もよく表現する方法でコードを書けるように信頼できるほど充分早くすることです。もしTraceMonkeyがあなたのプログラムを高速にしなかったら、バグとして報告してください。そうすれば我々はエンジンを改良できます。もちろん、プログラムを今日のFirefox 3.5で高速に実行する必要があるかもしれません。この節では、tracing JITが有効になっているのに（2倍以上）高速にならないプログラムの性能を改善するためのツールとテクニックについて説明します（JITは、about:configを表示してjavascript.options.jit.contentをfalseにすることで無効にできます）。
The first step is understanding the cause of the problem. The most common cause is a trace abort, which simply means that TraceMonkey was unable to finish recording a trace, and gave up. The usual result is that the loop containing the abort will run in the interpreter, so you won’t get a speedup on that loop. Sometimes, one path through the loop is traced, but there is an abort on another path, which will cause TraceMonkey to switch back and forth between interpreting and running native code. This can leave you with a reduced speedup, no speedup, or even a slowdown: switching modes takes time, so rapid switching can lead to poor performance.
最初にすることは、問題の原因を把握することです。最もよくある原因は、トレースの中断です。これは、TraceMonkeyがトレースを完了できなかったという意味です。通常の結果は、中断を含むループはインタプリタで実行されるので、そのループでは高速になりません。時折、そのループでひとつのパスがトレースされますが、他のパスで中断され、そのためTraceMonkeyがインタプリタとネイティブコードの間を行ったり来たりします。これにより速度が低くなることさえあります: モードの切り替えには時間がかかり、早い切り替えはプログラムを低速にします。
With a debug build of the browser or a JS shell (which I build myself – we don’t publish these builds) you can tell TraceMonkey to print information about aborts by setting the TMFLAGS environment variable. I usually do it like this:
ブラウザのデバッグビルドかJavaScriptシェル（自分でビルドしました -- これらを公開しません）で、TMFLAGS環境変数を設定することで、中断の情報を表示するようにTraceMonkeyに指示できます。私はこのようにします:
TMFLAGS=minimal,abort dist/MinefieldDebug.app/Contents/MacOS/firefox
The minimal option prints out all the points where recording starts and where recording successfully finishes. This gives a basic idea of what the tracer is trying to do. The abort option prints out all the points where recording was aborted due to an unsupported construct. (Setting TMFLAGS=help will print the list of other TMFLAGS options and then exit.)
minimalオプションは、記録が開始されたときと、記録が成功裡に完了したときを表示します。これによりトレーサが何をしようとしているか基本的なところが分かるようになります。中断すると、サポートされていない構成によって記録が中断したすべてのときを表示します（TMFLAGS=helpにすると、他のTMFLAGSのオプションのリストを表示し、終了します）。
(Note also that TMFLAGS is the new way to print the debug information. If you are using a debug build of the FF3.5 release, the environment variable setting is TRACEMONKEY=abort.)
（TMFLAGSがデバッグ情報を表示する新しい方法であることも、記しておきます。もしFirefox 3.5のデバッグビルドを使っているのなら、環境変数はTRACEMONKEY=abortです）
Here’s an example program that doesn’t get much of a speedup in TraceMonkey.
以下は、TraceMonkeyで高速にならないプログラムの例です。
function runExample2() { var t0 = new Date; var sum = 0; for (var i = 0; i < 100000; ++i) { sum += i; } var prod = 1; for (var i = 1; i < 100000; ++i) { eval("prod *= i"); } var dt = new Date - t0; document.getElementById(example2_time').innerHTML = dt + ' ms'; }
（略）
If we set TMFLAGS=minimal,abort, we’ll get this:
TMFLAGS=minimal,abortにしたら、以下のようになります:
Recording starting from ab.js:5@23 recording completed at ab.js:5@23 via closeLoop Recording starting from ab.js:5@23 recording completed at ab.js:5@23 via closeLoop Recording starting from ab.js:10@63 Abort recording of tree ab.js:10@63 at ab.js:11@70: eval. Recording starting from ab.js:10@63 Abort recording of tree ab.js:10@63 at ab.js:11@70: eval. Recording starting from ab.js:10@63 Abort recording of tree ab.js:10@63 at ab.js:11@70: eval.
The first two pairs of lines show that the first loop, starting at line 5, traced fine. The following lines showed that TraceMonkey started tracing the loop on line 10, but failed each time because of an eval.
最初の2組は、最初のループが5行目で始まり、トレースに成功したことを示します。続く行は、TraceMonkeyが10行目のループをトレースし始め、しかしevalによって失敗したことを示します。
An important note about this debug output is that you will typically see some messages referring to inner trees growing, stabilizing, and so on. These really aren’t problems: they usually just indicate a delay in finishing tracing a loop because of the way TraceMonkey links inner and outer loops. And in fact, if you look further down the output after such aborts, you will usually see that the loops eventually do trace.
このデバッグ表示で重要なのは、育ったり安定化したりしている内部のツリーを参照するメッセージが典型的に見られるということです。これらは問題ではありません: これらは通常、TraceMonkeyが内部と外部のループを繋げるので、ループのトレースを完了するときの遅れを示すものです。実際、もしあなたがこれらの中断以降の表示を見たら、ループは結局トレースしていることを見るでしょう。
Otherwise, aborts are mainly caused by JavaScript constructs that are not yet supported by tracing. The trace recording process is easier to implement for a basic operation like + than it is for an advanced feature like arguments. We didn’t have time to do robust, secure tracing of every last JavaScript feature in time for the FF3.5 release, so some of the more advanced ones, like arguments, aren’t traced in FF3.5.0. Other advanced features that are not traced include getters and setters, with, and eval. There is partial support for closures, depending on exactly how they are used. Refactoring to avoid these constructs can help performance.
あるいは、中断はJavaScriptの構造の結果であり、これはトレースによってまだサポートされていません。プロセスを記録するトレースは+のような基本的な演算については簡単に実装できますが、引数のような高度な特徴については難しいです。我々には時間がなくて、Firefox 3.5においてすべての最新のJavaScriptの特徴について、強固でセキュアなトレーシングをする時間がなく、引数のような高度な機能は、Firefox 3.5.0ではトレースされません。トレースされない他の高度な機能としては、ゲッタとセッタ、withとevalがあります。クロージャは部分的にサポートされ、どれくらい使用されているかに依存します。これらの構成要素を回避するようにリファクタリングすれば、性能が向上するかもしれません。
Two particularly important JavaScript features that are not traced are:
トレースされない、ふたつの重要なJavaScriptの機能があります:
- Recursion. TraceMonkey doesn’t see repetition that occurs through recursion as a loop, so it doesn’t try to trace it. Refactoring to use explicit for or while loops will generally give better performance.
- Getting or setting a DOM property. (DOM method calls are fine.) Avoiding these constructs is generally impossible, but refactoring the code to move DOM property access out of hot loops and performance-critical segments should help.
- 再帰。ループとしての再帰を通して発生する繰り返しを、TraceMonkeyは見ません。そのため、これをトレースしようとしません。明示的にforまたはwhileループを使うようにリファクタリングすることで、よい性能が得られるでしょう。
- DOMプロパティの取得と設定（DOMメソッドを呼び出すのはよいです）。これらの機能を回避するのは一般的に不可能ですが、DOMプロパティにアクセスするコードをホットなループと性能上クリティカルな部分の外に移動させうると、よいでしょう。
We are actively working on tracing all the features named above. For example, support for tracing arguments is already available in nightly builds.
我々は上の機能をすべてトレースできるように作業しています。たとえば、引数をトレースするのはnightly buildsですでに実装されています。
Here is the slow example program refactored to avoid eval. Of course, I could have simply done the multiplication inline. Instead, I used a function created by eval because that’s a more general way of refactoring an eval. Note that the eval still can’t be traced, but it only runs once so it doesn’t matter.
以下に、evalを回避するようにリファクタリングされる遅いプログラムの例を示します。もちろん、私は乗算を単純に実行できます。しかし、evalで生成された関数を使用します。なぜならば、これがevalをリファクタリングする一般的な方法だからです。evalは依然トレースされませんが、一回しか実行されないために、問題とならないことを記しておきます。
function runExample3() { var t0 = new Date; var sum = 0; for (var i = 0; i < 100000; ++i) { sum += i; } var prod = 1; var mul = eval("(function(i) { return prod * i; })"); for (var i = 1; i < 100000; ++i) { prod = mul(i); } var dt = new Date - t0; document.getElementById('example3_time').innerHTML = dt + ' ms'; }
There are a few more esoteric situations that can also hurt tracing performance. One of them is trace explosion, which happens when a loop has many paths through it. Consider a loop with 10 if statements in a row: the loop has 1024 paths, potentially causing 1024 traces to be recorded. That would use up too much memory, so TraceMonkey caps each loop at 32 traces. If the loop has fewer than 32 hot traces, it will perform well. But if each path occurs with equal frequency, then only 3% of the paths are traced, and performance will suffer.
トレースの性能を悪化させる奇妙な状況が、もう少しあります。ひとつはトレースの爆発で、これはループがその中に多数のパスを持つ場合に発生します。1行に10個のif文があるループを考えます: このループは1024個のパスを持ち、1024個のトレースが記録される可能性があります。これはとても多くのメモリを使用するので、TraceMonkeyは32個のトレースを補足します。もしループが32個以下のホットなトレースを持っていたら、これは高速に動作するでしょう。しかしもしどのパスも同じくらいの頻度で発生したら、そのときは3%のパスしかトレースされず、性能に影響が出るでしょう。
This kind of problem is best analyzed with TraceVis, which creates visualizations of TraceMonkey performance. Currently, the build system only supports enabling TraceVis for shell builds, but the basic system can also run in the browser, and there is ongoing work to enable TraceVis in a convenient form in the browser.
この手の問題は、TraceVisで分析されます。TraceVisは、TraceMonkeyの性能の可視化を行います。現在は、buildシステムだけがshellビルドのためのTraceVisをサポートしていますが、基本的なシステムがブラウザ内で実行され、ブラウザ内で使い易くTraceVisを有効にするための進行中の作業があります。
The blog post on TraceVis is currently the most detailed explanation of what the diagrams mean and how to use them to diagnose performance problems. The post also contains a detailed analysis of a diagram that is helpful in understanding how TraceMonkey works in general.
上の図が何を意味しているか、また性能の問題を診断するためにTraceVisをどのように使用するかについて、このブログのTraceVisのポストで説明しています。この投稿はまたTraceMonkeyが一般的にどのように動作するか理解する手助けになる図を詳細に解析しています。
JITの比較
Here I will give a few comparisons to other JavaScript JIT designs. I’ll focus more on hypothetical designs than competing engines, because I don’t know details about them — I’ve read the release information and skimmed a few bits of code. Another big caveat is that real-world performance depends at least as much on engineering details as it does on engine architecture.
ここでは、他のJavaScriptのJITの設計と比較してみます。競合しているエンジンより架空の設計について注目していますが、これは私がそれらの設計について知らないからです -- 私はリリース情報とコードを少々読みました。他の大きな警告は、実際の性能は少なくとも、エンジンの設計と同様に、技術上の詳細に依存している、ということです。
One design option could be a called a per-method non-specializing JIT. By this, I mean a JIT compiler that compiles a method at a time and generates generic code, just like what the interpreter does. Thus, the brown boxes from our diagrams are cut out. This kind of JIT doesn’t need to take time to record and compile traces, but it also does not type-specialize, so the orange boxes remain. Such an engine can still be made pretty fast by carefully designing and optimizing the orange box code. But the orange box can’t be completely eliminated in this design, so the maximum performance on numeric programs won’t be as good as a type-specializing engine.
設計のオプションのひとつは、per-method non-specializing JITと言われます。これは、インタプリタがするように、1回でひとつのメソッドをコンパイルして一般的なコードを生成するJITコンパイラを意味します。よって、我々の図から茶色の四角がなくなります。この種のJITはトレースを記録してコンパイルするのに時間を必要としませんが、型に特化していないので、オレンジの四角は残ります。このようなエンジンはオレンジの四角のコードを注意深く設計して最適化して素早く製作できます。しかしこの設計ではオレンジの四角は完全にはなくならないので、数値のプログラムの最高の性能は型に特化したエンジンと同等にはなりません。
As far as I can tell, as of this writing Nitro and V8 are both lightweight non-specializing JITs. (I’m told that V8 does try to guess a few types by looking at the source code (such as guessing that a is an integer in a >> 2) in order to do a bit of type specialization.) It seem that TraceMonkey is generally faster on numeric benchmarks, as predicted above. But TraceMonkey suffers a bit on benchmarks that use more objects, because our object operations and memory management haven’t been optimized as heavily.
述べた通り、NitroとV8はどちらも軽量で型に特化していないJITです（V8は、少しだけ型に特化するように、ソースコードを読み取っていくつかの型を推測しようとしているようです（a >> 2ではaは整数と推測するように））。TraceMonkeyの方が一般的に数値のベンチマークでは上に述べたように速くなるように思います。しかしTraceMonkeyはオブジェクトをより使用するベンチマークでは悪化します。なぜならばオブジェクトの操作とメモリ管理は最適化されないからです。
A further development of the basic JIT is the per-method type-specializing JIT. This kind of a JIT tries to type-specialize a method based on the argument types the method is called with. Like TraceMonkey, this requires some runtime observation: the basic design checks the argument types each time a method is called, and if those types have not been seen before, compiles a new version of the method. Also like TraceMonkey, this design can heavily specialize code and remove both the brown and orange boxes.
基本的なJITの進んだ開発は、メソッドごとの型に特化したJITです。この種類のJITは、メソッドが呼び出された引数の方を基準にして、メソッドを型に特化しようとします。TraceMonkeyのように、これは実行時に観察を必要とします: 基本的な設計では、メソッドが呼び出されるごとに引数の型を検査しますが、しかしそれらの型が以前と違っていたら、メソッドの新しいバージョンをコンパイルします。TraceMonkeyと同様、この設計はコードを特化でき、茶色とオレンジの四角を削除します。
I’m not aware that anyone has deployed a per-method type-specializing JIT for JavaScript, but I wouldn’t be surprised if people are working on it.
私はJavaScriptのメソッドごとの型に特化したJITを誰かが配布しているのを知りませんが、誰かがやろうとしていたとしても私は驚きません。
The main disadvantage of a per-method type-specializing JIT compared to a tracing JIT is that the basic per-method JIT only directly observes the input types to a method. It must try to infer types for variables inside the method algorithmically, which is difficult for JavaScript, especially if the method reads object properties. Thus, I would expect that a per-method type-specializing JIT would have to use generic operations for some parts of the method. The main advantage of the per-method design is that the method needs to be compiled exactly once per set of input types, so it’s not vulnerable to trace explosion. In turn, I think a per-method JIT would tend to be faster on methods that have many paths, and a tracing JIT would tend to be faster on highly type-specializable methods, especially if the method also reads a lot of values from properties.
トレースするJITと比較したときに、メソッドごとの型に特化したJITの主な欠点は、メソッドに与えられる入力の型を直接観察するだけである、という点です。このJITはアルゴリズムにのっとってメソッド内部の変数の型を推測しなければなりませんが、特にメソッドがオブジェクトのプロパティを読み取るとき、これはJavaScriptにとって難しいです。よって、このJITはメソッドのいくつかの部分で一般的な演算を使用しなければならないと私は期待します。メソッドごとの設計の主な利点は、入力の型の組み合わせひとつ毎に正確に1回メソッドがコンパイルされる必要がある、という点で、これにより、トレース爆発の脆弱性にはならないのです。今度は、メソッドごとのJITは多くのパスを持つメソッドではより速く実行される傾向があり、トレースするJITは、特にメソッドがプロパティから多くの値を読み取るときには、高度に型に特化されたメソッドではより高速に動作しそうです。
結び
By now, hopefully you have a good idea of what makes JavaScript engines fast, how TraceMonkey works, and how to analyze and fix some performance issues that may occur running JavaScript under TraceMonkey. Please report bugs if you run into any significant performance problems. Bug reports are also a good place for us to give additional tuning advice. Finally, we’re trying to improve constantly, so check out nightly TraceMonkey builds if you’re into the bleeding edge.
いま、あなたは何がJavaScriptエンジンを高速にし、TraceMonkeyがどのように動作し、TraceMonkeyでJavaScriptを走らせたときに発生する性能上の問題をどのように分析し、解決するかアイデアを持っていたらいいと思います。もし特に性能上の問題があれば、バグを報告してください。バグ報告は我々にとってチューニングの助言を得るいい場所です。最後に、我々は継続的に改良しており、エッヂに立ちたかたっらnightly TraceMonkey buildをチェックアウトしてください。
