3 ms·
As with any such subject, it's worth discussing the details but probably not the generalities really (except perhaps in the whimsical style of antirez). You're
by couchand 4y ago
As with any such subject, it's worth discussing the details but probably not the generalities really (except perhaps in the whimsical style of antirez).
You're right to point out that given the performance characteristics of most modern CPUs, accessing memory linerally is optimum. But it doesn't necessarily follow that all collection data structures should be stored as a vector. Consider a collection traversed very slowly relative to the overall computation. There may not be any cache win if the line's always evicted by the time you come back to it.
- fiddlerwoaroof 4y agoI’ve always wondered about whether you could have your cake and eat it too with linked lists where nodes are allocated in contiguous blocks of N nodes. So, the normal case of traversing the next pointer is not a discontinuous memory access.
- tsimionescu 4y agoThat's quite likely to happen to a linked list when using a compacting GC (such as Java's or C#'s generational garbage collectors) (assuming the elements of the list are only reachable from the preceding element, not from many other places as well).
- fiddlerwoaroof 4y agoThat depends on the GC’s traversal strategy, I think. If you assume that linked lists are implemented as in lisps (a pair of pointers), then if you traverse the head pointer before the tail pointer, the compacting GC will tend to spread the linked list out over time.