V8でのソートの整理

2018年9月28日 · 約24分

Simon Zünd（[@nimODota](https://twitter.com/nimODota)）、一貫性のある比較関数

Array.prototype.sortは、V8でセルフホスティングJavaScriptで実装された最後のビルトインの1つでした。このポート作業を通じて、異なるアルゴリズムや実装戦略を試す機会を得、それを最終的にV8 v7.0 / Chrome 70で安定化することができました。

背景

JavaScriptでのソートは難しいです。このブログポストでは、ソートアルゴリズムとJavaScript言語との相互作用におけるいくつかの奇妙な点を探り、V8を安定したアルゴリズムに移行してパフォーマンスをより予測可能にする旅について説明します。

異なるソートアルゴリズムを比較する際、最悪および平均的なパフォーマンスを、メモリ操作または比較回数の漸近増加の上限（すなわち「Big O」表記）として考慮します。動的言語では、JavaScriptのように比較操作は通常、メモリアクセスよりも桁違いにコストが高いです。これは、ソート中に2つの値を比較する際、通常はユーザーコードの呼び出しが含まれるためです。

ユーザーが提供した比較関数に基づいて、いくつかの数値を昇順にソートする単純な例を見てみましょう。一貫性のある比較関数は、提供された2つの値が小さい、等しい、大きい場合にそれぞれ-1（その他の負の値）、0、または1（その他の正の値）を返します。このパターンに従わない比較関数は一貫性がなく、意図したソート対象の配列を変更するなど、任意の副作用を持つ可能性があります。

const array = [4, 2, 5, 3, 1];

function compare(a, b) {
  // 任意のコード。例: `array.push(1);`。
  return a - b;
}

// 「典型的な」ソート呼び出し。
array.sort(compare);

次の例でも、ユーザーコードへの呼び出しが発生する場合があります。「デフォルト」比較関数は両方の値に対してtoStringを呼び出し、文字列表現に基づく辞書順比較を行います。

const array = [4, 2, 5, 3, 1];

array.push({
  toString() {
    // 任意のコード。例: `array.push(1);`。
    return '42';
  }
});

// 比較関数なしでソート。
array.sort();

アクセサおよびプロトタイプチェーンの相互作用のさらなる楽しみ

ここからは仕様を離れ、「実装に依存する」行動の領域に入ります。仕様には、エンジンがオブジェクト/配列を自由にソートするかどうかを選べる一連の条件がリストされています。エンジンはそれでも一部の基本ルールに従う必要がありますが、それ以外はほとんどが自由裁量です。一方で、エンジン開発者はさまざまな実装を試験する自由を得ます。他方では、ユーザーは合理的な行動を期待しますが、仕様はそれを要求するものではありません。この「合理的な行動」を判断するのが常に簡単ではないのがさらに問題です。

このセクションでは、Array#sortのいくつかの側面においてエンジンの動作が大きく異なることを示します。これらは難しいエッジケースであり、上述のように「正しいことをする」とは何かが常に明確であるとは限りません。このようなコードを書くことを強くお勧めしません; エンジンはそれに最適化されることはありません。

最初の例では、いくつかのアクセサ（すなわちgetterおよびsetter）を含む配列と異なるJavaScriptエンジンでの「呼び出しログ」を示します。アクセサは、結果のソート順が実装依存になる最初のケースです:

const array = [0, 1, 2];

Object.defineProperty(array, '0', {
  get() { console.log('get 0'); return 0; },
  set(v) { console.log('set 0'); }
});

Object.defineProperty(array, '1', {
  get() { console.log('get 1'); return 1; },
  set(v) { console.log('set 1'); }
});

array.sort();

以下は各エンジンでのそのスニペットの出力です。ここで「正しい」または「間違い」の答えはないことに注意してください — 仕様はこれを実装に任せています！

// Chakra
get 0
get 1
set 0
set 1

// JavaScriptCore
get 0
get 1
get 0
get 0
get 1
get 1
set 0
set 1

// V8
get 0
get 0
get 1
get 1
get 1
get 0

#### SpiderMonkey
get 0
get 1
set 0
set 1

次の例ではプロトタイプチェーンとの相互作用を示します。簡略化のために「呼び出しログ」は表示しません。

const object = {
 1: 'd1',
 2: 'c1',
 3: 'b1',
 4: undefined,
 __proto__: {
   length: 10000,
   1: 'e2',
   10: 'a2',
   100: 'b2',
   1000: 'c2',
   2000: undefined,
   8000: 'd2',
   12000: 'XX',
   __proto__: {
     0: 'e3',
     1: 'd3',
     2: 'c3',
     3: 'b3',
     4: 'f3',
     5: 'a3',
     6: undefined,
   },
 },
};
Array.prototype.sort.call(object);

出力は、ソート後のobjectを示しています。ここでも正解はありません。この例は、インデックス付きプロパティとプロトタイプチェーン間の奇妙な相互作用を示しています。

// Chakra
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

// JavaScriptCore
['a2', 'a2', 'a3', 'b1', 'b2', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined]

// V8
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

// SpiderMonkey
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

V8がソート前後に行う処理

:::注意 注意: このセクションは2019年6月に更新され、V8 v7.7でのArray#sortのソート前後の処理変更を反映しています。 :::

V8は、実際にソートを行う前に1つの前処理ステップと、ソート完了後の1つの後処理ステップを持っています。基本的な考え方は、すべての非undefined値を一時リストに収集し、この一時リストをソートしてから、ソートされた値を実際の配列やオブジェクトに書き戻すことです。この方法により、V8はソート処理中にアクセサやプロトタイプチェーンとの相互作用を気にする必要がなくなります。

仕様では、Array#sortが以下の3つのセグメントに概念的に分割可能なソート順を生成することを要求しています:

比較関数に基づいてソートされたすべての非undefined値。
すべてのundefined。
すべての穴、つまり存在しないプロパティ。

実際のソートアルゴリズムは最初のセグメントにのみ適用される必要があります。これを実現するため、V8には以下のような前処理ステップがあります:

lengthをソート対象の配列またはオブジェクトの”length”プロパティの値とする。
numberOfUndefinedsを0とする。
[0, length)の範囲内の各valueについて: a. valueが穴の場合: 何もしない。 b. valueがundefinedの場合: numberOfUndefinedsを1増やす。 c. それ以外の場合: valueを一時リストelementsに追加する。

これらのステップが実行されると、すべての非undefined値が一時リストelementsに含まれます。undefined値は単にカウントされるだけで、elementsに追加されません。上記で述べたように、仕様はundefined値を末尾にソートすることを要求しています。ただし、undefined値はユーザー提供の比較関数に渡されることはないため、発生したundefined値の数をカウントするだけで済みます。

次のステップは、実際にelementsをソートすることです。詳細についてはTimSortセクションを参照してください。

ソートが完了した後、ソートされた値を元の配列またはオブジェクトに書き戻す必要があります。後処理ステップは以下の3つの段階からなります:

[0, elements.length)の範囲でelementsから元のオブジェクトにすべての値を書き戻す。
[elements.length, elements.length + numberOfUndefineds)の範囲内のすべての値をundefinedに設定する。
[elements.length + numberOfUndefineds, length)の範囲内のすべての値を削除する。

ステップ3は、元のオブジェクトにソート範囲内で穴が含まれていた場合に必要です。[elements.length + numberOfUndefineds, length)範囲内の値は既に前方に移動されていますが、ステップ3を実行しないと重複した値が発生します。

歴史

Array.prototype.sortおよびTypedArray.prototype.sortは、JavaScriptで書かれたQuicksort実装を共有していました。ソートアルゴリズム自体は比較的簡単です: 基本はQuicksortで、短い配列（長さ<10）の場合はInsertion Sortにフォールバックしました。Quicksortの再帰がサブ配列の長さ10に達すると、Insertion Sortにフォールバックされました。小さい配列の場合、Insertion Sortは効率的です。その理由は、Quicksortが分割後に2回再帰的に呼び出されるためです。各再帰呼び出しにはスタックフレームの作成（および廃棄）のオーバーヘッドが伴います。

Quicksortではピボット要素の選択が非常に重要です。V8では次の2つの戦略が使用されます:

ピボットは、ソートされるサブ配列の最初、最後、および3番目の要素の中央値として選択されます。小さい配列の場合、その3番目の要素は単に中央の要素です。
大きな配列の場合、サンプルが取得され、次にソートされ、ソートされたサンプルの中央値が上記の計算における3番目の要素として使用されます。

Quicksortの利点の1つは、インプレースでソートすることです。メモリのオーバーヘッドは、大きな配列をソートするときにサンプル用に小さな配列を割り当てることと、log(n)のスタックスペースから来ます。欠点は、安定したアルゴリズムではなく、最悪の場合のシナリオではQuickSortが𝒪(n²)に劣化する可能性があることです。

V8 Torqueの導入

熱心なV8ブログの読者であれば、CodeStubAssemblerまたは略してCSAについて聞いたことがあるかもしれません。CSAは、V8のコンポーネントであり、適切なアーキテクチャ用の機械コードにTurboFanのバックエンドを使用して変換される低レベルのTurboFan IRを直接C++で記述することを可能にします。

CSA は、JavaScript ビルトインのいわゆる「高速パス」を記述するために大いに利用されています。ビルトインの高速パス版は通常、特定の不変条件が成立しているかどうかを確認し（例：プロトタイプチェーンに要素がない、アクセサがない、等）、その後、ビルトインの機能を実現するためにより高速で具体的な操作を使用します。これにより、より一般的なバージョンよりも桁違いに速い実行時間が実現されることがあります。

CSA の欠点は、まさにアセンブリ言語と見なすことができる点にあります。制御フローは明示的な label と goto を使用してモデル化されるため、より複雑なアルゴリズムを CSA で実装するのは読みにくく、エラーが発生しやすくなります。

V8 Torque を紹介します。Torque は TypeScript に似た構文を持つドメイン固有言語で、現在は CSA を唯一のコンパイルターゲットとして使用しています。Torque は CSA とほぼ同じレベルの制御を可能にすると同時に、while や for ループなどの高レベルの構造を提供します。さらに、強い型付けがされており、将来的には、V8 エンジニアに強い保証を提供する自動境界外チェックなどのセキュリティチェックを含む予定です。

最初に V8 Torque で書き直された主要なビルトインは TypedArray#sort と Dataview 操作でした。どちらも、ビルトインを書くために必要な言語機能や慣用表現について Torque 開発者にフィードバックを提供する追加目的を果たしました。この記事執筆時点で、いくつかの JSArray ビルトインは自分自身でホスティングされた JavaScript フォールバック実装が Torque に移行されました（例：Array#unshift）。また、他のものは完全に書き直されました（例：Array#splice と Array#reverse）。

`Array#sort` を Torque に移行する

最初の Array#sort の Torque バージョンは、JavaScript 実装をほぼそのまま移植したものでした。唯一の違いは、大きな配列の場合にサンプリングアプローチを使用する代わりに、ピボット計算のための第 3 の要素がランダムに選択された点です。

これは合理的にうまく機能しましたが、クイックソートを引き続き利用していたため、Array#sort は不安定なままでした。安定した Array#sort を求めるリクエストは V8 のバグトラッカーで最も古いチケットの 1 つです。次のステップとして Timsort を試すことは、いくつかの利点を提供しました。まず、安定しており、いくつかの素晴らしいアルゴリズム上の保証を提供する点が気に入りました（詳細は次のセクション参照）。次に、Torque はまだ作業中であり、Array#sort のようなより複雑なビルトインを Timsort を使って実装することで、Torque を言語として改善するための多くの実用的なフィードバックを得ることができました。

Timsort

2002 年に Python 用として Tim Peters によって開発された Timsort は、適応型で安定したマージソートの変種として最適に説明されるでしょう。その詳細はかなり複雑であり、本人による説明または Wikipedia ページに委ねるべきですが、基本は簡単に理解できます。マージソートは通常再帰的に動作しますが、Timsort は反復的に動作します。配列を左から右に処理し、いわゆるランを探します。ランはすでにソートされている単なるシーケンスです。これには「間違った方向」にソートされているシーケンスも含まれ、これらのシーケンスは逆転させるだけでランを形成できます。ソートプロセスの開始時に、入力の長さに応じて最小ラン長が決定されます。Timsort がこの最小ラン長の自然なランを見つけられない場合、ランは挿入ソートを使用して「人工的にブースト」されます。

この方法で見つかったランは、各ランの開始インデックスと長さを記憶するスタックを使用して追跡されます。時々、スタック上のランが統合され、最終的に 1 つのソートされたランだけが残ります。Timsort は、ランを統合する際にバランスを維持しようとします。一方では、ランのデータがキャッシュ内にある可能性が高いため、早期に統合したいという意図があります。他方では、データのパターンを利用するためになるべく遅く統合したいという意図があります。これを達成するために、Timsort は 2 つの不変条件を維持します。A、B、および C がトップ 3 のランであると仮定すると：

|C| > |B| + |A|
|B| > |A|

ランスタックが A と B を統合する前後の様子

画像は |A| > |B| の場合を示しており、B が 2 つのランのうち小さい方と統合されます。

注意すべきは、Timsort は連続するランのみを統合する点であり、これは安定性を維持するために必要です。そうでなければ、同値の要素がラン間で移動されてしまいます。また、第 1 不変条件により、ランの長さが少なくともフィボナッチ数と同じ速さで増加することが保証され、最大配列長が分かっている場合、ランスタックのサイズに上限が設けられます。

これで、すでにソートされたシーケンスはソートに 𝒪(n) を必要とするだけであることが分かります。このような配列は統合を必要としない単一のランを生じます。一方で最悪の場合は 𝒪(n log n) となります。これらのアルゴリズム特性と Timsort の安定性の性質を考慮し、最終的には Timsort を Quicksort よりも選んだ理由のいくつかとなりました。

Torque での Timsort の実装

組み込み関数（Builtins）は通常、さまざまな変数に依存して実行時に選択される異なるコードパスを持っています。最も汎用的なバージョンは、JSProxyであるか、インターセプターがあるか、またはプロパティの取得または設定時にプロトタイプチェーンを検索する必要があるかに関係なく、あらゆる種類のオブジェクトを処理することができます。汎用的なコードパスは多くの場合かなり遅いですが、それはすべての可能性を考慮しなければならないためです。しかし、ソートするオブジェクトが単純なJSArrayであり、Smisのみを含むことを事前に知っている場合、これらの高価な[[Get]]および[[Set]]操作を単純なFixedArrayへのロードおよびストアに置き換えることができます。主な区別点はElementsKindです。

次に問題となるのは、高速経路（fast-path）をどのように実装するかです。コアアルゴリズムはすべて同じままですが、要素へのアクセス方法はElementsKindに基づいて変化します。この問題を解決する方法の1つとして、各呼び出し箇所で正しい「アクセサー」にディスパッチすることが挙げられます。つまり、各「ロード」や「ストア」操作にスイッチを設け、選択された高速経路に基づいて異なる分岐を選ぶ形式です。

別の解法（そして試された最初のアプローチ）は、各高速経路専用に組み込み関数全体をコピーし、正しいロード/ストアアクセス方法をインライン化することです。しかし、このアプローチはTimsortには適していないことが判明しました。それは非常に大きい組み込み関数であり、各高速経路専用にコピーすると合計106 KBが必要となり、単一の組み込み関数には多すぎる容量となったためです。

最終的な解法は少し異なります。各高速経路における各ロード/ストア操作は、それぞれ独自の「ミニ組み込み関数」に分割されます。以下はFixedDoubleArrayに対する「ロード」操作を示すコード例です。

Load<FastDoubleElements>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  try {
    const elems: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(elements);
    const value: float64 =
        LoadDoubleWithHoleCheck(elems, index) otherwise Bailout;
    return AllocateHeapNumberWithValue(value);
  }
  label Bailout {
    // 前処理のステップではすべての穴を取り除き、配列の先頭に要素をコンパクト化しています。
    // ここで穴を見つけるということは、cmp関数またはToStringが配列を変更したことを意味します。
    return Failure(sortState);
  }
}

