数週間前、 「RustとWebAssemblyでソースマップを酸化する」という投稿を発見しました。
Twitterで広め、 source-mapライブラリの通常のJavaScriptをWebAssemblyでコンパイルされたRustに置き換えることによるパフォーマンスの向上について説明します

この投稿は、私がRustやWASMの大ファンだったからではなく、同様のパフォーマンスを達成するためにJavascriptに欠けている言語機能と最適化に常に関心があったために興味をそそりました。

そこで、GitHubからライブラリをダウンロードし、少しパフォーマンススタディを行いました。これについては、ここでほぼ逐語的に説明します。

内容

• コード検索
• 純粋なJavaScriptでバージョンをプロファイルします
• 並べ替えの最適化-引数の調整
• 並べ替えの最適化-単相化
• 解析の最適化-セグメントキャッシュの削除
• ソートの最適化-アルゴリズムの改善
• 生成された並べ替えの最適化
• 解析の最適化-GCの負荷を軽減
• 解析の最適化-文字列の代わりにUint8Arrayを使用
• 開始時の全般的な改善
• source-mapの「酸化」バージョンとの比較
• 学んだ教訓
• あとがき

コード検索

私の研究では、1月20日のコミット69abb960c97606df99408e6869d66e014aa0fb51のほぼ標準のx64.releaseビルドV8を使用しています。 標準構成との私の不一致は、必要に応じて、生成されたマシンコードをより深く掘り下げるために、GNフラグを介して逆アセンブラをオンにしたことだけです。

 ╭─ ~/src/v8/v8 ‹master› ╰─$ gn args out.gn/x64.release --list --short --overrides-only is_debug = false target_cpu = "x64" use_goma = true v8_enable_disassembler = true 

次に、 source-mapモジュールのsource-mapから取得しました：

• c97d38bコミット 。これは、Rust / WASMの実装を開始する前にdist/source-map.js最後に更新したものです。
• 51cf770をコミットします 。これは、調査時の最後のコミットでした。

純粋なJavaScriptでバージョンをプロファイルします

クリーンなJSバージョンのベンチマークを実行するのは簡単でした：

 ╭─ ~/src/source-map/bench ‹ c97d38b› ╰─$ d8 bench-shell-bindings.js Parsing source map console.timeEnd: iteration, 4655.638000 console.timeEnd: iteration, 4751.122000 console.timeEnd: iteration, 4820.566000 console.timeEnd: iteration, 4996.942000 console.timeEnd: iteration, 4644.619000 [Stats samples: 5, total: 23868 ms, mean: 4773.6 ms, stddev: 161.22112144505135 ms] 

最初にしたことは、ベンチマークのシリアル化部分をオフにすることでした。

 diff --git a/bench/bench-shell-bindings.js b/bench/bench-shell-bindings.js index 811df40..c97d38b 100644 --- a/bench/bench-shell-bindings.js +++ b/bench/bench-shell-bindings.js @@ -19,5 +19,5 @@ load("./bench.js"); print("Parsing source map"); print(benchmarkParseSourceMap()); print(); -print("Serializing source map"); -print(benchmarkSerializeSourceMap()); +// print("Serializing source map"); +// print(benchmarkSerializeSourceMap()); 

次に、これをLinux perfプロファイラーに投げ込みました。

 ╭─ ~/src/source-map/bench ‹perf-work› ╰─$ perf record -g d8 --perf-basic-prof bench-shell-bindings.js Parsing source map console.timeEnd: iteration, 4984.464000 ^C[ perf record: Woken up 90 times to write data ] [ perf record: Captured and wrote 24.659 MB perf.data (~1077375 samples) ] 

--perf-basic-profフラグをd8バイナリに渡すと、V8がマッピング/tmp/perf-$pid.mapマッピングファイル/tmp/perf-$pid.mapを生成することに/tmp/perf-$pid.map 。 このファイルにより、 perf reportはJIT生成のマシンコードを理解できます。

ここに、実行のメインスレッドを表示した後のperf report --no-childrenから得たものを示します。

 Overhead Symbol 17.02% *doQuickSort ../dist/source-map.js:2752 11.20% Builtin:ArgumentsAdaptorTrampoline 7.17% *compareByOriginalPositions ../dist/source-map.js:1024 4.49% Builtin:CallFunction_ReceiverIsNullOrUndefined 3.58% *compareByGeneratedPositionsDeflated ../dist/source-map.js:1063 2.73% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 2.11% Builtin:StringEqual 1.93% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.66% *doQuickSort ../dist/source-map.js:2752 1.25% v8::internal::StringTable::LookupStringIfExists_NoAllocate 1.22% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.21% Builtin:StringCharAt 1.16% Builtin:Call_ReceiverIsNullOrUndefined 1.14% v8::internal::(anonymous namespace)::StringTableNoAllocateKey::IsMatch 0.90% Builtin:StringPrototypeSlice 0.86% Builtin:KeyedLoadIC_Megamorphic 0.82% v8::internal::(anonymous namespace)::MakeStringThin 0.80% v8::internal::(anonymous namespace)::CopyObjectToObjectElements 0.76% v8::internal::Scavenger::ScavengeObject 0.72% v8::internal::String::VisitFlat<v8::internal::IteratingStringHasher> 0.68% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 0.64% *doQuickSort ../dist/source-map.js:2752 0.56% v8::internal::IncrementalMarking::RecordWriteSlow 

