abcdefGets

ゲッツ!

2019 Javascript engine 俯瞰

2019 Javascriptエンジン俯瞰

こんにちは 2019 Javascript Advent Calendarの11日目です

2019はJSエンジンが新たに2つもリリースされた
まずFacebook産のhermes
もう一つがFFMPEG作者のbellardが実装したquickjs

この2つを見ていこうと思う

ちなみにhermesは以前にも書いたので正直あまり書くことは無い
http://abcdef.gets.b6n.ch/entry/2019/07/22/142510

特徴

hermes

  • C++
  • FacebookがReact Nativeの高速化用に実装したエンジン
  • レジスタマシンのバイトコードインタプリタを搭載
  • flowを解釈できる
  • commonjsを解釈して実行できる
  • バイトコードのexportとimportも可能でスタートアップタイムを高速化することが可能
  • JITx86_64の実装はあるが使うパスが無いためOFFになっている
  • let/constやclass、ES Moduleといった機能はサポートされていない
  • Reflectionやwith、Symbol.speciesといったものは今後もサポートしない
  • 一部Ecma262と仕様が異なる

quickjs

実装

パーサ

両方ともシンプルな手書きの再帰下降構文解析でパース

hermes

hermesはパースしながらASTを生成する
hermesのASTはESTreeの仕様に準拠しているのでわかりやすい

quickjs

quickjsは非常にドラスティックな実装となっており、パースしながらなんとBytecodeを直接出力する
ファイルサイズ削減のためにASTをスキップしていて、完全にコンパクト方面に振り切っている感じ
ここらへんはエンジンの色がでていて面白い

Bytecode

hermes

hermesバイトコードBytecodeList.defに全てまとまっており、全てマクロ呼び出しで後々再利用できるようになっている
hermesバイトコードは可変長で、オペランド数はMaxが6、オペランドのサイズも可変長
NewObject等の割と大きめな命令から、BitXorの様なプリミティブ命令まで実装されている

quickjs

対するquickjsバイトコードquickjs-opcode.hにすべてまとまっており、こちらも同じくマクロ呼び出しとなっている
まあ言語エンジンを実装するときは大体こうなるよね
quickjsバイトコードだが、まあ大体hermesと同じような粒度かな
一部push_i32のようなスタックマシンぽいコードもあったり

Bytecodeは両者ともわりかし似ている感じ

Object Model

hermes

以前も書いたが、hermesはNaN-Boxingで実装されている(NaN-BoxingについてはFacebookのHermes Javascript Engineについてにも書いた)
hermesのヒープオブジェクトはGCCellクラスを頂点としたモデルになっている

GCCell
|
+--------+------+-----------------------+-----------+----------------+------------+--------------+--------------+-----+-----+---------+
|        |      |                       |           |                |            |              |              |     |     |         |
JSObject Domain VariableSizeRuntimeCell HiddenClass PropertyAccessor HashMapEntry OrderedHashMap OrderedHashMap Type1 Type2 EmptyCell FinalizerCell
|
|--------+--------------+------------------------------------+---------+---------------+-------------+----------+------+-------+-----------+---------+-----------------+--------+----------------+-----------------+------------+----------------+
|        |              |                                    |         |               |             |          |      |       |           |         |                 |        |                |                 |            |                |
Callable RequireContext HostObject                           ArrayImpl JSArrayIterator JSArrayBuffer JSDataView JSDate JSError JSGenerator JSMapImpl JSMapIteratorImpl JSRegExp JSTypedArrayBase JSWeakMapImplBase PrimitiveBox JSStringIterator SingleObject
|                                                            |                                                                                                                  |                |                 |
+-------------+-----------------------------------+          +---------+                                                                                                        |                |                 +--------+--------+---------+
|             |                                   |          |         |                                                                                                        |                |                 |        |        |         |
BoundFunction NativeFunction                      JSFunction Arguments JSArray                                                                                                  JSTypedArray     JSWeakMapImpl     JSString JSNumber JSBoolean JSSymbol
              |                                   |
              NativeConstructor NativeConstructor JSGeneratorFunction GeneratorInnerFunction

