Hacker News Reader

Comment by tialaramex | Hacker News Reader

I think when we're looking back on the 2020s we'll be struck by the Allocator obsession

All of the Handmade "C successor" languages seem to have this obsession, including not only Zig but Odin, C3 and Jai.

For some toy problems you can do clever allocator tricks and get a huge perf win. For example Jai and Odin both seem to really want you to write code which can throw away a "per-frame" arena periodically so they're not paying to track allocations in the arena because they're all thrown away at the same time.

But a lot of real world software just isn't that simple. This doesn't make such features worthless, it just means they're one of a thousand tools the experienced developer could want in their toolkit, not really deserving headline status.

View on HN

AAA games use allocators extensively, and they are more complex pieces of software with higher performance requirements than nearly anything else out there. So I'm not sure what toy problems you're talking about.

Allocators have been in wide use long before the 2020s but I agree there does seem to be a resurgent interest lately. Although I would argue it's part of a more broad trend of focusing data driven design. Which makes sense because accessing main memory is one of the slowest things your program can do.

And those games do so in a language (C++) where allocators is not a headline feature, and is barely even supported at all in the standard library.

The important part is a language where the standard library isn't special, and Rust has this property, too. So in domains where things like per-frame allocators are useful, you can still have them. That capability just isn't cluttering up the more common path where that isn't useful.

I never used it in practice, so maybe the support isn't that good, but I was under the impression that it was possible to pass custom allocators basically everywhere in the STL. See for example the definition of a vector here:

https://en.cppreference.com/cpp/container/vector

std::allocator was so painful to use it was almost always easier to just reimplement the container instead (especially for trivial ones like vector).

I haven't used the relatively new C++17 polymorphic_allocator, though, maybe it fixes this.

> and is barely even supported at all in the standard library.

What does that mean?

> AAA games use allocators extensively

They do, but not necessarily together with generic, standard containers.

When you find yourself wanting a nonstandard allocator, you usually want it because you want it to have some interesting property. It's not necessarily trivial to fit that into the interface of something like `std::vector`, or `std::unordered_map`, etc.

Here's my take as a game developer: 99% of use cases for custom allocators are scratch allocators for doing stuff within a frame. 95% of those are much easier to serve by just amortizing allocations by storing things in an `std::vector` (or equivalent) that gets cleared every frame. You can use linear storage to back many interesting data structures, including queues, ring buffers, priority queues, binary heaps, etc., and that's more than enough for a large number of systems in a game.

The overwhelming majority of the time, more complex data structures (like hash maps etc.) have a longer lifetime than the current frame, because the whole point of using them in the first place is to amortize lookup time across frames.

> But a lot of real world software just isn't that simple.

Zig doesn't force or even tends to prefer one way or another. If I want unassuming heap allocations that can be reclaimed in any order, there's an allocator for that. If I want an arena to discard at the end of something like a request or a video frame, there's an allocator for that. If I want to use a fixed backing buffer for the allocations, there's an allocator for that.

The point is that the standard library doesn't assume one or the other, which seems good if the problem is that "real world software just isn't that simple" in the more general sense that there's no one-size-fits-all allocation strategy.

But for how many software domains are allocators more specialized than a single built-in general purpose one so important it should be the focus of your language?

How many seems like an irrelevant question to me. If there are such software domains at all, Zig may be a compelling alternative to languages that don't have a standard library that lets you choose an allocation strategy freely.

I also disagree that this is "the focus" of Zig. Technically speaking it seems like a rather minor design choice for the standard library.

I'd word it slightly differently, as something like the Allocator Effect System obsession. It's not so much that allocator tricks don't have a role in modern software--all of the large applications I've worked on rely on things like arena allocation at least some of the time--but rather that things like making container types generic over allocators seems to be more trouble than it's worth. I've never seen anyone use anything other than the default allocator for STL types, for example.

Allocation happens. You can leave it to the compiler, the runtime, or let the code control it.

The automatic solutions are usually pretty good and usually the right place to start. But if performance is a priority, you want options.

BTW, “per-frame arena” is part of a general pattern of a repeated interval of work doing significant allocation. This is really common in software of all kinds… servers that process requests (like web servers and database servers) and typical command line tools.

Way back in the aughties I saw an interesting analysis (on a now defunct blog) indicating that under typical usage C# implementations tend to outperform C++ implementations in long-running business applications. The supposed reason was that C#’s compacting GC keeps the cost of new allocations fairly constant. By contrast, in C++ under typical use every new allocation requires probing for a sufficiently large block of free memory in an increasingly fragmented heap.

I haven’t tried to replicate this for myself. And, even assuming for the sake of argument that it was definitely true back then, a lot can happen in 20 years. But still, it does speak to wanting options when performance really is critical.

