Re: Array vs. Linked List Traversal

On Thu, 1 Aug 2024 14:55:57 +0000, jseigh wrote:

It's claimed that array traversal is faster than linked list traversal.
What would be the reasons for that?
>
Array elements being in cache, assuming the element size is small enough
to fit multiple elements in a cache line?
>
No dependent load delay from having to load the linked list next
pointer?  If that was the case, then moving the load of the next pointer
to the beginning of the loop should ameliorate that somewhat.
>
Something else?

The next element address in an array can be found by addition
The next element address in a linked list can be found by a load
With cache hits, add is 1 cycle
With cache hits, load is 3-4 cycles
If you want to access the 14 successive member you add 15 to the
current index--1 addition with very low change of a TLB miss.
If you want to access the 15 successive linked list, you have to
perform 14 address dependent loads--with an unpredictable number
of TLB misses.

>
Joe Seigh