Stack-Buffer Based Stl Allocator

Stack-buffer based STL allocator?

Apparently, there is a conforming Stack Allocator from one Howard Hinnant.

It works by using a fixed size buffer (via a referenced arena object) and falling back to the heap if too much space is requested.

This allocator doesn't have a default ctor, and since Howard says:

I've updated this article with a new allocator that is fully C++11 conforming.

I'd say that it is not a requirement for an allocator to have a default ctor.

What data type to use for the buffer of a custom stack-based allocator?

Okay for simplicity let's say you're tracking a collection of MyFunClass for your engine. It could be anything, and your linear allocator doesn't necessarily have to track objects of a homogenous type, but often that's how it's done. In general, when using custom allocators you're trying to "shape" your memory allocations to separate static data from dynamic, infrequently accessed vs. frequently accessed, with a view towards optimizing your working set and achieving locality of reference.

Given the code you provided, first, you'd allocate your memory pool. For simplicity, assume you want enough space to pool 1000 objects of type MyFunClass.

StackAllocator sa;
sa.Init( 1000 * sizeof(MyFunClass) );

Then each time you need to "allocate" a new block of memory for a FunClass, you might do it like this:

void* mem = sa.allocUnaligned( sizeof(MyFunClass) );

Of course, this doesn't actually allocate anything. All the allocation already happened in Step 1. It just marks some of your already-allocated memory as in-use.

It also doesn't construct a MyFunClass. Your allocator isn't strongly typed, so the memory it returns can be interpreted however you want: as a stream of bytes; as a backing representation of a C++ class object; etc.

Now, how would you use a buffer allocated in this fashion? One common way is with placement new:

auto myObj = new (mem) MyFunClass();

So now you're constructing your C++ object in the memory space you reserved with the call to allocUnaligned.

(Note that the allocUnaligned bit gives you some insight into why we don't usually write our own custom allocators: because they're hard as heck to get right! We haven't even mentioned alignment issues yet.)

For extra credit, take a look at scope stacks which take the linear allocator approach to the next level.

Improvements for this C++ stack allocator?

You've implemented a stack based allocator. You can't free up without leaving gaps. Usually a pool refers to a block of contiguous memory with fixed sized slots, which are doubly linked to allow constant time add and delete.

Here's one you can use as a guide. It's along the same lines as yours but includes basic iterators over allocated nodes, and uses templates to be type aware.

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

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;

Non-Copyable STL Allocator

This is not possible. From [container.requirements.general]/8

[...] All other constructors for these container types take a const allocator_­type& argument. [ Note: If an invocation of a constructor uses the default value of an optional allocator argument, then the allocator type must support value-initialization. — end note ] A copy of this allocator is used for any memory allocation and element construction performed, by these constructors and by all member functions, during the lifetime of each container object or until the allocator is replaced.

^{emphasis mine}

So you cannot pass a move only allocator to any of the container constructors that take an allocator.

Hinnant's stack allocator and exceptions

The gcc and clang implementations follow a specification called the Itanium ABI. It says, among other things:

Storage is needed for exceptions being thrown. This storage must persist while stack is being unwound, since it will be used by the handler, and must be thread-safe. Exception object storage will therefore normally be allocated in the heap, although implementations may provide an emergency buffer to support throwing bad_alloc exceptions under low memory conditions (see Section 3.3.1).

Memory will be allocated by the __cxa_allocate_exception runtime library routine. This routine is passed the size of the exception object to be thrown (not including the size of the __cxa_exception header), and returns a pointer to the temporary space for the exception object. It will allocate the exception memory on the heap if possible. If heap allocation fails, an implementation may use other backup mechanisms (see Section 3.4.1).

If __cxa_allocate_exception cannot allocate an exception object under these constraints, it calls terminate().

The libc++abi implementation of __cxa_allocate_exception is here. It will first go to the heap, and if that fails, try an emergency backup buffer that is statically allocated within the libc++abi.dylib. If both the heap, and the emergency-stash fail to allocate enough memory for the arbitrary-sized user-created exception, terminate() is called.

Custom allocator to store stl vector in OpenGL buffer objects

Is it possible doing so without relying in a specific implementation of STL, by writing a custom allocator and/or subclassing the container?

You can, but that doesn't make it a good idea. And even that you can is dependent on your compiler/standard library.

Before C++11, allocators can not have state. They can cannot have useful members, because the containers are not required to actually use the allocator you pass it. They are allowed to create their own. So you can set the type of allocator, but you cannot give it a specific allocator instance and expect that instance to always be used.

So your allocator cannot just create a buffer object and store the object internally. It would have to use a global (or private static or whatever) buffer. And even then, multiple instances would be using the same buffer.

You could get around this by having the allocator stores (in private static variables) a series of buffer objects and mapped pointers. This would allow you to allocate a buffer object of a particular size, and you get a mapped pointer back. The deallocator would use the pointer to figure out which buffer object it came from and do the appropriate cleanup for it.

Of course, this would be utterly useless for actually doing anything with those buffers. You can't use a buffer that is currently mapped. And if your allocator deletes the buffer once the vector is done with the memory, then you can never actually use that buffer object to do something.

Also, don't forget: unmapping a buffer can fail for unspecified reasons. If it does fail, you have no way of knowing that it did, because the unmap call is wrapped up in the allocator. And destructors shouldn't throw exceptions.

C++11 does make it so that allocators can have state. Which means that it is more or less possible. You can have the allocator survive the std::vector that built the data, and therefore, you can query the allocator for the buffer object post-mapping. You can also store whether the unmap failed.

That still doesn't make it a good idea. It'll be much easier overall to just use a regular old std::vector and use glBufferSubData to upload it. After all, mapping a buffer with READ_WRITE almost guarantees that it's going to be regular memory rather than a GPU address. Which means that unmapping is just going to perform a DMA, which glBufferSubData does. You won't gain much performance by mapping.

Reallocation with buffer objects is going to be much more painful. Since the std::vector object is the one that decides how much extra memory to store, you can't play games like allocating a large buffer object and then just expanding the amount of memory that the container uses. Every time the std::vector thinks that it needs more memory, you're going to have to create a new buffer object name, and the std::Vector will do an element-wise copy from mapped memory to mapped memory.

Not very fast.

Really, what you want is to just make your own container class. It isn't that hard. And it'll be much easier to control when it is mapped and when it is not.

---

Related Topics