JSObject階層以外は省略したが、hermesは上記の様なオブジェクト階層を持っておりまあ割と複雑
GCCellクラスはVTableというオブジェクトに関する情報を保持しているクラスをラップしており、VTableが実際にGC用の型情報やマーク情報を持っている
ただ、VTableクラス自体はGCによってアドレスが変わる可能性があるため、GCCellクラスがハンドルの役目を果たしている
そのため、GCCellはメンバを持たない

ランタイムでのオブジェクトの型情報はその名の通りHiddenClassが保持しており、V8っぽくHiddenClassの中にプロパティのキャッシュを持っていたりする
当然プロパティ追加時のTransitionも実装されていて、ちゃんとhidden classとして機能している

{symbol_id} = internal variable name id
{property_flag} = enumerable|writable|configurable|...

+------------------------+
| HiddenClass(root)      |
+------------------------+
            |
            | (Transition HiddenClass(propertyA))
            |
+------------------------+
| HiddenClass(propertyA) |
+------------------------+
             | (TransitionMap {symbol_id}_{property_flag}: HiddenClass(propertyB), {symbol_id}_{property_flag}: HiddenClass(propertyC)})
             +-------------------------+
             |                         |
+------------------------+ +------------------------+
| HiddenClass(propertyB) | | HiddenClass(propertyC) |
+------------------------+ +------------------------+

こんな風に1つの派生だけの場合はTransitionオブジェクトを直接参照して、複数のTransitionがある場合はsymbol_idproperty_flagのキーとHiddenClassを直接ハッシュマップとして持つことでTransitionを実現している

quickjs

quickjsはCなので明示的なオブジェクト階層はないもののJSObjectが多くのJS型のベースとなっておりメンバをunionを選択する形となる
またJSValueという空のstructGenericな値として利用しており、内部に持つ値はvoid*ではなくJSValue*型で保持している

JSObject
|
+-JSBoundFunction
+-JSCFunctionDataRecord
+-JSForInIterator
+-JSArrayBuffer
+-JSTypedArray
+-JSFloatEnv
+-JSMapState
+-JSMapIteratorData
+-JSArrayIteratorData
+-JSRegExpStringIteratorData
+-JSGeneratorData
+-JSProxyData
+-JSPromiseData
+-JSPromiseFunctionData
+-JSAsyncFunctionData
+-JSAsyncFromSyncIteratorData
+-JSAsyncGeneratorData
+-func
+-cfunc
+-JSTypedArray
+-array
+-JSRegExp

こんな感じでJSObjectにunionを持っている
クラシックなunionベースのモデルなので読みやすくていい

JSObjectはルートの構造体となるので、型情報や、GCMark等の情報を保持している

型情報は全てJSObject内のJSShapeというstructに持っている

JSShapeはプロパティ自体も保持しているが、現在のプロパティのバージョンをハッシュとしても持っており、プロパティが変化することでJSShape内のハッシュ値も変化する
さらに次のハッシュ値をプロパティのメモリアドレスから計算して、前のJSShapeへ持たせることで、次のJSShapeを検索することが可能になり、Transitionを実現している

+-----------+
| JSShape A |             |A(next_hash = null)| ...
+-----------+
     |
     | Add property
     |
+-----------+
| JSShape B |             |A(next_hash = 3)   | |B(next_hash = null)|
+-----------+

だいぶ簡略化して描いているが、next_hashに次のインデックスを格納するイメージ(本当は直接インデックスは格納しない)

VM

hermes

再掲となるが
VMで利用されるレジスタは一応無限の仮想レジスタとなっているが、単純なリニア生存区間解析をCFG上で行っている
一応無制限と書いたのは、Bytecodeのレジスタインデックスが1byteしか受けつけないので、実質256までしかレジスタ割付ができないからである

https://github.com/facebook/hermes/blob/master/doc/Design.mdに書いてあるが、Facebook調べでは256以上のレジスタを使う関数は 見当たらなかったらしい(ので大丈夫ということか)

quickjs

スタックマシンなので単純にstack pointerを伸縮している

両者ともラベルアドレスへのダイレクトジャンプを実装している(もちろんラベルのアドレスが取得できないコンパイラ向けのswitch-caseもある)
ちなみにどんな機能かというと

Label_A: {
  ...
}

Label_B:
.
.
.

const void* dispatch_tables = {&&Label_A, ...}

goto *dispatch_tables[1]

