3
\$\begingroup\$

Let´s say I have a single frame stack allocator, so I´m using it for allocating memories for my temporary data.

size_t freeTilesSize = 10;
int* freeTiles = _allocator.allocate<int>(freeTilesSize);

The stack doesn´t save any conditional stuff about the memory it creates(it cares only about the size of the chunk so it knows the new header offset). I see this a good for using with POD data structures or classes with default destructor, however, is it usable also for bigger entities with some behavior at the destruction? At this moment, my function rewind only sets the header ptr to the start of the allocated block so it doesn´t call any destructors.

Am i doing something wrong? What was your approach?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Yep, releasing storage without destructing objects properly is an issue. It's formally UB, and the most probable symptom will be resource leaks everywhere. Please call your destructors :) \$\endgroup\$
    – Quentin
    Nov 20, 2017 at 13:59
  • \$\begingroup\$ @Quentin It is not that simple because the stack is for general purposes and all I know about the bucks of the memory allocated is their size. How will the allocator define what class is it (and what destructor should be called)? I would need to store them into heterogenous container and that would affect performance. No? Even the "release" keyword is different now, because I dont free the huge block of the preallocated memory but just modify the stack top pointer.(in the pool it behaves easier, as you define the class type of the objects stored so you can explicitly call the Destructors). \$\endgroup\$
    – Pins
    Nov 20, 2017 at 14:25
  • \$\begingroup\$ It sounds like you have painted yourself in a corner then... Unfortunately you will have to call the proper destructors one way or another. That means recording enough information to know which ones to call -- that may be an array of type-erased functions, or separating the objects by class, or some other method. Your call :) \$\endgroup\$
    – Quentin
    Nov 20, 2017 at 14:40

2 Answers 2

4
\$\begingroup\$

You have 2 options,

  1. keep track of destructors that need to be called and call them on clear

  2. Make sure that any object stored in the stack will only allocate from a allocator that will be cleared after (or at the same time) as the allocator it is allocated in and make sure it does not hold sole ownership to third-party-library handles that need a destructor.

The first is more foolproof while the second is a bit more error prone but you can use std::is_trivially_destructible<T> to make sure you only allocate types without a destructor.

\$\endgroup\$
1
  • \$\begingroup\$ As I want to have this stack allocator as fast as possible I will go with the 2nd option. Thanks. \$\endgroup\$
    – Pins
    Nov 21, 2017 at 19:17
0
\$\begingroup\$

Is single/double frame allocator suitable only for POD datas?

Nope, as long as it allocates memory properly aligned for any user-defined type. That said, about construction and destruction of non-trivial types...

[...] so it doesn´t call any destructors. Am i doing something wrong? What was your approach?

You are doing things exactly right if that's, indeed, a memory allocator.

An allocator shouldn't actually care about the data types it stores, or else it's more like a data structure than memory allocator. The memory allocator's job is simple: it gives you requested amount of bytes, often from a pool of memory already allocated in advance, to do with as you like, after which you might free it and return it to the pool to be used somewhere else. The only type-related concerns an allocator faces is alignment and size. If you are using type traits for anything more than figuring out alignment and size, that's no longer resembling an allocator.

For your case:

int* freeTiles = _allocator.allocate<int>(freeTilesSize);

... the only purpose I see to making allocate a function template is to avoid a cast and avoid specifying type size/alignment. If it's a genuine allocator it shouldn't bother constructing whatever type, T, is. That's up to the client to do.

Double Construction/Destruction UB

You'd actually make your allocator far, far less general-purpose if you attempted to construct elements and destroy them through it, because imagine what happens if you tried to make std::vector use your allocator. vector would attempt to allocate with your allocator which would construct elements, and then vector would then try to construct them a second time. Likewise when you attempt to destroy the vector, it would attempt to destroy all the elements it contains and then free the memory, at which point your allocator would want to destroy them a second time. It's not the job of an allocator to be constructing and destroying elements. That's the job of the data structure.

It's for these reasons that std::allocator and practically all other allocator designs, widely-used, do not construct or destroy elements, since the point of an allocator is to be used by something that does if that's necessary, like a data structure.

Probably the result of this confusion between an allocator and data structure's responsibility is because of the nature of default operator new/new[] and operator delete/delete[]. The former carries the responsibility of both allocating and constructing elements, and the latter both destroying and freeing elements. But that's kind of for convenience. These operators shouldn't be considered allocators (and default operator new/new[] generally use malloc under the hood, which is an actual allocator and does not bother to construct things). Also none of the standard library containers use default operator new[] because that would make them redundantly default-construct elements. They rely on std::allocator instead which also does not construct/destroy elements while they manually construct and destroy elements themselves.

