Let's Write a Malloc (2014) | Hacker News Reader

Let's Write a Malloc (2014)

danluu.com

129 pointsyla9229 comments

There are so many complaints here about how simplistic this is and how it is nowhere near what a "good" malloc does. That's kind of the point. Let's implement the most brain-dead version of this code. This is code you can quickly understand and reason about. It gives you a baseline to understand all the improvements that are included in a "real" malloc.

It would have been nice to include a list of the types of changes that a modern malloc would make to this basic structure to make it faster or fix bugs.

Correct. I also think that if the author would have said "minimum viable" or "baseline" in the title then all would have been forgiven.

"Let's write a ..." is a common way of introducing a tutorial, to the point it's almost a meme by now, so I don't think that is necessary.

Maybe we could standardise on a set of adjectives to cover the spectrum from: "this is a handwave that needs filling in" and "this is cheap and cheerful code that does the basic thing" all the way to "this has been in production for a decade" and "this code not only handles 99,7% of the corner cases, it even also handles several dozen corner cases that only ever occurred on architectures which haven't existed since the 20th century"?

I always enjoy reading this article from time to time:

https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...

As someone who really enjoys reinventing the wheel for fun, the final words are something of a mantra for me:

> Let me stress here that while this collector is simple, it isn’t a toy.

> There are a ton of optimizations you can build on top of this—in GCs and programming languages, optimization is 90% of the effort—but the core code here is a legitimate real GC.

> It’s very similar to the collectors that were in Ruby and Lua until recently.

> You can ship production code that uses something exactly like this.

> Now go build something awesome!

One of my OS class assignments was writing an allocator. It was scored by running some artificial workloads and measuring the memory overhead.

The results from past years were public and included the test case names like "PowersOfTwo" or "Primes". So instead of a generic allocator some of us optimized for the test suite :)

I managed to get one of the all time high scores by implementing a variable length integer encoding scheme that could fit powers of two, primes and other "interesting" numbers up to some size into one or two bytes.

It is unfortunate that the reference to the explanations used[0] is at the very end.

It is very useful to at least scan through this before reading this post and have it in front of you as a reference.

[0] https://wiki-prog.infoprepa.epita.fr/images/0/04/Malloc_tuto... -- for example here; the link in the post is stale.

I've had to find a malloc simple enough to port to another language recently and this one was really well written with good features and research papers behind it: https://github.com/mattconte/tlsf

For the algorithm used see https://github.com/jserv/tlsf-bsd

Incidentally, it’s also what AssemblyScript uses: https://github.com/AssemblyScript/assemblyscript/blob/main/s...

Unfortunately, allocation is far more complicated than that. Even more unfortunately, the ecosystem around such a critical task is woefully incomplete.

One of the biggest dangerous for the link's approach is partial interception, leading to conflicting libraries being used.

I collected some of my thoughts about allocation in a gist (originally on Reddit before it imploded): https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...

Implementing a malloc was one of the assignments of CS110 when I was an undergrad at Stanford ages ago. Grades were based on correctness, memory efficiency and maybe speed. IIRC mine used a variant of the dlmalloc strategy, and got perfect or near perfect marks. Definitely a cool and challenging assignment.

Here's another one such assignment https://ocw.mit.edu/courses/6-172-performance-engineering-of...

(I didn't take that class, but have reviewed students' code for this assignment several times)

Here is an example of a more complete, but still 'student level' malloc (2nd year 42 project) https://github.com/Jibus22/malloc/blob/main/srcs/malloc.c

[edit] : the header file is better to understand how everything work : https://github.com/Jibus22/malloc/blob/main/srcs/includes/ma...

This is not a real malloc(3),but this is better than the OP to understand the bases.

Yes, by all means, let's implement malloc(3) in a way it should never have been implemented after the VAX/11 architecture, and using much less readable code and worse examples than in the Old Testament ?

Hint: Storing the free-list in the free space means that to free even more memory, you have to page in otherwise unused VM pages.

[flagged]

Except, this seems to be no ordinary HN commenter. If I didn't know better, I'd say that the username seems to be that of Poul-Henning Kamp.

Yes, I am the author of that paper and the "phkmalloc" it describes.

glasses adjusting intensifies

Not sure how that changes anything lol. The point still stands that the original comment is needlessly rude.

There are systems that need a heap without virtual memory. "Naive" solutions can be perfectly suitable for them.

Nice to see this here. This article really helped me learn how memory allocation worked. I managed to implement my own thanks to it and a few other resources.

I used a doubly linked list of memory blocks. They are split into smaller blocks on allocation and merged with surrounding free blocks on deallocation.

If you are going to do it at this level, it already exists as an example (section 8.7) in K & R.

Super cool. I'm not a C programmer by any stretch, used to code C++ a lot a long time ago, I'm always in awe of the low level shenanigans going on in the bellows of C.

this blog desperately needs a “let’s write some css” post

For technical stuff I find those type of simple pages a lot more trustworthy.

Renders perfectly, readable and usable on Firefox Android.

Which browser are you using that makes this look bad?

Calloc sometimes doesn't really do this. I believe on some architectures (like Linux) it requests the page and sets a traps so that it only fills with zeros when you first access segments of the memory space. This winds up being much better for cache coherency if you're doing something that runs across the memory space.

(2014)

Reply on news.ycombinator.com