Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Arena allocator tips and tricks

nullprogram.com

Post reply on HN
Print view View original

41–50 of 99 posts

Re: Arena allocator tips and tricks

#41

Post by eschneider »

londons_explore wrote: post #40

Having 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…

This...depends on your application. With a lot of small memory/embedded applications, deciding how much memory you need ahead of time is how you do things and normally you don't malloc at all. Because you absolutely need to know the memory bounds of your app. In that sort of environment, this approach can be useful.

Re: Arena allocator tips and tricks

#42

Post by galangalalgol »

londons_explore wrote: post #40

Having 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…

You aren't the target audience I think? The main two reasons to use custom alloctors, or the two I run into at least, is when memory allocation profiles as a significant portion of your flamegraph, and/or there is a real probability of memory fragmentation preventing new allocation even when there is plenty of space left. That latter is often the case with embedded. The former can be, and is also pretty common any time you are cpu bound as in gaming or signal processing.

Re: Arena allocator tips and tricks

#44

Post by logicchains »

londons_explore wrote: post #40

Having 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…

> 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 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.

Re: Arena allocator tips and tricks

#45

Post by vidarh »

londons_explore wrote: post #40

Having 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…

It's straightforward to make this slightly more dynamic by keeping a linked list of arenas and just add new one when you run out of space. You get most of the benefit with only a tiny increase in complexity.

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.

Re: Arena allocator tips and tricks

#46

Post by galangalalgol »

saagarjha wrote: post #12
sakras wrote: post #2

Fantastic 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…

Yeah, profiling is your friend. I forget if it's called a sharded slab or a buddy allocator, but the one where you have different preallocated buffers chunked at different sizes. Any time you allocate you are given the smallest chunk that will hold what you asked for. Profiling gives you optimal size boundaries as well as the number of each. Add a safety margin and off you go. Super fast allocation and guaranteed no fragmentation. In a c++ codebase overloading std::new to do this is probably the easiest way to get your allocation performance back and avoid fragmentation.

Re: Arena allocator tips and tricks

#47

Post by olodus »

kgeist wrote: post #38

In 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…

Oh wow that is a really interesting test solution. That would be an interesting thing to add to all zig tests (I know they already have the testing allocator and good valgrind support but I don't think that tests/simulates oom).

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.

Re: Arena allocator tips and tricks

#48

Post by judofyr »

olodus wrote: post #47
kgeist wrote: post #38

In 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…

Oh wow that is a really interesting test solution. That would be an interesting thing to add to all zig tests (I know they already have the testing allocator and good valgrind support but I don't think that tests/simulates oom). 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 mod…

I've been using this helper: https://github.com/judofyr/zini/blob/ea91f645b7dc061adcedc91.... It starts by making the first allocation fail, then the second, then the third, and so on. As long as it returns OutOfMemory (without leaking memory) then everything is fine.

Re: Arena allocator tips and tricks

#49

Post by habibur »

kgeist wrote: post #38

In 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.

Re: Arena allocator tips and tricks

#50

Post by amalcon »

habibur wrote: post #49
kgeist wrote: post #38

In 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.

Interestingly (confusingly), Linux's OOM killer is invoked for a different notion of OOM than a null return from malloc / bad_alloc exception. On a 64-bit machine, the latter will pretty much only ever happen if you set a vsize ulimit or you pass an absurd size into malloc. The OOM killer is the only response when you actually run out of memory.

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.

Post reply on HN