Dynamically switching between stack and heap

Question

Suppose I'm writing a simple buffer class. This buffer would act as a simple wrapper for a standard C array of objects. It should also be backwards-compatible to work with existing functions that take simple arrays as input.

The goal here is to make this buffer efficient in both speed and memory usage. Since stack allocation is always faster than heap, I want to allocate everything on a stack to a certain threshold, and if it grows larger, re-allocate on the heap. How can this be done efficiently?

I researched, and apparently std::string does something similar. I'm just not sure how. The closest solution I've had has been something along the lines of (pseudo-code, not compiled):

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

As you can see, _stack is simply wasted space when the buffer grows beyond MinSize. Also, push and pop can be especially costly if Buffer is large enough. Another solution was to keep the first few elements always on stack, and put the overflow on heap. But that would mean the Buffer could not be 'converted' to a simple array.

Is there a better solution? If this is done in std::string, could anybody point out how or provide some resources?

Answer 1

I would suggest you use a pointer _data instead of _heap, which always refers to your data store. _heap == NULL would become _data == _stack and so on, but in all situations which don't chanmge the length of the data, you could avoid the case distinction.

Your current sketch doesn't include a _capacity member to keep track of the currently allocated space. YOu'll need that to implement the “append to it, re-allocate if needed” part, unless you want to reallocate for each and every length change of a heap-allocated container.

You might also consider not freeing the heap space the moment your data fits onto the stack. Otherwise there might be applications adding and removing a single element just at that boundary, causing an allocation each time. So either implement some hysteresis or don't free the heap space at all once you've allocated it. In general I'd say freeing heap memory should go together with shrinking heap memory. Both of these you might want to do either automatically, in response to a certain function call like shrink_to_fit, or not at all, but there is little point in doing one but not the other in a similar situation.

Apart from this, I believe your solution is pretty much all you can hope for. Perhaps provide a default value for MinSize. If MinSize is small, to avoid stack overflows, then wasting that space isn't going to be much of a problem, is it?

Of course, in the end it all depends on your actual application, as a lot of unused stack allocations of this form might have an adverse impact e.g. on the caching of stack memory. Given the fact that default allocators can be pretty smart as well, you probably should benchmark whether you actually gain anything from this optimization, for a given application.

Answer 2

I am not convinced that you need a new data structure here. It seems to me that you really want is a new allocator, to be used with whatever structure you think is best.

In C++03, this would have been relatively difficult, however C++11 now requires that STL containers work with stateful allocators, so you could perfectly create an allocator with a small stack for its own use... and use that as an argument to std::vector<>.

Example (using template aliases)

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

This way you'll benefit from all the robustness and optimizations that went into the implementation of std::vector, and you'll just provide the allocation layer, which was the goal initially, it seems.