比較として、最も汎用的な「ロード」操作は単にGetPropertyへの呼び出しにすぎません。しかし、上記のバージョンは、Numberをロードして変換する効率的で高速な機械コードを生成するのに対し、GetPropertyは別の組み込み関数への呼び出しであり、プロトタイプチェーンのルックアップを含む可能性があるアクセサー関数を実行する可能性があります。

builtin Load<ElementsAccessor : type>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  return GetProperty(context, elements, index);
}

高速経路は、単純に一連の関数ポインタになります。これにより、コアアルゴリズムのコピーが1つだけ必要になり、すべての関連する関数ポインタを事前に設定することで済みます。これにより必要なコードスペースが大幅に削減され（20kまで縮小）、各アクセサーサイトで間接的な分岐が発生するというコストが付随します。この問題はembedded builtinsの使用を採用した最近の変更によりさらに悪化しています。

ソート状態

上記の図は「ソート状態」を示しています。これは、ソート中に必要なすべてを追跡するためのFixedArrayです。Array#sortが呼び出されるたびに、このソート状態が割り当てられます。エントリ4から7は、前述の高速経路に関連する関数ポインタのセットです。

「チェック」組み込み関数は、ユーザーのJavaScriptコードから戻るたびに、現在の高速経路で継続できるかを確認するために使用されます。これには「初期受信者マップ」と「初期受信者の長さ」が使用されます。ユーザーコードが現在のオブジェクトを変更した場合、単にソート処理を中止して、すべてのポインタを最も汎用的なバージョンにリセットし、ソートプロセスを再開します。スロット8の「バイアウト状態」はこのリセットを示すために使用されます。

