Post by @MaddieM4@raphus.social

So, something that happens in my life is that I'll be on some kind of kick, and end up separately talking about it in several distant corners of my social space independently and redundantly. Lately, that's been the war I'd like to someday wage against general-purpose allocators. Well, guess what just coincidentally happened across my recommended feed today?

Parts of this will feel remedial to experts, since Nic is doing something that I do a lot (attempt to write for a wide audience and train people up in better patterns than the mainstream), but if you're already a low-level programmer, the thing to pay attention to is the philosophy here. `malloc` (and its wrappers, like C++ new or smart pointers, default allocation in Rust) is a general-purpose allocator, and those are... inherently, jacks-of-all-trades, which leads to several problems of lifetime complexity and runtime cycle use.

(or, in more incendiary terms: death to `malloc`!)

https://www.youtube.com/watch?v=3rez2rDYHHA

Memory Management, Explained Simply (Part 1)

YouTube

0 Boosts

0 Likes

crzwdjk ✅

@crzwdjk@mastodon.social 7 hr. ago

@MaddieM4 One of the things that I discovered when digging into the internals of shader compilers is that they all (well, glslang and Mesa at least) use custom allocators because they have specific object lifecycles, so you really want the ability to slowly build up a complicated tangle of objects that all point to each other and then when you're done compiling just discard all of them in one go.

MaddieM4

@MaddieM4@raphus.social 14 hr. ago

This is an idea that first got planted in my head by Casey, and I've historically considered this to be a required watch for people who write software as a pointer forest, or avoid C because they think a scary pointer forest is the only way to write code in that landscape.

Note that there are *parts* of his ZII idea at the end which are applicable outside of gamedev, but not entirely. There are a lot of good reasons to try to design your types to mean a sensible thing when the contents are a correctly-sized block of zero bytes - consider C99 designated initializers and the API patterns they open up. Also, cleared memory is cheap to allocate - not quite as cheap as uninitialized memory, but cheaper than "these fields need these values". And you can, of course, get a heckload of valid structs at once as a contiguous block of zeros. Using this for infallible allocation by using a (shared) cleared memory region as a fallback during allocator failure? Game-only stuff.

https://www.youtube.com/watch?v=xt1KNDmOYqA

Casey Muratori | Smart-Pointers, RAII, ZII? Becoming an N+2 programmer

YouTube

MaddieM4

@MaddieM4@raphus.social 13 hr. ago

I would argue that, if we were to start from scratch, low-level programming is easier for everybody if GP allocators *simply do not exist.* They are complex bags of heuristics that can't serve anybody really well, with nuanced tradeoffs between speed of execution, quality of decision-making, complexity of source code, multithread-safety, fragmentation, and trying to infer what you want from indirect and limited information. And because it's a performance strain point, everyone is trying to make their `malloc` as fast as possible and keep changing the internals over time. We have had terrible bugs in glibc malloc multiple times over the years because it's a dense mess of conditional behavior with tons of tuning options. This still doesn't please everyone, which is why things like `jemalloc` exist.

But this also gets in the way of permanent computing. Notice what this does to the update schedule? Your ability to deliver something simple and robust that never needs fixes later?

MaddieM4

@MaddieM4@raphus.social 13 hr. ago

This is one of the glowing lines that I see in programming these days, which I try to make visible for other programmers, because it's kind of like putting on the They Live glasses, and which I usually describe as mechanism vs policy.

When we say that a function _does a job,_ there's a little linguistic ambiguity there. Two functions `sort` and `quicksort` do the same job from an externally visible perspective. But `quicksort` is a well-defined and well-documented algorithm, a specific way of sorting... that's a mechanism. And `sort`, you're delegating to some other software author "make a good decision on my behalf here", and that's not a bad thing to do, but I call that a policy function. I think functions should either be mechanism or policy, not mix the two, and most policy functions in C should be macro aliases to a choice of mechanism function.

GP allocators are complex policy functions that have to operate almost blind to your use cases.

MaddieM4

@MaddieM4@raphus.social 13 hr. ago

So how do you allocate with only mechanism functions? Well that's where something I call a "page allocator" comes into play, and per Nic's video at the top, this can be a simple wrapper over `mmap` (in POSIX contexts). What does a page allocator do?

1. You ask it for an integer multiple of the system page size.
2. It is always a system call.
3. It uses mutexes or other mechanisms to be threadsafe.

This always works the same way: a bit slow, operating on a bulk scale. That isn't a bad thing, though! It means you can schedule your life around the predictable behavior, and you are incentivized to not use this thing a lot.

Once you get a region of memory from the OS, that's when you can use some sort of _special-purpose allocator_ and tell it "manage this range of bytes from start pointer to end pointer", and it will, with a specific algorithm. Your choice of algorithm.