堆棧VS高速緩存友好分配器

Question

一些天前我開始處理緩存友好代碼，並推出了一些不同的結構來determin性能是如何改變，如果我把變量在堆棧或堆和如何不同的內存佈局與線性任務擴展像迭代和搜索。

我沒有處理分配時間，正好與處理性能。

這些測試並不準確，但至少應該給出一些相關數字，表現可能會有所不同。

首先我比較了的矢量的表現一個std ::陣列之間的性能。

用於陣列測試代碼：

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.004秒0.003之間東西，同時在載體的的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之間落下就像第一陣列的例子。

有任何這方面的例子不清理的，我知道。

所以，這裏是一個問題：因爲我必須增加visual studio 2015中的堆棧大小才能運行此示例（否則會發生堆棧溢出），並且簡單的事實是堆棧將隨着大小的增加而變慢，會是緩存友好代碼的首選方式？

使用緩存友好的分配器可以保持對象在堆上的接近性，這與使用堆棧的性能是一樣的（這可能會在不同的示例中有所不同，但即使接近堆棧性能也足以滿足大多數程序的需求）。

那豈不是更有效的建立一個適當的分配和存儲堆上的大東西，並保持「真實」的分配低計數，而不是過度使用堆棧的？我問這個問題是因爲我經常在整個互聯網上閱讀「儘可能頻繁地使用堆棧」，我擔心這種方法並不像很多人想象的那麼簡單。

謝謝。

Answer 1

值不要高估保持在棧上一切的高速緩存。是的，新分配的對象適合已經被緩存的行是很好的。但是，例如，Haswell的緩存行只有64個字節，因此就緩存而言，您的連續性會非常快。 （緩存集合分佈有一些好處，但它是次要的。）如果你正在編寫一些代碼，你可以從額外的緩存一致性中受益，那麼你通常使用大型數組，它們是連續無論其中他們是。

我認爲，「使用堆棧而不是堆」的建議是，建議您避免間接。

綜上所述，是對於假定並從LIFO分配模式中受益的單獨分配器有一些小的好處。但它來自減少的簿記成本，而不是來自緩存友好。