Hacker News Reader

Comment by jiggawatts | Hacker News Reader

Every time I hear someone talking about writing a memory allocator, it always reminds me of the brilliant CppCon 2015 talk by Andrei Alexandrescu about how he wrote an modular allocator library that can be built up in pieces to make whatever you like.

https://www.youtube.com/watch?v=LIb3L4vKZ7U

View on HN

I also really like John Lakos' talks on allocators. He does a great job of systematically decomposing the problem space.

The only problem is that he is wrong on almost every detail. He has apparently never heard of mmap, which is awkward because mmap is how memory is obtained, nowadays.

And if you want, you know, performance, it needs to know something about threads, pre-allocating chunks to assign to threads, and batching free ops per thread.

Most of what you can find about writing allocators is written by people who don't actually know how; and actually useful allocators are made by people who don't write tutorials about it.

Thread-based allocators are a bit overrated. In apps it’s quite common for objects to migrate across threads, especially from workers to the main thread.

That's not the point at all. Having a per-thread pool means synchronization-free alloc.

What happens with the object afterwards is not relevant.

But objects are passed around between threads and another thread might want to free it?

Then it goes to the freeing thread memory pool. Thread-aware mallocs know this and have clever balancing mechanisms for situations like producer-consumer, where one thread allocs a lot and another frees a lot.

Edit: wrong, I re-checked. The solution to this is that marking an object as free is lock-free. The freed objects do not immediately change thread pools.

What is he wrong about? He's upfront about limiting the scope to single-threaded arena allocators, but still mentions mmap and threads in passing. For talks that are mostly sales pitches, I think it's a pretty informative introduction to how to select and compare allocators.

Can you explain what you mean by mmap is how memory is obtained nowadays?

mmap is not only to map a file content into a process address space, it can also be used to request memory from the OS using the MAP_ANONYMOUS flag. Early on a malloc-like allocator would use brk/sbrk to get a chunk of "raw" memory, and manage this for the user providing access using malloc/free. Nowadays the same "raw" memory can be obtained using an anonymous map. A raw pool, when unused, can be returned to the OS by unmapping it.

Using an anonymous map provides address space randomization by default (for the raw pool location), whereas brk/sbrk extends a limit and because of this are predictable.

sbrk is emulated via mmap today on MacOS and others, this is an abstraction (for bump allocation), not just a function

you may implement custom sbrk via mmap easily

sbrk isn't even supported on some platforms anymore, if I'm not mistaken

It’s a great talk, but something I would watch after learning how to implement a malloc as it talks about other kinds of allocators and how to make them composable rather than say “how would I encode a freelist”.

His implementation of it can be found in the D programming languages standard library.

You can build a jemalloc in about 10 lines roughly.

Reply on news.ycombinator.com