abcdefGets

ゲッツ!

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