みが市立図書館

Appearance

パフォーマンスを最適化する方法 ​

この記事では、Duktape固有のパフォーマンス特性について説明し、Duktape固有のパフォーマンスの落とし穴を回避するためのヒントを提供します。

コンパイラ・オプション ​

一般的なガイドラインとして

  • Gcc/clang -O2 はパフォーマンス最適化のための良いデフォルトです。
  • パフォーマンスが重要な場合は、Profile Guided Optimization (PGO)を強く推奨します。

プレーンな-O2とPGOを使った-O2の差は非常に大きく、しばしば20%程度になります!例えば

sh
# -O2 without PGO.
$ time ./duk.O2 tests/perf/test-mandel.js
[...]

real    0m3.061s
user    0m3.059s
sys 0m0.000s

# -O2 with PGO.
$ time ./duk-pgo.O2 tests/perf/test-mandel.js
[...]

real    0m2.488s
user    0m2.487s
sys 0m0.000s

この場合、性能はほぼ20％向上しています。

参照:

Duktapeの性能特性 ​

ストリングスインターニング ​

文字列はインターンされます。ある文字列のコピーは、ある時点では1つしか存在しません。文字列のインターンでは、文字列をハッシュ化し、グローバル文字列テーブルを検索して、 その文字列がすでに存在しているかどうかを調べます。存在する場合は、既存の文字列へのポインタが返されます。存在しない場合は、文字列が文字列テーブルに挿入され、文字列テーブルのリサイズを伴う可能性があります。文字列に到達できる間は、文字列は一意で安定したポインタを持つので、バイト単位の文字列比較を単純なポインタ比較に変換することができます。また、文字列ハッシュはインターン中に計算されるので、内部ハッシュテーブルでの文字列キーの使用は効率的です。

一方、多くの欠点もあります。文字列はインプレースで変更することができず、変更するたびにコピーを作成する必要があります。例えば、文字列の連結を繰り返すと、中間文字列ごとに一時的な値が生成されます。これは、結果文字列を1文字ずつ構築する場合には特に悪い点です。Duktapeの内部プリミティブである文字列の大文字小文字変換や配列結合()は、作成される一時的な文字列の数を最小限にすることで、これらのデメリットを回避しようとしています。

文字列のメモリ表現と文字列キャッシュ ​

文字列の内部メモリ表現は拡張 UTF-8 で、各 ASCII 文字を 1 バイトで表し、非 ASCII 文字を表すには 2 バイト以上使用します。これにより、ほとんどの文字列のメモリ使用量が削減され、Cコードでの文字列の扱いが容易になります。しかし、ASCII以外の文字列では、文字が可変のバイト数で表現されるため、ランダムアクセスが高価になります。ランダムアクセスは、部分文字列の抽出や、特定の文字インデックスにある文字の検索などの操作に必要です。

Duktapeは、純粋なASCII文字列を自動的に検出し（文字数とバイト長が同じであることに基づいて）、そのような文字列に対する効率的なランダムアクセスを提供します。

しかし、文字列が非ASCII文字を含む場合、文字インデックスを内部バイトインデックスに解決するために文字列キャッシュが使用されます。Duktapeは、最近アクセスされた文字列の最後のバイト・オフセットと文字オフセットを 記憶するいくつかの文字列キャッシュ・エントリ（内部定義DUK_HEAP_STRCACHE_SIZE、現在4）を維持します。キャッシュされた文字/バイトオフセット付近の文字インデックス検索は、キャッシュされた位置から後方または前方にスキャンすることで効率的に処理できます。文字列へのアクセスがキャッシュを使用して解決できない場合、文字列は先頭または末尾からスキャンされますが、これは明らかに大きな文字列に対して非常に高価です。キャッシュは非常に単純な LRU メカニズムで維持され、ECMAScript と C の両方のコードに対して透過的です。

文字列キャッシュは、以下のような単純なループを効率的にします。

js
var i;
var n = inp.length;
for (i = 0; i < n; i++) {
    print(inp.charCodeAt(i));
}

複数の文字列に対してあちこちからランダムアクセスが行われると、少なくとも長い文字列では、非常に簡単にキャッシュから抜け落ち、高価になる可能性がある。

なお、キャッシュは各文字列に対して1つ以上のエントリを保持することはないので、以下のようにすると非常に非効率になる。