I’m not so sure the usefulness of custom allocators really relates to the complexity of the problem. Take the scratch arena example: ifaik it’s just free performance (& simplicity) whenever you need dynamic allocations with lifetimes that begin and end on a critical path. Presumably this is why Jai/Odin focus on this situation so much since it applies to per-frame stuff in videogames, but generally I’d expect this to come up more often in nontrivial problems.

> For example Jai and Odin both seem to really want you to write code which can throw away a "per-frame" arena periodically

You can generalize this far beyond per-frame semantics. Think per-http-request, per-pubsub-message.

Per each, you can create a new virtual.Arena, set it as your context.temp_allocator and use it for the entirety of the request or message. Afterwards, throw it away.

The nice thing about video game frames is that they're monotonous. We render exactly one at a time for ever. So all the memory we don't reserve for long-lived data forms a single Arena for our per-frame temporary storage and we can put all kinds of stuff in there "for free" so long as we don't fill the Arena in any one frame we're all good.

Our HTTP server may have dozens, or hundreds, or thousands of simultaneous requests. But we've decided to give each a specific arena with a size chosen in advance so that we can use arenas. This means that the request to check a CSS file hasn't changed (it has not) and the request to modify the holiday of an employee whose manager is changing mid-way through their annual leave are both given, say, a 10MB Arena. No problem for that CSS check, some text parsing, one OS call, an ALU operation, done. But alas the SQL Transaction for that holiday change used up so much memory now the text parsing code "temporary" allocation in code to queue email for both managers fails and it unwinds the whole HTTP request. 500 error, rewrite your Odin program.

Arenas make lots of sense for video games, but their applicability for these other applications is much more dubious.

> Arenas make lots of sense for video games, but their applicability for these other applications is much more dubious.

It's a fairly common pattern in non-video contexts to preallocate arenas of different sizes for different workload pools (e.g. different routes for a server).

It's also fairly common to allocate per-work-item (e.g. request/session/batch job) arenas for "general-purpose" scratch allocations that are small (your header parsing, auth context retrieval, etc.) and then default to a global manual/refcounting allocator for one-off large data actions like your holiday change. Since most business applications are returning summary/small aggregates over the large data action (in this example, something like "holiday updated successfully", not the entire history of the PTO table or the database connection's internal state), the copy cost of moving data between the global dynamic allocator and the arena for result transmission tends to be small.

That's not a terrible approach in some situations. If the large majority of code only needs the scratch arena and/or some per-handle allocators stored on e.g. the database connection pool, it can work well. But if, over time, the amount of bookkeeping required to maintain data tagging/movement between arenas/allocators becomes severe, it's worth stopping, stepping back, and considering that you've kind of walked backwards into inventing a shitty generational GC.

Some of this surely stems from Rust not originally supporting allocators at the standard API level until later. You can manually create your own, and create/modify your own containers, but until GlobalAlloc came around it sometimes involved doing things like passing through Arc<Allocator> through to things if you wanted multiple things to use a single one.

Sometimes using a global one isn't the best thing (it's often a good idea to specialise base on allocation size, reuse and lifetimes), but I've used them quite a bit in C++ over the past 16 years doing HPC for graphics, rendering and simulation, so calling them only useful for "toy problems" likely shows you just haven't found a need for them in what you've been doing.

The C3 temp allocator leans into this though. It’s not a frame allocator but acts like a stack allocator. It solves the ”oh, how do you make sure the data you got back is properly freed”. In Zig you need to create and free arenas by hand, which is not far from freeing the returned allocations by hand.

But I think C3 shows it can be taken further.

> For example Jai and Odin both seem to really want you to write code which can throw away a "per-frame" arena periodically so they're not paying to track allocations in the arena because they're all thrown away at the same time

Given that both of these are intended for game development, wouldn't that make the most sense?

actually large programs that are persistent is where you really care. kernels and databases often use explicit allocators because there is so much policy wrapped up in allocation.

this goes back decades, its not just a feature of the 2020s. as a systems programmer I always want this, and the idea that allocator state should be completely hidden and implicit is shortsighted.

but yes, it is a bit onerous to pass around allocator(s). the real complaint that I have is that if 'malloc' is global and a compiler primitive, then we can do things like coalesce allocations and have compiler managed lifetimes when appropriate.

explicit allocators are an important lever, its not clear to me that we could never find a way to make them possible without the minor downsides.

Making allocators part of a type or scope instead of in every function call might be a start.

yes i've noticed this as well. they all stem from a heterodoxical corner of the programming community who are obsessed about performance. this isn't a bad thing, considering how slow modern software is! but this group believes performance is a memory issue, which is true for some software but not all. i think these languages can be really useful for realtime applications like gaming where allocation has a real cost, but the so-called "pointer jungles" are probably not the reason why microsoft teams takes a trillion cpu instructions to boot.

Reply on news.ycombinator.com