賀老微博から引き出された「遍歴器(Iterators)はそれらの奥義を加速させる」

私が注目している賀老-賀師俊先輩@johnhaxは最近、このような微博を発表しました.
この微博は広い範囲の注目と討論を引き起こしていないが、新人として、私は思考に陥った.果たしてV 8エンジンはどのような魔法をかけて、最大限の最適化に達したのだろうか.
この文章は、これらの最適化の背後にある奥義を深く分析するだろう.大神が斧正と導きを与え、同時に読者に啓発と助けを与えることを望んでいる.

私たちはいったい何を議論していますか。

ECMAScript 2015言語標準規格では、MapsとSets(もちろん、WeakMapsやWeakSetsなど)など、いくつかの新しいデータ構造が紹介されていますが、これらの新しく導入されたデータ構造には、同じように新しく導入された遍歴プロトコル(iteration protocol)に基づいて遍歴できる共通性があります.これはforを使うことができることを意味します...ofループまたは拡張演算子で操作します.Setsの簡単な例を挙げます.

const s = new Set([1, 2, 3, 4]);
console.log(...s);
// 1 2 3 4
for (const x of s) console.log(x);
// 1
// 2
// 3
// 4

同様にMaps:

const m = new Map([[1, "1"], [2, "2"], [3, "3"], [4, "4"]]);
console.log(...m);
// (2) [1, "1"] (2) [2, "2"] (2) [3, "3"] (2) [4, "4"]
console.log(...m.keys());
// 1 2 3 4
console.log(...m.values());
//  1 2 3 4
for (const [x, y] of m) console.log(x, "is", y);
// 1 "is" "1"
// 2 "is" "2"
// 3 "is" "3"
// 4 "is" "4"

この2つの簡単な例を通して,最も基本的な用法を示した.興味のある読者はECMA仕様:Map Iterator ObjectsとSet Iterator Objectsを参照することができる.
しかしながら、残念なことに、これらの遍歴可能なデータ構造は、V 8エンジンにおいて最適化されていない.あるいは、これらの実装の詳細な最適化の程度は非常に悪い.ECMAScriptのBrian TerlsonもTwitterで、Setsを使用して正規エンジンを実現する際に悩ましい性能問題に遭遇したと愚痴をこぼしたことがある.
だから、今は彼らを最適化する時間です!しかし、最適化に着手する前に、これらのデータ構造の処理が遅い本当の原因は何なのかを徹底的に認識する必要があります.パフォーマンスのボトルネックはどこですか?この問題を明らかにするためには,底層実装において反復器がどのように動作しているのかを理解する必要がある.

テーマに深く入り込んで真相を探る

そのため、私たちはまず簡単なforから...ofループ説.
ES 6はC++、Java、C#、Python言語を参考にforを導入しました...ofループは,すべてのデータ構造を遍歴する統一的な方法として用いられる.
最も簡単な使用:

function sum(iterable) {
  let x = 0;
  for (const y of iterable) x += y;
  return x;
}

このコードをBabelでコンパイルすると、次のようになります.