とすることでなんとlabelへとgotoできるという素敵な仕様
これを使うことでジャンプの度にcmpする必要がなくなる(indexの計算のみ)さらにCPUの分岐予測もいらないので、VMのループが高速化される

GC

hermes

GenerationalMark-Sweep GCでしたそれ以外特に言うこともないかな
オブジェクトグラフをひたすらVisitorがたどっていくprecise GCの実装となっていた

quickjs

こっちはちょっと特殊で参照カウント + mark-sweepとなっている
最初にオブジェクトグラフを巡回して参照カウントをdecrefしたのち、参照カウントが0のオブジェクトをdelete_listに詰め込んで回り、全て回収完了後にJSObjectを解放する
Pythonの方式と同じ方法でオブジェクトを削除している

すべての割り当てられたオブジェクトはobj_list内にあるので、それをtmp_obj_listにコピーして、
巡回中の参照カウントが1以上のオブジェクトはobj_listに戻す

+----------------+
|   global_env   |
+----------------+
        |
        |         +----------------+
        |         |  tmp_obj_list  |
        |         +----------------+
        |                 |
        |                 |     +------------+        +------------+
        |                 |-----|  objectA 1 |------->|  objectB 1 |
        |                 |     +------------+    |   +------------+
        |                 |                       |
        |                 |                       |   +------------+
        |                 |                       +-->|  objectC 2 |
        |                 |                           +------------+
        |      REF        |     +------------+              ↑
        |==============>  |-----|  objectD 2 |--------------+
                          |     +------------+
                          |
                          |                           +------------+  REF
                          |                      ---->|  objectF 2 |<=====+
                          |     +------------+   |    +------------+      |
                          |-----|  objectE 1 |---+                        |
                                +------------+   |    +------------+  REF |
                                                 ---->|  objectG 2 |<=====+
                                                      +------------+

これが巡回前 参照されているのはすでにObjectDのみの状態で、objectFとobjectGは循環参照している

+----------------+
|   global_env   |
+----------------+
        |
        |         +----------------+
        |         |  tmp_obj_list  |
        |         +----------------+
        |                 |
        |                 |     +------------+        +------------+
        |                 |-----|  objectA 0 |------->|  objectB 0 |
        |                 |     +------------+    |   +------------+
        |                 |                       |
        |                 |                       |   +------------+
        |                 |                       +-->|  objectC 1 |
        |                 |                           +------------+
        |      REF        |     +------------+              ↑
        |==============>  |-----|  objectD 1 |--------------+
                          |     +------------+
                          |
                          |                           +------------+  REF
                          |                      ---->|  objectF 1 |<=====+
                          |     +------------+   |    +------------+      |
                          |-----|  objectE 0 |---+                        |
                                +------------+   |    +------------+  REF |
                                                 ---->|  objectG 1 |<=====+
                                                      +------------+

これが巡回後
親が外部から参照されているオブジェクト以外は参照カウントが0になる、そして親が0の場合は回収されるので、循環していても関係なく削除できるようになる

ちなみにquickjsはメモリ割り当てに通常のmallocを使用していて、mallocの管理ヘッダ分のサイズも計算して割当中のオブジェクトサイズを保持している
メモリを回収する場合も単純にfreeを呼び出しており、メモリ管理は基本的にすべてglibcにまかせている

まとめ

簡単に2つのエンジンを俯瞰したが、quickjsは軽い実装ながら面白い箇所が多く、またコードもきれいで読みやすいのでおすすめ
quickjs.cにほぼ全てのコードが書かれているので読むのも簡単だと思う
hermesは普通に読むの面倒だし、そんなに面白いことも無いかもしれない

疲れました

では

FacebookのHermes Javascript Engineについて

最近、JSエンジンが何故かいくつか出て来たのでいっちょ見て見ることに
最初はFacebookが実装したjavascriptエンジンHermes(エルメス)の実装を見てみた

面倒くさいのでコードとかは引用しない

概要

どうやらReactNativeの高速化のために実装したエンジンのようだ
ReactNative側ですでに利用できるっぽい
売りとしてはバイトコードを出力・読み込みができるのでスタートアップタイムを高速化できるということらしい

commonjsの静的解析機能もついており今風な感じ

仕様

