2 ms·
I believe it corresponds to the traditionally learnt O(n) lookup, O(1) insertion/deletion of linked lists, whereas the reverse is true of arrays (having to move
by kaba0 4y ago
I believe it corresponds to the traditionally learnt O(n) lookup, O(1) insertion/deletion of linked lists, whereas the reverse is true of arrays (having to move the items).
Though in practice I find that unless you are often deleting elements from the middle, modern CPUs will really prefer copying a huge amount of serial data, so an arraylist may still be faster all around then LinkedLists. (The CPU will recognize you moving values in a given direction and will have the best pipeline it can have)
- PaulHoule 4y agoMost of the time that is right. In fact, there was a revolution in how people write query processing systems in the 2010s where people realized that the performance of a processing pipeline that reads columnar data structures straight through is amazing, particularly if you can use SIMD instructions. On the other hand, pointer chasing often isn't as bad as you think it might be. That is, modern allocator/garbage collectors often end up laying out the parts of a linked list in a predictable way such that access is somewhat strided and the fetcher is reasonably efficient at traversing the list.
- kllrnohj 4y ago> On the other hand, pointer chasing often isn't as bad as you think it might be. It kinda really is, though. In addition to cache line locality, serial access also benefits from being speculatable. The CPU can't very effectively speculate past a pointer chase (and on arm little cores it doesn't even try), so those become pipeline stalls. Even if the pointer happened to be close-ish, it's still going to end up being a stall more often than not. And an allocator / GC is only going to lay out a linked list in any sort of predictable way if the linked list is built up all at once, in which case a linked list is obviously not the right data structure anyway ;)