🍩

jsエンジンはソースコードをどう実行しているのか〜バイトコード、JITコンパイル〜

2022/07/06に公開

JavaScript

Node.js

tech

下記画像における各フェーズをちゃんと見ていってみようという記事です
how v8 works
Benedikt Meurer; “An Introduction to Speculative Optimization in V8”;

大前提の「jsエンジンとは何か、どこに潜んでいるのか」ということだけさっと流したら、さっそく本題に入っていきましょう👶

jsエンジンとは何か、どこに潜んでいるのか

jsエンジンとは、JavaScriptエンジンのこと。JavaScriptエンジンとは、JavaScriptで書かれたコードを実行してくれるプログラムのこと
jsエンジンの主な生息地はブラウザおよびサーバーサイドJavaScript実行環境

ブラウザにおけるUIからjsエンジンまでの道のりは長い

ブラウザの内部構成は下記のようになっている
- めちゃくちゃ有名であろう画像だけど、やはり何度見ても味わい深い
- jsエンジンはUIからブラウザエンジン、レンダリングエンジンとハシゴした先に潜んでいる

js engine in a browser
Tali Garsiel & Paul Irish; “How browsers work”;

ブラウザによって使用しているjsエンジンが違う

jsエンジンはブラウザによって違う(rendering engineも違うから載せてみた)

	JS engine	rendering engine
Chrome	V8	Blink
Opera	V8	Blink
Edge	V8	Blink
Safari	JavaScriptCore	WebKit
Firefox	SpiderMonkey	Gecko
IE	Chakra	Trident

js実行環境であるnodeはV8を使っている

jsエンジンはソースコードをどうやって実行しているのか

ここからが本題です。jsエンジンの裏側をのぞいてみましょう👀

全体像

下記が基本的な流れ
- V8って書いてあるけど、下記の基本的な流れはエンジンによらずほとんど同じはず
- もちろんそれぞれのフェーズで実装の違いは在る。“Optimize & Compile it”の具体的な実装などはエンジンにより異なる
  
  Benedikt Meurer; “An Introduction to Speculative Optimization in V8”;
jsの面白いところは、ASTから直接コンパイルして実行されるわけでもなく、単純なインタプリタのようにコンパイルを挟まずに実行しているわけでもないところ。それに、なんだか見慣れない”Get feedback”というフェーズさえある……！ここがJIT compileと呼ばれる面白い部分で、このあと説明していきます！！

1. Parsing(構文解析)→AST(抽象構文木)

さて、まずはここから始まっていきます

Parsing(構文解析)とは、ここでは「文法に沿って、文の構造を解析すること」くらいで捉えておく
AST(抽象構文木)とは、ここでは「プログラムをデータ構造としての木を使って整理したもの」くらいで捉えておく
下記が実際のプログラムとASTのセット(V8のケース)

Benedikt Meurer; “An Introduction to Speculative Optimization in V8”;
ソースコードをASTにすることで、コンパイラをはじめとしたソースコード処理モジュールたちが扱いやすい形になる
- モジュールにとっては、人間が書き連ねた平坦なテキストデータよりも断然わかりやすい
- TSとかBabelとか、そういうのもみんな独自のASTを作っている
  - RomeはASTをモジュール間で共通化することで高速化を狙っているらしい(原典未確認)
    
    rome 開発チームはこの状態が問題だとしていて、統一的なツールチェインがあれば、一回の実行パスでコードのパース、解析、コンパイルが済むはずだ、というのが基本的な発想にある。すべての抽象構文木はローマに通じる、というわけ。
    rome は既存のエコシステムを否定して、自前の AST で全部を実装するという野望を抱えている。
    mizchi; 大統一 Node ツールチェイン Rome の野望現状の実装;

2. Bytecode(バイトコード)

お次はASTからバイトコードが生成される

バイトコードとは、1バイト区切りで仮想マシン向けの命令が記述されるコードのこと
- V8のBytecode Interpreter(Ignitionと呼ばれる)が出力するバイトコードはレジスタマシンを想定したもの
  - Ignitionは演算対象のレジスタをアキュムレータと呼ばれるレジスタへと基本的に固定することでコードサイズの圧縮を実現している

下記が実際のプログラムとバイトコードのセット(V8のケース)

const array = [1,2,3];

function getByIndex(arr) {
	bb = arr[1];
	return bb;
}

getByIndex(array);

$ node --print-bytecode --print-bytecode-filter=getByIndex getByIndex.js