function sum(iterable) {
  var x = 0;
  var _iteratorNormalCompletion = true;
  var _didIteratorError = false;
  var _iteratorError = undefined;

  try {
    for (var _iterator = iterable[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
      var y = _step.value;
      x += y;
    }
  } catch (err) {
    _didIteratorError = true;
    _iteratorError = err;
  } finally {
    try {
      if (!_iteratorNormalCompletion && _iterator.return) {
        _iterator.return();
      }
    } finally {
      if (_didIteratorError) {
        throw _iteratorError;
      }
    }
  }

  return x;
}

皆さんに伝えなければならない事実は、現在の現代JavaScriptエンジンは本質的にBabelとforに対して...ofの脱文法糖化処理は同じであり、具体的な細部に差があるだけである.
この事実の出典:
All modern JavaScript engines essentially perform the same desugaring that Babel does here to implement for-of (details vary)
上記はV 8コアメンバー、GoogleエンジニアBenedikt Meurerから引用されています.
しかし、上のBabelでコンパイルされたコードはあまり読みにくいです.焦らないで、私は煩わしい異常処理を削除して、最も核心的な論理だけを残してみんなの参考にして、研究のために:

function sum(iterable) {
  var x = 0;
  var iterator = iterable[Symbol.iterator]();
  for (;;) {
    var iterResult = iterator.next();
    if (iterResult.done) break;
    x += iterResult.value;
  }
  return x;
}

このコードを理解するには予備知識が必要ですfor...これとSymbol.iteratorメソッド関係:
1つのデータ構造はSymbolが配備されている限りです.iteratorプロパティは、iteratorインタフェースがあると見なされ、for...ofそのメンバーをループします.つまりfor...ofループ内部で呼び出されるのはデータ構造のSymbolである.iteratorメソッド.
for...ofループで使用できる範囲には、配列、SetおよびMap構造、argumentsオブジェクト、DOM NodeListオブジェクトなど、いくつかの類似配列のオブジェクト、Generatorオブジェクト、および文字列があります.
上段のコードをよく観察すると、反復器の性能最適化の鍵は、サイクル中に複数回繰り返し呼び出されるiteratorを保証することである.next()は最大限の最適化が得られるとともに、iterResultへのメモリ割り当てを完全に回避することが望ましい.このような目的を達成できるいくつかの手段はstore-load propagation,escape analysis,scalar replacement of aggregatesのような先進的なコンパイル処理技術を使用することである.
また、最適化されたコンパイルでは、反復器自体であるiterable[Symbol.iterator]の呼び出し割り当てを完全に除去し、反復器backing-store上で直接操作する必要があります.
実際,配列と文字列反復器の最適化過程では,このような技術と理念が用いられている.具体的な実施文書は、ここを参照してください.
では、Set反復器の性能の問題について具体的には、JavaScriptとC++環境が混在していることが主な原因です.例えばnext()の実装:

function SetIteratorNextJS() {
  if (!IS_SET_ITERATOR(this)) {
    throw %make_type_error(kIncompatibleMethodReceiver,
                        'Set Iterator.prototype.next', this);
  }

  var value_array = [UNDEFINED, UNDEFINED];
  var result = %_CreateIterResultObject(value_array, false);
  switch (%SetIteratorNext(this, value_array)) {
    case 0:
      result.value = UNDEFINED;
      result.done = true;
      break;
    case ITERATOR_KIND_VALUES:
      result.value = value_array[0];
      break;
    case ITERATOR_KIND_ENTRIES:
      value_array[1] = value_array[0];
      break;
  }

  return result;
}

このコードは実際にはいくつかのことをしています.

定義はvalue_を割り当てたarray配列は、初期化時に2つのundefinedである.

は、{value:value_array,done:false}の形式で割り当てられたresultオブジェクトを定義する.

C+%SetIteratorNext runtime関数を呼び出し、反復器のthisとvalue_arrayはパラメータとして渡されます.

C+%SetIteratorNext runtime関数に従って結果を返し、resultを正しく値付けするとどのような結果になりますか?巡るたびに2つのオブジェクトを絶えず割り当てています:value_arrayとresult.V 8のTurboFanもCrankshaft(V 8の最適化コンパイラ)もこのような操作を排除することはできません.さらに悪いことに、一歩一歩JavaScriptとC++を切り替えなければなりません.次の図は、簡単なSUM関数の最下位レベルでの実行フローを簡単に示しています:

V 8の実行では、C++コードの実行とJavaScriptの実行の2つの状態(実際にはより多く)になります.この2つの状態間の変換のオーバーヘッドは大きい.JavaScriptからC++へは、いわゆるCEntryStubに依存して完了し、CEntryStubはC++で指定されたRuntime_をトリガーしますSomething関数(この例ではRuntime_SetIteratorNext).だから、このような変換を避けることができるかどうか、value_を避けることができます.arrayとresultオブジェクトの割り当ては、パフォーマンスの鍵を決定します.
最新の%next()実現はまさに急所を突いて、この“肝心な”処理をしました.我々が実行したいコードは呼び出す前にhot(熱処理)となり,TurboFanは最終的に熱処理最適化される.いわゆるCodeStubAssembler,baseline implementationにより,JavaScriptレベルでのアクセスが完全に実現されている.これにより、使用可能なメモリが消費された場合、C++を呼び出してゴミ回収や異常処理を行うだけです.

コールバック関数に基づくループ

遍歴プロトコルではJavaScriptも同様にSet.prototype.それはいいわprototype.forEachメソッドは、コールバック関数を受信します.これらはC++の処理ロジックにも依存しており、JavaScriptをC++に変換するだけでなく、コールバック関数をJavascriptに変換する作業モードを以下の図に示します.
したがって、CodeStubAssemblerを使用すると、単純な非コールバック関数シーンしか処理できません.本当に完全な意味での最適化はforEach法を含むTurboFan化には開発すべき魔法が必要である.

Benchmarkの最適化

最適化の度合いを評価するには、次のbenchmarkコードを使用します.

const s = new Set;
const m = new Map;
for (let i = 0; i < 1e7; ++i) {
  m.set(i, i);
  s.add(i);
}

function SetForOf() {
  for (const x of s) {}
}

function SetForOfEntries() {
  for (const x of s.entries()) {}
}

function SetForEach() {
  s.forEach(function(key, key, set) {});
}

function MapForOf() {
  for (const x of m) {}
}

function MapForOfKeys() {
  for (const x of m.keys()) {}
}

function MapForOfValues() {
  for (const x of m.values()) {}
}

function MapForEach() {
  m.forEach(function(val, key, map) {});
}

const TESTS = [
    SetForOf,
    SetForOfEntries,
    SetForEach,
    MapForOf,
    MapForOfKeys,
    MapForOfValues,
    MapForEach
];

// Warmup.
for (const test of TESTS) {
  for (let i = 0; i < 10; ++i) test();
}

// Actual tests.
for (const test of TESTS) {
  console.time(test.name);
  test();
  console.timeEnd(test.name);
}
    

Chrome 60とChrome 61の比較では、次のアイコンの結論が得られます.
大幅に向上したが、私たちはあまり理想的ではない結果を得たことが明らかになった.特にSetForOfEntriesとMapForOfに現れる.しかし、これはより長期的な計画で処理されます.

まとめ

この記事では、遍歴器のパフォーマンスが直面しているボトルネックと既存のソリューションを大まかに紹介しただけです.賀老の微博を通じて、一つの問題を探究し、最終的にV 8コアメンバーBenedikt MeurerのFaster Collection Iteratorsの一文を見つけ、参考にして翻訳した.元の文章の内容を完全に理解するには、しっかりしたコンピュータの基礎、v 8エンジンの働き方、コンパイル原理の知識の蓄積が必要です.
私はやっと勉強が浅いので、入行しても2年も経たないうちに、コンピュータ科のクラス出身ではありません.人の歯を拾うと同時に、偏差と漏れがあることを理解するのは避けられません.より多くのV 8エンジンに関する知識は、@justjavac、コンパイルに関する知識に注目することをお勧めします.結局、私たちがフロントエンドのV、ネット人気に注目するのは、にぎやかさを見たり、bを引き裂いたりするためではなく、先輩にもっと多くの知識を学び、もっと啓発されたいからです.
最後に、ECMAScriptの急速な発展に伴い、先端開発者一人一人が絶えず勉強していることを感じ、奔走に疲れているかもしれません.しかし、新しい特性と文法を学ぶ以外に、より深い内容を理解することが学習の進歩の鍵です.
同じように海とは何か分かりませんが、
裸足で砂浜に立って、
夜明けを待ち焦がれる.
Happy Coding!
PS:著者Github倉庫と知乎問答リンクは様々な形式の交流を歓迎します.