I was surprised by how simple an allocator is • Hacker News Board

Re: I was surprised by how simple an allocator is

#41

Post by rcxdude » Mon, Jun 23, 2025, 8:38 AM UTC

notepad0x90 wrote: post #37

duped wrote: post #29

Earlier quoted context omitted.

That's essentially what an allocator is, it's an abstraction between a requested size and alignment from the user space program and the memory management API that interfaces with the MMU hardware (which maps virtual addresses into physical addresses where the virtual address is a "page" number + offset). The MMU is what's dealing in pages and offsets more than the kernel.

What I mean is, there is always a minimum page size you're given by the kernel. Typically that is 4kb. if you malloc(sizeof(int)); you're not getting sizeof(int), you're getting a 4kb page allocated. You can change that value to something other than 4kb but then the entire system will use that value. I'm asking why the page size allocated can't be depending on the user space allocator's syscall parameter (dynamic pag…

Note that the page file is essentially a datastructure which maps addresses to other addresses, but it also resides in the same physical memory. If you were to try to map every byte of a system to different physical address, it would need significantly more memory than the system had! Further, the datastructure needs to allow efficient lookup of data because the pagefile mapping occurs on every memory access (results are cached in the Translation Lookaside Buffer (TLB) and the speed and accuracy of this cache is often a limiting factor in the speed of the CPU). This all biases towards the mapping wanting to be quite coarse, in fact 4kB is probably already not optimal on today's systems with gigabytes of memory.

Re: I was surprised by how simple an allocator is

#42

Post by romesmoke » Mon, Jun 23, 2025, 10:55 AM UTC

I spent the most part of my PhD trying to convince people that allocators are not simple. But the not-simple part is design, specifically the strategy/policy part. In other words, minimizing fragmentation by adapting to linked program behavior. From what I know, no product-level allocator and very few research-level ones go beyond a "one size fits all" approach.

The reason why this is so is pragmatic: fancy strategies take extra compute time that is too expensive when one's sitting on the critical path. So what follows has a good chance of not bearing practical value but (i) there are setups where memory capacity is a bottleneck and (ii) hey, it's just a PhD anyway.

So what does a fancy strategy even look like? Let's look at the simplest non-trivial version of the problem. Say, we know the sizes and lifetimes of all objects in advance, and we want to pack them in as tight a contiguous address space as possible. Mathematicians call this the Dynamic Storage Allocation (DSA) problem and it's NP-complete, i.e., no known optimal algorithm exists for the general case. Deep learning compilers battling the AI memory wall have been returning to DSA lately (it's an old problem).

The implication of the above is that a real allocator, that is, one forced to work under uncertainty w.r.t. object sizes and lifetimes down the line, can always fail remarkably. So going for a general-purpose solution begs that you know what you're doing (one could argue that most programs out there are "well-behaved", and I would agree up until the point where this observation is turned into a universal law).

Nevertheless, it remains a fact that writing a toy allocator is both educational and soberingly not hard.

Re: I was surprised by how simple an allocator is

#43

Post by o11c » Tue, Jun 24, 2025, 12:00 AM UTC

WalterBright wrote: post #35

GuB-42 wrote: post #31

Writing a malloc/free replacement was a 1 day project we did at school in the first couple of weeks of learning C/UNIX. Many students didn't even know how to code before that. All that to say that writing an allocator is not hard. Writing a good allocator however is another story. Not because the algorithms are complicated, but because it is a very critical part of most systems and requires extensive knowledge of rea…

Writing a basic allocator should be a foundational part of any programming curriculum. It removes the mystery of them. Just like writing a lexer should be. It's amazing how many programming tasks are improved by writing a lexer for it, and the awful code I see from people who have no idea how to write one. (For example, I wrote a lexer for function that read a date like "Mar 7, 1997" and turned it into a time_t. The…

And how did you lex "September 3, 1752"?

Re: I was surprised by how simple an allocator is

#44

Post by o11c » Tue, Jun 24, 2025, 12:13 AM UTC

notepad0x90 wrote: post #28

allocators can be simple but how about memory management kernel subsystems? One question I have for those who know the topic at a greater depth: Are there simpler memory managers that don't use a fixed page size? Or does that make it a lot more complex? imagine requesting allocation of 1 byte and the kernel allocating a page of 1 byte and immediately you request 20GB and you get a 20GB page. Other than memory-managem…

Fragmentation is one major reason to use fixed size classes. After just a few allocate/free-a-bit cycles, you can very easily end up with a large amount of free space in unusably tiny chunks. (this is one reason why languages with a Garbage Generator tend to prefer being allowed to move and compact their objects - their whole thing is keeping the allocator as simple as possible to beat the benchmarks, so they can't use the usual solutions)

There's also the matter of space overhead.

A bitmap allocator is simple and has an overhead of 1 bit per chunk (allocated or not). Normally the chunk is at least 16 bytes, but if you know you're doing smaller allocations there's nothing stopping you from doing one at byte granularity.

If there exists an invalid value (for example, UTF-8 strings cannot contain the byte 0xff), you can implement allocators with zero overhead, though efficiency requires changing the API (`malloc` requires writing to all the memory to erase the tombstones, so it's more efficient for the allocator to support `strdup` and `realloc_strcat` directly).

By bucketing you can vary the overhead based on allocation size. But also remember, a lot of the trickery you can do here comes at the cost of becoming more vulnerable to use-after-free bugs.

Besides all the missing APIs, one major annoyance related to allocators is the fact that userland lacks support for CPU-local variables that the kernel can use for more efficient operations. `rseq` helps a little but still falls short.

Re: I was surprised by how simple an allocator is

#45

Post by WalterBright » Tue, Jun 24, 2025, 5:14 AM UTC

o11c wrote: post #43

WalterBright wrote: post #35

Earlier quoted context omitted.

Writing a basic allocator should be a foundational part of any programming curriculum. It removes the mystery of them. Just like writing a lexer should be. It's amazing how many programming tasks are improved by writing a lexer for it, and the awful code I see from people who have no idea how to write one. (For example, I wrote a lexer for function that read a date like "Mar 7, 1997" and turned it into a time_t. The…

And how did you lex "September 3, 1752"?

Month, DayOrMonth, Year

Re: I was surprised by how simple an allocator is

#46

Post by marssaxman » Tue, Jun 24, 2025, 8:44 PM UTC

WalterBright wrote: post #35

GuB-42 wrote: post #31

Writing a malloc/free replacement was a 1 day project we did at school in the first couple of weeks of learning C/UNIX. Many students didn't even know how to code before that. All that to say that writing an allocator is not hard. Writing a good allocator however is another story. Not because the algorithms are complicated, but because it is a very critical part of most systems and requires extensive knowledge of rea…

Writing a basic allocator should be a foundational part of any programming curriculum. It removes the mystery of them. Just like writing a lexer should be. It's amazing how many programming tasks are improved by writing a lexer for it, and the awful code I see from people who have no idea how to write one. (For example, I wrote a lexer for function that read a date like "Mar 7, 1997" and turned it into a time_t. The…

I wrote a lexer-driven date parser like that as one of the first contract jobs I ever did - maybe the first, I can't quite remember - at the very beginning of my software development career, back in the previous century. I remember feeling rather proud of it.

(In hindsight, I'm not sure that trying to accept any conceivable date format as if by magic was really such a great idea, but that's what my client wanted, and building it was an enjoyable challenge.)

Re: I was surprised by how simple an allocator is

#47

Post by notepad0x90 » Thu, Jun 26, 2025, 5:36 PM UTC

rcxdude wrote: post #41

notepad0x90 wrote: post #37

Earlier quoted context omitted.

What I mean is, there is always a minimum page size you're given by the kernel. Typically that is 4kb. if you malloc(sizeof(int)); you're not getting sizeof(int), you're getting a 4kb page allocated. You can change that value to something other than 4kb but then the entire system will use that value. I'm asking why the page size allocated can't be depending on the user space allocator's syscall parameter (dynamic pag…

Note that the page file is essentially a datastructure which maps addresses to other addresses, but it also resides in the same physical memory. If you were to try to map every byte of a system to different physical address, it would need significantly more memory than the system had! Further, the datastructure needs to allow efficient lookup of data because the pagefile mapping occurs on every memory access (results…

But why does it work that way, why does all memory need to be mapped before allocation? why can't it work like file systems where you have a table/datastructure mapping inodes to files? The smaller your allocations are, the less total ram you have, that would make sense. Some apps need huge chunks of memory, some don't, why the one-size-fits-all approach? TLB lookup can also be O(n), it will be slower when you have lots of small allocations because that means lots of lookups but that lets applications optimize performance that way instead of having it be a system-wide setting.

Re: I was surprised by how simple an allocator is

#48

Post by notepad0x90 » Thu, Jun 26, 2025, 5:43 PM UTC

Veserv wrote: post #39

notepad0x90 wrote: post #37

Earlier quoted context omitted.

What I mean is, there is always a minimum page size you're given by the kernel. Typically that is 4kb. if you malloc(sizeof(int)); you're not getting sizeof(int), you're getting a 4kb page allocated. You can change that value to something other than 4kb but then the entire system will use that value. I'm asking why the page size allocated can't be depending on the user space allocator's syscall parameter (dynamic pag…

MMU hardware has a hardware-defined minimum mapping granularity (i.e. page size). On x86-64 this is 4KB. On ARMv8/v9 the specification allows runtime configuration for any of 4KB, 16KB, or 64KB as the minimum mapping granularity on a per-process basis, though the actual chip implementation is free to only support a subset of such configurations and still be conformant. Implementations may also define certain sizes th…

I suppose having some sort of minimum granularity for the MMU makes a lot of sense, but above that point, why limit the "steps" or the maximum? why not 4KB+2 for example (4098)? For the sake or discussion, let's say I have 128GB ram and 50TB page file, can that work? Why is a fixed-size page more efficient, is it because of offset calculations being simpler arithmetic operations? I figured the TLB is (or can be) a simple (large) table implemented in hardware, the simplicity translating into O(N) complexity. I am suspecting it might have to do with hardware cost?