サポートされる仕様はhttps://github.com/facebook/hermes/blob/master/doc/Features.mdにある

サポートしている言語仕様はES5 + α

let/constやclass、ES Moduleといった機能はサポートされていない
とりあえずbabelとかts使うから動くでしょ といったところか

またReflectionwithSymbol.speciesといったものは今後もサポートしないらしい

Function.prototype.toStringソースコードを返さないなど、割と必要ないものはバッサリ切った感じ
React Navtiveのためと言っているのでいいのかな

ビルド

成果物が結構あるのに解説があんまないので困る

以下が成果物

中身

とりあえず概要をみてみた
以下が基本的なパスとなりそう

ソースコード => AST => IR => (最適化) => バイトコード => 実行

またバイトコードを読み込むことで

バイトコード => 実行

のパスもある

AST

NodeがあってBNF定義に近いASTがある
要は普通のAST実装
ただdecoratorで実装しているっぽいのでちょっと読みづらい

Visitorパターンでトラバーサルする

IR

ASTが生成されたらIRを生成する
hermesのIRはCFGも兼ねるグラフとなっている
このIRは結構低レベルでInstructionレベルまで表現している

バイトコード

IRから変換して生成される
OPコードは1byteでOperandは可変長

VM

バイトコードを実行するVMレジスタベースの仮想マシン
教科書通りGCC拡張のアドレスへのgotoとLabelアドレスの取得機能でループ無しで実装されている
ただしサポートされないコンパイラ向けにループとSwitch構文での実行機能も持っている

レジスタ

VMで利用されるレジスタは一応無限の仮想レジスタとなっているが、単純なリニア生存区間解析をCFG上で行っている
一応無制限と書いたのは、Bytecodeのレジスタインデックスが1byteしか受けつけないので、実質256までしかレジスタ割付ができないからである

https://github.com/facebook/hermes/blob/master/doc/Design.mdに書いてあるが、Facebook調べでは256以上のレジスタを使う関数は
見当たらなかったらしい(ので大丈夫ということか)

ABI

Facebook HermesはNaN-Boxingでオブジェクトを表現している

NaN-Boxingとは64bitフロートのNaN定義を利用したポインタと数値の表現方法
NaNは上位17bitが1であれば下位のBitがどんな値でも問題ないので、それを利用してポインタやタグ情報を埋め込んでいる
ただし64bitシステムだとポインタは64bit利用するので埋め込めないように見えるのだが、現状64bitシステムであっても全ての領域は使い切っていないので問題なく収まる (Linux x86-64で48bitまで利用と書いてあった)
ただし、そこまで考えなくてもVMのヒープが47bitで収めきればいいだけなので、そこまで問題は起きないだろう

Hidden Class

今のご時世、ShapeやらHidden Classは高速化に必須だろう
HermesもHidden Classを実装している
V8と同じようにオブジェクトレイアウトをclassとして認識して、プロパティの追加・削除等のレイアウト変更を行うと新たなクラスが生成されるようになっている

新たにHidden Classを生成した場合はtransitionをした結果を保存して検索するような仕組みになっている

IC

複雑なインラインキャッシングは実装されていないように見える
一応プロパティのキャッシュとhidden classの保持はしているのでプロパティキャッシュ自体はしているが

正規表現

正規表現は独自バイトコードを使ったVM型のエンジンを実装している
既存のエンジンのJITに比べるとちょっと見劣りするかもしれない

最適化

主にIRに対しての最適化が実行されている
内容はIRのloweringとかinline化など
面倒だったのであんまりちゃんと読んでない

JIT

実はJITエンジンももっている がまだリリースされていなのでOFFになっている
中を見た感じx86-64から提供する様だ

ARMは...?

まとめ

React Nativeのために作ったというだけあって、色々省いてあったりバイトコードローディングなど工夫があった
後発のエンジンなだけにcommonjs対応してたり、今風な感もあって面白い

ただ、言語仕様がEcmascriptのエディションと変わってきてしまっている(withがなかったり)のはちょっと気になっている

最近感じていることだが、Ecmascriptも仕様が大きくなってきていてエンジンの実装も大変になってきているし、
使用目的がはっきりしているエンジンにとっては多分サポートする意味の無い機能(withとかnot strictなモード、多言語対応等)は省いたEcmascriptのサブセットがあってもいいのかもしれない
というか個人的にはほしい