[generated bytecode for function: getByIndex (0x3ed998cfc401 <SharedFunctionInfo getByIndex>)]
Bytecode length: 12
Parameter count 2
Register count 0
Frame size 0
OSR nesting level: 0
Bytecode Age: 0
   # accumulatorに整数値1をロード
   52 S> 0x3ed998cfcec6 @    0 : 0d 01             LdaSmi [1]
   # accumulatorにある値をkeyとして、オブジェクトa0(=1番目の引数)のkeyedPropertyをaにロード
   # つまりここではarray[1]をaにロード
   60 E> 0x3ed998cfcec8 @    2 : 2f 03 00          LdaKeyedProperty a0, [0]
   # accumulatorにある値をglobalの0番キー(=下記のFixedArrayから#bbに対応)にいれる
   55 E> 0x3ed998cfcecb @    5 : 23 00 02          StaGlobal [0], [2]
   # globalの0番キー(=下記のFixedArrayから#bb)にある値をaccumulatorにいれる
   66 S> 0x3ed998cfcece @    8 : 21 00 04          LdaGlobal [0], [4]
   # accumulatorの値を返す
   76 S> 0x3ed998cfced1 @   11 : a8                Return
Constant pool (size = 1)
0x3ed998cfce79: [FixedArray] in OldSpace
 - map: 0x247dd1d812c1 <Map>
 - length: 1
           0: 0x3ed998cfc249 <String[2]: #bb>
Handler Table (size = 0)
Source Position Table (size = 13)
0x3ed998cfced9 <ByteArray[13]>

バイトコードはマシン語ほど特定のマシンによっておらず、しかし人間用の言語ほどデータサイズなどの観点での無駄が多くない
- 実行しつつチューニングすること(後述のJIT compile)をしたいというブラウザjs実行におけるニーズにうってつけ！
  - チューニングはOSやCPUアーキテクチャに左右されてしまった後のコードでやりたくないよね
興味がある人はこのあたりの記事やdocsでバイトコードを解読しよう👶
- @kakts; v8によって生成されるbytecodeを確認してみる
- Franziska Hinkelmann; Understanding V8’s Bytecode;
- v8/v8.git - Git at Google; src/interpreter/interpreter-generator.cc
  - 最後のgitはv8の公式で、全てのバイトコードの読み方が載っています

3. Getting Feedback, Optimize & Compile it(さて、これはいったい……？)

バイトコードの次はいよいよ謎が多き部分に入る

Optimize & Compile itってことは要するに「バイトコードの無駄を削ぎ落として、マシン語にする」ということ
でも、実は無駄を削ぎ落とすといってもそんな単純な話じゃない。動かしてみてはじめて分かる無駄がjsにはたくさんある……！
- 例えばjs(というかECMAScript)は動的型付け、つまり実行してはじめて型が特定され、かつ、そのうえで変数の型の多義性を認めるような演算子定義をしている。例えば加算演算子は整数も文字列も配列も色々なものを引数として受け入れ、計算の仕方が引数の型によって異なる
- このような多義的な演算がプログラムのどこかで定義されると、計算機は色々な可能性に備えないといけない。例えば足し算の関数が定義されたら文字列が来るかもしれないし、リストかもしれないし……それぞれのケースに備えてメモリ準備などやることが発生する
- しかし、例えば文字列にも備えていたのに数字しか入力されなかったら、文字列を受け入れるためにしていた準備は無駄になる。時間的計算量、空間的計算量に無駄が生じる
- こういったことを防ぐには、プログラムを実行しながら様子を伺えばいいのではという発想で、下記のJIT Compileをやろうという話になる

JIT compile(実行時コンパイル)

以上の背景から、Optimize & Compile itの部分で実際に採用されているのはJIT compile(実行時コンパイル)と呼ばれる処理方式
プログラムを1行ずつ(正確には実行単位ずつ)実行しながら、その実行で得た情報をもとに、後続のコードをより効率的なマシン語に変換して実行していく方式のこと
- 「単純なインタプリタ方式」と「コンパイラ方式」の間と言える
  - 単純なインタプリタ: 1行ずつ(なんの工夫もなく)実行していく
  - コンパイラ: 事前に全部マシン語にしておく
