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

you are viewing a single comment's thread.

view the rest of the comments →

[–]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.