js
var i;
var n = inp.length;
for (i = 0; i < n; i++) {
    // 文字列の先頭と末尾から交互にアクセスすると、大きな文字列では性能に大きな影響を与えます。
    print(inp.charCodeAt(i));
    print(inp.charCodeAt(n - 1 - i));
}

上述したように、これらの性能上の問題は、期待通りの動作をするASCII文字列の場合には完全に回避されます。より一般的には、Duktapeは内部アルゴリズムにおいて、ASCII文字と純粋なASCII文字列のための高速なパスを可能な限り提供します。これは、大文字小文字の変換や正規表現マッチングなどのアルゴリズムに適用されます。

配列とバッファの数値インデックス・アクセス ​

(密な)配列やプレーンなバッファ値の数値インデックスの読み書きに高速なパスがあります (例: x = buf[123] または buf[123] = x)。

バッファオブジェクト（Duktape.Buffer、Node.js Buffer、ArrayBuffer、TypedArrayビュー）にも同様の高速パスがありますが、20%ほど遅くなります。

Object/array storage ​

オブジェクトのプロパティは、安定した順序付け (挿入順序) を提供する線形キー/値リストに格納されます。オブジェクトが十分なプロパティを持つ場合 (内部定義 DUK_HOBJECT_E_USE_HASH_LIMIT、現在は 32) 、プロパティ検索を高速化するためにハッシュ検索テーブルも確保されます。この場合でも、ECMAScript の実装で実用的な要件であるキーの順序は保持されます。ハッシュ部分はほとんどのオブジェクトで避けられます。なぜなら、ハッシュ部分はメモリフットプリントを増加させ、非常に小さなオブジェクトのプロパティ検索を著しく高速化することができないからです。

ほとんどのオブジェクトのプロパティ検索は、オブジェクトのプロパティテーブルとの線形比較になります。プロパティは挿入順にプロパティテーブルに保持されるため、先に追加されたプロパティは後に追加されたプロパティよりも若干高速にアクセスできます。オブジェクトが大きくなり、ハッシュテーブルが必要になると、この効果はなくなります。

配列の要素は、メモリフットプリントを減らし、アクセスを高速化するために、特別な「配列部分」に格納されます。数値インデックスを持つ配列へのアクセスは、まず公式に数値を文字列に変換し (例えば x[123] から x["123"] へ) 、それから文字列のキー検索を行います。オブジェクトが配列部分を持つ場合、ほとんどの読み書きの場面で実際には一時文字列は作成されません。

配列部分は「スパース」、つまりマッピングされていないエントリーを含むことができます。Duktapeは時々配列部分の密度を再チェックし、あまりに疎になった場合は配列部分を放棄します（現在の限界はおおよそ、配列部分の要素の25%未満しかマップされていない場合、その配列部分は放棄されます）。その後、配列のエントリは通常のオブジェクトプロパティに変換され、マッピングされた配列の各インデックスは明示的な文字列キー（"123 "など）に変換されますが、これは比較的高価な処理です。一度放棄された配列部分は、たとえそのオブジェクトが配列部分を必要とするほど高密度であったとしても、再作成されることはありません。

配列部分の要素は、（アクセッサではなく）プレーンなプロパティであり、デフォルトのプロパティ属性（書き込み可能、列挙可能、設定可能）であることが要求されます。もし、これと異なる要素があれば、配列部分は放棄され、配列要素は通常のプロパティに変換されます。

識別子へのアクセス ​

Duktapeには、識別子（関数の引数、ローカル変数、関数宣言）の格納とアクセスに、高速パスと低速パスの2つのモードがあります。高速パスは、識別子を仮想マシン・レジスタ、つまり関数に割り当てられた仮想スタック・フレーム内の固定インデックスにバインドできる場合に使用されます。この場合、識別子へのアクセスは単に配列検索となります。スローパスは、ファーストパスが安全に使用できない場合に使用されます。識別子へのアクセスは、外部または内部オブジェクトの明示的なプロパティ検索に変換され、1桁以上遅くなります。

識別子へのアクセスを高速な経路で維持するために

  • トップレベルの global や eval コードではなく、ECMAScript 関数内で (ほとんどすべての) コードを実行します。global/eval コードでは高速パス識別子アクセスを使用しません (ただし global/eval 内の関数コードでは使用します)。
  • 頻繁にアクセスされる値は、グローバルオブジェクトや他のオブジェクトから探すのではなく、ローカル変数に格納する。