RegEx実装するだけでICU必要になったり面倒なことが多い

JavascriptのObjectリテラルとJSON.parseについて

V8のJSON.parseについて

最近(ちょっと前か)話題のオブジェクトリテラルよりもJSON.parseのほうが早い件について。
その理由を内部実装の観点から書く。

また注意点を最後に書いた。

話題のブログは以下から https://v8.dev/blog/cost-of-javascript-2019

パースについて

V8はjavascriptコードをパースするにあたって、Lazy Parseを行っている。

Lazy Parse

javascriptはブラウザという特殊な環境で実行される言語であるため、パースにも少々工夫が必要になる。
基本的にV8はすべてのソースコードをパースしない。
一旦グローバルスコープにあるものだけをちゃんとパースして、それ以外はPreParserというパーサで関数だけをかき集める。

function foo() {
}

function bar() {
  function baz() {
    const value = 100;
  }
}

この例だと、foobarbazという関数が存在していることはパースするが、const value = 100は一切パースせずASTを生成しない。
bazが呼び出されて初めてconst value = 100がパースされる。

How to skip parsing

ではどのようにコードのパースをスキップしているかというと、V8のパーサは手書きの再帰下降構文解析器になっており、
ParserFunctionのようなメソッドが一杯あるクラスになっている。

さらにパーサはPreParserParserに分かれており、それをテンプレート引数で受け取って実行するParserBaseクラスが各パースのエントリーポイントを定義している

template <typename Impl>
class ParserBase<Impl> {
  ...
 protected:
  ...
  ExpressionT ParseFunctionExpression();
  ...
 private:
  Impl* impl() {return parser_;}
  Impl* parser_;
};

のような感じでParserBaseがパーサのBNFに対応する各パース段階のエントリーポイントを持つ。
その中でimpl()->ParserFunctionLiteral()のような形で実際のパーサを呼び出してパース処理を行っている。

Parser and PreParser

さて実際にパース処理を行うパーサは2種類ある。
PreParserはASTを生成せずに関数名やその他情報を集めるだけのパーサで、Parserは実際にASTの生成を行うパーサとなっている。
ここで大事なのがPreParserの実装である。

PreParserはASTは生成しないものの実際に構文のパースは行う。
そのため、V8ではjavascriptソースコードは2回パースされることとなる。

ここでJSON.parseの特殊性が影響してくる。

JSON.parse

JSON.parseの第一引数には文字列のJSONオブジェクトが渡される。
これがキモになる。何故かと言うと、文字列のパースコストは非常に低いのだ。
なぜなら文字列はパース段階ではなく、スキャン段階でトークン化されるため、何度パースされても文字列リテラルトークンを判定するだけで処理が完了する。
そのため、パースの負荷が非常に低くなる。

また、JSON.parse自体もランタイムで処理が行われるために、実際に呼び出されるまで処理が行われず、不要なパースをすべてスキップすることができる。
すなわち手動でLazy Parsingをしているに等しい状態となっている訳だ。

これらの要因が組み合わさってオブジェクトリテラルをべた書きするよりも、JSON.parseの方が早くなるという不思議な現象が発生する。

注意点

ただしこの方法には注意点があって、あくまでこの手法はstartup timeの高速化しかできない
実際の実行時間はJSON.parseのほうが遅くなるので、FMPの高速化には寄与するかもしれないが、すべてのオブジェクトリテラルをこれで置き換えると結構遅くなりそうなので注意。
あくまでパースのLazy化と考えたほうが良い。

ちなみにJSON.parseが遅いのはASTを作らず、毎回パースの手間がかかるから。
一度しか実行されないケースに関してはそこまで速度の差はでない。

一応ベンチマーク

https://jsperf.com/json-parse-vs-object-literal-in-parser

自分の環境では80%くらいJSON.parseが遅い

React hooks for React-Redux

久しぶりに時間が少しあったので、今更ながらReact hooksで遊んでみた。

Redux

とりあえず、useReducerとか触ってみたけど、redux勢には物足りない感... reduxをReact hooksで使えるやつ探したらfacebookが出してるredux-react-hookを見つけた。 使ってるうちに、こんな仰々しいものじゃなくていいんだよなという思いが拭えず...

