[解決済み] ヒープにあるデータへのアクセスは、スタックからよりも速いのですか？

2023-07-20 05:55:38

質問

これは一般的な質問に聞こえるでしょうし、多くの似たような質問を（ここでもウェブ上でも）見てきましたが、どれも私のジレンマのようなものではありませんでした。

私がこのコードを持っているとします。

void GetSomeData(char* buffer)
{
    // put some data in buffer
}

int main()
{
     char buffer[1024];
     while(1)
     {
          GetSomeData(buffer);
          // do something with the data
     }
     return 0;
}

buffer[1024]をグローバルに宣言した場合、パフォーマンスは向上するでしょうか？

unixでtimeコマンドを使用していくつかのテストを実行しましたが、実行時間の差はほとんどありませんでした。

しかし、あまり納得がいきません...。

理論的には、この変化で違いが出るはずなのでしょうか？

どのように解決するのですか？

<ブロッククオート

ヒープ内のデータへのアクセスは、スタックからのアクセスより速いのですか？

私がこれまで取り組んできたすべてのアーキテクチャにおいて、すべてのプロセスのメモリは、現在のデータを保持している CPU キャッシュ/RAM/スワップファイルのどのレベルに基づいて、同じ速度で動作することが期待されます。

OS (ページフォルト/スワップを担当) とハードウェア (CPU) は、まだアクセスされていないページやスワップアウトされたページへのアクセスをトラップしますが、どのページが "global" vs "stack" vs "heap" であるかさえ追跡しません... メモリページはメモリページなのです。

メモリが置かれるグローバル vs スタック vs ヒープの使用法は OS やハードウェアには不明であり、すべて同じパフォーマンス特性を持つ同じタイプのメモリによって支えられていますが、他にも微妙な考慮事項があります (このリストの後で詳しく説明します)。

割り当て - プログラムがメモリの割り当てと割り当て解除に費やす時間。 sbrk (ヒープ使用量の増加に伴う仮想アドレスの割り当てなど。
アクセス - グローバルとスタックとヒープにアクセスするためにプログラムが使用する CPU 命令の違い、および、余分な インダイレクト ヒープベースのデータを使用する場合は、ランタイムポインタを介して。
レイアウト - 特定のデータ構造 ("container" / "collections") はよりキャッシュフレンドリーですが (したがって高速)、いくつかの汎用実装はヒープ割り当てを必要とし、キャッシュフレンドリーでない場合があります。

割り当てと解放

について グローバルデータ (C++ 名前空間データメンバを含む) では、仮想アドレスは通常、計算されて コンパイル時 (絶対値として、またはセグメントレジスタからのオフセットとして。時には、OS によってプロセスがロードされるときに微調整が必要な場合もあります)。

については スタック -ベースのデータでは、スタックポインタ・レジスタ相対アドレスも計算され、以下のようにハードコードされます。 コンパイル時 . それから、スタックポインタレジスタは、関数が入力され、戻るとき（すなわち実行時）、関数の引数、ローカル変数、リターンアドレスと保存されたCPUレジスタの合計サイズによって調整されるかもしれません。スタックベースの変数を追加すると、スタックポインタレジスタを調整するために使用される合計サイズが変化するだけで、むしろ有害な影響が大きくなります。

ヒープベースのオーバーヘッドは非常に現実的で、一部のアプリケーションでは重要かもしれませんが、上記の両方は実行時の割り当て/解放のオーバーヘッドから効果的に解放されます...

のために ヒープ -ベースのデータでは ランタイム ヒープアロケーションライブラリは、アプリケーションがメモリを解放または削除するまで、管理しているヒープメモリのブロックまたはプールのどの部分が、ライブラリがアプリケーションに提供した特定のポインタと関連しているかを追跡するために、内部データ構造を参照し更新しなければなりません。ヒープメモリの仮想アドレス空間が足りない場合、OSの機能である sbrk を実行して、より多くのメモリを要求します（Linux では mmap を呼び出して、大きなメモリ要求のためのバッキングメモリを作成し、そのメモリは free / delete ).

アクセス方法

グローバルおよびスタックベースのデータに対して、コンパイル時に絶対仮想アドレス、またはセグメントまたはスタックポインタ・レジスタ相対アドレスを計算できるため、実行時のアクセスは非常に高速になります。

