3 ms·
Even if the list were fully cached in L1, traversing an array can be significantly faster as the CPU can extract a lot of parallelism. On the other hand a list
by gpderetta 10y ago
Even if the list were fully cached in L1, traversing an array can be significantly faster as the CPU can extract a lot of parallelism. On the other hand a list is a long dependency chain of non trivial latency instructions.
Linked lists (and other node-based data structures) of course shine for modification heavy work, when traversal is uncommon or when you need to preserve addresses.