Fast variable-length stack allocator for vector<> in C++

Question

I wrote a variable-length stack allocator for the vector<> class in C++ 11. In order to be able to allocate size dynamically at runtime I made use of the non-standard alloca() function, which is available in a multitude of C++ implementations, including GCC and Visual Studio.

The purpose of this class is to improve performance of allocation of small arrays on the stack whose size cannot be determined at compile-time while still retaining the helpful features of the vector<> class.

#pragma once

#include <functional>

template <typename T>
class stack_allocator {
    template<typename> friend class stack_allocator;

public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;

    template<typename T2>
    struct rebind {
        typedef stack_allocator<T2> other;
    };

private:
    T* ptr;
    size_t currentSize, maxSize;

public:
    stack_allocator() noexcept :
        ptr(nullptr),
        currentSize(0),
        maxSize(0) {
    }

    stack_allocator(T* buffer, size_t size) noexcept :
        ptr(buffer),
        currentSize(0),
        maxSize(size) {
    }

    template <typename T2>
    explicit stack_allocator(const stack_allocator<T2>& other) noexcept :
        ptr(reinterpret_cast<T*>(other.ptr)),
        currentSize(other.currentSize),
        maxSize(other.maxSize) {
    }

    T* allocate(size_t n, const void* hint = nullptr) {
        T* pointer = ptr + currentSize;
        currentSize += n;
        return pointer;
    }

    void deallocate(T* p, size_t n) {
        currentSize -= n;
    }

    size_t capacity() const noexcept {
        return maxSize;
    }

    size_t max_size() const noexcept {
        return maxSize;
    }

    T* address(T& x) const noexcept {
        return &x;
    }

    const T* address(const T& x) const noexcept {
        return &x;
    }

    T* buffer() const noexcept {
        return ptr;
    }

    template <typename T2>
    stack_allocator& operator=(const stack_allocator<T2>& alloc) {
        return *this;
    }

    template <typename... Args>
    void construct(T* p, Args&&... args) {
        new (p) T(forward<Args>(args)...);
    }

    void destroy(T* p) {
        p->~T();
    }

    template <typename T2>
    bool operator==(const stack_allocator<T2>& other) const noexcept {
        return ptr == other.ptr;
    }

    template <typename T2>
    bool operator!=(const stack_allocator<T2>& other) const noexcept {
        return ptr != other.ptr;
    }
};

#define init_stack_vector(Type, Name, Size) std::vector<Type, std::stack_allocator<Type>> Name((std::stack_allocator<Type>(reinterpret_cast<Type*>(alloca(Size * sizeof(Type))), Size))); Name.reserve(Size)

A simple usage example:

#include <vector>
#include <string>
#include "stdio.h"
#include <iostream>
#include "stack_allocator.h"

using namespace std;

int main() {
    string input;
    cout << "How many integers shall we store? ";
    getline(cin, input);

    init_stack_vector(int, v, stoi(input));
    for (int i = v.capacity() - 1; i >= 0; i--)
        v.push_back(i);
    for (int i = v.capacity() - 1; i >= 0; i--)
        printf("%d\n", i);
    system("pause");
    return 0;
}

The init_stack_vector() macro cannot be substituted by a template function, as that would risk the function not being inlined in Debug mode, and if it's not inlined, alloca() would allocate on its stack and it would be popped immediately returning, causing usage of the pointer returned by alloca() to depend on undefined behaviour.

Any thoughts/critique?

The completed code can now be found at: https://github.com/mathusummut/StackVector.

Disclaimer: Never use very large array sizes on the stack in general. Like you should not use int var[9999999], you should similarly not use new_stack_vector(int, vec, 9999999)! Use responsibly.

Answer 1

Well this is going to cause problems:

void deallocate(T* p, size_t n) {
    currentSize -= n;
}

You can't assume that the last allocated object is the one that is de-allocated (I would even say that will never happen).

As a result your next call to allocate is going to re-use that memory even though it is already being used.

T* allocate(size_t n, const void* hint = nullptr) {
    T* pointer = ptr + currentSize;
    currentSize += n;
    return pointer;
}

Your allocator assumes that its memory is allocated with alloca(). But the interface allows any memory to be injected so it has a high likely hood that it is going to be used incorrectly and leak memory. If you are assuming that the memory is going to be free'ed dynamically like that then you need to design the allocator to allocate the appropriate memory.

Also relying on this kind of low level functions is dangerous. What happens when the vector is part of an object? What if the object that holds it is dynamically allocated? There are too many flaws in this design for it be used anywhere apart from your one small use case senario and even then it will need to be well documented to make sure that a future maintainer does not break it.

Answer 2

If you're going to hide something this dangerous in a macro, you should use upper case for its name to highlight the problems.

Do you know what counts as "small enough" for alloca()? On every platform? On GNU systems, the man page says:

If the allocation causes stack overflow, program behavior is undefined.

and:

The inlined code often consists of a single instruction adjusting the stack pointer, and does not check for stack overflow. Thus, there is no NULL error return.

This means that there is no recovery from allocation failure.

What happens when you add more elements to the vector than the reserved size?

Rather than mislead future coders, it would be more honest to use a bare alloc() and manage it as an array using pointer and size variables.