スタック対キャッシュフレンドリーなアロケータ

Question

数日前、私はキャッシュフレンドリーなコードに取り組み、スタックやヒープに変数を配置するとパフォーマンスがどのように変化するかを決定するためにいくつかの異なる構造をロールバックし、反復と検索のように。

私は割当時間を処理していません。処理のパフォーマンスだけです。

テストは正確ではありませんが、少なくともパフォーマンスがどのように異なるかを示す関連数字が記載されています。

まず、std :: arrayのパフォーマンスとベクターのパフォーマンスを比較しました。

アレイのテストコード：

int main() 
{ 
    std::array<mango::int16, 5000000> v; 

    mango::delta_timer timer; //simple timer class 

    for (int i = 0; 5000000 > i; ++i) 
    { 
     v[i] = i; //I know that i will overflow but that's no problem in this case 
    } 

    timer.start(); 
    mango::for_each(v.begin(), v.end(), [](mango::int16& i)->void {++i; }); 
    timer.stop(); 

    std::cout << (double)timer.totalTime(); 

    mango::mgetch(); /*crossplatform wrapper for _getch() --> supposed to 
    give me a point where I can exit the program without printing the results*/ 

    mango::for_each(v.begin(), v.end(), print); /*print the entire 
    vector and hope that this will prevent the compiler from optimizing the array away*/ 

    return 0; 
} 

通常のベクトルのためのコード：

int main() 
{ 
    std::vector<mango::int16> v; 
    v.reserve(5000000); 

    mango::delta_timer timer; 

    for (int i = 0; 5000000 > i; ++i) 
    { 
     v.push_back(i); 
    } 

    timer.start(); 
    mango::for_each(v.begin(), v.end(), [](mango::int16& i)->void {++i; }); 
    timer.stop(); 

    std::cout << (double)timer.totalTime(); 

    mango::mgetch(); 

    mango::for_each(v.begin(), v.end(), print); 

    return 0; 
} 

for_eachアレイ上には、ベクターに0.003〜0.004秒とfor_eachの間に何かを取りました0.005秒と0.007秒との間であった。

最初のテストの後、私はスタックメモリで同様のパフォーマンスを得ることができるかどうかを試すために、非常にスリムで最小限のアロケータを使いました。

アロケータは、次のようになります。

class block_allocator 
{ 
public: 
    block_allocator(mango::int32 n, mango::int32 bsize, mango::int32 id) 
     : m_Memory(new mango::byte[n * bsize]), m_Capacity(n), m_BlockSize(bsize), m_ID(id), m_Blocks(n) 
    { 
     for (mango::byte* iterator = (mango::byte*)m_Memory; ((mango::byte*)m_Memory + n * bsize) > iterator; iterator += bsize) 
     { 
      m_Blocks.push_back(iterator); 
     } 
    } 

    ~block_allocator() 
    { 
     delete[](mango::byte*)m_Memory; 
     m_Memory = nullptr; 
    } 

    void* allocate(mango::uint32 n) 
    { 
     if (m_Blocks.empty()) 
     { 
      throw mango::exception::out_of_range(mango::to_string(m_ID) + std::string(" allocator went out of range"), "out_of_range"); 
     } 

     void* block = m_Blocks.back(); 
     m_Blocks.pop_back(); 

     return block; 
    } 

    void deallocate(void* target) 
    { 
     if (m_Blocks.size() == m_Capacity) 
     { 
      delete[](mango::byte*)target; 
     } 

     m_Blocks.push_back(target); 
    } 

private: 
    void*    m_Memory; 

    mango::int32   m_Capacity; 
    mango::int32   m_BlockSize; 
    mango::int32   m_ID; 

    std::vector<void*> m_Blocks; 
}; 

それはテストのためだけに非常に最小限のサンプルだとそれが生産的使用には適していません！

これはアロケータと私のテストサンプルである：

int main() 
{ 
    std::array<mango::int16*, 5000000> v; 

    mango::delta_timer timer; 

    for (int i = 0; 5000000 > i; ++i) 
    { 
     v[i] = allocate_int(i); //allocates an int with the allocator 
    } 

    timer.start(); 
    mango::for_each(v.begin(), v.end(), [](mango::int16* i)->void {++(*i); }); 
    timer.stop(); 

    std::cout << (double)timer.totalTime(); 

    mango::mgetch(); 

    mango::for_each(v.begin(), v.end(), print); 

    return 0; 
} 

この例ではfor_eachの性能はちょうど最初の配列例のように0.003と0.004の間に落下しました。

この例ではクリーンアップはありません。

これは質問です。このサンプルを実行するにはビジュアルスタジオ2015のスタックサイズを増やす必要がありました（それ以外の場合はスタックオーバーフローが発生します）。また、サイズが大きくなるにつれてスタックが遅くなるという単純な事実キャッシュフレンドリーなコードのための好ましい方法でしょうか？

ヒープ上でオブジェクトを密接に保つキャッシュフレンドリーなアロケータを使用すると、スタックを使用する場合と同等のパフォーマンスになります（これは異なる例では異なるかもしれませんが、ほとんどのプログラムではスタックのパフォーマンスには十分です）。

適切なアロケータを構築し、大きなものをヒープに格納し、スタックを過度に使用するのではなく、「本当の」割り当ての数を低く保つことは、より効果的ではないでしょうか？インターネット上で頻繁にできるだけ頻繁にスタックを使用することを読んでいるので、このアプローチは多くの人々が考えるように単純ではないことを心配しています。

ありがとうございます。

Answer 1

スタック上のすべてを保持するキャッシュの値を過大評価しないでください。はい、新しく割り当てられたオブジェクトが既にキャッシュされている行に収まるのはいいことです。しかし、例えば。Haswellは、キャッシュラインは64バイトしかないので、キャッシュが関わる限り、かなり速く連続性がなくなります。 （キャッシュセットの配布にはいくつかのメリットがありますが、それはマイナーなものです）そして、実際に余分なキャッシュ一貫性が得られるような種類のコードを書いているのであれば、大規模な配列連続していてもです。

「ヒープではなくスタックを使用する」アドバイスは間接を避けるようにアドバイスしています。

これらのことはすべて、がであることを前提とし、LIFO割り当てパターンから恩恵を受ける別個のアロケータには少しのメリットがあります。しかし、それはキャッシュの親切からではなく、簿記費用の削減から来ています。