Hi !

I wonder how to implement a stack allocator and how this prevent from memory fragmentation ?

Can help me ?

https://www.gamedev.net/articles/programming/general-and-gameplay-programming/c-custom-memory-allocation-r3010/

This awnser is correct in the terms of information but not useful. The allocator is usually named to the allocation technology, it dosen't say anything about where the allocations are made. So a StackAllocator will most likely allocate on the heap rather than the “Program Stack” even if it isn't supposed to but this wasn't the question.

So, a StackAllocator is allocating on a stack maintained anywhere in memory. This means that allocations are time linear (they are in order of the time memory was requested) and also have to be released in the same order. This makes it hard to use stack based allocation in scenarios where allocations might not be in order, for example in the Network or multithreaded applications.

If you want to further read about allocations in general, @3vilstar already posted a good article

I'd note with the larger physical and virtual memory spaces, and improvements to the standard allocators (e.g. “buckets” based on object size so you don't have small objects fragmenting the space) that fragmentation is far less of a problem, so I wouldn't be concerned unless found a situation in practice.

The only fully custom one I came across frequently in recent-ish code (older code/libraries seem to commonly have their own allocator, string functions, etc.) is the “linear allocator” also mentioned in that article, and even here, I think its 95% programmer convenience in C (because no garbage collector, destructors, finally, or similar) and 5% maybe an optimisation (usually loads of unneeded temp string copies and such on at least some code paths). This includes in some multithreaded networked servers.

The general concept is they can create a pool/stack that takes say 4K blocks from the heap/OS at a time, for a connection/request/etc. and use it to allocate everything to do with it, then at the end just discard the entire thing. In C this is really convenient as functions can then return or jump anywhere easily (e.g. error returns/handling) and not worry about what temp strings or such are in local variables.

An actual stack allocator, seen it far less often. It is fairly uncommon to have a situation that all general purpose allocations and deallocations will be in reverse order but the threads own stack itself isn't what is wanted. Mostly only seen in implementations of stack data structures (e.g. `std::stack`), and then I think more about it as a data structure than as an allocation strategy. I think I once saw an implementation for storing polymorphic types without separate dynamic allocation (e.g. as with `std::stack<std::unique_ptr<MyBaseType>>`, or `std::stack<std::variant<A,B,C,D>>`) but again that is basically a data structure, not a general purpose allocator.

I suppose you could use it for allocating temp strings/arrays in functions that might be too big for the stack, but would need some additional mechanics to actually get that deallocation order correct without a lot of careful manual code.

Thanks !