8 ms·
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 li
by gpderetta 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.
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...
- gpderetta 6y agoso, what I have in mind is this. Let's assume in both cases the allocator is static. In the list case you have: 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 } } There is a single load in the critical path (loading the content of result); the additional load of result next and the store are not in the critical path as the result does not depend on them. Also loading the content of result->next will touch a cacheline that will be accessed very soon by the caller of alloc anyway. 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 */ } } In this case the chain b->c is in the critical path (a can be in parallel with b, and the sub has minimal latency); the store is not in the critical path. So as you can see there is an additional dereference. Also it will touch the additional cacheline pointed by data+sz. 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.
- deleted 6y ago[deleted]
- dragontamer 6y agoOkay, I had something wrong earlier, but I deleted my earlier, incorrect post. That's what I get for rushing and trying to do this in one go. I think I got it correct this time: 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; It'd be a stack, not a queue. So I changed the name to "stack" to better represent the strategy. stackLinkSize doesn't need to be part of the link structure. That's why the fast path is simply: return root->nodePtrs[stackLinkSize--]; This basically breaks down into: dereference(root + offsetOf(nodePtrs) + stackLinkSize * sizeof(Node)) Just one dereference, if I'm counting correctly. 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.
- imtringued 6y agowhen you're unrolling your linked lists you don't have to go that far. I'd say at least 128 elements and 1024 elements at most. To be fair, this is just based on intuition.