実際、 「Oxidizing Source Maps ...」で述べたように、このベンチマークは基本的にソートをロードしますdoQuickSort関数はプロファイルの上部に表示され、リストの数倍下に表示されます（つまり、数回最適化および最適化解除されました） 。

並べ替えの最適化-引数の調整

プロファイラーで際立っている点の1つは、疑わしいエントリ、つまりBuiltin:ArgumentsAdaptorTrampolineとBuiltin:CallFunction_ReceiverIsNullOrUndefinedです。これらはV8実装の一部のようです。 perf reportに、それらにつながる呼び出しのチェーンを明らかにするように依頼すると、これらの関数は主にソートコードから呼び出されることがわかります。

 - Builtin:ArgumentsAdaptorTrampoline + 96.87% *doQuickSort ../dist/source-map.js:2752 + 1.22% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 + 0.68% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 + 0.68% Builtin:InterpreterEntryTrampoline + 0.55% *doQuickSort ../dist/source-map.js:2752 - Builtin:CallFunction_ReceiverIsNullOrUndefined + 93.88% *doQuickSort ../dist/source-map.js:2752 + 2.24% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 + 2.01% Builtin:InterpreterEntryTrampoline + 1.49% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 

そして、ここでコードを見てみましょう。 クイックソートの実装はlib/quick-sort.jsあり、 lib/source-map-consumer.jsのパーサーコードから呼び出されます。
ソートに使用される比較関数（コンパレータ）は、 compareByGeneratedPositionsDeflatedおよびcompareByOriginalPositionsです。

