4 ms·
One more allocator to mention: * Fixed size allocator If you don't need multiple sizes (like malloc(size)), then a fixed-size allocator is significantly simpl
by dragontamer 6y ago
One more allocator to mention:
* 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 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.
- hinkley 6y agoIsn't this a variant/degenerate case of slab allocation?
- dragontamer 6y agoHmmm... I'm pretty sure that when I hear "slab allocation", I imagine multiple sizes supported. 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.
- gpderetta 6y agoWell, if your stack is using a dynamic array as backing store, push is only amortized O(1). You can simply chain all all freed blocks in a singly linked free list without using additional space. Edit: ... which is what is described in the article which most definitely I had read when I originally made this comment!
- dragontamer 6y ago> Well, if your stack is using a dynamic array as backing store, push is only amortized O(1). You can simply chain all all freed blocks in a singly linked free list without using additional space. 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 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.
- gpderetta 6y agoIn this case the linked list will actually be lower latency, as you'll only be touching two locations: the root and the node itself while with the queue you'll have an additional hop through it. And yes, of course you would allocate your nodes from a linear contiguous (but possibly chunked) fix size bump allocator first.
- dragontamer 6y agoI'm just making this up as I go, but I'm only seeing 1x pointer dereference in the hot-loop (the "if-side" of the following if statement. The "else-side" is more complex, but not really bad) 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--]; } Or something like that. I'm not really seeing how this scheme incurs many indirect pointer references. > 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...