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)).
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.
* 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.