Allocating N Elements != Constructing N Elements

This separation of responsibilities between, say, data structure and allocator isn't an arbitrary separation of concerns but actually a fundamental requirement. For example, a data structure might want to allocate 1 kilobyte even though only half of that kilobyte is used to store and construct elements in the container. That's a common scenario with std::vector which often allocates more memory than needed to store its elements to avoid a memory allocation every time you insert to it, so it doesn't actually want to construct a kilobyte's worth of element data in that case (maybe only a fraction of it). This will be the case for any data structure which has something like a capacity concept separate from size (unrolled lists, deques, n-ary trees, hash tables, etc. etc. etc) which is generally any variable-sized data structure that doesn't allocate one element at a time.

If the allocator design favored constructing N elements when requested to allocate memory for N elements, it would make it impossible to implement std::vector let alone any variable-sized sequence or associative container which doesn't allocate one node at a time unless you don't mind constructors being called on elements you never inserted into the container, e.g. It is very, very important and useful for an allocator not to construct and destroy elements.

Among the variable-sized standard library containers, only a handful like std::list, std::set, and std::map could be implemented using a memory allocator that constructed and destroyed elements itself.

Data Structures vs. Allocators

Now if you are creating a data structure, that's a considerably higher level concept dealing with elements of a particular type rather than raw bits and bytes as with the case of an allocator. And in a C++ data structure, you should properly copy-construct or move elements inserted or emplaced with placement new and invoke their destructors manually on removal for non-trivial types (potentially using type traits as an optimization detail to skip that for plain old types) if you want to make them widely applicable, but a memory allocator has no such requirements.

And I actually recommend focusing more on data structures for performance than allocators, since splitting efficient memory allocation away from the data structure is always considerably more fiddly than having a data structure which just allocates memory efficiently without the help of an external allocator. Life becomes a lot simpler if you use a tree structure like a quad-tree or octree which just very efficiently allocates its nodes against any general-purpose allocator instead of relying on a separate allocator to be specified to have any hope of being reasonably efficient while it attempts to allocate one node at a time.

But for allocators, all you're concerned with is bits and bytes, so it shouldn't matter whether you're allocating things that are trivially constructible or not or deallocating things that are trivially destructible or not. That's not a concern for allocators to deal with. It's for the data structures. So your allocator should be suitable for allocating any data type provided it allocates bytes of memory to store them with proper alignment and size, but it would be up to the client to make sure that elements are constructed and destroyed properly after allocation and prior to freeing.

Questions

I see this a good for using with POD data structures or classes with default destructor, however, is it usable also for bigger entities with some behavior at the destruction?

Again an allocator should not be concerned with construction and destruction, just as malloc/free aren't along with variants (jemalloc, e.g.), and just as std::allocator isn't. However, the client has the responsibility to properly construct and destroy elements as needed. Naive example assuming Foo is not trivially constructible and destructible:

// Allocate memory for Foos (not constructing them):
Foo* foos = stack_allocator.pop<Foo>(num_foos);

// Construct Foos:
for (int j=0; j < num_foos; ++j)
    new(foos + j) Foo(...);

// Do stuff with Foos.
...

// Destroy Foos:
for (int j=0; j < num_foos; ++j)
    foos[j].~Foo();

// Free memory, pushing it back to the stack.
stack_allocator.push<Foo>(num_foos);

However, aside from the above code being tedious to write, it also may not be exception-safe. So often you'd want to make it conform to `std::allocator to allow standard library containers or create some kind of data structure which uses your allocator, like so:

// Allocate and construct Foos.
StackArray<Foo> foos(num_foos, stack_allocator);

// Do stuff with Foos.
...

// Destruction and memory freeing is done automatically
// when 'StackArray' goes out of scope.

I would need to store them into heterogenous container and that would affect performance. No?

Just noticed this part in the comments but depends on the container and it doesn't have to be heterogeneous. If you really like the concept a stack frame allocator, then you can build some general-purpose containers against it like:

StackArray<Foo> array(alloc, size);

The only conceptual overhead is that it does need to store the size of the array as a data member since it needs that to destroy all the Foos in its dtor. And in the constructor it can construct all the Foos in the array and in the destructor it can destroy them. If Foo is trivially destructible or constructible, it can skip all that using type traits to determine whether that's needed or not at compile-time.

