5 ms·
Let's Write a Malloc (2014)
- o11c 3y agoUnfortunately, 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/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
- yomritoyj 3y agoIf you are going to do it at this level, it already exists as an example (section 8.7) in K & R.
- throwawaymaths 3y agoCalloc 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.
- rich_sasha 3y agoSuper 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.
- pieterr 3y ago(2014)
- progbits 3y agoOne 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.
- phkamp 3y agoYes, 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. See also: https://papers.freebsd.org/1998/phk-malloc/ https://papers.freebsd.org/1998/phk-malloc/
- tourist2d 3y ago[flagged]
- mangamadaiyan 3y agoExcept, 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.
- phkamp 3y agoYes, I am the author of that paper and the "phkmalloc" it describes.
- calamari4065 3y agoglasses adjusting intensifies
- kasool 3y agoNot sure how that changes anything lol. The point still stands that the original comment is needlessly rude.
- kevin_thibedeau 3y agoThere are systems that need a heap without virtual memory. "Naive" solutions can be perfectly suitable for them.
- wscott 3y agoThere 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.
- 082349872349872 3y agoMaybe 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"?
- matheusmoreira 3y agoI always enjoy reading this article from time to time: https://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ 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!
- ranting-moth 3y agoCorrect. I also think that if the author would have said "minimum viable" or "baseline" in the title then all would have been forgiven.
- 3y ago
- oefrha 3y agoImplementing 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.
- jbn 3y agoHere's another one such assignment https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/resources/mit6_172f18hw6/ 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)
- speps 3y agoI'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 https://github.com/mattconte/tlsf
- gizmo 3y agoFor the algorithm used see https://github.com/jserv/tlsf-bsd https://github.com/jserv/tlsf-bsd
- mananaysiempre 3y agoIncidentally, it’s also what AssemblyScript uses: https://github.com/AssemblyScript/assemblyscript/blob/main/std/assembly/rt/tlsf.ts https://github.com/AssemblyScript/assemblyscript/blob/main/s...
- deleted 3y ago[deleted]
- matheusmoreira 3y agoNice 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.
- orwin 3y agoHere 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 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/malloc.h 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.
- ptero 3y agoIt 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_tutorial.pdf https://wiki-prog.infoprepa.epita.fr/images/0/04/Malloc_tuto... -- for example here; the link in the post is stale.
- 5cott0 3y agothis blog desperately needs a “let’s write some css” post
- rwaksmunski 3y agoFor technical stuff I find those type of simple pages a lot more trustworthy.
- gkbrk 3y agoRenders perfectly, readable and usable on Firefox Android. Which browser are you using that makes this look bad?