「比較」エントリは2つの異なる組み込み関数を指すことができます。1つはユーザー提供の比較関数を呼び出し、もう1つはデフォルトの比較を実行し、両方の引数にtoStringを呼び出して辞書式比較を行います。

その他のフィールド（高速経路IDを除く）はTimsort特有のものです。ランスタック（上記で説明）はサイズ85で初期化されており、長さ2⁶⁴までの配列をソートするのに十分です。一時的な配列はランをマージするために使用されます。必要に応じてサイズが拡張されますが、入力の長さnのn/2を超えることはありません。

パフォーマンスのトレードオフ

JavaScriptのセルフホストからTorqueにソート処理を移行することで、パフォーマンスのトレードオフが生じます。Array#sortがTorqueで記述されるため、静的にコンパイルされたコードになります。特定のElementsKindに対して高速化パスを構築できますが、型フィードバックを活用する高度に最適化されたTurboFanバージョンほど高速にはなりません。一方で、コードがJITコンパイルされるほど頻繁に呼び出されない場合や、呼び出し元がメガモーフィックである場合、インタプリタや遅い汎用バージョンを使用せざるを得ません。また、セルフホストされたJavaScriptバージョンの解析、コンパイル、そして可能な最適化には、Torque実装では不要なオーバーヘッドが含まれます。

