More info about the default allocator

Explain
1

I know it says “OS heap allocator” in the docs but I want to know more about it’s implementation. It’s thread safe, but is it lock free? Or does it use a mutex. Does it internally use a cache? Or does it allocate new virtual memory blocks each malloc call (unlikely). I only have a surface level understanding of this stuff so I was hoping someone could explain.

2

This depends on what you’re referring to.

  • @jasonKercher had a custom heap allocator for Linux in core:os which was removed back in August 2024 due to its incompleteness.
  • Currently in base:runtime, we actually do just use malloc for every allocation on POSIX-compatible platforms and HeapAlloc on Windows. There’s some padding that happens in the Odin allocator, but it’s largely just mallocing for every new/make.
  • I’m currently working on a lock-free dynamic heap allocator written in pure Odin, and I’m in the optimization phase.

I’m hoping to have the allocator done soon, but it has been a lot of work not only to get right (synchronization issues) but to make it faster than libc while also keeping it simple enough for maintenance.

To let you know where I am now, I’m considering an alternative design for the middle size class allocations (~8KiB..<1.5MiB), which is where the allocator is the slowest currently. It’s actually not uncommon for heap allocators to use completely different strategies for different size classes, so I thought it might work here too.

Depending on how this new strategy goes in testing and benchmarking, I’ll be able to give a more clear answer on the complete design of the allocator, but presently it requests 2MiB blocks from the OS and subdivides them into slab allocators based on power-of-two sizes relevant to the allocation requests made by the program. For the medium size allocations, it coalesces these slabs together to make room (this is the old strategy). For the largest class of allocations (>=1.5MiB) it requests virtual memory directly from the OS. That’s the quick overview.

Link: Add native lock-free dynamic heap allocator by Feoramund · Pull Request #4749 · odin-lang/Odin · GitHub

Let me know if you have any more questions.

7 Likes
3

That answers just about everything. It’s really cool that you are working on a replacement for the default allocator. Most people are going to just use that so it’s a pretty big value add. I wish you the best and thanks for answering my question.

3 Likes
4

I’m much closer to having the new heap allocator done. I pushed the rewrite to the PR, and there’s just a few items left to do.

2 Likes