3 ms·

A buddy allocator has no such constraints. It's general-purpose. Thus, there's no obvious opportunity to do better than the system allocator. The system alloca

A buddy allocator has no such constraints. It's general-purpose. Thus, there's no obvious opportunity to do better than the system allocator. The system allocator isn't guaranteed to be optimal for your workload. Way back in college one of the assignments was to write a custom allocator. The fastest allocator got extra credit. Our school lab was running Linux on SGIs with AMD Opteron CPUs. The native malloc would get 3000 allocs per second in the grading program's benchmark. I managed to top 10000/s with a buddy list allocator with coalescing, if I recall correctly. One of the weird things was that replacing all structs with pointer arithmetic (managed by preprocessor macros) gave a pretty big boost in speed. I didn't dig too much into the assembly because it was already more than fast enough.

scottlamb 6y ago
I think the system allocator on most platforms is a lot better now than it was then, and if it's not, you can swap in jemalloc easily. I'd recommend this over implementing your own buddy allocator.
- nitrogen 6y ago
  For sure, writing your own allocator is the last thing you reach for after all else fails. I've never needed to do so in practice. My allocator was fast because it had no thread safety, no debugging features, raw pointer arithmetic (hard to read code), and no/optional error checking.
  - 59nadir 6y ago
    > For sure, writing your own allocator is the last thing you reach for after all else fails. Writing your own general purpose allocator might be the last thing, but custom allocators for well-understood limited/localized behavior is both trivial and something one should do even for simplification in many cases. Freeing an entire arena/resetting an allocation pointer is both much faster and simpler than `malloc`/`new` & `free`/`delete`. People often misunderstand "custom allocators" to mean "making your own `jemalloc`" and it feels like your comment runs the risk of fueling that fire. Creating your own `jemalloc` is both wasteful in that `jemalloc` performs worse than even the most simple of custom allocators and a waste of your time in that general purpose allocators already exist so if you need something like that you probably can save your time for something else.

scottlamb 6y ago

I think the system allocator on most platforms is a lot better now than it was then, and if it's not, you can swap in jemalloc easily. I'd recommend this over implementing your own buddy allocator.

nitrogen 6y ago
For sure, writing your own allocator is the last thing you reach for after all else fails. I've never needed to do so in practice. My allocator was fast because it had no thread safety, no debugging features, raw pointer arithmetic (hard to read code), and no/optional error checking.
- 59nadir 6y ago
  > For sure, writing your own allocator is the last thing you reach for after all else fails. Writing your own general purpose allocator might be the last thing, but custom allocators for well-understood limited/localized behavior is both trivial and something one should do even for simplification in many cases. Freeing an entire arena/resetting an allocation pointer is both much faster and simpler than `malloc`/`new` & `free`/`delete`. People often misunderstand "custom allocators" to mean "making your own `jemalloc`" and it feels like your comment runs the risk of fueling that fire. Creating your own `jemalloc` is both wasteful in that `jemalloc` performs worse than even the most simple of custom allocators and a waste of your time in that general purpose allocators already exist so if you need something like that you probably can save your time for something else.