堆栈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分配模式中受益的单独分配器有一些小的好处。但它来自减少的簿记成本，而不是来自缓存友好。