これはallocaを使う良い理由ですか？

Question

私は、次の機能を有する：

double 
neville (double xx, size_t n, const double *x, const double *y, double *work); 

xとyに格納されているn点を用いてxxでラグランジュ補間を行います。 workアレイのサイズは2 * nです。これは多項式補間であるため、nは〜5の球場にあり、非常にまれに10を超えることはほとんどありません。

この関数は積極的に最適化されており、きついループで呼び出されるはずです。プロファイリングでは、ループ内のワーク配列を割り当てるヒープが悪いことが示唆されています。残念ながら、私はこれを関数に似たクラスにパッケージ化し、クライアントはワーク配列を認識しなくてはなりません。の可変メンバーとして作業配列を格納することも可能だったでしょう

template <size_t n> 
struct interpolator 
{ 
    double operator() (double xx) const 
    { 
     std::array<double, 2 * n> work; 
     size_t i = locate (xx); // not shown here, no performance impact 
           // due to clever tricks + nice calling patterns 

     return neville (xx, n, x + i, y + i, work.data()); 
    }   

    const double *x, *y; 
}; 

：

は今のところ、私はwork配列の動的割り当てを避けるために、学位やstd::arrayのテンプレート整数の引数を使用しますしかし、operator()は、複数のスレッドによって同時に使用されることになっています。このバージョンはコンパイル時にnを知っていればOKです。

実行時にnパラメータを指定する必要があります。 allocaを使用した場合

double operator() (double xx) const 
{ 
    auto work = static_cast<double*> (alloca (n * sizeof (double))); 
    ... 

いくつかの鐘リング：私はこのような何かについて疑問に思って、私はもちろん、とにかくそれが度100を使用することは非常に愚かだ（オーバーフローするalloca呼び出しを避けるためにn上のキャップを持っているつもりです多項式補間）。

しかし私は、アプローチにはかなりunconfortableだ：

• 私はallocaのいくつかの明白な危険が足りませんか？
• ここでヒープ割り当てを避けるより良い方法はありますか？

Answer 1

しかし私は、アプローチにはかなりunconfortableだ：

• 私はallocaをいくつかの明白な危険が足りませんか？

あなたは1つの本当の危険を指摘した：スタックオーバーフローの動作はallocaのために定義されていません。さらに、allocaは実際には標準化されていません。たとえば、Visual C++の代わりに_alloca、GCC by default defines it as a macroがあります。しかし、この問題は、いくつかの既存の実装の周りに薄いラッパーを提供することによって、かなり簡単に回避することができます。

• ここでヒープ割り当てを避けるより良い方法はありますか？

実際にはありません。 C++ 14には、（潜在的に！）スタックに可変長配列型が割り当てられます。しかし、それまでにstd::arrayが適切でないと考えるときは、あなたのような場合はallocaに行ってください。

マイナーニックネーム：あなたのコードには戻り値のキャストがありませんalloca。コンパイルすべきではありません。

Answer 2

スタックメモリの使用には、常にメモが追加されます。あなたが指摘しているように、スタックは、そのスペースがなくなると、有限のサイズとかなり重大な誤動作をします。ガードページがあると、スタックオーバーフローがうまくクラッシュすることがありますが、一部のプラットフォームやスレッド環境では、サイレントな破損（悪い）やセキュリティの問題（悪化）が生じることがあります。

またそのスタック割り当てを覚えてmalloc、（それは、スタック・ポインタ・レジスタからわずか減算です）に比べて非常に高速です。しかし、そのメモリのを使用することはできません。スタックフレームを大量に押し込むことによる副作用は、呼び出すリーフ関数のキャッシュラインがもはや常駐していないことです。したがって、そのメモリを使用すると、キャッシュラインを排他的（MESIの意味で）の状態に戻すためにSMP環境に出る必要があります。 SMPバスは、L1キャッシュよりもはるかに制約の厳しい環境です。これを回避するためにスタックフレームをスパムしているのであれば、実際のスケーラビリティの問題になる可能性があります。

また、gccとclang（そしてIntelのコンパイラはどちらも）C99の可変長配列構文をC++拡張としてサポートしていることに注意してください。 libc alloca()ルーチンを実際に呼び出す必要はありません。

最後に、mallocが本当に遅くないことに注意してください。数十キロバイト以上の領域の単一バッファを扱っている場合、あなたが行う作業をサービスするために必要なメモリ帯域幅は、mallocからのオーバヘッドを溜めてしまいます。

基本的に：alloca()は可愛く、その用途がありますが、必要なことを証明する準備ができていない限り、従来の割り当てに固執する必要はありません。

Answer 3

これはどう：

double operator() (double xx) const 
{ 
    double work_static[STATIC_N_MAX]; 
    double* work = work_static; 
    std::vector<double> work_dynamic; 

    if (n > STATIC_N_MAX) { 
     work_dynamic.resize(n); 
     work = &work_dynamic[0]; 
    } 

    ///... 

ノー非ポータブル機能、例外安全、およびnが大きすぎると優雅に低下します。もちろん、work_staticをstd::arrayにすることもできますが、その点でどのようなメリットがあるのか​​分かりません。