c++ - 堆栈与缓存友好分配器

Question

几天前，我开始处理缓存友好型代码，并推出了一些不同的结构，以确定如果我将变量放在堆栈或堆上，性能会如何变化，以及不同的内存布局如何随着迭代和搜索等线性任务而扩展。

我不处理分配时间，只处理处理性能。

测试不是很准确，但至少应该给出一些相关的数字，说明性能可能有何不同。

首先，我比较了 std::array 与 vector 的性能。

数组的测试代码:

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;
}

规则 vector 的代码:

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 秒， vector 上的 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

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

我认为，“使用堆栈，而不是堆”的建议是建议您避免间接访问。

综上所述，采用后进先出分配模式并从中受益的单独分配器有一些小好处。但它来自降低的簿记成本，而不是缓存友好性。