Looking for C++ STL-like vector class but using stack storage

Question

Before I write my own I will ask all y'all.

I'm looking for a C++ class that is almost exactly like a STL vector but stores data into an array on the stack. Some kind of STL allocator class would work also, but I am trying to avoid any kind of heap, even static allocated per-thread heaps (although one of those is my second choice). The stack is just more efficient.

It needs to be almost a drop in replacement for current code that uses a vector.

For what I was about to write myself I was thinking of something like this:

char buffer[4096];
stack_vector<match_item> matches(buffer, sizeof(buffer));

Or the class could have buffer space allocated internally. Then it would look like:

stack_vector<match_item, 256> matches;

I was thinking it would throw std::bad_alloc if it runs out of space, although that should not ever happen.

Update

Using Chromium's stack_container.h works great!

The reason I hadn't thought of doing it this way myself is that I have always overlooked the allocator object parameter to the STL collection constructors. I have used the template parameter a few times to do static pools but I'd never seen code or written any that actually used the object parameter. I learned something new. Very cool!

The code is a bit messy and for some reason GCC forced me to declare the allocator as an actual item instead of constructing it into vector's allocator parameter. It went from something like this:

typedef std::pair< const char *, const char * > comp_list_item;
typedef std::vector< comp_list_item > comp_list_type;

comp_list_type match_list;
match_list.reserve(32);

To this:

static const size_t comp_list_alloc_size = 128;
typedef std::pair< const char *, const char * > comp_list_item;
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type;
typedef std::vector< comp_list_item, comp_list_alloc_type > comp_list_type;

comp_list_alloc_type::Source match_list_buffer;
comp_list_alloc_type match_list_alloc( &match_list_buffer );
comp_list_type match_list( match_list_alloc );
match_list.reserve( comp_list_alloc_size );

And I have to repeat that whenever I declare a new one. But it works just like I wanted.

I noticed that stack_container.h has a StackVector defined and I tried using it. But it doesn't inherit from vector or define the same methods so it wasn't a drop-in replacement. I didn't want to rewrite all the code using the vector so I gave up on it.

Solution 1

You don't have to write a completely new container class. You can stick with your STL containers, but change the second parameter of for example std::vector to give it your custom allocator which allocates from a stack-buffer. The chromium authors wrote an allocator just for this:

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

It works by allocating a buffer where you say how big it is. You create the container and call container.reserve(buffer_size);. If you overflow that size, the allocator will automatically get elements from the heap (since it is derived from std::allocator, it will in that case just use the facilities of the standard allocator). I haven't tried it, but it looks like it's from google so i think it's worth a try.

Usage is like this:

StackVector<int, 128> s;
s->push_back(42); // overloaded operator->
s->push_back(43);

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container();
std::cout << v[0] << " " << v[1] << std::endl;

Solution 2

It seems that boost::static_vector is what you are searching. From the documentation:

static_vector is an hybrid between vector and array: like vector, it's a sequence container with contiguous storage that can change in size, along with the static allocation, low overhead, and fixed capacity of array. static_vector is based on Adam Wulkiewicz and Andrew Hundt's high-performance varray class.

The number of elements in a static_vector may vary dynamically up to a fixed capacity because elements are stored within the object itself similarly to an array.

Solution 3

Some options you may want to look at:

STLSoft by Matthew Wilson (author of Imperfect C++) has an auto_buffer template class that puts a default array on the stack but if it grows larger than the stack allocation will grab the memory from the heap. I like this class - if you know that your container sizes are generally going to be bounded by a rather low limit, then you get the speed of a local, stack allocated array. However, for the corner cases where you need more memory, it all still works properly.

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

Note that the implementation I use myself is not STLSoft's, but an implementation that borrows heavily from it.

"The Lazy Programmer" did a post for an implementation of a container that uses alloca() for the storage. I'm not a fan of this technique, but I'll let you decide for yourself if it's what you want:

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

Then there's boost::array which has none of the dynamic sizing behavior of the first two, but gives you more of the vector interface than just using pointers as iterators that you get with built-in arrays (ie., you get begin(), end(), size(), etc.):

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

Solution 4

If speed matters, I see run times

• 4 ns int[10], fixed size on the stack
• 40 ns <vector>
• 1300 ns <stlsoft/containers/pod_vector.hpp>

for one stupid test below -- just 2 push, v[0] v[1], 2 pop, on one platform, mac ppc, gcc-4.2 -O3 only. (I have no idea if Apple have optimized their stl.)

