C++ヒープメモリの性能向上

Question

ヒープメモリがかなり必要な場所に関数を書いています。パフォーマンスを向上させるために（コンパイルオプションなどで）特定のforループ内で頻繁にアクセスされることをコンパイラに伝えることは可能ですか？

私はスタックを使用できない理由は、格納する必要がある要素の数が多いため、しようとするとセグメント化違反が発生するためです。

現在、コードは機能していますが、速くなる可能性があります。

UPDATE： 私はこの

vector< set<uint> > vec(node_vec.size()); 
for(uint i = 0; i < node_vec.size(); i++) 
    for(uint j = i+1; j < node_vec.size(); j++) 
    // some computation, basic math, store the result in variable x 
     if(x > threshold) { 
     vec[i].insert(j); 
     vec[j].insert(i); 
     } 

いくつかの詳細のようなものをやっている：
- 私はhash_set、少し改善を使用し、hash_set私はシミュレーションの目的のために持っているすべてのマシンでは利用できないという事実のそば
- 私は、私が言ったように要素数が

node_vec.size（）は、たとえば、等しいがkにされている場合は大きすぎる場合、私はセグメンテーションフォールトを取得する可能性があります、配列を使用してスタック上にVECを割り当てるしようとしたが、ここで、kは数千人、私はvecがnode_vecの4倍または5倍になると期待しています。この程度の大きさでは、コードを何度も実行しなければならないという事実を考慮して、コードは遅く見えます。もちろん、私はこれらの呼び出しを並列化するためにマルチスレッドを使用していますが、私が今見ているものよりもはるかに高速に機能することはできません。

たとえば、vecを高速データ取得などのためにキャッシュメモリに割り当てることは可能でしょうか？

Answer 1

UPDATE我々は条件x > thresholdが真となりますどのくらいの頻度を知ることができないので、まだ、あまり表示されません

vector< set<uint> > vec(node_vec.size()); 
for(uint i = 0; i < node_vec.size(); i++) 
    for(uint j = i+1; j < node_vec.size(); j++) 
    // some computation, basic math, store the result in variable x 
     if(x > threshold) { 
     vec[i].insert(j); 
     vec[j].insert(i); 
     } 

。 x > thresholdが非常に頻繁に真の場合、std::setは、挿入するuintごとに動的メモリ割り当てを行う必要があるため、ボトルネックになる可能性があります。

「何らかの計算」が実際に何を意味するのかわかりません。それが多ければ、それは間違ったやりかたでそれがボトルネックになる可能性があります。

結果にアクセスする方法がわかりません。

とにかく、勘に：あなたはそのフォームで結果を使用できる場合

vector<pair<int, int> > vec1; 
    vector<pair<int, int> > vec2; 

    for (uint i = 0; i < node_vec.size(); i++) 
    { 
     for (uint j = i+1; j < node_vec.size(); j++) 
     { 
      // some computation, basic math, store the result in variable x 
      if (x > threshold) 
      { 
       vec1.push_back(make_pair(i, j)); 
       vec2.push_back(make_pair(j, i)); 
      } 
     } 
    } 

、あなたは完了です。それ以外の場合、後処理を行うことができます。もう一度std::setにコピーしないでください（明らかに）。 std::vector<POD>に固執してください。例えば。あなたはこのようなベクターにインデックスを構築することができ：

// ... 
    vector<int> index1 = build_index(node_vec.size(), vec1); 
    vector<int> index2 = build_index(node_vec.size(), vec2); 
    // ... 
}  

vector<int> build_index(size_t count, vector<pair<int, int> > const& vec) 
{ 
    vector<int> index(count, -1); 

    size_t i = vec.size(); 
    do 
    { 
     i--; 
     assert(vec[i].first >= 0); 
     assert(vec[i].first < count); 
     index[vec[i].first] = i; 
    } 
    while (i != 0); 

    return index; 
} 

PS：私はあなたのループがないメモリバウンドで、ほぼ確信しています。しかし、あなたが私たちを見せていない "ノード"が本当に大きい場合、それはまだあるかもしれません。

---

オリジナルの答え：

簡単なI_will_access_this_frequently_so_make_it_fast(void* ptr, size_t len) -kind-の解決策はありません。

あなたはいくつかのことができます。

