4 ms·
This works because we've arranged for the nodes to be sequential in memory, if we have the luxury of doing that then we could use an array instead of a linked l
by kardos 5y ago
This works because we've arranged for the nodes to be sequential in memory, if we have the luxury of doing that then we could use an array instead of a linked list. Is there a scenario where this value speculation trick would work, where we /don't/ have this luxury?
- twoodfin 5y agoGiven the nature of branch prediction, I’d expect it would still help dramatically in the case where the list was almost entirely sequential, which seems a bit more plausible.
- kardos 5y agoAgree; if a mispredict costs 15-20 cycles and a predict saves 4 cycles, does that mean we break even around 1/4-1/3 sequential?
- munchbunny 5y agoI could imagine behaviors like this happening with object pools, though it does still feel a bit contrived.