Custom Allocators Demystified
slembcke.github.io
slembcke.github.io
> Over the years, I’ve wasted many hours debugging memory issues. With just a hash table and a set of linked lists, you can track the history of all your allocations. That makes it pretty easy to track down use after free errors, double free errors, and memory leaks. Using guard pages around your allocations, you can detect overflows.
No, just use address sanitizer–it's meant for this. Odds are your custom allocator might have a few bugs in itself and they will make you life more annoying if you're trying to use it for only this.
j/k, though I've fixed memory bugs, overflow, use after free, etc. written by people much smarter than me. without static analyzers, valgrind, and afl its possible that some would still exist nearly a decade later.
Also, any custom C++ allocator is going to contain a bunch of unsafe code too.
It's true that a C++ custom allocator will have lots of "unsafe" code, but this is really where C++ shines. The tooling is more complete, the aliasing rules are better documented and understood, the language fights you less, the stdlib has explicit support, it is easier to control the codegen. Rust cannot bring its strengths to bear on this sort of problem.
http://btorpey.github.io/blog/2014/03/27/using-clangs-addres...
Article mentions JVM noise, but my actual experience is with python noise. Good riddance; this is going into my CI test suite today.
In fairness, the next sentence in the post is:
> Techniques like this can be a nice complement to external tools like Valgrind or AddressSanitizer.
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...
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.
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.
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.
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.
I don't think this is true. As I understand it, it just gets put into Thread#25's pool rather than returned to Thread#10s. If there's a long-running imbalance—like a producer-consumer pattern in which all the mallocs are from Thread#10 and all the frees are from Thread#25—that will lead to more global synchronization because the allocator will have to repeatedly refill Thread#10's pool and empty Thread#25's pool. But if it's just that there's some shuffling of threads between the allocations and frees but stuff is generally balanced, there's little if any additional cost.
I think you're suggesting using a set of "task-local" custom allocators, and each of those can ignore threads? I suppose that would work, as each task is only on one thread at once, and there has to be a barrier anyway when it hops from thread to thread. But I'm skeptical it's faster than the system allocator. I'd love
0. Garbage Collection: Reference Counting -- C++, Python, Rust. Reference counting augments any of the allocators discussed in the blogpost with a simple garbage-collection scheme.
1. Garbage Collection: Stop and Copy -- This is the easiest garbage collection to implement. This is closely related to the Linear-Allocator, except "free" compiles into a nop. Only "new" matters. When "new" runs out of space (which it will inevitably do), you scan the entire memory space, and copy all "current live objects" to the 2nd heap. (An identically sized heap).
Stop and copy uses up 50% of the space (If you have 32GB available, you can only have 2x16GB heaps, and can only use up to 16GBs total). Still, the gross simplicity of stop-and-copy is cool.
2. Garbage Collection -- Mark and Sweep: is a bit complicated in my experience. It works well in practice, but its harder to program (especially if you want to do it efficiently, with tri-color invariants and all that).
--------
Because of the gross simplicity of alloc() in stop-and-copy, it can be very fast in some use cases! If you can't figure out how to make free() work with linear allocators, just stop-and-copy the darn thing.
-------
Garbage collection is reserved for when your links start to point to each other in ways far more complicated thank linked lists.
If you have cycles in your linked lists ... or your linked lists act like cons pairs (aka: car / cdr) from Lisp, garbage collection is basically almost inevitable. There's no real way to know when to delete a pointer safely if you're using Lisp-style car/cdr pairs. Even reference counting is bad, because cycles are pretty common in that style of programming.
1. A "pop-to" operation. If you're ready to free ALL memory allocated at or after allocation X, you can do this by moving the start-of-free-space pointer back to the start of allocation X.
2. An end-of-free-space pointer, with its own push and pop-to operations.
In combination, these are often enough to get maximum value out of a fixed-size memory workspace. A function can allocate all returned data structures on one side of the workspace, and use the other side of the workspace for all temporary allocations. This approach does require tight coupling so there are a lot of settings where it clearly doesn't belong, but I've found it to be very effective for high-performance scientific code.
The main drawback I find is that you can't use some generic data structure implementations that expect to be able to free memory out of order, unless you're fine with leaking before the final cleanup (if integrated into a generic allocator interface, the "free" method will probably be a no-op). For example, maybe you need a temporary hashmap to help with parsing a text file. It can be interesting to come up with implementations that work without freeing out of order.
Of course, you can always opt to use another, more general purpose allocator, on a block of memory retrieved from the hunk (see Quake's "zones").
[0] https://github.com/id-Software/Quake/blob/master/WinQuake/zo...
> The trick is to use the allocations themselves as linked list nodes so you don’t have to waste any extra memory for tracking.
There was an article that I'm struggling to find—posted to hn iirc—recommending against this approach. IIRC there were two reasons stated:
* Efficiency due to CPU cache. Freed allocations might have been unused for a long time and thus out of cache. Writing the pointer to the linked list on free puts it back into cache—a whole cache line when you only need 8 bytes or whatever for the singly-linked list—possibly at the expense of something hotter. (I think there are special instructions on many platforms to store without adding to cache, but that's probably not wise either because a bunch of frees might come together and thus need to access a previous one's book-keeping info. Better to keep all the bookkeeping info together in a dense region so you use more of the cache line.)
* Debugging troubles on buggy applications. They're more likely to overwrite adjacent allocations and thus the memory allocator's book-keeping, resulting in hard-to-debug failures. (I recall not being super convinced of this reason—I think having external tracking is insufficient for making it easy to debug this kind of error. I think you'd want to make it possible for ASAN to work well, thus you'd want to implement its "manual poisoning" interface.)
edit: I found this tcmalloc issue talking about not wanting to use singly-linked lists because of cache effects when moving stuff from the thread cache to the central list. Kind of similar. https://github.com/gperftools/gperftools/issues/951
* Fixed size allocator
If you don't need multiple sizes (like malloc(size)), then a fixed-size allocator is significantly simpler to implement, to the point of absurdity.
Step 1: Put all valid memory locations into a stack.
Step 2: alloc with stack.pop();
Step 3: free with stack.push();
The end. You get memory locality, cache-friendliness, O(1) operations, zero external fragmentation. The works. Bonus points: stack.push() and stack.pop() can be implemented with SIMD with help of stream-compaction (http://www.cse.chalmers.se/~uffe/streamcompaction.pdf), and can therefore serve as a GPU-malloc as long as one-size is sufficient.
--------------
The only downsize of "fixed size" allocation is the significant amount of internal fragmentation per node. (Ex: if you only use 8-bytes per node, your 64-byte reservation is mostly wasted). But if you're making a custom-allocator, fixed-size is probably one of the easiest to implement in practice.
-------------
You can extend this to multithreaded operations by simply using atomic-swap, atomic-and, and atomic-or across a shared bitset between threads. 1-bit per fixed-size block. (bit == 1 means something has been alloc(). bit == 0 means something is free()). The stack.push() and stack.pop() operations can run thread-local.
I recommend 64-bytes or 128-bytes as your "fixed size", because 64-bytes is the smallest you get before false-sharing becomes a thing.
---------
If you have a fixed-size allocator but need items to extend beyond a fixed-size array, then learn to use linked lists.
In the case of "fixed-size" allocations, you support all "smaller sizes" by returning a large size. Ex: malloc(4) returns a 64-byte block. malloc(20) returns a 64-byte block. malloc(64) returns a 64-byte block. malloc(65) causes assert( size < 64) fails, and your program exits.
malloc(65) would probably create a "new slab", supporting 128-byte blocks under a slab allocator. At least, based on how I normally hear the term used. malloc(34) may return a 64-byte block, but malloc(31) may return 32-byte block (supporting true sizes as power-of-2).
-------------
The "slab allocator" discussed in the blogpost seems to be a fixed-size slab allocator though. So the blogpost's terminology doesn't match my own.
Edit: ... which is what is described in the article which most definitely I had read when I originally made this comment!
Given the higher latency on linked lists, and the relative simplicity of calculating the stack-size needed, it doesn't seem like going through the linked-list traversal is the best plan to me.
If you repeatedly need extra space for "additional slabs", I suggest an unrolled linked list (https://en.wikipedia.org/wiki/Unrolled_linked_list). Each 1MB slab with 64B blocks gets associated with a new std::array<void*, 16384>. This keeps the relative simplicity of a linked list (O(1) push / pop operations), while keeping the cache-friendliness of a normal array.
And yes, of course you would allocate your nodes from a linear contiguous (but possibly chunked) fix size bump allocator first.
if(this->size >= 0){
return lastLinkedSlab[this->size--];
} else {
auto old = lastLinkedSlab;
lastLinkedSlab = lastLinkedSlab->next;
delete old;
if(lastLinkedSlab == nullptr){
lastLinkedSlab = new LinkedSlab();
}
this->size = 16384 - 1;
return lastLinkedSlab->heap[this->size--];
}
> And yes, of course you would allocate your nodes from a linear contiguous (but possibly chunked) fix size bump allocator first.
Hmm, that's probably a bit more efficient, but probably not a big deal because its a "once ever" optimization. You usually want an optimization to loop over itself a few times...
struct node { node* next; };
static node * root;
void * alloc() {
node * result = root; // 1 load
if (result) { // fast path
root = result->next; // 1 load + 1 store
return result;
} else {
//slow path
}
}
In the queue case you have:
struct queue { void ** data; int size; }
static queue q;
void * alloc() {
int sz = q.size -1; // 1 ld [a] + 1 sub
if (sz >= 0) { // fast path
size = sz; // 1 store
void ** data = q.data; // 1 ld [b]
return data[sz]; // 1 ld [c]
} else { /* slow path */ }
}
If you are doing many allocations in a very tight loop, then the store in the linked list example suddenly becomes part of the critical path and can become a problem, while the compiler can extract some parallelism from the size computation in the queue example. If that scenario is important for you then the queue can be preferable.
struct Node{
char rep[64]; // 64-bytes per node
};
struct StackLink {
struct StackLink* prev;
Node* nodePtrs[4096];
};
static StackLink* last; // Points to nullptr when empty
static int stackLinkSize;
return root->nodePtrs[stackLinkSize--];
dereference(root + offsetOf(nodePtrs) + stackLinkSize * sizeof(Node))
I think I agree with you that "size" is dereferenced (for dereference #2), but since its "Hot" I don't think it would be the bottleneck for anything. L1 references are very fast.
The stack case will touch three cachelines (root, nodeptrs and the final block). The linked list only two (there is no nodeptrs).
TBH it would be very hard to design a nonncompletely artificial benchmark were une desig make a difference compared to the other. Only way is test on an actual application and check what fits best.
I think I can agree to that.
I should note that I designed this allocator to be used on the GPU. "Size" is shared between a wavefront / SIMD unit. popcnt(exec_mask) determines how many items to alloc at a time. (if 200 threads call alloc, then they will collectively grab 200 pointers all at once, by doing size -= popcount(exec_mask)).
Then discovered mimalloc, which hooks at low-level malloc/free, and at the same time a coworker also did similar job and now I'm no longer in love with "pmr".
I wish it was success story, but it's not. It probably is, if everyone is on board with it. But hardly this was my case. Also libraries are not - Qt is not, and many others.
pmr is great for things like - try to alloc on the stack, and if not enough continue with heap (under the hood), but the extra 8 bytes, and the fact that do_alloc is virtual call is problem (last one maybe not perf enough, but still hard to sell to performance oriented programmers).
I wish it was designed in way where it could've been sold as such.
If you want to use jemalloc everywere, just create your own (stateless) allocator wrapper and instantiate your string with it.
In fact you probably don't even need to do that. Doesnt jemalloc provide a dll interposer mode that transparently replaces malloc/free?
For tiny platforms often it's bare-metal so there's only one running "process" and so something like "malloc" that needs to be aware of memory usage across the system isn't relevant. Moreover, embedded systems tend to care about deterministic performance so an allocator specific to the application can be a better match.
Fans of Java may rightly point out that garbage collection also has this property, but GC brings other costs. Nothing in Java even remotely approximates the performance of an STL container backed by an arena allocator.
The simplest and fastest allocator you could possibly write is something where malloc just increments a pointer into a chunk of memory, and free is a no-op. This is obviously terrible as your system-wide allocator, but you can allocate an arena from the system malloc, then use the simple allocator to chunk out that arena. This is useful for example if you know that a web request has a reasonable upper bound on memory usage. You just allocate that much memory from the system at the start of the request, use the increment allocator for all request-bound objects, then release the arena at the end of the request. One single call to the system's somewhat heavy malloc/free, many calls to a trivially simple malloc and a no-op free.
Other languages don't so much "get away with it" as they're simply not used for workloads where it matters.
For tiny platforms like micro controllers used all over your car, standard practice is to never use dynamic memory allocation. When you have 1K or even 64K of RAM and need to run for a while the only way to be sure you never run out of memory is not to use malloc at all. Fragmentation is a thing. This may mean managing fixed collections of objects much like the allocators in the article, but the linker figures out where to put them at compile time.
This can also give you better control over cache locality of memory.
Custom allocators are important when memory performance is relevant. Allocation/deallocation is really slow compared to using memory which is already allocated to a program, so this can often be one of the biggest performance syncs in a program, especially one which churns through a lot of data (e.g. videogames, simulation, ML training etc.)
Custom allocators can also help with memory coherency: you can pack objects you're using together close together in memory, which minimizes the amount of CPU cache misses, which can also be one of the most expensive parts of execution. It may be difficult or impossible for a compiler to design a more optimal memory layout than a programmer with knowlege of how the program will use the data.
> And how do other languages get away with it?
Custom allocators are most relevant in performance-critical contexts, so you're probably already using C++ because a higher-level language was already too slow for your use-case. In other words, other languages pay the same cost for memory management, but if you're programming in Python you're probably working in a domain where the performance difference doesn't matter.
Even programs written in a "fast" GC'd language like GO will have a performance ceiling largely dictated by memory churn.
They either bring similar mechanisms, bring a selection of their own allocators that covers enough space or just don't allow influencing it much and get away with it because many applications/users do not care.
General purpose allocators are (basically) never the best for speed, fragmentation, and so on. They can at most be good enough. Basic knowledge about how your memory is going to be used that'll inform the use of a few simple custom allocators is likely to give you several times the performance that you'd see with a general purpose allocator. In the best case you'll literally reset an allocation pointer once per loop and just overwrite memory that you know isn't used anymore, for example, making allocation a write into an already existing buffer and "free" the resetting of the pointer. This has nothing to do with platforms, but rather is just basic removal of dumb code that shouldn't be running. There's zero reason a an actual `free`/`delete` should be used in those cases and using it is likely to slow down that loop considerably.
> And how do other languages get away with it?
Much like general purpose allocators are never the best, there is zero evidence to suggest that garbage collection is ever the optimal choice; it can only ever be good enough. There's also a lot of lore around garbage collectors being magic and doing lots of great things for you to ensure less fragmentation and nice cache locality but people are usually just amazed at how it's "not that bad" in the end.
There's no silver bullet: Garbage collectors and general purpose allocators aren't magic pieces of code written by developers who can conjure up the best code for every use case. Like most general code they're "not bad" at everything but not actually very good at anything. Running less code for your allocation and eliminating things based on your knowledge of how things are going to be used is always going to be better.
They don't get away with it. They suffer the consequences of bad performance. Of course depending on your metric they are "faster" in some situations that are common to that language but C++ often lets you avoid temporary heap allocations by using the stack which further increases performance.
He and others made these principles manifest in Dlang's std.experimental.allocator [0] which offers composability and is really quite nice, allowing for you to use Dlang's GC, malloc, custom malloc, various strategies for metering out the allocated blocks, and any combination thereof.
The documentation can be hard to navigate and it is easy to miss the submodules listed in the tree on the left hand side, so I would especially draw attention to `building blocks` [1] and `mallocator`, `gc_allocator`, etc.
[0] https://dlang.org/phobos/std_experimental_allocator.html [1] https://dlang.org/phobos/std_experimental_allocator_building...
I might bring it up on the forum later.
- C is "write once, compile everywhere, run everywhere"
- Java is "write once, compile once, run everywhere"
- Java is "write once, partially compile once, finish compiling everywhere, run everywhere"
?
I'm starting to think the biggest selling point for Java and dotNET platforms is, not platform-independence, but code obfuscation.
In mid-1990s closed source was big, and Java provided a platform to obfuscate the code before shipment, while retaining the advantages of hardware-specific code-gen (final phase of a compiler), to make it harder for the user to copy the ideas.
These days open source is king, no need to obfuscate, and a reason C is making a comeback of sorts.
I wouldn't agree for that in the case of .NET Framework.
On one hand, the safety of both languages does make it easier for obfuscators to pull certain tricks i.e. swapping out direct calls for Delegates (memory safe pointers for those unfamiliar with .NET terms) or throwing a bunch of indirect method calls, etc etc because in most cases object lifetime is something you don't think about in LOB .NET.
On the other hand, the problem is that almost any IL can be pulled back into a representation that may not be -fully- comprehensible, but again there are tools to even help with that b/c the C# language spec is well defined enough you know what you need to strip that isn't truly needed for a decompile.
Java/C# got big because of (1) hype, (2) somewhat-filled promises of xplat, (3) somewhat filled promises of better productivity because you don't have to think about most object lifetimes.
We're seeing a shift back to Go/C/Rust/Etc because people are realizing as data grows that a lot of their C#/Java code suddenly isn't so great at huge scale when a GC is churning all the time.
Both C# and Java are working on this in their own way of course; Java is doing a lot of work on their GC, .NET is doing a lot of work to make sure that their IO pipelines for things like sockets are better handled; after that it's up to the dev to decide if they want to go struct-happy.
If you want to obfuscate your codebase then write your software in Delphi. The native code it outputs will drive any reverse engineer insane even though there was no attempt at obfuscation...