結局React Hooksの勉強がてら全てをhooksでこなすrrhというYet another redux-hookを作ってみた。

RRH

使い方は簡単でcreateStoreをhookにした感じ

Provider側

import React from 'react';
import { useProvider } from 'rrh';
import reducer from './reducer';
import middleware from './middleware'
import Child from './child';

const Component = () => {
  const Provider = useProvider(() => ({
    reducer,
    preloadedState: {count: 1},
    storeEnhancer: applyMiddleware(middleware)
  }));

  return <Provider><Child></Provider>
}

connectもhookにしてみた

import React from 'react';
import { useSelector } from 'rrh';

const Child = (props) => {
  const selected = useSelector(
    props,
    (dispatch, props) => ({
      increment: () => dispatch({type: 'INCREMENT', payload: 1}),
      decrement: () => dispatch({type: 'DECREMENT', payload: -1}),
    }),
    (state, props) => ({count: state.count}),
    state => [state.count]
  );

  return (
    <div>
      {selected.count}
      <button onClick={selected.increment}>INC</button>
      <button onClick={selected.decrement}>DEC</button>
    </div>
  )
}

使い勝手は素のreduxに近くなるようにしてみた。

typescript

tsで作ってるので、型定義も同包してます。

rrh https://github.com/brn/rrh

WeJS2周年おめでとうございます

久しぶりのブログはこちらのアドベントカレンダー

adventar.org

WeJSについて

We are Javascritpers

wajs.connpass.com

初心者登壇歓迎なJavascript勉強会
最近はJS初心者歓迎も兼ねていて、多方面で参加しやすい勉強会になってる

思い出

21Cafeでやってるときに参加して依頼、だいたい行ってると思う
3回目くらいからかな?

全ての勉強会の中でここで最もLTしてると思う
いつもお世話になっております

ここでいろんな人と知り合いになれました

良いなと思っていること

今の時代にjavascriptで初心者歓迎なLT会は貴重

とにかく登壇の敷居を下げてくれているので登壇しやすい
特に一度も登壇したことない人はぜひ申し込んで登壇してほしい

ただ、倍率が高いので抽選通るまで頑張ろう

あと毎回賑やかでよい
懇親会とかすごく話しやすい雰囲気だなぁと毎回思う

これもひとえに主催者の方々の人柄ですね

これからWeJSでLTする方へ

自分のネタがしょぼいかなとか、みんな知ってるしとか考えなくていいよ!
まずは自分が楽しもう

昔WeJSでLTした心得的なやつ

speakerdeck.com

最後に

いつもありがとうございます。毎月楽しみにしてます。感謝。

JSのproposal-numeric-separatorを実装したよ

タイトルの通りなんだけど、書くのが遅れてしまった。
V8 のmasterにマージされた。

機能

javascriptのプロポーザルで数値リテラルの間にアンダースコアを挿入できるやつ

現在stage3にあってまだ正式に採用されているわけではない。

github.com

このスライドにも書いた

speakerdeck.com

例.

1_0_00_0
0xFF_FF_FF
0b0101_01_01
0o7_7_7

16進数、10進数、8進数、2進数の各リテラルに対応している。

あとBigIntにも当然対応している

39_950_934n

ただ、実装したあとに修正してもらったんだけど、implicit octalには対応していない。

0777_7 // Error!

あと、以下の場合はすべてエラー

0x_000 // Error !
0b_01 // Error !
0o_10 // Error !

アンダースコアの重複と末尾もだめ

12__00 // Error !
1200_ // Error !

制限

キャストされる数値には使えません!

Number('1_0_0') // Error !
parseInt('1_0_0', 10) // Error !

以下のIssueに詳しい

Numeric separator supported in implicit coercions, e.g., `+"0_0"`? · Issue #32 · tc39/proposal-numeric-separator · GitHub

簡単に話すと今までは

IsNaN(Number('1_0_0')) // true

だったので急にアンダースコアを数値として使えるようになると、NaNであることを期待しているコードが壊れるからという理由。
そのようなコードが一体どれほどあるのか知らないけど安全側に倒した。
breaking webを避けるためには仕方ないかなと言う感じ。

以上です。

V8の Object.entries/values を高速化した

