[dead]
Arena allocator tips and tricks
11–20 of 99 posts
Re: Arena allocator tips and tricks
#12Fantastic 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 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.
Re: Arena allocator tips and tricks
#13I really like arena / bump allocators, they're really useful and powerful tools. I've been playing around lately with a Julia package that makes it relatively easy and safe to manage an arena https://github.com/MasonProtter/Bumper.jl
The thread-safety and dynamic extent is something I'm particularly pleased about.
Re: Arena allocator tips and tricks
#14Zig has arena allocator in the standard library
https://github.com/ziglang/zig/blob/master/lib/std/heap/aren...
Re: Arena allocator tips and tricks
#15> Typically arena lifetime is the whole program
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.
Re: Arena allocator tips and tricks
#16A very old trick for running Lua in your PlayStation 2 game (where the PS2 is a machine with 32MB of RAM and no memory paging) is to hook Lua’s realloc function into the venerable Doug Lea’s Malloc ( https://gee.cs.oswego.edu/dl/html/malloc.html ) set up to run in arena mode (ONLY_MSPACES? It’s been a decade or two…). That way Lua can fragment the arena all it wants without making a mess of the rest of the tiny addre…
> (where the PS2 is a machine with 32MB of RAM and no memory paging)
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.
Re: Arena allocator tips and tricks
#17Excellent article.
> 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.
Re: Arena allocator tips and tricks
#18Excellent article. > 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…
If you overlay a struct in your (char) buffer and dereference a pointer to it you would be accessing something with a different type than its declared type(char* as struct something *), it’s strict aliasing violation
To do stay in the rules you could set up a void* to suitable region in a linkerscript
Re: Arena allocator tips and tricks
#19Didn'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).
You can however use bump allocation for things that are not arenas. There are some GC allocators that use the technique.
Re: Arena allocator tips and tricks
#20Excellent article. > 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…
char can alias everything, i.e. you can deference a char pointer with impunity, even if the actual dynamic type[1] of an object is a different type. The reverse is not true: if the dynamic type of an object is char, just by using the alias rules, you can't deference it as an object of a different type.
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.