これらの比較関数の定義とクイックソート実装での呼び出し方法を見ると、呼び出しの場所に不一致のアリティがあることがわかります。

 function compareByOriginalPositions(mappingA, mappingB, onlyCompareOriginal) { // ... } function compareByGeneratedPositionsDeflated(mappingA, mappingB, onlyCompareGenerated) { // ... } function doQuickSort(ary, comparator, p, r) { // ... if (comparator(ary[j], pivot) <= 0) { // ... } // ... } 

ライブラリソースをquickSortと、テスト以外では、これら2つの関数でのみquickSortが呼び出されていることがquickSortます。

しかし、アリティを修正したらどうなるでしょうか？

 diff --git a/dist/source-map.js b/dist/source-map.js index ade5bb2..2d39b28 100644 --- a/dist/source-map.js +++ b/dist/source-map.js @@ -2779,7 +2779,7 @@ return /* **** */ (function(modules) { // webpackBootstrap // // * Every element in `ary[i+1 .. j-1]` is greater than the pivot. for (var j = p; j < r; j++) { - if (comparator(ary[j], pivot) <= 0) { + if (comparator(ary[j], pivot, false) <= 0) { i += 1; swap(ary, i, j); } 

_{[注：アセンブリプロセスに時間をかけたくないため、 dist/source-map.js直接編集します]}

 ╭─ ~/src/source-map/bench ‹perf-work› [Fix comparator invocation arity] ╰─$ d8 bench-shell-bindings.js Parsing source map console.timeEnd: iteration, 4037.084000 console.timeEnd: iteration, 4249.258000 console.timeEnd: iteration, 4241.165000 console.timeEnd: iteration, 3936.664000 console.timeEnd: iteration, 4131.844000 console.timeEnd: iteration, 4140.963000 [Stats samples: 6, total: 24737 ms, mean: 4122.833333333333 ms, stddev: 132.18789657150916 ms] 

アリティの不一致を簡単に修正することで、ベンチマークのV8値を4774ミリ秒から4123ミリ秒に14％改善しました。 ベンチマークを再度プロファイルすると、 ArgumentsAdaptorTrampolineがそこから完全に消えていることがわかります。 なぜ彼は初めてそこにいたのですか？

ArgumentsAdaptorTrampolineは、javascript呼び出しの可変性をサポートするためのV8メカニズムであることがわかります。2つだけで3つの引数を持つ関数を呼び出すことができます。この場合、3番目の引数にはundefined値が入力されます。 V8は、スタック上に新しいフレームを作成し、そこに引数をコピーして、ターゲット関数を呼び出すことでこれを行います。

_{[ パフォーマンススタックについて聞いたことがない場合は、 ウィキペディアとフランシスコヒンケルマンの投稿をご覧ください。]}

コールドコードではこのようなコストは無視できますが、ここでは、ベンチマークの起動時にcomparatorが何百万回も呼び出されたため、引数を適応させるための追加コストが発生しました。

注意深い読者は、暗黙のundefined以前に使用された場所にfalseを明示的に渡すことに気付くかもしれません。 これもパフォーマンスの向上に貢献しているようです。 falseをvoid 0置き換えると、わずかに悪い値が得られます。

 diff --git a/dist/source-map.js b/dist/source-map.js index 2d39b28..243b2ef 100644 --- a/dist/source-map.js +++ b/dist/source-map.js @@ -2779,7 +2779,7 @@ return /* **** */ (function(modules) { // webpackBootstrap // // * Every element in `ary[i+1 .. j-1]` is greater than the pivot. for (var j = p; j < r; j++) { - if (comparator(ary[j], pivot, false) <= 0) { + if (comparator(ary[j], pivot, void 0) <= 0) { i += 1; swap(ary, i, j); } 

 ╭─ ~/src/source-map/bench ‹perf-work U› [Fix comparator invocation arity] ╰─$ ~/src/v8/v8/out.gn/x64.release/d8 bench-shell-bindings.js Parsing source map console.timeEnd: iteration, 4215.623000 console.timeEnd: iteration, 4247.643000 console.timeEnd: iteration, 4425.871000 console.timeEnd: iteration, 4167.691000 console.timeEnd: iteration, 4343.613000 console.timeEnd: iteration, 4209.427000 [Stats samples: 6, total: 25610 ms, mean: 4268.333333333333 ms, stddev: 106.38947316346669 ms] 

そうかもしれないが、議論の適応はV8に非常に特有のようだ。 SpiderMonkeyのベンチマークを開始したとき、一致するアリティからの著しいパフォーマンスの向上は見られませんでした。

 ╭─ ~/src/source-map/bench ‹ d052ea4› [Disabled serialization part of the benchmark] ╰─$ sm bench-shell-bindings.js Parsing source map [Stats samples: 8, total: 24751 ms, mean: 3093.875 ms, stddev: 327.27966571700836 ms] ╭─ ~/src/source-map/bench ‹perf-work› [Fix comparator invocation arity] ╰─$ sm bench-shell-bindings.js Parsing source map [Stats samples: 8, total: 25397 ms, mean: 3174.625 ms, stddev: 360.4636187025859 ms] 

_{[ jsvuツールの Matthias Byensのおかげで、SpiderMonkeyシェルのインストールは非常に簡単になりました]}

ソートコードに戻りましょう。 ベンチマークのプロファイルを再度作成すると、 ArgumentsAdaptorTrampolineプロファイルから消えたことがCallFunction_ReceiverIsNullOrUndefinedますが、 CallFunction_ReceiverIsNullOrUndefinedはまだここにあります。 これは驚くことではありません。なぜなら、私たちはまだcomparator呼び出しているからです。

並べ替えの最適化-単相化

通常、何が関数を呼び出すよりも速く実行されますか？ 彼の不在！

ここでの明らかなオプションは、 doQuickSort比較関数を埋め込むことdoQuickSort 。 ただし、 doQuickSortが異なる関数で呼び出されるという事実に直面しています。

これを回避するために、クローニングによってdoQuickSortを単doQuickSortしようとします。 方法は次のとおりです。

doQuickSort 、 doQuickSortおよびその他のヘルパーユーティリティをSortTemplate関数でラップすることから始めましょう。

 function SortTemplate(comparator) { function swap(ary, x, y) { // ... } function randomIntInRange(low, high) { // ... } function doQuickSort(ary, p, r) { // ... } return doQuickSort; } 

次に、 SortTemplateを文字列に変換し、 Functionコンストラクターを介してFunctionに渡して解析することにより、並べ替え手順のクローンを作成できます。

 function cloneSort(comparator) { let template = SortTemplate.toString(); let templateFn = new Function(`return ${template}`)(); return templateFn(comparator); // Invoke template to get doQuickSort } 

cloneSortを使用して、使用する各コンパレータのソート関数を作成できます。

 let sortCache = new WeakMap(); // Cache for specialized sorts. exports.quickSort = function (ary, comparator) { let doQuickSort = sortCache.get(comparator); if (doQuickSort === void 0) { doQuickSort = cloneSort(comparator); sortCache.set(comparator, doQuickSort); } doQuickSort(ary, 0, ary.length - 1); }; 

ベンチマークを再起動すると、次のことがわかります。

 ╭─ ~/src/source-map/bench ‹perf-work› [Clone sorting functions for each comparator] ╰─$ d8 bench-shell-bindings.js Parsing source map console.timeEnd: iteration, 2955.199000 console.timeEnd: iteration, 3084.979000 console.timeEnd: iteration, 3193.134000 console.timeEnd: iteration, 3480.459000 console.timeEnd: iteration, 3115.011000 console.timeEnd: iteration, 3216.344000 console.timeEnd: iteration, 3343.459000 console.timeEnd: iteration, 3036.211000 [Stats samples: 8, total: 25423 ms, mean: 3177.875 ms, stddev: 181.87633161024556 ms] 

平均時間が4268ミリ秒から3177ミリ秒に減少したことがわかります（25％改善）。

プロファイリングは次の図を示します。

  Overhead Symbol 14.95% *doQuickSort :44 11.49% *doQuickSort :44 3.29% Builtin:StringEqual 3.13% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.86% v8::internal::StringTable::LookupStringIfExists_NoAllocate 1.86% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.72% Builtin:StringCharAt 1.67% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.61% v8::internal::Scavenger::ScavengeObject 1.45% v8::internal::(anonymous namespace)::StringTableNoAllocateKey::IsMatch 1.23% Builtin:StringPrototypeSlice 1.17% v8::internal::(anonymous namespace)::MakeStringThin 1.08% Builtin:KeyedLoadIC_Megamorphic 1.05% v8::internal::(anonymous namespace)::CopyObjectToObjectElements 0.99% v8::internal::String::VisitFlat<v8::internal::IteratingStringHasher> 0.86% clear_page_c_e 0.77% v8::internal::IncrementalMarking::RecordWriteSlow 0.48% Builtin:MathRandom 0.41% Builtin:RecordWrite 0.39% Builtin:KeyedLoadIC 

comparator呼び出しに関連するオーバーヘッドは、プロファイルから完全に消えました。

この瞬間、私はマッピングのソートに比べて、マッピングの解析にどれだけ時間がかかるかに興味を持ちました。 解析コードに行き、 Date.now()いくつかの呼び出しを追加しました：

_{[ performance.now()を追加したいのですが、SpiderMonkeyシェルはこれをサポートしていません。]}

 diff --git a/dist/source-map.js b/dist/source-map.js index 75ebbdf..7312058 100644 --- a/dist/source-map.js +++ b/dist/source-map.js @@ -1906,6 +1906,8 @@ return /* **** */ (function(modules) { // webpackBootstrap var generatedMappings = []; var mapping, str, segment, end, value; + + var startParsing = Date.now(); while (index < length) { if (aStr.charAt(index) === ';') { generatedLine++; @@ -1986,12 +1988,20 @@ return /* **** */ (function(modules) { // webpackBootstrap } } } + var endParsing = Date.now(); + var startSortGenerated = Date.now(); quickSort(generatedMappings, util.compareByGeneratedPositionsDeflated); this.__generatedMappings = generatedMappings; + var endSortGenerated = Date.now(); + var startSortOriginal = Date.now(); quickSort(originalMappings, util.compareByOriginalPositions); this.__originalMappings = originalMappings; + var endSortOriginal = Date.now(); + + console.log(`${}, ${endSortGenerated - startSortGenerated}, ${endSortOriginal - startSortOriginal}`); + console.log(`sortGenerated: `); + console.log(`sortOriginal: `); }; 

結果は次のとおりです。

 ╭─ ~/src/source-map/bench ‹perf-work U› [Clone sorting functions for each comparator] ╰─$ d8 bench-shell-bindings.js Parsing source map parse: 1911.846 sortGenerated: 619.5990000000002 sortOriginal: 905.8220000000001 parse: 1965.4820000000004 sortGenerated: 602.1939999999995 sortOriginal: 896.3589999999995 ^C 

したがって、解析とソートの時間は、V8とSpiderMonkeyでベンチマーク起動の各反復について調べます。

V8では、マッピングのソートとほぼ同じ時間をマッピングの分析に費やすようです。 SpiderMonkeyでは、解析ははるかに高速ですが、並べ替えが遅くなります。 これにより、解析コードを確認できました。

解析の最適化-セグメントキャッシュの削除

もう一度プロファイルを見てみましょう。

 Overhead Symbol 18.23% *doQuickSort :44 12.36% *doQuickSort :44 3.84% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 3.07% Builtin:StringEqual 1.92% v8::internal::StringTable::LookupStringIfExists_NoAllocate 1.85% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.59% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 1.54% Builtin:StringCharAt 1.52% v8::internal::(anonymous namespace)::StringTableNoAllocateKey::IsMatch 1.38% v8::internal::Scavenger::ScavengeObject 1.27% Builtin:KeyedLoadIC_Megamorphic 1.22% Builtin:StringPrototypeSlice 1.10% v8::internal::(anonymous namespace)::MakeStringThin 1.05% v8::internal::(anonymous namespace)::CopyObjectToObjectElements 1.03% v8::internal::String::VisitFlat<v8::internal::IteratingStringHasher> 0.88% clear_page_c_e 0.51% Builtin:MathRandom 0.48% Builtin:KeyedLoadIC 0.46% v8::internal::IteratingStringHasher::Hash 0.41% Builtin:RecordWrite 

既にわかっているJavaScriptコードを削除すると、次のようになります。

 Overhead Symbol 3.07% Builtin:StringEqual 1.92% v8::internal::StringTable::LookupStringIfExists_NoAllocate 1.54% Builtin:StringCharAt 1.52% v8::internal::(anonymous namespace)::StringTableNoAllocateKey::IsMatch 1.38% v8::internal::Scavenger::ScavengeObject 1.27% Builtin:KeyedLoadIC_Megamorphic 1.22% Builtin:StringPrototypeSlice 1.10% v8::internal::(anonymous namespace)::MakeStringThin 1.05% v8::internal::(anonymous namespace)::CopyObjectToObjectElements 1.03% v8::internal::String::VisitFlat<v8::internal::IteratingStringHasher> 0.88% clear_page_c_e 0.51% Builtin:MathRandom 0.48% Builtin:KeyedLoadIC 0.46% v8::internal::IteratingStringHasher::Hash 0.41% Builtin:RecordWrite 

個々のレコードのコールチェーンを調べ始めたとき、それらの多くがKeyedLoadIC_Megamorphicを通過することがKeyedLoadIC_Megamorphicました。

 - 1.92% v8::internal::StringTable::LookupStringIfExists_NoAllocate - v8::internal::StringTable::LookupStringIfExists_NoAllocate + 99.80% Builtin:KeyedLoadIC_Megamorphic - 1.52% v8::internal::(anonymous namespace)::StringTableNoAllocateKey::IsMatch - v8::internal::(anonymous namespace)::StringTableNoAllocateKey::IsMatch - 98.32% v8::internal::StringTable::LookupStringIfExists_NoAllocate + Builtin:KeyedLoadIC_Megamorphic + 1.68% Builtin:KeyedLoadIC_Megamorphic - 1.27% Builtin:KeyedLoadIC_Megamorphic - Builtin:KeyedLoadIC_Megamorphic + 57.65% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 + 22.62% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 + 15.91% *SourceMapConsumer_parseMappings ../dist/source-map.js:1894 + 2.46% Builtin:InterpreterEntryTrampoline + 0.61% BytecodeHandler:Mul + 0.57% *doQuickSort :44 - 1.10% v8::internal::(anonymous namespace)::MakeStringThin - v8::internal::(anonymous namespace)::MakeStringThin - 94.72% v8::internal::StringTable::LookupStringIfExists_NoAllocate + Builtin:KeyedLoadIC_Megamorphic + 3.63% Builtin:KeyedLoadIC_Megamorphic + 1.66% v8::internal::StringTable::LookupString 

このような呼び出しスタックのソートは、コードがobj[key]形式で多くのキーマッピングを実行することを通知しました。ここで、 keyは動的に生成された文字列です。 ソースを見ると、 次のコードが見つかりました。

 // Because each offset is encoded relative to the previous one, // many segments often have the same encoding. We can exploit this // fact by caching the parsed variable length fields of each segment, // allowing us to avoid a second parse if we encounter the same // segment again. for (end = index; end < length; end++) { if (this._charIsMappingSeparator(aStr, end)) { break; } } str = aStr.slice(index, end); segment = cachedSegments[str]; if (segment) { index += str.length; } else { segment = []; while (index < end) { base64VLQ.decode(aStr, index, temp); value = temp.value; index = temp.rest; segment.push(value); } // ... cachedSegments[str] = segment; } 

このコードは、Base64 VLQエンコードシーケンスのデコードを担当します。つまり、ラインAは[0]としてデコードされ、 UAAAA [10,0,0,0,0]デコードされます。 エンコードプロセス自体をよりよく理解したい場合は、ソースマップの内部についてこの投稿を参照することをお勧めします。

このコードは、各シーケンスを個別にデコードする代わりに、復号化されたセグメントをキャッシュしようとします：区切り文字（ ,または; ）を楽しみ、現在の位置から区切り文字まで部分文字列を抽出し、キャッシュにそのようなセグメントがあるかどうかを確認します-そして、ある場合、キャッシュされたセグメントを返します。それ以外の場合は、解析してキャッシュに入れます。

キャッシング（ メモ化でもあります ）は非常に強力な最適化手法です。ただし、キャッシュ自体を処理し、そこで結果を見つけることが、それ自体を再計算するよりも安価である場合にのみ意味があります。

抽象分析

これら2つの操作を抽象的に比較してみましょう。

一方で、クリーンな分析：

セグメントを解析して、各文字を1回調べます。 各文字について、base64文字を整数値に変換するために、いくつかの比較および算術演算が実行されます。 次に、いくつかのビット演算が実行され、これらの数値が1つの大きな数値に結合されます。 次に、デコードされた値が配列に格納され、セグメントの次の部分に進みます。 セグメントは5つの要素に制限されています。

一方、キャッシュ：

1. キャッシュされた値を見つけるために、セグメントのすべての文字を一周してその終わりを見つけます。
2. JS VMでの文字列の実装方法に応じて、配置し、場合によってはコピーする必要がある部分文字列を抽出します。
3. この行を辞書のキーとして使用します：
   
   1. まず、VMがこの文字列のハッシュを計算する必要があり（再度渡すと、文字に対してさまざまなビット単位の操作を実行します）、文字列を内部化する必要があります（実装によって異なります）。
   2. 次に、VMはテーブルでハッシュマッチングを実行する必要があります。これには、値に基づいてキーにアクセスし、他のキーと比較する必要があります（個々の文字を再度表示する必要がある場合があります）。

一般に、直接解析が高速になるように見えます。これは、JS VMが個別の算術演算とビット演算でうまく機能することを意味します。キャッシュにヒットするかどうかを判断するだけです。

プロファイリングもこれを確認しているようです： KeyedLoadIC_Megamorphic 、上記のコードのcachedSegments[str]ように、V8でキーアクセスを実装するために使用されcachedSegments[str] 。

これらの観察に基づいて、いくつかの実験を行いました。 最初に、解析の終了時にcachedSegmentsキャッシュの大きさを確認しました。 小さいほど、より効率的なキャッシュが可能になります。

それは非常に強く成長することがわかります：

 Object.keys(cachedSegments).length = 155478 

別個のマイクロベンチマーク

今、私は小さな別個のベンチマークを書くことにしました：

 //    [n] ,      [v], // ..  0, v, 2*v, ... ,     1, 1 + v, 1 + 2*v, ... // [base]      -    //    // // :   [v],    [cachedSegments] function makeString(n, v, base) { var arr = []; for (var i = 0; i < n; i++) { arr.push([0, base + (i % v), 0, 0].map(base64VLQ.encode).join('')); } return arr.join(';') + ';'; } //   [f]   [str]. function bench(f, str) { for (var i = 0; i < 1000; i++) { f(str); } } //     [f]  [str]. //    [v]   function measure(v, str, f) { var start = Date.now(); bench(f, str); var end = Date.now(); report(`${v}, ${f.name}, ${(end - start).toFixed(2)}`); } async function measureAll() { for (let v = 1; v <= 256; v *= 2) { //    1000     [v] , //   [cachedSegments]   [v]  . let str = makeString(1000, v, 1024 * 1024); let arr = encoder.encode(str); //  10     . for (var j = 0; j < 10; j++) { measure(j, i, str, decodeCached); measure(j, i, str, decodeNoCaching); measure(j, i, str, decodeNoCachingNoStrings); measure(j, i, arr, decodeNoCachingNoStringsPreEncoded); await nextTick(); } } } function nextTick() { return new Promise((resolve) => setTimeout(resolve)); } 

Base64 VLQ, .

— decodeCached , source-map — :

 function decodeCached(aStr) { var length = aStr.length; var cachedSegments = {}; var end, str, segment, value, temp = {value: 0, rest: 0}; const decode = base64VLQ.decode; var index = 0; while (index < length) { // Because each offset is encoded relative to the previous one, // many segments often have the same encoding. We can exploit this // fact by caching the parsed variable length fields of each segment, // allowing us to avoid a second parse if we encounter the same // segment again. for (end = index; end < length; end++) { if (_charIsMappingSeparator(aStr, end)) { break; } } str = aStr.slice(index, end); segment = cachedSegments[str]; if (segment) { index += str.length; } else { segment = []; while (index < end) { decode(aStr, index, temp); value = temp.value; index = temp.rest; segment.push(value); } if (segment.length === 2) { throw new Error('Found a source, but no line and column'); } if (segment.length === 3) { throw new Error('Found a source and line, but no column'); } cachedSegments[str] = segment; } index++; } } 

— decodeNoCaching . , decodeCached , . . Array Int32Array segment .

 function decodeNoCaching(aStr) { var length = aStr.length; var cachedSegments = {}; var end, str, segment, temp = {value: 0, rest: 0}; const decode = base64VLQ.decode; var index = 0, value; var segment = new Int32Array(5); var segmentLength = 0; while (index < length) { segmentLength = 0; while (!_charIsMappingSeparator(aStr, index)) { decode(aStr, index, temp); value = temp.value; index = temp.rest; if (segmentLength >= 5) throw new Error('Too many segments'); segment[segmentLength++] = value; } if (segmentLength === 2) { throw new Error('Found a source, but no line and column'); } if (segmentLength === 3) { throw new Error('Found a source and line, but no column'); } index++; } } 

, , decodeNoCachingNoString JavaScript- , utf8- Uint8Array . , , , JS VM . String.prototype.charCodeAt , , JS VM.

: utf8 , . "" , , typed array ⇒ string ⇒ typed array . , source map array buffer , .

 let encoder = new TextEncoder(); function decodeNoCachingNoString(aStr) { decodeNoCachingNoStringPreEncoded(encoder.encode(aStr)); } function decodeNoCachingNoStringPreEncoded(arr) { var length = arr.length; var cachedSegments = {}; var end, str, segment, temp = {value: 0, rest: 0}; const decode2 = base64VLQ.decode2; var index = 0, value; var segment = new Int32Array(5); var segmentLength = 0; while (index < length) { segmentLength = 0; while (arr[index] != 59 && arr[index] != 44) { decode2(arr, index, temp); value = temp.value; index = temp.rest; if (segmentLength < 5) { segment[segmentLength++] = value; } } if (segmentLength === 2) { throw new Error('Found a source, but no line and column'); } if (segmentLength === 3) { throw new Error('Found a source and line, but no column'); } index++; } } 

, Chrome Dev
66.0.3343.3 (V8 6.6.189 ) Firefox Nightly 60.0a1 (2018-02-11) :

:

• , , V8, SpiderMonkey. — ;
• SpiderMonkey , , V8 — "--" (.. );

, V8 - charCodeAt – , Crankshaft charCodeAt , charCodeAt , , , .

- V8 :

• Issue 6391: StringCharCodeAt slower than Crankshaft ;
• Issue 7092: High overhead of String.prototype.charCodeAt in typescript test ;
• Issue 7326: Performance degradation when looping across character codes of a string ;

2018 , , charCodeAt . Chrome Beta Chrome Dev.

, V8 : charCodeAt 6.5.254.21 6.6.189 . "no cache" "using array", , charCodeAt V8 , Uint8Array , . , V8.

, , . なぜそう , V8:

 function foo(str, i) { return str.charCodeAt(i); } let str = "fisk"; foo(str, 0); foo(str, 0); foo(str, 0); %OptimizeFunctionOnNextCall(foo); foo(str, 0); 

 ╭─ ~/src/v8/v8 ‹master› ╰─$ out.gn/x64.release/d8 --allow-natives-syntax --print-opt-code --code-comments x.js 

, , V8 charCodeAt . , , V8, , charCodeAt .

, source-map .

, , : .

–

, .

:

1. originalMappings compareByOriginalPositions ;
2. generatedMappings compareByGeneratedPositionsDeflated .

originalMappings

compareByOriginalPositions .

 function compareByOriginalPositions(mappingA, mappingB, onlyCompareOriginal) { var cmp = strcmp(mappingA.source, mappingB.source); if (cmp !== 0) { return cmp; } cmp = mappingA.originalLine - mappingB.originalLine; if (cmp !== 0) { return cmp; } cmp = mappingA.originalColumn - mappingB.originalColumn; if (cmp !== 0 || onlyCompareOriginal) { return cmp; } cmp = mappingA.generatedColumn - mappingB.generatedColumn; if (cmp !== 0) { return cmp; } cmp = mappingA.generatedLine - mappingB.generatedLine; if (cmp !== 0) { return cmp; } return strcmp(mappingA.name, mappingB.name); } 

, source , . source , . , originalMappings , , originalMappings : originalMappings[i] i . , originalMappings[i] , , .

_{[ , – ]}

:

 if (typeof mapping.originalLine === 'number') { //      originalMappings.push(mapping). //            . let currentSource = mapping.source; while (originalMappings.length <= currentSource) { originalMappings.push(null); } if (originalMappings[currentSource] === null) { originalMappings[currentSource] = []; } originalMappings[currentSource].push(mapping); } 

:

 var startSortOriginal = Date.now(); //    : // quickSort(originalMappings, util.compareByOriginalPositions); for (var i = 0; i < originalMappings.length; i++) { if (originalMappings[i] != null) { quickSort(originalMappings[i], util.compareByOriginalPositionsNoSource); } } var endSortOriginal = Date.now(); 

compareByOriginalPositionsNoSource compareByOriginalPositions , source — , originalMappings[i] .

V8, SpiderMonkey, V8.

_{[ originalMappings : originalMappings , originalMappings[i] . , .]}

generatedMappings

generatedMappings compareByGeneratedPositionsDeflated .

 function compareByGeneratedPositionsDeflated(mappingA, mappingB, onlyCompareGenerated) { var cmp = mappingA.generatedLine - mappingB.generatedLine; if (cmp !== 0) { return cmp; } cmp = mappingA.generatedColumn - mappingB.generatedColumn; if (cmp !== 0 || onlyCompareGenerated) { return cmp; } cmp = strcmp(mappingA.source, mappingB.source); if (cmp !== 0) { return cmp; } cmp = mappingA.originalLine - mappingB.originalLine; if (cmp !== 0) { return cmp; } cmp = mappingA.originalColumn - mappingB.originalColumn; if (cmp !== 0) { return cmp; } return strcmp(mappingA.name, mappingB.name); } 

generatedLine . , , , , generatedMappings .

, :

 while (index < length) { if (aStr.charAt(index) === ';') { generatedLine++; // ... } else if (aStr.charAt(index) === ',') { // ... } else { mapping = new Mapping(); mapping.generatedLine = generatedLine; // ... } } 

generatedLine , , generatedLine , , generatedMappings generatedLine , . . :

 let subarrayStart = 0; while (index < length) { if (aStr.charAt(index) === ';') { generatedLine++; // ... //   [subarrayStart, generatedMappings.length]. sortGenerated(generatedMappings, subarrayStart); subarrayStart = generatedMappings.length; } else if (aStr.charAt(index) === ',') { // ... } else { mapping = new Mapping(); mapping.generatedLine = generatedLine; // ... } } //    sortGenerated(generatedMappings, subarrayStart); 

, , VM Array.prototype.sort .

_{[: , … , . , generatedMappings , , generatedMappings , .]}

 const compareGenerated = util.compareByGeneratedPositionsDeflatedNoLine; function sortGenerated(array, start) { let l = array.length; let n = array.length - start; if (n <= 1) { return; } else if (n == 2) { let a = array[start]; let b = array[start + 1]; if (compareGenerated(a, b) > 0) { array[start] = b; array[start + 1] = a; } } else if (n < 20) { for (let i = start; i < l; i++) { for (let j = i; j > start; j--) { let a = array[j - 1]; let b = array[j]; if (compareGenerated(a, b) <= 0) { break; } array[j - 1] = b; array[j] = a; } } } else { quickSort(array, compareGenerated, start); } } 

:

, – , generatedMappings , . ( )

, .

- , ?

, : asm.js / WASM, Rust JavaScript .

– GC

Mapping , (GC) – , – . .

_{[ , JavaScript- , . , , , , : , C++ :-(]}

Mapping , , .

 function Mapping(memory) { this._memory = memory; this.pointer = 0; } Mapping.prototype = { get generatedLine () { return this._memory[this.pointer + 0]; }, get generatedColumn () { return this._memory[this.pointer + 1]; }, get source () { return this._memory[this.pointer + 2]; }, get originalLine () { return this._memory[this.pointer + 3]; }, get originalColumn () { return this._memory[this.pointer + 4]; }, get name () { return this._memory[this.pointer + 5]; }, set generatedLine (value) { this._memory[this.pointer + 0] = value; }, set generatedColumn (value) { this._memory[this.pointer + 1] = value; }, set source (value) { this._memory[this.pointer + 2] = value; }, set originalLine (value) { this._memory[this.pointer + 3] = value; }, set originalColumn (value) { this._memory[this.pointer + 4] = value; }, set name (value) { this._memory[this.pointer + 5] = value; }, }; 

, :

 BasicSourceMapConsumer.prototype._parseMappings = function (aStr, aSourceRoot) { //  4    .     //  aStr        this._memory = new Int32Array(1 * 1024 * 1024); this._allocationFinger = 0; let mapping = new Mapping(this._memory); // ... while (index < length) { if (aStr.charAt(index) === ';') { //  ,        , //         sortGenerated(this._memory, generatedMappings, previousGeneratedLineStart); } else { this._allocateMapping(mapping); // ... //     ""   . generatedMappings.push(mapping.pointer); if (segmentLength > 1) { // ... originalMappings[currentSource].push(mapping.pointer); } } } // ... for (var i = 0; i < originalMappings.length; i++) { if (originalMappings[i] != null) { quickSort(this._memory, originalMappings[i], util.compareByOriginalPositionsNoSource); } } }; BasicSourceMapConsumer.prototype._allocateMapping = function (mapping) { let start = this._allocationFinger; let end = start + 6; if (end > this._memory.length) { // Do we need to grow memory buffer? let memory = new Int32Array(this._memory.length * 2); memory.set(this._memory); this._memory = memory; } this._allocationFinger = end; let memory = this._memory; mapping._memory = memory; mapping.pointer = start; mapping.name = 0x7fffffff; // Instead of null use INT32_MAX. mapping.source = 0x7fffffff; // Instead of null use INT32_MAX. }; exports.compareByOriginalPositionsNoSource = function (memory, mappingA, mappingB, onlyCompareOriginal) { var cmp = memory[mappingA + 3] - memory[mappingB + 3]; // originalLine if (cmp !== 0) { return cmp; } cmp = memory[mappingA + 4] - memory[mappingB + 4]; // originalColumn if (cmp !== 0 || onlyCompareOriginal) { return cmp; } cmp = memory[mappingA + 1] - memory[mappingB + 1]; // generatedColumn if (cmp !== 0) { return cmp; } cmp = memory[mappingA + 0] - memory[mappingB + 0]; // generatedLine if (cmp !== 0) { return cmp; } return memory[mappingA + 5] - memory[mappingB + 5]; // name }; 

, . Mapping , , . VM allocation sinking , scalar replacement . , SpiderMonkey , .

_{[ JS. , , "" source-map , WASM]}

, GC :

, SpiderMonkey , , .

SpiderMonkey

, SpiderMonkey: 4 64 , , 7 .

- , , .

SpiderMonkey Jan de Mooij , – asm.js 2012 … SpiderMonkey, .

– Uint8Array .

, Uint8Array , .

_{[ source-map , JavaScript- JSON.decode . , .]}

:

 $ d8 bench-shell-bindings.js ... [Stats samples: 5, total: 24050 ms, mean: 4810 ms, stddev: 155.91063145276527 ms] $ sm bench-shell-bindings.js ... [Stats samples: 7, total: 22925 ms, mean: 3275 ms, stddev: 269.5999093306804 ms] 

 $ d8 bench-shell-bindings.js ... [Stats samples: 22, total: 25158 ms, mean: 1143.5454545454545 ms, stddev: 16.59358125226469 ms] $ sm bench-shell-bindings.js ... [Stats samples: 31, total: 25247 ms, mean: 814.4193548387096 ms, stddev: 5.591064299397745 ms] 

4 !

, , originalMappings , . , originalMappings :

• allGeneratedPositionsFor , ;
• eachMapping(..., ORIGINAL_ORDER) , .

, allGeneratedPositionsFor originalMappings[i] , , - .

, V8 19 , V8 19 ( untrusted code mitigations ).

"" source-map

19 , source-map source-map , Rust WASM.

Rust parse_mappings , Rust- , generatedMappings . JS-, originalMappings[i] .

( generatedMappings ) generatedMappings .

, , Rust- generatedMappings , JS-.

" Rust+WASM " . , , Rust source-map .

(27-02-2018)

, source-map Rust+WASM, . :

, WASM+Rust 15% SpiderMonkey V8.

JavaScript

–

– . . perf – "" , .

. , .

– . , 100 , 3333 30 ?

$$$100000 \log 100000$3 $$$3333 \times 30 \log 30$– , .

, : , , ?

VM . !

. . : " !" 。 (VM) – , , . , . C++ .

VM

, JavaScript.

, , , - .

/

, , , .

JavaScript , , , VM, – .

VM , . , DevTools.

, , , . ? , . , . , (.. Rust).

: - , , , . , , .

あとがき

, :

1. ;
2. , , ;
3. , V8.

, , . , "" , "" , . :

• ;
• .

. V8 . JS . . (Rust, ) .

.

, , ( ) . . JS VM .

… ? , , , . , .

明らかに、各開発者と各チームはN、JavaScriptコードを慎重にプロファイリング、読み取り、検討する時間を費やすかM、ファームを言語に書き換える時間を費やすかを自由に選択できますX。

ただし、（a）選択肢が実際に存在することを誰もが完全に認識する必要があります。（b）言語デザイナーとアーティストが協力して、この選択をますます明確にしなくてはなりません。つまり、言語機能とツールに取り組み、「グループ＃3」最適化の必要性を減らします。