Just be a bit careful with data structures you create against a stack frame allocator, since their lifetimes should not persist beyond that of the allocator. And naturally the only data structures you can effectively create are ones that would not free memory themselves directly or only free memory in precise reverse order. Often what I suggest if you want a persistent stack frame allocator is to not make any data structures that use it free memory (or ignore their requests). Instead just do something like this:

void some_func(StackAlloc& stack_alloc, int n)
{
     ScopedAlloc scoped_alloc(stack_alloc);

     // Important: 'scoped_array' uses ScopedAlloc, not StackAlloc.
     ScopedArray<Foo> scoped_array(scoped_alloc, n);

     // Do stuff with 'scoped_array'. ScopedAlloc ignores any requests
     // from ScopedArray to free memory.  ScopedArray does,
     // however, invoke destructors when it is destroyed.
     ...

     // Meanwhile when 'scoped_alloc' goes out of scope, it frees
     // any memory chunks allocated through it in reverse order
     // from 'stack_alloc'.
}

[...] however, is it usable also for bigger entities with some behavior at the destruction?

If you cover the destructors through data structures like the above, sure. That said the main thing to keep in mind about any kind of stack allocator is that it needs to free memory in the precise reverse order in which it is allocated. It can't free elements from the middle, e.g., so you generally need to tie everything to be allocated and freed to the local scope of a function which will take care of making sure memory is pushed/popped in a proper LIFO pattern.

What was your approach?

I generally avoid stack allocators since they're a bit fragile in the ways described above if you aren't careful to tie your objects to the scope of a function to the point where it starts to feel like we're fighting the programming language and need a new one that allows the analogical equivalent of variable-length arrays in C. Instead the way I avoid heap allocations for common cases is doing something like this:

// 'n' is, 99% of the time, in the range [0, 64)...
void func(int n)
{
     int stack_mem[64];

     // Use stack_mem if the data fits, otherwise use heap.
     int* data = (n <= 64) ? stack_mem: new int[n];

     // Do stuff with data.
     ...

     // Free the memory if it was allocated on the heap.
     if (data != stack_mem)
         delete[] data;
}

... which you can generalize to a RAII-compliant, exception-safe data structure which properly invokes ctors/dtors if necessary like:

template <class T, int FixedBufferSize>
class SmallVector
{
public:
    ...

private:
     // Used to store data if it fits. We do not store
     // an array of T[] here since that would want to
     // invoke the default ctor on all of them. We only
     // want to construct elements which are actually 
     // inserted to the container.
     typename std::aligned_storage<sizeof(T), alignof(T)>::type buf[FixedBufferSize];

     // Points to 'buf' if data fits, heap otherwise.
     T* data;

     int num:
     int cap;
};

... at which point the above turns into simply:

// 'n' is, 99% of the time, in the range [0, 64)...
void func(int n)
{
     // Only uses heap if 'n > 64'.
     SmallVector<int, 64> data(n);

     // Do stuff with data.
     ...
}

It's not as theoretically optimal as a stack frame alloc since it has to anticipate common cases and it could reserve more stack space than necessary (too much stack or too little -- both would not be ideal), but it's so much less delicate. It can't be misused nearly as easily. You can even safely store these persistently if you want and treat it interchangeably with std::vector, only it doesn't heap allocate unless you insert more elements than you reserved through FixedBufferSize.

I actually prefer sequential allocators which only purge all memory allocated over a stack allocator that requires a strict LIFO push/pop pattern, since that can be so, so delicate when the language doesn't give us the tools to make sure we allocate and free in that precise order at all possible times.

Stack Allocators

Again IMO stack allocators are easy to misuse so I tend to avoid them, but one of the most interesting things about allocator proposals from Alexandrescu is that he generalized the concept of a "parent allocator". That is, every allocator can recursively use another allocator to allocate its own memory pool.

A stack allocator as a parent allocator becomes a lot more interesting, because you might implement a free list which actually does allow freeing elements in any order using a parent stack allocator for its pool, or vice versa.

But anyway, a single/double frame allocator is perfectly capable of allocating memory for UDTs, provided that it's allocating memory properly aligned for that UDT. Just make sure your stack pointer is aligned properly before you return its address for the client to use. But again you do need to properly construct and destroy those elements somewhere else, but that's not the concern or job of an allocator. It just deals with things at the level of bits and bytes, not data types.

\$\endgroup\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .