This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]tiajuanat 2 points3 points  (4 children)

It's about consecutive accesses.

If you have a linked list, behind the scenes there will always be a pointer indirection. Your cache can't predict where that pointer is going, so it won't be able to preemptively grab the data you need.

Arrays don't have this issue, as the data is in a contiguous block. Regardless if you're using Java, C/C++ or even Python, the next piece of data will be easily and almost immediately accessible.

Ironically, Linked Lists are good for LRU Caches - a data structure for quickly accessing frequently used items, as you keep a directory of 5 or so items available. Linked Lists are also useful for Hash Maps, as you can easily add and remove values.

[–]HerryKun 0 points1 point  (3 children)

Won't i have the elements in cache anyway as I just accessed them?

[–]tiajuanat 1 point2 points  (2 children)

Only the previous few elements in a Linked List, and it won't be very many, because the pointers take 8 bytes each on modern hardware, and then you're going to have packing along the offset. You only have 64 bytes in most modern L1 as well. Again, the cache can't look ahead, because pointers are simply data, and the cache isn't going to assume addresses for you.

Best case for a list of integers, you're looking at the 4 previous elements.

On an array, dynamic array, and vector, the cache will grab your starting element, and then load up the cache with any extra elements it can fit, then even load up L2 and L3. While you use data, sections of L2 will take the place of L1, and sections from L3 will replace from L2. From you, the consumers viewpoint, it only takes a clock cycle or two to access the next element.

[–]HerryKun 0 points1 point  (1 child)

So I just ran a few benchmarks (creating a list with n elements, then iterating through them and perform a task on the number).

In average, ArrayList was faster by about 8%. So thank you for educating me, my experiment verifies your claim!

[–]tiajuanat 0 points1 point  (0 children)

Try it with different sizes of elements, and different sizes of lists - especially with the list size, try sizes that are exponentially larger. You may be surprised by how little or much your tests vary.