列挙 ​

オブジェクトをfor-in文やObject.keys()で列挙する場合、Duktapeはまず対象となるオブジェクトとそのプロトタイプ・チェーンを走査して、すべての列挙キーを文字列として含む内部列挙オブジェクトを形成します。特に、すべての配列インデックス（文字列の場合は文字インデックス）は、列挙の前に文字列値に変換され、列挙が完了するまでインターナルされたままになります。これは、特に大きな配列や文字列を列挙する場合、メモリを大量に消費する可能性があります。

しかし、文字列や配列をfor-inで反復処理し、配列要素や文字列インデックスが昇順で列挙されることを期待することは、移植性がないことに注意してください。このような動作は、Duktapeを含む多くの実装で保証されていますが、ECMAScript E5.1標準では保証されていません。

関数の特徴 ​

ECMAScriptには、関数の入力と実行を非常に高価にするいくつかの特徴があります。Duktape ECMAScriptコンパイラの一般的な目標は、ほとんどの関数で厄介な機能を回避し、残りの関数では完全な互換性を提供することです。

理想的なコンパイル済み関数は、その全ての変数と関数が仮想マシン・レジスタに束縛され、パス識別子への高速アクセスを可能にし、入力時の引数オブジェクトの生成を避け、入力時および実行時の明示的な語彙環境記録の生成を避け、内部識別子-レジスタ結合テーブルなどの語彙環境関連の制御情報を保存しないようにします。

以下の機能は、実行性能に大きな影響を与えます。

  • 引数オブジェクトへのアクセス: 引数オブジェクトにアクセスする場合に備えて，関数エントリ時に高価なオブジェクトを生成する必要がある．
  • eval()を直接呼び出す場合：引数の初期化が必要で、評価されるコードが必要とする場合に備えて完全な識別子バインディング情報を保持する必要がある。
  • 一般にグローバルコードと eval コードでは、識別子は仮想マシンのレジスタにバインドされず、明示的なプロパティ検索が使用されます。eval コード内のステートメントも暗黙の値を持つため、評価するためにバイトコード命令が必要になります。

以下の機能は、より穏やかな影響を与えます。

  • try-catch-finallyステートメント： catch変数の動的バインディングが必要であり、現時点では比較的高価である。
  • withステートメント：オブジェクトのバインディングが必要であり、現時点では比較的高価である。
  • バインドされた関数（Function.prototype.bind()で生成された関数）の使用：追加の関数オブジェクトが生成され，バインドされた関数オブジェクトの処理と引数のシャッフルにより，関数起動が遅くなる．
  • 約250以上の正式な引数、リテラル、アクティブなテンポラリ：バイトコードがレジスタシャッフリングを使用するようになり、バイトコードのサイズが大きくなって実行速度が遅くなる。

これらを避けるには、パフォーマンスが重要な部分を別の最小限の関数に分離し、上記の機能を使用しないようにします。

一時的な文字列の使用を最小限に抑える ​

一時的な文字列はすべてインターナル化する。特に、ループの中で文字列を蓄積するのは良くない。

js
var t = '';
for (var i = 0; i < 1024; i++) {
    t += 'x';
}

これは1025個の文字列をインターンすることになる。実行時間は O(n^2) で、n はループの限界です。代わりに一時的な配列を使用するのがよいでしょう。

js
var t = [];
for (var i = 0; i < 1024; i++) {
    t[i] = 'x';
}
t = t.join('');

ここでは、xは関数定数に一度インターンされ、各配列エントリは単純に同じ文字列を参照し、通常、配列エントリあたり8バイトしかかかりません。最後のArray.prototype.join()は不要なインターンを回避し、一度に最後の文字列を作成します。

できるだけ大きな非ASCII文字列は避けるべき ​

1つ以上の非ASCII文字を含む大きな文字列の中のランダムな文字オフセットにアクセスする必要がある操作は避けてください。このようなアクセスは内部の「文字列キャッシュ」を使用する必要があり、最悪の場合、文字オフセットに対応する正しいバイトオフセットを見つけるために文字列を総当たりでスキャンする必要があるかもしれません。