ヒープホストされたデータでは、プログラムはヒープ上の仮想メモリアドレスを保持する実行時に決定されたポインタを介してデータにアクセスしなければならず、時にはポインタから特定のデータメンバーへのオフセットが実行時に適用されます。これは、いくつかのアーキテクチャでは少し時間がかかるかもしれません。

ヒープアクセスでは、ポインターとヒープメモリの両方が、データにアクセスするためのレジスタになければなりません (したがって、CPU キャッシュに対する要求が多くなり、規模によってはキャッシュミス/障害オーバーヘッドが多くなります)。

注意: これらのコストは、レイテンシーやスループットが非常に重要であるようなものを書いていない限り、しばしば取るに足らないもので、見たり考えたりする価値さえありません。

レイアウト

ソースコードの連続した行がグローバル変数をリストしている場合、それらは（アライメント目的のパディングはあり得るものの）隣接するメモリ位置に配置されます。同じ関数にリストされているスタックベースの変数についても同様です。 X バイトのデータがある場合、N バイトのキャッシュラインでは、X/N または X/N + 1 のキャッシュラインを使ってアクセスできるメモリにうまくパックされることがわかります。関数の引数やリターンアドレスなど、近くにある他のスタックコンテンツが、プログラムによって同じ時期に必要になる可能性はかなり高いので、キャッシュは非常に効率的です。

ヒープベースのメモリを使用する場合、ヒープ割り当てライブラリへの連続した呼び出しは、特に割り当てサイズがかなり異なる場合 (たとえば、3 バイトの割り当てに続いて 13 バイトの割り当て)、またはすでに多くの割り当てと解放が行われている場合 ("fragmentation" を引き起こす)、異なるキャッシュラインのメモリへのポインタを簡単に返すことができます。つまり、ヒープに割り当てられた小さなメモリの束にアクセスしようとすると、最悪の場合、（ヒープへのポインタを含むメモリをロードする必要があるのに加えて）多くのキャッシュラインをフォールトする必要があるかもしれないのです。ヒープに割り当てられたメモリは、スタックに割り当てられたデータとキャッシュラインを共有することはありません。

さらに、C++ 標準ライブラリは、スタックベースのメモリで使用するために設計された、リンクリスト、平衡バイナリツリー、ハッシュテーブルなどのより複雑なデータ構造を提供しません。そのため、スタックを使用する場合、プログラマは、多少ブルートフォース検索を意味するとしても、メモリ内で連続している配列でできることを行う傾向があります。キャッシュ効率は、要素がより多くのキャッシュラインに分散しているヒープベースのデータコンテナよりも、全体として優れていると言えるかもしれません。もちろん、スタックの使用は多数の要素に対してスケールしませんし、少なくともヒープを使用するというバックアップオプションがなければ、予想以上に処理するデータが与えられると動作しなくなるプログラムを作成します。

サンプルプログラムについての議論

あなたの例では、グローバル変数と関数ローカル（スタック/自動）変数を対比しています...ヒープは関係ありません。ヒープメモリは new または malloc / realloc . ヒープメモリの場合、注目すべきパフォーマンス上の問題は、アプリケーション自身が、どのアドレスでどれだけのメモリが使用されているかを記録していることです。 new / malloc / realloc というように更新され、さらにいくつかのポインタが delete または free d.

グローバル変数の場合、メモリの割り当ては事実上コンパイル時に行われます。一方スタックベースの変数の場合、通常スタックポインタがあり、関数が呼ばれるたびにコンパイル時に計算されたローカル変数のサイズ（およびいくつかのハウスキーピングデータ）の合計によって増分されます。そのため main() が呼ばれた場合、スタックポインタを修正する時間があるかもしれません。 buffer がなければ変更されず、あれば変更されるというだけのことで、実行時の性能に違いは全くありません。

ノート

上記では、退屈でほとんど関係のないいくつかの詳細を省略しました。たとえば、CPU によっては、ある関数が別の関数の呼び出しに入るときに、その状態を保存するためにレジスターのウィンドウを使用します。

[解決済み] ヒープにあるデータへのアクセスは、スタックからよりも速いのですか？

質問

どのように解決するのですか？

割り当てと解放

アクセス方法

レイアウト

サンプル プログラムについての議論

ノート

関連

最新

おすすめ

サンプルプログラムについての議論