V8のObject.entries/valuesを高速化したよというお話

Object.entires/values

そもそもObject.entriesObject.valuesとは何かというと、
GitHub - tc39/proposal-object-values-entries: ECMAScript Proposal, specs, and reference implementation for Object.values/Object.entriesで提案されていた仕様である。
見事stage4まで到達して採用された。

仕様

機能をおさらいしておく

Object.entries(O)

const ret = Object.entries({a: 1, b: 2, c: 3});
console.log(ret) // [['a', 1], ['b', 2], ['c', 3]];

キーと値をすべて配列に書き出してくれる。

Object.values(O)

const ret = Object.values({a: 1, b: 2, c: 3});
console.log(ret) // [1, 2, 3];

値のみを配列に書き出してくれる。

Ecma262のspecによると以下のように動作が規定されている

  • ToObject(O)を呼び出す
  • EnumerableOwnList(O)を呼び出して結果をnameListに格納
    • Type(O)がObjectかチェック
    • O.[[OwnPropertyKeys]]()を呼び出してキー一覧をownKeysに代入
    • properties配列を初期化
      • for each key of ownKeys
        • Type(key)が文字列なら続行
          • descにプロパティデスクリプタをO.[[GetOwnProperty]](key)を呼び出して代入
          • descundefinedではなくdesc.[[Enumerable]]なら
            • もしObject.keysならkeypropertiesに追加
            • Object.values/entriesなら
              • Get(O, key)を呼び出してvalueに代入
              • Object.valuesの場合にはvaluepropertiesに代入
              • Object.entriesの場合にはCreateArrayFromList(« key, value »).を呼び出してentryに代入
              • propertiesentryを追加
  • CreateArrayFromList(nameList)を呼び出してReturn

コードで表すと

function ObjectEntries(O) {
  O = ToObject(O);
  const nameList = EnumerableOwnList(O, 'entry');
  return new JSArray(nameList);
}

function ObjectValues(O) {
  O = ToObject(O);
  const nameList = EnumerableOwnList(O, 'value');
  return new JSArray(nameList);
}

function EnumerableOwnList(O, kind) {
  const ownKeys = O.[[OwnPropertyKeys]]();
  const properties = [];
  for (const key of ownKeys) {
    if (Type(key) === String) {
      const desc = O.[[GetOwnProperty]](key);
      if (desc && desc.[[Enumerable]]) {
        if (kind === 'key') {
          properties.push(key);
        } else {
          const value = Get(O, key);
          if (kind === 'value') {
            properties.push(value);
          } else {
            const entry = [key, value];
            properties.push(entry);
          }
        }
      }
    }
  }
  return properties;
}

て感じの動作になる。

基本的にはキー一覧を取得してからPropertyDescriptorを各々取得していって、Enumerableなら配列に追加していく形になる。

Too Slow

V8のObject.entries/valuesV6.5.172までは非常に遅くて使うのを躊躇するほどだった。

ベンチマークをとるとこんな感じ

Fast Path

forIn: 134 ms.
objectKeys: 552 ms.
objectKeysAndValues: 1010 ms.
objectEntries: 2541 ms.

Slow Path

forIn: 3117 ms.
objectKeys: 837 ms.
objectKeysAndValues: 1740 ms.
objectEntries: 2536 ms.

objectEntriesobjectKeysAndValuesforInに対して10倍以上遅いのがわかる。
ちなみにFast Pathはプロパティのみを含む通常のシンプルなオブジェクトで、Slow PathはSymbolGetterを含んでいる。

なぜこんなに遅いのか

こんなに遅い理由はRuntimeですべて実装されていたためである。
RuntimeとはC++で書かれたコードでC++コードとして静的にコンパイルされる。
一見C++ならば早そうに見えるが、やはり直にアセンブリに変換されるCSA等と比べると遅く、
さらにjavascriptの世界から呼び出す際にも大きなオーバーヘッドがある。

どのように高速化したか

CSA(CodeStubAssembler)に移植した。
ちなみにRuntimeとかCSAに関してはV8 javascript engineについての細かい話 (Node.js Advent Calendar 2017) - abcdefGetsに記載している。

ただし、完全にすべてのコードを移植したわけではない。

V8の方針