大文字小文字の変換やその他の Unicode 関連の操作は、ASCII コードポイントに対しては高速なパスがありますが、非 ASCII コードポイントに対しては低速なパスにフォールバックされます。この遅いパスはサイズに最適化されており、速度に最適化されておらず、多くの場合、線形範囲マッチングを伴います。

Bufferオブジェクトではなく、プレーンなバッファの値に対して反復処理を行う。 ​

バッファの内容に数値インデックスでアクセスする場合、バッファオブジェクトとプレーンなバッファの値の両方が高速なパスを持ちます。プレーンバッファーの値の高速パスは少し速いので、反復処理の前にプレーンバッファーを取得すれば、コードの実行は速くなります。

js
var b, i, n;

// Buffer object, typeof is 'object'
var bufferValue = new Duktape.Buffer('foo');
print(typeof bufferValue);  // 'object'

// プレーンなバッファを取得する（すでにプレーンであれば問題なし
b = bufferValue.valueOf();
print(typeof b);  // always 'buffer'

n = b.length;
for (i = 0; i < n; i++) {
    print(i, b[i]);  // プレーンバッファアクセスのための高速パス
}

バッファを作成する場合、new Duktape.Buffer(x) は常に Buffer オブジェクトを作成し、 Duktape.Buffer(x) はプレーン・バッファの値を返すことに注意してください。これはECMAScriptのnew String()とString()がどのように動作するかを真似ています。可能な限り、プレーン・バッファを優先すべきです。

可能な限り疎な配列は避ける ​

もし配列がある時点であまりに疎になった場合、Duktapeはその配列部分を永久に放棄し、配列のプロパティを明示的に文字列をキーとするプロパティに変換します。これは例えば、配列が降順のインデックスで初期化されている場合などに起こります。

js
var arr = [];
for (var i = 1000; i >= 0; i--) {
    // 悪い点：最初の書き込みで配列部分を永久に放棄してしまう。
    arr[i] = i * i;
}

最初の配列書き込みの直後は，配列部分に1001個のエントリがあり，マッピングされた配列要素は1つだけです．したがって、配列の密度は0.1%未満となります。これは、アレイ部分を放棄するための密度制限をはるかに下回っているため、アレイ部分は直ちに放棄されます。最終的に配列の密度は100%になりますが、復元されることはありません。昇順インデックスを使用すると、この問題は解決されます。

js
var arr = [];
for (var i = 0; i < 1000; i++) {
    arr[i] = i * i;
}

配列の length プロパティを手動で設定しても、それ自体で配列部分が放棄されることはありません。少し単純化すると、配列の密度チェックは、最も使用されている要素（実際に割り当てられているサイズ）に対するマッピングされた要素数を比較するものです。lengthプロパティはこのチェックに影響しません。配列の長さをあらかじめ設定することで、効果的に配列を事前割り当てする実装もありますが、少なくとも現時点では、Duktapeではそのような効果はありません。例えば

js
var arr = [];
arr.length = 1001;  // 配列部分は捨てないが、Duktapeでは高速化せず
for (var i = 0; i < 1000; i++) {
    arr[i] = i * i;
}

"for-in "ではなく明示的なインデックスによる配列の反復処理 ​

内部の列挙オブジェクトには、文字列値に変換されたすべての（使用された）配列インデックスが含まれているため、少なくとも大きな配列のfor-in列挙は避けてください。具体的な例として、考えてみましょう。

js
var a = [];
for (var i = 0; i < 1000000; i++) {
  a[i] = i;
}
for (var i in a) {
  // Before this loop is first entered, a million strings ("0", "1",
  // ..., "999999") will be interned.
  print(i, a[i]);
}
// The million strings become garbage collectable only here.

この例で作成された内部列挙オブジェクトは、"0", "1", ..., "999999 "の100万個の内部文字列キーを含むことになる。これらのキーはすべて、列挙の全期間にわたって到達可能なままである。次のコードは、列挙の順序を仮定していないので、より良いパフォーマンスを発揮する。

js
var a = [];
for (var i = 0; i < 1000000; i++) {
  a[i] = i;
}
var n = a.length;
for (var i = 0; i < n; i++) {
  print(i, a[i]);
}

トップレベルのグローバル/エバリュエーションコードの最小化 ​

グローバルコードと評価コードの識別子アクセスは、常にスローパス命令を使用して正しさを保証します。これは、識別子が関数起動のレジスタにマッピングされる高速パスよりも、少なくとも数桁遅いです。

