1,463 karma · joined June 25, 2011
I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding and what it’s there to prevent. I’m hoping that comes across, even without any deeper exploration of seeding.
The initial announcement of murmur (https://tanjent.livejournal.com/756623.html) makes it seem like it's trial and error.
I will say up front: my posts don't read well in an RSS reader. Sorry about that. But at least you'll get a notification when new ones come out.
1. It's what people are going to be exposed to in any material outside of this post. 2. Within this post, it helps distinguish between pointers and sizes/values.
Most of the research for this post was done by reading papers for various malloc implementations (phkmalloc, dlmalloc, tcmalloc, mimalloc) and reading their source code.
Someone else already mentioned, but garbage collected languages do actually do this. Because they’re fully in control of memory (the language exposes no raw pointers), they’re able to create the layer of indirection you’ve suggested and move things around as they please. I know at minimum the JVM does this. The term to search for is “heap compaction.”
There’s also the weird and wonderful work of Emery Berger et al with their “Mesh” malloc implementation, which blows my mind: https://youtu.be/XRAP3lBivYM.
I made a deliberate choice to not include that, mostly due to post size/complexity reasons. I decided that the focus of the piece was going to be on the task of effectively managing the memory you have in the face of calls to malloc/free. I decided against talking about any environment-specific information (brk, mmap, cache locality, multithreading, etc.)
May not have been the right call, but it kept the length fairly reasonable and I think it gives people enough of a nudge to dip their toes into the playground if they have time.
If you check the HTML comments on the page you'll find quite a lot of cut content. I wanted to do deep dives on real-world malloc implementations, but it ended up being very difficult to cover without making the post take over an hour to read.
In another universe I'd hook in to the page scroll and highlight each block being referred to as I talk about it in the text. I'm probably not explaining that well here, but imagine something like the way this article works: https://pudding.cool/2017/05/song-repetition/.
Definitely open to ideas.
The post is intending to talk about the topic of memory allocation in a general sense. The way that malloc works on any given system is implementation dependent, it's not possible to say "malloc works in this way" because Debian can differ from Arch can differ from BSD, etc.
It's not my goal to tell you exactly how modern malloc/free implementations work. I could probably be more clear about this at the start of the post.
I had originally written about threading and locality but it made the post too long and complicated, so I cut it out for the final draft. You can see remnants of it if you check the HTML comments in the post :D
I've started writing my next post and have learnt a bit more about PixiJS/GSAP3, and think I know a way to do it that would work nicely but would require changing some of the underlying code. I can't promise I'll revisit this soon, but I would like to in future.
I'm glad you like the playground. If you don't mind me asking, what/where/how do you teach? I was actually hoping to get the attention of educators with this tool to see if it would make sense in, e.g., undergrad CS courses.
I wrote this:
<div class="memory" bytes="32">
<malloc size="4" addr="0x0"></malloc>
<malloc size="5" addr="0x4"></malloc>
<malloc size="6" addr="0x9"></malloc>
<malloc size="7" addr="0xa"></malloc>
<free addr="0x0"></free>
<free addr="0x4"></free>
<free addr="0x9"></free>
<free addr="0xa"></free>
</div>
Instead of this: <div class="memory" bytes="32">
<malloc size="4" addr="0x0"></malloc>
<malloc size="5" addr="0x4"></malloc>
<malloc size="6" addr="0x9"></malloc>
<malloc size="7" addr="0xf"></malloc>
<free addr="0x0"></free>
<free addr="0x4"></free>
<free addr="0x9"></free>
<free addr="0xf"></free>
</div>