1. コンパイラがクリティカルループ内で呼び出されるすべての関数の実装を「参照」できることを確認します。コンパイラが実装を「参照」できるようにするために必要なことは、コンパイラによって異なります。 1つの方法はありますが、同じ翻訳単位内のすべての関連する関数をの前にループを定義してと定義し、inlineと宣言します。

   ではなく、のいずれかの重要なループで「外部」機能を呼び出す必要があります。そして、「外部」機能とは、システムコール、ランタイムライブラリ、DLL/SOで実装されたものなどを意味します。また、仮想関数を呼び出さず、関数ポインタを使用しないでください。もちろん、クリティカルループ内でメモリを割り当てたり解放したりすることはありません。

2. 最適なアルゴリズムを使用してください。線形最適化は、アルゴリズムの複雑さが必要以上に高い場合は問題になります。

3. 可能な限り小さなタイプを使用してください。例えば。 signed charがジョブを実行する場合はintを使用しないでください。これは私が通常はお勧めしないものですが、大きなメモリを処理する場合、パフォーマンスがかなり向上する可能性があります。特に非常にタイトなループで。

4. メモリをコピーまたは埋めただけの場合は、memcpyまたはmemsetを使用してください。 チャンクが約50〜100バイトより大きい場合は、を無効にします。

5. キャッシュに適した方法でデータにアクセスしてください。最適なのは「ストリーミング」です。つまり、昇順または降順のアドレスでメモリにアクセスします。あなたは一度にいくつかのバイトを "ジャンプ"することができますが、あまりにも遠くにジャンプしないでください。最悪は、大きなメモリブロックへのランダムアクセスです。例えば。 p [0]〜p [1]が「右へ」（x + 1）のステップである2次元行列（ビットマップイメージのような）を扱う必要がある場合は、内側ループがxを増やし、外側がp yをインクリメントする。あなたがそれを行うならば、パフォーマンスは他の方法でになります。悪化します。

6. ポインタにエイリアスがない場合、コンパイラに指示できます（コンパイラによって異なります）。エイリアスフリーの意味がわからない場合は、ネットとコンパイラのドキュメントを検索することをお勧めします。説明は範囲を超えているためです。

7. 必要に応じて、固有のSIMD命令を使用してください。

8. 近い将来にどのメモリロケーションが必要になるかわかっている場合は、明示的プリフェッチ命令を使用してください。

Answer 2

コンパイラオプションではこれを実行できません。あなたの使用法（挿入、ランダムアクセス、削除、並べ替えなど）に応じて、おそらくより適切なコンテナを得ることができます。

Answer 3

コンパイラは、ループ内で頻繁にデータにアクセスしていることを既に確認できます。

Answer 4

私はヒープメモリを大量に必要とする機能を書いている...ループ

のための特定の範囲内頻繁にアクセスされます。これは、あなたが本当にで最適化できるものではありませんコンパイラレベル。私はあなたの懸念は、あなたが "古い"（ページアウト）かもしれない多くのメモリを持っていると思いますが、特定の時点では、すべてを繰り返していく必要があります。ページをディスクにページアウトする。

パフォーマンスを向上させるためにプラットフォーム固有の戦略を調べる必要があります。ページをメモリに保存するには、mlockallまたはVirtualLockを使用できますが、これを行う必要はありません。しかし、あなたのアプリケーションのメモリページをRAMにロックすることがどのような意味を持つのかを確認してください。あなたは他のプロセスからメモリを奪い取っています。

low fragmentation heap（ただし、この問題にはまったく関連しない可能性があります）と、forループに関するキャッシュラインを記述するthis pageを調べることもできます。

後者のページは、メモリアクセスに関して、CPUがどのように機能するかについての詳細です（詳細については、通常は気にする必要はありません）。

例1：メモリアクセスとパフォーマンス Loop 1と比較して、Loop 2の実行速度はどれくらい速いでしょうか。

最初のループは配列のすべての値に3を掛け、2番目のループは16番目にのみ掛けます。 2番目のループは最初のループの作業の約6％を行いますが、現代のマシンではの2つのforループは、私のマシン上でそれぞれ同じ時刻の：80と78msです。

Answer 5

ルーピングを行う前にヒープからデータを1回だけ割り当てていると仮定すると、@ lvellaはメモリがメモリであり、頻繁にアクセスされる場合は実行中に効果的にキャッシュされるはずです。