堆栈与缓存友好分配器

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 之间。

我知道这些示例中的任何一个都没有清理。

所以问题来了：由于我不得不在 visual studio 2015 年增加堆栈大小才能获得此示例运行（否则会发生堆栈溢出）以及堆栈的简单事实随着大小的增加会变慢，缓存友好代码的最佳方式是什么？

使用缓存友好的分配器将对象在堆上保持在一起可以达到与使用堆栈相同的性能（这在不同的示例中可能有所不同，但我认为即使接近堆栈性能对于大多数程序来说也足够了）。

构建一个合适的分配器并将大量内容存储在堆上并保持较低的 "real" 分配计数而不是过度使用堆栈会不会更有效？我问这个是因为我经常在整个互联网上阅读 "use the stack as frequently as you can"，我担心这种方法并不像很多人想象的那么简单。

谢谢。

Answer 1

不要高估将所有内容保存在堆栈中对缓存的价值。是的，新分配的对象适合已经缓存的行是很好的。但是在例如Haswell，缓存行只有 64 字节，所以就缓存而言，很快运行就失去了连续性。（缓存集分布有一些好处，但它是次要的。）如果你正在编写的代码实际上可以从额外的缓存一致性中获益，那么你通常使用的是大型数组无论在哪里都是连续的。

我认为 "use the stack, not the heap" 建议是建议您避免间接访问。

综上所述，假定并受益于 LIFO 分配模式的单独分配器有一些小好处。但它来自降低的簿记成本，而不是缓存友好性。

堆栈与缓存友好分配器

Stack vs cache friendly allocator

c++

performance

stack

allocation