Torqueアプローチではソートに対して同じピーク性能を期待することはできませんが、パフォーマンスの突然の低下を避けることができます。その結果、以前よりもかなり予測可能なソート性能が得られます。Torqueは現在非常に動的に変化しており、CSAをターゲットにするだけでなく、将来的にはTurboFanをターゲットにしてTorqueで記述されたコードのJITコンパイルを可能にする可能性があります。

マイクロベンチマーク

Array#sortの実装に取り掛かる前に、多数のマイクロベンチマークを追加して、この再実装が与える影響をより良く理解できるようにしました。最初のチャートは、ユーザー提供の比較関数を使ってさまざまなElementsKindをソートする「通常の」使い方を示しています。

これらの場合、JITコンパイラは多くの作業が可能です。なぜなら、ほとんどがソート処理だからです。JavaScriptバージョンでは最適化コンパイラが比較関数をインライン化することができますが、TorqueケースではJavaScriptのビルトインから呼び出す際のオーバーヘッドがあります。それでもほとんどの場合でパフォーマンスが向上しています。

次のチャートは、すでに完全にソートされている配列や、サブシーケンスがいずれかの方向で既にソートされている配列を処理する際のTimsortの影響を示しています。このチャートではクイックソートを基準にし、Timsortでの速度向上を示しています（例：「DownDown」の場合、配列が2つの逆順にソートされたシーケンスで構成されている場合、最大17倍の速度向上があります）。ランダムデータの場合を除いて、他のすべてのケースでTimsortのパフォーマンスが良好であることが見て取れます。これは、前述のマイクロベンチマークでQuicksortがTimsortよりも優れていたPACKED_SMI_ELEMENTSをソートしている場合も同様です。

