HNHacker News
TopNewBestAskShowJobs

samwho

1,463 karma · joined June 25, 2011

I write interactive visualisations of programming topics at https://samwho.dev
submissionscomments
samwho··on Hashing
Ahh I see, the limitation you’re talking about is that there isn’t any inherent guarantee that a different seed will mean two values no longer collide? It’s just likely (in the case of murmur3 at least).
samwho··on Hashing
I did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt.

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.

samwho··on Hashing
Thank you! That puts to bed some of my anxieties around whether I’ve misrepresented the qualities of murmur3
samwho··on Hashing
Thank you! I'm really glad you liked it.
samwho··on Hashing
I'm actually not sure, to be honest. The post explicitly doesn't touch on the implementation of murmur3, and part of the reason is that while I can see what it's doing, I have no idea why it's doing it.

The initial announcement of murmur (https://tanjent.livejournal.com/756623.html) makes it seem like it's trial and error.

samwho··on Hashing
To be mentioned in the same breath as Bartosz Ciechanowski is an incredible compliment, thank you <3

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.

samwho··on Hashing
I didn't know that, but it makes perfect sense after reading your explanation of it. Thank you, TIL!
samwho··on Hashing
Thank you! I absolutely love making these, and have plans for several more.
samwho··on Hashing
Thank you <3
samwho··on Show HN: My recommendation engine for Hacker News
Aww, thank you for using my Memory Allocation post as the placeholder text. <3
samwho··on Memory Allocation
I went back and forth on this and decided in the end that it makes sense to use hex for 2 reasons:

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.

samwho··on Memory Allocation
You’re awesome.
samwho··on Memory Allocation
You can’t really have the interactivity with a book. I do wish you could.
samwho··on Memory Allocation
Good question! I’m not aware of one, but I also haven’t looked.

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.

samwho··on Memory Allocation
I’ve seen a few people doing it, seems to work well.
samwho··on Memory Allocation
You’d need cooperation between your malloc implementation and the application code. It’s possible, but tricky. If your malloc returned a pointer to a pointer, and promised to keep the first level pointer up to date, and was able to lock your application whenever it moved things around, it could work.

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.

samwho··on Memory Allocation
Deja vu. :D
samwho··on Memory Allocation
I have some bad news for you about books.
samwho··on Memory Allocation
Ahh yes, I'm with you now.

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.

samwho··on Memory Allocation
The blocks aren't HTML elements, they're drawn on to a canvas. It _could_ be possible regardless, though. I may revisit this. Thanks for the idea! :)
samwho··on Memory Allocation
Yes, this is one of the things I look back on as a weak point in the writing. I wanted to make this a lot more clear but by the time I'd gotten to this point in the article, I'd sort of coded myself into a corner with the visualisation code.

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/.

samwho··on Memory Allocation
Could you elaborate on what you mean?
samwho··on Memory Allocation
The accessibility of this technique is something that greatly worries me. I try and be quite thoughtful about things like colour palette. I'm not sure how to achieve the level of interactivity I want while still being accessible to screen readers, without writing two completely separate articles with and without JavaScript.

Definitely open to ideas.

samwho··on Memory Allocation
Don't tell Amos, but Cool Bear is the inspiration for Haskie, my little husky companion.
samwho··on Memory Allocation
The master of this artform.
samwho··on Memory Allocation
I'm sorry you're more confused than you were when you started!

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.

samwho··on Memory Allocation
You're absolutely right, I've corrected this. Thank you!

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

samwho··on Memory Allocation
I completely agree with you on this, though I couldn't find a great way to do it. It was suggested to me to put an outline around the allocation or free that just happened, but I struggled to get the box to look good when the allocation was split across 2 lines.

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.

samwho··on Memory Allocation
Thanks so much, I really appreciate it.

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.

samwho··on Memory Allocation
Nah, I just failed at basic arithmetic :D

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>
← PreviousPage 8 of 10Next →