动态切换堆栈和堆

Question

假设我正在编写一个简单的缓冲区类。这个缓冲区将作为标准 C 对象数组的简单包装器，并向后兼容现有函数，以便使用简单数组作为输入。

这里的目标是使此缓冲区在速度和内存使用方面都高效。由于堆栈分配始终比堆快，因此我想在堆栈上分配一切到一定阈值，如果它增长得更大，则重新在堆上分配。如何高效地实现这一点？

我进行了研究，显然 std::string 做了类似的事情。我只是不确定怎么做。我遇到的最接近的解决方案是以下伪代码（未编译）：

template <typename T, int MinSize>
class Buffer
{
public:

    void Push(const T& t)
    {
        ++_size;

        if (_size > MinSize && _heap == NULL)
        {
            // allocate _heap and copy contents from stack
            // _stack is unused and wasted memory
        }
        else if (_heap != NULL)
        {
            // we already allocated _heap, append to it, re-allocate if needed
        }
        else
        {
            // still got room on stack, append to _stack
        }
    }

    void Pop()
    {
        --_size;

        if (_size <= MinSize && _heap != NULL)
        {
            // no need for _heap anymore
            // copy values to _stack, de-allocate _heap
        }
        else if (_heap != NULL)
        {
            // pop from heap
        }
        else
        {
            // pop from stack
        }
    }

private:

    T _stack[MinSize];
    T* _heap;
    int _size;
};

正如您所看到的，当缓冲区增长超过MinSize时，_stack只是浪费空间。另外，如果Buffer足够大，则push和pop可能特别昂贵。另一个解决方案是始终在堆栈上保留前几个元素，并将溢出放在堆上。但这意味着缓冲区无法“转换”为简单的数组。

有更好的解决方案吗？如果在std :: string中完成此操作，是否有人指出如何或提供一些资源？

- Zeenobit

---

std::string有一个指针，它动态分配内存。实际上，栈上没有任何数据；所有数据都在堆上。坦白地说，我不确定为什么你不想一开始就把它放在堆上。当大小接近栈的极限时，如果发生其他事情导致栈溢出会怎样呢？ - chris

@chris 如果 MinSize 很小，那么栈溢出的可能性会很小（哈！）（除非对象真的很大，但这不应该是情况）。如果小缓冲区可以在堆栈内存上工作，那么将会有性能提升。因此，我想知道是否可能同时拥有两全其美的效果。 - Zeenobit

有些 std::string 实现并不像 OP 所说的那样对小字符串使用堆内存。你可以尝试搜索“短字符串优化(short string optimization)”以了解更多信息。 - john

我会使用minsize作为字节大小。你可以使用minsize/sizeof T作为数组大小，这样在栈使用方面更安全。对于动态数组，我会使用std::vector<T>。 - PiotrNycz

@FarbodT：你的方法与LLVM的SmallVector并不相差，它提供了类似的接口。然而...也许你在这里混淆了要求。 - Matthieu M.

Answer 1

我建议您使用指针_data代替_heap，它始终指向您的数据存储。 _heap == NULL 将变为 _data == _stack 等等，但在所有不改变数据长度的情况下，您可以避免情况的区别。

您当前的草图不包括_capacity成员以跟踪当前分配的空间。您需要它来实现“追加到它，如果需要则重新分配”的部分，除非您想为每个堆分配的容器长度更改重新分配。

你可能还需要考虑不要立即释放堆空间，一旦数据适合于栈。否则，可能会有应用程序在该边界上添加和删除单个元素，从而每次都会引起分配。因此，要么实现一些hysteresis，要么在分配后根本不释放堆空间。总的来说，释放堆内存应该与缩小堆内存一起进行。这两个操作可以自动执行，响应某个函数调用，如shrink_to_fit，或者根本不执行，但在类似情况下只执行其中一个没有什么意义。

除此之外，我认为你的解决方案几乎是你所能期望的全部了。也许为MinSize提供一个默认值。如果MinSize很小，为了避免堆栈溢出，那么浪费这些空间也不会成为问题，对吧？

当然，最终一切取决于您的实际应用程序，因为这种形式的许多未使用的堆栈分配可能会对堆栈内存的缓存产生不利影响。鉴于默认分配器也可以非常智能化，您可能应该对给定应用程序实际获得的优化进行基准测试。

- MvG

Answer 2

我并不认为你需要一个新的数据结构。在我看来，你真正需要的是一个新的分配器，以便与你认为最好的任何结构一起使用。

在C++03中，这可能相对困难，但C++11现在要求STL容器能够使用有状态的分配器，因此你完全可以创建一个带有小堆栈的分配器... 并将其作为参数传递给std :: vector <>。

示例（使用模板别名）

template <typename T, size_t N = 8>
using SmallVector = std::vector<T, SmallAllocator<T, N>>;

通过这种方式，您将受益于实现std::vector中所涉及的所有稳健性和优化措施，并且您只需提供分配层，这似乎是最初的目标。

- Matthieu M.