Web Tooling ベンチマーク

Web Tooling ベンチマークは、BabelやTypeScriptなど、Web開発者が通常使用するツールのワークロードを集めたものです。このチャートでは、JavaScriptクイックソートを基準にし、Timsortによる速度向上を比較しています。ほとんどのベンチマークで同じパフォーマンスを維持していますが、例外としてchaiが存在します。

chaiベンチマークは、単一の比較関数（文字列距離計算）の内部で全体の時間の3分の1を費やしています。このベンチマークはchai自体のテストスイートです。このデータのために、Timsortはこのケースではいくつかの追加の比較を必要とし、特定の比較関数内部に大量の時間を費やすため、全体の実行時間に大きな影響を及ぼします。

メモリへの影響

モバイルおよびデスクトップで約50のサイトを閲覧しながらV8ヒープスナップショットを分析したところ、メモリの後退や改善は見られませんでした。一方では、これは驚きです：クイックソートからTimsortへの切り替えにより、マージランのための一時的な配列が必要になり、サンプリング用の一時的な配列よりもかなり大きくなる可能性があります。しかし一方で、これらの一時的な配列は非常に短命です（sort呼び出しの間だけ）。そしてV8の新しいスペースで迅速に割り当てて破棄することができます。

結論

まとめると、Torqueで実装されたTimsortのアルゴリズム特性と予測可能な性能動作に非常に良い印象を持っています。TimsortはV8 v7.0およびChrome 70以降で利用可能です。良いソートをお楽しみください！

背景​

アクセサおよびプロトタイプチェーンの相互作用のさらなる楽しみ​

V8がソート前後に行う処理​

歴史​

V8 Torqueの導入​

Array#sort を Torque に移行する​

Timsort​

Torque での Timsort の実装​

ソート状態​

パフォーマンスのトレードオフ​

マイクロベンチマーク​

Web Tooling ベンチマーク​

メモリへの影響​

結論​

背景