- 厳密にはJITコンパイルはインタプリタ方式の一種であるといえる
具体的には、例えば下記の関数がプログラム実行中に一度実行されたとき、引数が両方とも整数だったのなら、一旦そのあとの実行も全て整数同士行われるだろうとあたりをつけ、プログラム中のその関数の実行部分を整数同士の演算に特化したマシンコードに紐づけておく(実行するときもマシンコードで実行する)、というような投機的な最適化が行われる
```
function add(x, y) {
	return x + y;
}
console.log(add(1, 2));
```
- V8のBytecode InterpreterであるIgnitionが生成したバイトコードは、feedback vectorと呼ばれる構造体に実行情報を入れていくように仕組まれている。実際、さっきのバイトコードをよくみると、末尾の配列インデックスっぽいものは命令ではないことがわかる。それらは実行情報をfeedback vectorの何番目に入れるか指定しているもの
繰り返し呼び出される(=hotである)コードほど、優先的に最適化の対象となる
JITコンパイルはインタプリタのような柔軟性を保ちつつ、コンパイラのような効率性を追求できる。だからブラウザのJS実行環境ではJITコンパイルが採用されている
- 事前コンパイルではOSやCPUアーキテクチャの違いを吸収できない
- 正直にインタプリタを走らせたら実行速度が遅すぎる

V8の場合のJIT Compile概要

bytecode interpreterであるIgnitionがバイトコードを実行していく。そしてその結果をふまえて、bytecodeをもとにした最適化をJIT compilerであるTurbofanが実施する
- ASTからバイトコードを生成するのはIgnitionであるし、バイトコードを実行するのもIgnitiionであることに注意
  - The name "Ignition" refers to both the Bytecode Generator and the Bytecode Interpreter. Often, the entire thing is also seen as one big black box and casually called "the interpreter", which can sometimes lead to a bit of confusion around the terms.
  - The Bytecode Generator takes the AST produced by the Parser for a given JavaScript function, and generates bytecode from it.
  - The Bytecode Interpreter takes the bytecode generated by the Bytecode Generator and executes it by interpreting it by sending it to a set of Bytecode Handlers.
  - The Bytecode Handlers that make up the Bytecode Interpreter are generated using parts of the Turbofan pipeline. This happens at V8 compilation time, not at runtime. In other words, you need Turbofan to build (parts of) Ignition, but not to run Ignition.
  - The Parser (and the AST/Abstract Syntax Tree it produces are not part of Ignition.
  jmrk(a V8 developer); Stack Overflow;
- バイトコードをもとにした最適化、つまりJIT compileをやるのはTurbofanと呼ばれるモジュール。ちなみに一世代前のJIT compilerはCrankShaftと呼ばれ、最適化をバイトコードではなく元のソースコードを基に行っていたらしい
- バイトコードをそのまま実行していくのはV8に限った話ではないのかもしれないが、調べきれていないのと自信がないのとで一旦V8の話として書いておく
JIT Compileにおける最適化は、実行情報からの予測に基づいた投機的な最適化(Speculative Optimization)に過ぎないため、予想がはずれれば最適化前のバイトコードを実行することになる。これはDeoptimizeと呼ばれる
- 実際にDeoptimizationが起きる様子をV8の開発者用シェル”d8”で確認できる。興味のある人は下記の記事を見てみよう
  
  Benedikt Meurer; “An Introduction to Speculative Optimization in V8”;
- Deoptimizationは下図の赤い矢印に対応する
  
  Franziska Hinkelmann; Understanding V8’s Bytecode;

V8のモジュール群

最後に、ここまでの各フェーズをV8で担当しているモジュールの名前をメモ

フェーズ	モジュール名
AST	名前なさそう
bytecode generation	Ignition
bytecode execution	Ignition
JIT compile	Turbofan
garbage collection	Orinoco
web assembly process	Liftoff

Orinocoはわからないけど、V8という名前も含めどれもエンジンを想起させる名前でかっこいい……！
Ignitionはバイトコードの生成も実行もやる

とても参考になった記事

今回の記事はこれの要約＋寄せ集めの情報です。本当にいい記事です。すごすぎるのでぜひ読んでみてください

Benedikt Meurer; “An Introduction to Speculative Optimization in V8”;
本記事はコードが実行される「まで」の話でしたが、jsが実行されている「間」の話は下記の記事やサイトがとてもためになります

@tokuda109; JavaScriptがブラウザでどのように動くのか;

Andrew Dillon; JavaScript Visualizer 9000;
レジスタマシンとスタックマシンの違いについて参考になりました(Ignitionはレジスタマシンを想定しており、レジスタマシンとよく対置されるのがスタックマシンです)

えくー; 週アレ（１４）　スタックマシンとレジスタマシン

GitHubで編集を提案