V8のObject.entries/values
を高速化したよというお話
Object.entires/values
そもそもObject.entries
、Object.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)
を呼び出して代入desc
がundefined
ではなくdesc.[[Enumerable]]
なら- もし
Object.keys
ならkey
をproperties
に追加 Object.values/entries
ならGet(O, key)
を呼び出してvalue
に代入Object.values
の場合にはvalue
をproperties
に代入Object.entries
の場合にはCreateArrayFromList(« key, value »).
を呼び出してentry
に代入properties
にentry
を追加
- もし
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/values
はV6.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.
objectEntries
とobjectKeysAndValues
がforIn
に対して10倍以上遅いのがわかる。
ちなみにFast Pathはプロパティのみを含む通常のシンプルなオブジェクトで、Slow PathはSymbol
やGetter
を含んでいる。
なぜこんなに遅いのか
こんなに遅い理由は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.etnries
は2541 ms
から469 ms
Object.values
は1010 ms
から320 ms
という結果に。約3 ~ 5.5倍ほど高速化した。
やはりSlow Pathの移植を一旦止めて、Fast Pathのみに絞ったことがより洗練されたコードを可能にし、
その結果としてCSAの力を振り絞ることができたようだ。
ちなみにSlow Pathに関しては今のところはそこまで高速化するチャンスがないのと、使用用途的にあまり通らないパターンが多いので、
また議論が起きたときに高速化する予定。
なので、現状の実装は以下のパターンの場合のみ超高速に動作する。
Symbol
を含まない- Getterを含まない
- 数値プロパティを含まない
Proxy
ではない
まとめ
V8ほどの規模になると、小さく始めていくのがレビュアーにとっても実装者にとっても重要である。
という学びを得た。
ちなみにこのコードはV8 6.5.173にShipされました。
※ベンチマークに使ったコードは以下のものです。