最初、私はRuntimeにあったObject.entries/valuesのすべての実装をCSAで書き直した。
これは一見うまく行ったのだが、いくつかの問題をはらんでいた。

  • 高速化したのだがCSAの本来のポテンシャルを活かしきれていない
  • 小さなRuntime呼び出しを残さざるを得なかった
  • 修正箇所が多すぎる

高速化したのだがCSAの本来のポテンシャルを活かしきれていない

これは私のCSA力不足が原因だった。
確かに最初の実装で信じられないほど高速化した。以下のベンチマークを見ていただきたい。

Fast Path

forIn: 136 ms.
objectKeys: 561 ms.
objectKeysAndValues: 472 ms.
objectEntries: 617 ms.

Slow Path

forIn: 1307 ms.
objectKeys: 946 ms.
objectKeysAndValues: 1526 ms.
objectEntries: 1623 ms.

確かにFast Pathのコードは非常に高速化しているものの、
Slow Pathの方は微かに高速化しただけだ。
これはFast Pathでさえ本来のCSAのポテンシャルで考えるとまだまだ遅いものだった。
しかもこのバージョンのコードは以下の問題を抱えていた。

小さなRuntime呼び出しを残さざるを得なかった

確かにCSAに移植はしたものの、CSAで記述するには明らかに複雑すぎるコード(数値プロパティの要素を取得するためのコードと、Slow Pathのコード)を含んでいたため、
結局小さなRuntimeを別途実装してCSAからRuntimeを呼び出すコードになっていた。
CSAからRuntimeを呼び出すのはjavascriptの世界から呼び出すのと同じくコンテキストスイッチのオーバーヘッドがかなり大きい。
そのためFast PathもSlow Pathも非効率なコードになっていた。
そしてさらに問題だったのはコード量だった。

修正箇所が多すぎる

明らかにV8という世界規模のOSSにコミットするコードとしては修正量が大きすぎた。
最初はレビュアーもなんとなく見てくれていたが、さすがにこれは一旦方針を変えようという話になった。

小さくすすめる

大切なのはいきなり大きな変更をしないことだ。
V8ほど複雑なコードベースなら尚更だ。
V8はすでに一部分の変更がどう影響するか、机上のみで推測するのは不可能なほどの複雑さを持っていた。
そこでレビュアーと話し合って、以下の方針で再実装することにした。

  • 既存のRuntimeは残す
  • Slow Pathは移植しない
  • 数値プロパティ検索も移植しない
  • もし途中でSlow Pathに入る場合にはRuntime呼び出しを行い、Runtimeですべて行う。

結局泣く泣くSlow Pathのコードを全削除し、Fast Pathで最速のケースのみをCSAに移植した。

終結

上述の過程を踏まえた上でコードを修正した結果以下の様になった。

Fast Path

forIn: 134 ms.
objectKeys: 525 ms.
objectKeysAndValues: 320 ms.
objectEntries: 469 ms.

Slow Path

forIn: 1307 ms.
objectKeys: 945 ms.
objectKeysAndValues: 1304 ms.
objectEntries: 2043 ms.

Slow Pathは以前と変わらない速度だが、Fast Pathに至っては、

  • Object.etnries2541 ms から 469 ms
  • Object.values1010 ms から 320 ms

という結果に。約3 ~ 5.5倍ほど高速化した。

やはりSlow Pathの移植を一旦止めて、Fast Pathのみに絞ったことがより洗練されたコードを可能にし、
その結果としてCSAの力を振り絞ることができたようだ。
ちなみにSlow Pathに関しては今のところはそこまで高速化するチャンスがないのと、使用用途的にあまり通らないパターンが多いので、
また議論が起きたときに高速化する予定。

なので、現状の実装は以下のパターンの場合のみ超高速に動作する。

  • Symbolを含まない
  • Getterを含まない
  • 数値プロパティを含まない
  • Proxyではない

まとめ

V8ほどの規模になると、小さく始めていくのがレビュアーにとっても実装者にとっても重要である。
という学びを得た。

ちなみにこのコードはV8 6.5.173にShipされました。

ベンチマークに使ったコードは以下のものです。

Fast Path
object-entries-values-fast-path-bench.js · GitHub

Slow Path
object-entries-values-slow-path-bench.js · GitHub