3 ms·

One of these things is not like the others. Slabs and bump/arena allocators have significant advantages over just using the system allocator. You use them in a

One of these things is not like the others. Slabs and bump/arena allocators have significant advantages over just using the system allocator. You use them in a constrained way which allows for a more efficient implementation—slabs by having only one size of allocation and bump/arena by freeing things all at once (or maybe in LIFO order if you're fancy). Thus, they make sense in a lot of performance-oriented programs. A buddy allocator has no such constraints. It's general-purpose. Thus, there's no obvious opportunity to do better than the system allocator. And it's pretty wasteful if your allocations aren't close to sizes of 2 (internal fragmentation => wasted RAM and cache). If you have a system allocator available that uses say size classes instead, I have no idea why you'd prefer to use a buddy allocator. For that matter, if your system allocator is a buddy allocator (or more likely: some kind of hybrid), I have no idea why you'd prefer your own implementation. One constraint might be that you promise your buddy allocator's usage is single-threaded, and thus no locking is necessary. But a production-quality system allocator likely uses thread-local or CPU-local caches to accomplish much the same thing, so I don't think this constraint buys you much efficiency. If you're implementing a bare-metal system on a microcontroller and need a very small memory allocator implementation for light usage, implementing your own buddy allocator might make sense. But that's a lot of caveats...

nitrogen 6y ago
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.
dragontamer 6y ago
Thread safety, or the lack of it. The system-allocator needs to be thread-safe in a large variety of situations. Your custom allocator doesn't have to be: maybe you know only 1 thread is running. Heck, even knowing that only 32-threads or 64-threads will ever run can make gross simplifications to the synchronization code. System-allocator needs to be thread-safe with an unbounded number of threads (because you may call pthread_create at any time). Your custom allocator may know more specifics about when, and where, pthreads are created, as well as whether or not they interact with each other. --------- Case in point: lets say you malloc a 256MB region per thread. You know that only one thread would ever access this 256MB region, so you write it without any synchronization primitives what so ever. But you still want a general purpose, multi-size supported allocator to split up the data inside the 256MB region. You call void* fooptr = malloc(256MB), because grabbing from the system allocator should remain thread-safe (who knows how many other threads are calling malloc?). But afterwards, you can make very specific assumptions about the access patterns of that fooptr.
- scottlamb 6y ago
  Given that the system allocator likely has a thread-local or CPU-local cache, does that constraint really make things noticeably more efficient? It simplifies your implementation, sure, but the system allocator already exists, and one implementation is simpler than two...
  - dragontamer 6y ago
    Hmm... my multithreaded strategy typically uses task-based parallelism with a thread-pool. In particular: #pragma omp task Those omp-tasks can "float" between threads, depending on your implementation. If some task enters a blocking situation (usually a task-barrier), it could switch to another pthread during the implementation. Ex: Task A is running on Hardware-Thread#10. Task A mallocs something from Thread#10's local malloc. Task A calls barrier, which means Thread#10 "gives up Task A" back to the work queue. Later, all tasks hit the barrier, and Task A can run again. But which threads run TaskA is left up to the runtime. Thread#25 might be running the task now. At this point, Thread#25 calls free(fooptr), but it now has to be a global-synchronization, since the data came from Thread#10's pool. ---------- Its probably not safe to assume thread-local storage to be sufficient for task-based parallelism.

nitrogen 6y ago

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.

dragontamer 6y ago

Thread safety, or the lack of it. The system-allocator needs to be thread-safe in a large variety of situations. Your custom allocator doesn't have to be: maybe you know only 1 thread is running. Heck, even knowing that only 32-threads or 64-threads will ever run can make gross simplifications to the synchronization code. System-allocator needs to be thread-safe with an unbounded number of threads (because you may call pthread_create at any time). Your custom allocator may know more specifics about when, and where, pthreads are created, as well as whether or not they interact with each other. --------- Case in point: lets say you malloc a 256MB region per thread. You know that only one thread would ever access this 256MB region, so you write it without any synchronization primitives what so ever. But you still want a general purpose, multi-size supported allocator to split up the data inside the 256MB region. You call void* fooptr = malloc(256MB), because grabbing from the system allocator should remain thread-safe (who knows how many other threads are calling malloc?). But afterwards, you can make very specific assumptions about the access patterns of that fooptr.

scottlamb 6y ago
Given that the system allocator likely has a thread-local or CPU-local cache, does that constraint really make things noticeably more efficient? It simplifies your implementation, sure, but the system allocator already exists, and one implementation is simpler than two...
- dragontamer 6y ago
  Hmm... my multithreaded strategy typically uses task-based parallelism with a thread-pool. In particular: #pragma omp task Those omp-tasks can "float" between threads, depending on your implementation. If some task enters a blocking situation (usually a task-barrier), it could switch to another pthread during the implementation. Ex: Task A is running on Hardware-Thread#10. Task A mallocs something from Thread#10's local malloc. Task A calls barrier, which means Thread#10 "gives up Task A" back to the work queue. Later, all tasks hit the barrier, and Task A can run again. But which threads run TaskA is left up to the runtime. Thread#25 might be running the task now. At this point, Thread#25 calls free(fooptr), but it now has to be a global-synchronization, since the data came from Thread#10's pool. ---------- Its probably not safe to assume thread-local storage to be sufficient for task-based parallelism.