Coding a MUD as a hobby project using memory arenas and I am straight up not having a good time with strings. Right now I'm giving the players fixed size 4k buffers to send commands too instead of using dynamically sized strings. Everything else is golden. Just slap it on to the frame/temp arena and reset the marker back to 0 after an update.
Arena allocator tips and tricks
61–70 of 99 posts
Re: Arena allocator tips and tricks
#62Didn't know these were called Arenas, this technique is prevalent in game development.
also called a "bump" allocator... because all it does is bump a pointer. nice to use when you have a nicely ordered order of execution where you are guaranteed to always come back to a known position where you can free the entire heap/arena at once. (i.e. a typical main message handling loop).
Also called "regions".
Re: Arena allocator tips and tricks
#63Fantastic article! I have a project with a similar arena allocator, so I'll definitely be taking some of these tricks. One thing my allocator does do is organize arenas into a linked list so that you can grow your size dynamically. However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then…
> However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then divide the giant arena up into smaller arenas. That depends. If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory, go ahead. On a system with other things running, you gene…
[deleted]
Re: Arena allocator tips and tricks
#64Fantastic article! I have a project with a similar arena allocator, so I'll definitely be taking some of these tricks. One thing my allocator does do is organize arenas into a linked list so that you can grow your size dynamically. However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then…
> However I really like the article's point that you're always going to be living within _some_ memory budget, so you might as well allocate everything up front into a giant arena, and then divide the giant arena up into smaller arenas. That depends. If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory, go ahead. On a system with other things running, you gene…
> If you’re running on e.g. a video game console where you’re the sole user of a block of pretty much all memory
Games consoles haven't been that for a long time. PS5 and XSS are full blown multi-user multi-application systems. PS4 and Xbox One were multi user systems with reserved blocks for the OS, but still very close to a modern OS.
Re: Arena allocator tips and tricks
#65Coding a MUD as a hobby project using memory arenas and I am straight up not having a good time with strings. Right now I'm giving the players fixed size 4k buffers to send commands too instead of using dynamically sized strings. Everything else is golden. Just slap it on to the frame/temp arena and reset the marker back to 0 after an update.
If you're using c++ look at pmr::string.
Re: Arena allocator tips and tricks
#66Having to decide ahead of time how much memory to allocate to the arena is... crap... The vast majority of programmers don't want arbitrary 'out of memory in arena' errors just because the user inputted slightly more things than expected. Yes, I know that modern OS's don't actually allocate memory till you use it, but when you make widespread use of that functionality, typically your reuse of address space is poor an…
The actual point to understand is that a general purpose allocator is usually "mostly crap" because it requires an incredible internal complexity to meet all requirements. It's often better to use specialized local allocators, and write code which expects an allocator to be provided instead of calling into global allocator functions. Such specialized allocators can often be a lot simpler, while being at least as fast general purpose allocators like jemalloc or mimalloc.
Very often you don't actually need to track or manage the lifetime of individual objects, since related objects are often created and destroyed at the same time. For instance when parsing a JSON file you might end up with many individual nodes which can all be discarded at the same time once the parsing result has been consumed. With an arena allocator, you just throw away the memory for all those nodes at once, instead of calling a free/deallocate/delete functions tens- or hundreds-of-thousand times.
Re: Arena allocator tips and tricks
#67In my hobby project, I started always passing an allocator argument to every function or object which requires allocation (inspired by Zig) and I love it so far. Often I can just pass a bump pointer allocator or a stack-based allocator and do not care about deallocation of individual objects. I also wrote a simple unit testing framework to test out-of-memory conditions because it's easy to do when you're in control o…
Adding that when many linux distributions face OOM, a killer daemon steps in and might kill your service even if you were handling the situation properly.
The idea is that the server must have a known allocation budget, similar to Java's max heap size. There's a tree of allocators, i.e. a temporarily created arena allocator needs initial memory for its arena, so it can grab it from the root allocator. And the root allocator ultimately must be fixed-size and deterministic. Sure if there are other processes in the system allocating without concern for other apps, then the OOM killer can kill the server. But if there's no such process, I think it should be pretty stable.
Re: Arena allocator tips and tricks
#68[deleted]
Re: Arena allocator tips and tricks
#69Earlier quoted context omitted.
> Having to decide ahead of time how much memory to allocate to the arena is... crap... A nice solution in many cases is to just keep a bunch of std::vector (or equivalent) around for the types you need, and .clear() them all at the start of each request/frame/message/whatever being processed. Calling push_back on a vector will only allocate when the vector's already reached its capacity, which will happen very rarel…
Generally, std::vector not going to work for allocator backend. The issue being, std::vector relocates all elements every time it increases the capacity. Therefore, adding an element to std::vector may invalidate addresses of all previously added vector elements. You gonna have to adjust your higher-level data structures which use that allocator, replacing pointers with offsets relative to the start of that std::vect…
Yes, that's true if you need higher-level datastructures, but if your functions are just taking vectors/spans of stuff as input then it works out fine.
Re: Arena allocator tips and tricks
#70Earlier quoted context omitted.
> Having to decide ahead of time how much memory to allocate to the arena is... crap... A nice solution in many cases is to just keep a bunch of std::vector (or equivalent) around for the types you need, and .clear() them all at the start of each request/frame/message/whatever being processed. Calling push_back on a vector will only allocate when the vector's already reached its capacity, which will happen very rarel…
Generally, std::vector not going to work for allocator backend. The issue being, std::vector relocates all elements every time it increases the capacity. Therefore, adding an element to std::vector may invalidate addresses of all previously added vector elements. You gonna have to adjust your higher-level data structures which use that allocator, replacing pointers with offsets relative to the start of that std::vect…
std::vector is fine if you access elements by index, instead of pointer, which can be a perfectly fine approach. Of course this kills the general purpose allocator aspect, since you're not getting back pointers, only offsets.
However, if you combine that with generation numbers, you can make yourself a very handy container with stable and safe references. slotmap [1] comes to mind.