つまり、これは遅いのです。

js
for (var i = 0; i < 100; i++) {
    print(i);
}

iの読み取りと書き込みはそれぞれ、明示的な環境レコードの検索となり、基本的には文字列キーiを持つ内部環境レコードオブジェクトからプロパティを検索することになる。

ほとんどのコードを関数に入れることで最適化する。

js
function main() {
    for (var i = 0; i < 100; i++) {
        print(i);
    }
}
main();

ここでは，iwillは関数レジスタにマップされ，各アクセスは単純なレジスタ参照（基本的にはタグ付き値へのポインタ）となり，スローパスよりはるかに高速になります．

明示的な関数名をつけたくない場合は、次のようにします。

js
(function() {
    var i;

    for (i = 0; i < 100; i++) {
      print(i);
    }
})();

評価コードは暗黙のうちに戻り値を提供しますが、これも性能に影響を及ぼします。例えば、次のようなことを考えてみてください。

js
var res = eval("if (4 >= 3) { 'foo'; } else { 'bar'; }");
print(res);  // prints 'foo'

このようなコードをサポートするために、コンパイラは、文の暗黙の戻り値を、それが必要とされる場合に備えて一時的なレジスタに格納するバイトコードを発行します。これらの命令は実行速度を低下させ、バイトコードのサイズを不必要に増加させます。

外部変数よりローカル変数を優先 ​

変数が仮想マシンレジスタに束縛されている場合、識別子の検索はグローバルオブジェクトや他のオブジェクトの明示的なプロパティ検索を使用するよりもはるかに高速になります。

外部の値や関数が複数回必要な場合は、代わりにローカル変数にコピーします。

js
function slow(x) {
    var i;

    // 'x.length'は明示的なプロパティ検索であり、ループごとに発生する
    for (i = 0; i < x.length; i++) {
        // 'print' は、グローバルオブジェクトのプロパティを検索します。
        print(x[i]);
    }
}

function fast(x) {
    var i;
    var n = x.length;
    var p = print;

    // ループ内のすべてのアクセスは、レジスタにバインドされた識別子を介して行われるようになりました。
    for (i = 0; i < n; i++) {
        p(x[i]);
    }
}

このような最適化は、コードの可読性を低下させることが多いので、重要な場合にのみ使用してください。

"undefined "の使用 ​

ECMAScriptにおいてundefinedの値は、実際にはリテラルではなく、グローバル変数であるため、興味深いものです。そのため、undefinedとして参照すると、Duktapeは現在、遅いパス変数読み取りを使用してそれを読み取ります。例えば

js
    print("undefined is: " + undefined);

次のようなバイトコードを生成します。

    ; constant 19: "undefined"

    ...
    GETVAR r123, c19   ; load undefined
    ...

これは遅く、必要以上に大きなバイトコードを使用します。void null (または同等の void 0 など) を使うと、よりよいバイトコードが生成されます。例えば

js
    print("undefined is: " + void null);

次のようなバイトコードを生成します。

    ...
    LDUNDEF r123
    ...

これは、遅いパスアクセスがないため、より高速です。また、グローバルな未定義バインディングがそのままであることに依存しなくなったので、コードもより良くなっています。

JSON.stringify() 高速パス ​

JSON.stringify()シリアライズには、replacer引数がない場合に使用されるfast pathが用意されています。Duktape 1.4.0で、インデント引数とJX/JCサポートが高速パスに追加されました。

高速パスは、シリアライズされる値を変化させるかもしれない副作用のリスクを負わずに引数値をシリアライズできると仮定し、必要に応じてより低速なデフォルト・アルゴリズムにフォールバックすることになります。

これは少なくとも以下の場合に起こります。

  • 任意のオブジェクトに toJSON() プロパティがあります。
  • 任意のオブジェクトのプロパティはゲッターです
  • 任意のオブジェクトがプロキシ

現在の制限に関する詳細な注意点は、test-bi-json-enc-fastpath.jsを参照してください。高速パスの前提条件と制限は、Duktapeのリリース間で変更される可能性が非常に高いです。

高速パスは現在、デフォルトでは有効になっていません。有効にするには、DUK_USE_JSON_STRINGIFY_FASTPATH が duk_config.h で有効になっていることを確認してください。

Copyright © 2023-present dolphilia