Arena allocator tips and tricks
nullprogram.com
nullprogram.com
I love things like these that use existing tests and expand the to just test further thing in already covered flows. We have done similar things at my work where we test expansion of data models against old models to check that we cover upgrade scenarios.
- https://github.com/ziglang/zig/blob/1606717b5fed83ee64ba1a91...
- https://www.ryanliptak.com/blog/zig-intro-to-check-all-alloc...
(Where crash means a worker process or something limited to something less than the entire system. See Erlang for the logical extension of this.)
I realize this implies Windows and Java are badly designed and my answer to that is "yes".
Actually since you skipped all the less than a page stuff I'm not sure you actually understand what my post is about…?
If you want to avoid your program triggering the OOM killer all on its own, you need to set up a vsize such that you'll get an application level error before actually exhausting memory. Even that isn't completely foolproof (obviously anyone with a shell can allocate a large amount of RAM), but in practice -- if your program is the only significant thing on the system -- you can get it to be very reliable this way.
Add in some cgroup settings and you should be able to keep your program from being OOM killed at all, though that step is a bit more complex.
I guess in practice the kernel might be in such dire straits that it is not able to even swap to disk and might need to kill indiscriminately.
If you're going to do drastic things, you can configure Linux's memory overcommit behavior, although strictly avoiding overcommit usually results in trouble from software not written with that in mind.
In extreme circumstances, the OOM killer can decide to kill your process even if it barely uses any memory (a simple way to get there is by fork-bombing copies of such processes)
Also, using oom_score_adj (https://www.baeldung.com/linux/memory-overcommitment-oom-kil...) is a lot easier.
https://www.kernel.org/doc/Documentation/vm/overcommit-accou...
The PS2 hardware does have full support for memory paging (at least on the main cpu core). PS2 Linux makes full use of it.
But the default TLB configuration from the BIOS is just a single static 31MB page (the other 1MB is reserved for the BIOS) and the SDK doesn't provide any tooling for dynamic pages.
And this is MIPS, so it's a software managed TLB with 48 entries. I wouldn't be surprised if some games did have dynamic paging, but they would need to provide their own TLB exception handler.
The double-sided approach is useful for various purposes. For instance you can allocate short-lived data from the front and long-lived data from the back. It also makes better use of free space: with two separate arena allocators one could be out-of-memory but the other might have free space. With the double-sided approach all memory is fair game.
Also I've heard that you can save an instruction when checking if your allocator is full by subtracting from the top, and checking the zero flag. It seems to complicate alignment logic. Does that ever end up mattering?
Anyways, you can find a full article about up vs down at https://fitzgeraldnick.com/2019/11/01/always-bump-downwards....
However if you do this note how the article hints at this strategy needing a bit more code on Windows: Windows doesn't do overcommit by default. If you do one big malloc Windows will grow the page file to ensure it can page that much memory in if you start writing to it. That's fine if you allocate a couple megabytes, but if your area is gigabytes in size you want to call VirtualAlloc with MEM_RESERVE to get a big contiguous memory area, then call VirtualAlloc with MEM_COMMIT as needed on chunks you actually want to use.
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 generally don’t want to assume you can just take some amount of memory, even if it’s “just the free memory”, or even “I probably won’t use it so it will be overcommitted”. Changing system conditions and other system pressure are outside of your control and your reservation may prevent the system from doing its job effectively and prioritizing your application appropriately.
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.
> While you could make a big, global char[] array to back your arena, it’s technically not permitted (strict aliasing).
Aren't char pointers/arrays allowed to alias everything?
I used that technique in my programming language and its allocator. It's freestanding so I couldn't use malloc. I had to get memory from somewhere so I just statically allocated a big array of bytes. It worked perfectly but I do disable strict aliasing as a matter of course since in systems programming there's aliasing everywhere.
To do stay in the rules you could set up a void* to suitable region in a linkerscript
(Yes, I know he understands it. Clearly he just refuses to accept that compilers can also reorder his code and he needs to accommodate that.)
The idea that he just needs to accommodate the compiler people is silly. Compilers exist to serve programmers, not the other way around. It's entirely reasonable to disagree with the compiler developers and use a flag to disable behaviour your don't want.
Clearly he doesn't. He just disabled harmful features and called it a day. Stuff like strict aliasing and undefined signed integer overflow apparently do nothing but serve as an excuse for the optimizer to screw up perfectly reasonable code.
https://cellperformance.beyond3d.com/articles/2006/06/unders...
https://stackoverflow.com/q/2958633/512904
Looks like this is a pretty good approach to fixing the C language. Take the nonsensical undefined stuff and tell the compiler to define it.
Looks like there is a may_alias type attribute to tell GCC that some types may alias:
https://gcc.gnu.org/onlinedocs/gcc/Common-Type-Attributes.ht...
I'm not sure if it's worth the effort though. Too much uncertainty.
In C++ you can just use placement new to change the dynamic type of (part of ) a char array (but beware of pointer provenance). In C is more complex: I don't claim to understand this fully, but my understanding is you can't change the type of a named object, but you should be able to change the type of anonymous memory (for example, what is allocated with malloc) by simply writing into it.
In practice at least GCC considers the full alias rules unimplementable and my understanding is that it uses a conservative model where every store can change the type of an object, and uses purely structural equivalence.
[1] of course most C implementations don't actually track dynamic types at runtime.
A limitation like that simply makes no sense to me. Everything is a valid char array but I can't place structs on top of one? Oh well, nothing I can do about it. I'll just keep strict aliasing disabled. If we're writing C, it's because we want to do stuff like that without the compiler getting clever about it.
> you should be able to change the type of anonymous memory (for example, what is allocated with malloc) by simply writing into it
Well, in my case, I'm the one writing the malloc and the buffer is the anonymous memory. I remember months ago I scoured the GCC documentation for some kind of builtin that would allow me to mark the memory as such but there was nothing. I did add some malloc attributes to my allocation function just like TFA suggested but apparently its main purpose is to optimize based on aliasing nonsense which I disabled anyway.
Well, yeah. Strict aliasing is less about the incidental values of memory addresses and more about the actual semantics of what you're doing. Where writing a struct into the middle of a char array makes no sense because you have no guarantee in the type system that the array is properly sized or aligned to contain that struct.
__attribute__((aligned(N)))
__builtin_assume_aligned(P, N)
Making sure that you respect all the underspecified, obscure, and often contradicting rules is not easy, so if you prefer to disable strict-alias, you have my sympathy. For the most part is useful for high performance numerical code, and less advantageous for typical pointer chasing stuff.
From the practical point of view, the safest way to implement a custom allocator is to make sure that the compiler can't see through it, so separate compilation and no LTO and/or launder your pointers through appropriate inline asm.
[1] but other 'anonymous' sources, like mmap, would also work in practice.
Yeah. I've read that the aliasing rules and features like restrict were introduced to C because Fortran had them.
> the safest way to implement a custom allocator is to make sure that the compiler can't see through it
Makes sense.
> launder your pointers through appropriate inline asm
This is a really neat trick indeed. I learned a lot today.
Some other good cases for arenas are rendering of a frame in a video game and handling of a http request. The memory is contained within that context and short lived.
For requests it might make sense to have low and high water marks so that additional arenas are created during request peaks and destroyed after if you want to limit long term memory usage of your application.
The general idea being that you don't need to track granular 'per-object lifetimes', but only a handful of 'arena lifetimes', and all objects share the lifetime of the arena they've been allocated in.
Of course it's also possible to manually call a destructor on an object in the arena without recycling its memory, but I heavily prefer using plain POD structs without owning pointers and which can be safely 'abandondend' at any time without leaking memory.
The thread-safety and dynamic extent is something I'm particularly pleased about.
I know that it’s a different “kind” of defect, but none of the code has overflow checks even with ptrdiff_t…
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).
It first allocates objects into an arena like structure. In a second step, it moves (evacuates) long lived objects into a compact region. The first region gets deallocated at once after.
Roughly speaking this leans on a heuristic that most objects are short lived. So it has arena like characteristics, but is of course managed/dynamic.
This might be one reason why managed languages like Java/C# get such good out of the box performance. You really need insight in your program and how it executes to beat this.
Interesting definition of "minority"
The number of deploys is a different thing.
That said, it really depends on the data usage semantics, and one could write a much less costly allocator for such specific data. Virtual address stable generic allocators have a tendancy to be technical abominations based on statistical usage assumptions. Namely, their cost could be not worth for the improvment, even if there is a significant one.
Yes, there can be. Security-critical software often does this explicitly, and it's been a bug when compilers have removed the zeroing by reasoning that unreachable memory is unreachable...leading to crypto secrets floating in memory unnecessarily.
For languages like Java and Go where objects are at least zero-initialized before the constructor(s) run, usually the allocator just zeroes the entire TLAB before allocation.
Destructors are a very bad idea if you are using any form of garbage collection other than reference counting. The destructors won't run until some arbitrary time after the last access to the object, and in the case of arenas, what would be a very fast deallocation becomes proportional to the number of objects. Further, if destructors can revive objects, everything gets very complicated.
Typical use: set up a specific arena just to read in the config file. Once it's done, release the whole arena.
> you don’t need to write destructors
I think this is not accurate. Destructors are not deallocators, they are supposed to set the object field in an invalid state. Now truth is that both are often called together, e.g `delete`.
> Typically arena lifetime is the whole program, so you don’t need to worry about freeing it
A technic I use is to increment a counter on `arena.alloc` and decrement it on `arena.dealloc`, and then free the memory (if it's on the heap) accordingly.
>
> I think this is not accurate. Destructors are not
> deallocators, they are supposed to set the object field in
> an invalid state. Now truth is that both are often called
> together, e.g `delete`.
If the object manages some resource other than memory, and if the object's lifetime is intended to guard the resource, then a destructor is needed.
But if the object manages memory only, as is often the case, and all of that memory came from the arena, then you really don't need to call any destructors.
This is the approach taken in one C++ [library][1] I've worked with, where objects represented scalar values to be used en masse for spreadsheet-like applications. In those applications (especially in 32-bit mode), being able to omit an allocator pointer and neglect a destructor call made things smaller and faster.
[1]: https://bloomberg.github.io/bde-resources/doxygen/bde_api_pr...
A typical arena allocator would just reset an offset to zero when the arena is 'freed' without calling any object destructors, and the allocator wouldn't actually have any type information about the objects allocated in the arena (of course you could also write an allocator which registers a destructor function with each allocation, and which would be called before the arena is reset):
bla_t* bla = arena_alloc(arena, alignment, size, destructor_func);
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 and free'd stuff will be neither reused nor returned to the OS.
Likewise, not being able to free things within the arena is also crap - I'm sure there will be plenty of times the system is running low of RAM, but hundreds of applications have thousands of arenas, all half full of never-to-be-used again items that the OS can't reuse.
A nice solution in many cases is to just keep a bunch of std::vector<T> (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 rarely after the first few runs, so the hot loop will usually be allocation-free, but without needing to allocate a fixed amount of memory ahead of time.
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::vector. This introduces another level of indirection, adds complexity, and in some edge cases may even ruin the performance.
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.
The block size is controlled with a template argument, the number must be a compile-time constant.
That doesn't fix your second objection, but where you want to use this tends to be where you know object lifetimes are similar anyway.
E.g. way back we loaded fonts for an embedded device using t1lib, which on loading a font made hundreds of tiny malloc calls, all of which were freed at the exact same time when the font was freed. Adding an arena allocator both sped it up, reduced memory use (less malloc overhead), and it didn't matter at all that we couldn't free things within the arena because they'd always be freed at the same time anyway.
So the takeaway from that might be that arena allocators aren't always right, but you'd be surprised how often you can predictably group allocations into sets with similar enough lifetimes it doesn't matter much. A key to this is often the trick showed in the linked article: Don't just lump everything into the same arena; use different arenas for different lifetimes. You might well find you're left with so few allocations that don't seem to fit that you can afford to just keep those around in a single long-lived arena as well.
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.