Don't accept any timings you haven't faked yourself. And of course every usage pattern is different. Nonetheless factors > 2 surprise me.

(If mems, memory accesses, are the dominant factor in runtimes, what are all the extra mems in the various implementations ?)

#include <stlsoft/containers/pod_vector.hpp>
#include <stdio.h>
using namespace std;

int main( int argc, char* argv[] )
{
        // times for 2 push, v[0] v[1], 2 pop, mac g4 ppc gcc-4.2 -O3 --
    // Vecint10 v;  // stack int[10]: 4 ns
    vector<int> v;  // 40 ns
    // stlsoft::pod_vector<int> v;  // 1300 ns
    // stlsoft::pod_vector<int, std::allocator<int>, 64> v;

    int n = (argv[1] ? atoi( argv[1] ) : 10) * 1000000;
    int sum = 0;

    while( --n >= 0 ){
        v.push_back( n );
        v.push_back( n );
        sum += v[0] + v[1];
        v.pop_back();
        v.pop_back();
    }
    printf( "sum: %d\n", sum );

}

Solution 5

You can use your own allocator for std::vector and have it allocate chunks of your stack-based storage, similar to your example. The allocator class is the second part of the template.

Edit: I've never tried this, and looking at the documentation further leads me to believe you can't write your own allocator. I'm still looking into it.

View more solutions

Comments

[Zan Lynx]

On the stack because the program is multi-threaded and multi-architecture and I don't want to mess with all the different ways to get TLS storage. Not on the heap because of thread contention on the heap lock.

[Steve Jessop]

Slight worry in that stack_container.h: "IMPORTANT: Take care to ensure that stack_buffer_ is aligned since it is used to mimic an array of T. Be careful while declaring any unaligned types (like bool) before stack_buffer_." Eek! Order of automatics on the stack is not defined IIRC.

[Johannes Schaub - litb]

yeah that sounds naughty. better we create an union around it with the largest possible primitive type. only idea i get now: union { unsigned long _a; double long _b; char stack_buffer_[sizeof(T[stack_capacity])]; }; and hope they will make the alignment good enough

[Johannes Schaub - litb]

otherwise, we still have atttribute weapons and whatever visual c++ provides us :D

[Steve Jessop]

Wonder why the authors didn't do it - maybe there's something that can't be done portably. uint64_t? I think one of the ARM ABIs 8-aligns 64bit integers, so perhaps the caller has to do something non-portable on such platforms anyway.

[Admin]

Allocate per-thread block on the heap and use it the same way as stack-allocated block?

[Steve Jessop]

Requires TLS, to store the pointer to "this thread's" allocated block.

[Zan Lynx]

Bumped you because you were close to right. I didn't realize it either, but you can make an allocator do this.

[Tom]

alloca is awesome, but on some platforms you may not be able to detect allocation failure until you receive SIGSEGV. I believe this is the case on Linux.

[Jason]

Assuming N is a multiple of sizeof(uint32_t), wouldn't union { uint32_t _x[N / sizeof(uint32_t)]; uint8_t buffer[N]; }; gaurantee that buffer is aligned on a 32-bit boundary due to the fact that _x has to be?

[Steve Jessop]

Sure, for the same reason as litb's union with long int. But it's platform-specific whether 4 bytes is enough alignment for every type.

[Jason]

fair enough, I suppose if you only type pun buffer to types of uint32_t* or smaller, then it should always be well defined behavior then?

[Johannes Schaub - litb]

i've recently read about boost::type_with_alignment<N>::type, which could solve your exact problem.

[Arto Bendiken]

The link to Chromium's stack_container.h is dead. Here's an updated one: src.chromium.org/viewvc/chrome/trunk/src/base/containers/…

[Zan Lynx]

Not a bad idea if I was using Qt. I wonder why you say "chances are?" Qt is nice enough, but having a gigantic dependency I'd have to compile on MacOS, Windows, Linux (5 types) and BSD (3 types) for x86, x64, ARM, MIPS is just not on.

[Sebastian Graf]

My bad, I had hardwired a different meaning for "chances are" in my mind. Actually meant "it may be the case".

[underscore_d]

boost::static_vector is probably more simple and semantic for the OP, since they said "I am trying to avoid any kind of heap", so they don't need or want the ability of boost::small_vector to exceed its stack count and start allocating from the heap. I didn't investigate it, but it might be the case that static_vector gains some efficiency from not having to account for this.