7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You say this is mainly for allocating small vectors. What's wrong with vector<int> v(stoi(input),0);? \$\endgroup\$ – tinstaafl Feb 15 '17 at 1:33
  • \$\begingroup\$ vector<int> v(stoi(input),0); is allocated on the heap with is allocated on the heap and is zero-initialized, both of which incur an overhead. \$\endgroup\$ – MathuSum Mut Feb 15 '17 at 10:08
  • 1
    \$\begingroup\$ May be *p = T(args...); should've been placement new? \$\endgroup\$ – Incomputable Feb 15 '17 at 13:08
  • \$\begingroup\$ Ah, you're right! Lemme fix it... \$\endgroup\$ – MathuSum Mut Feb 15 '17 at 16:24
  • 1
    \$\begingroup\$ Seems like due to strongly typed pointer, memory alignment issue is waived. I apologize for worrying about that so much. I would also recommend having a look at this video, which has recipes for some more sophisticated and interesting allocators. And with std::memory_resource it will be possible to implement most of the allocators mentioned in the video. \$\endgroup\$ – Incomputable Feb 15 '17 at 20:35
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I tested whether the assertions made above actually hold true using the following test code: pastebin.com/Y9C1tXUh, but the test results were all correct as expected. This is probably due to the Name.reserve(Size) statement in the init_stack_vector() macro. \$\endgroup\$ – MathuSum Mut Feb 15 '17 at 21:17
  • \$\begingroup\$ @MathuSumMut: Not sure that test proves anything. You are testing the state after the object has been resized. The problem will occur during a re-size. But you are probably correct in the it will not happen if your first action is to reserve the maximum space available and never force re-allocation (Which sort of wastes all the work in your allocator you may as well simplify it to the point where it does no work). Sure it will work for your use case but that does not change its brittleness thus making it not very suitable for general coding or re-use and a definite headache for maintainers. \$\endgroup\$ – Martin York Feb 16 '17 at 0:38
  • \$\begingroup\$ Indeed, flexibility has definitely been traded-off for speed of execution. I only intend to use it for personal projects where I want to make use of vector features such as insert while still pretty much retaining the allocation speed of stack arrays. :) \$\endgroup\$ – MathuSum Mut Feb 16 '17 at 5:24
  • \$\begingroup\$ @MathuSumMut: Given that you can only resize the once. I don't think you will gain any speed. This kind of optimization for speed is only useful if you are doing it billions of times. Since you only do it once I don't believe this code gains you anything; apart from brittle code. \$\endgroup\$ – Martin York Feb 16 '17 at 17:25
  • \$\begingroup\$ Of course, that goes without saying. I wrote a simple benchmark, and the stack-allocated vector of 128 integers was approximately 7 times faster to allocate than 128 integers on the heap. The benefits are significant given the right circumstances. \$\endgroup\$ – MathuSum Mut Feb 16 '17 at 19:55
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How is it "misleading"? Allocating on the stack always suffers from the same dangers, even when using plain C stack arrays. Why would a C++ newbie even think about custom allocators for vector? \$\endgroup\$ – MathuSum Mut Mar 7 '18 at 13:31
  • \$\begingroup\$ Where has the newbie come from? Are you expecting init_stack_vector to be used by developers who don't understand what it's doing, and why such vectors can't be extended beyond their original capacity? Even more reason to avoid it, IMO. \$\endgroup\$ – Toby Speight Mar 7 '18 at 13:37
  • \$\begingroup\$ Actually what I mean was that I expect init_stack_vector to be used exclusively by non-newbie C++ developers, because why would a newbie even consider custom allocators? \$\endgroup\$ – MathuSum Mut Mar 7 '18 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.