1. Forum
  2. Usenet
  3. COMP.ARCH

  • Re: Array vs. Linked List Traversal

    From Scott Lurndal@21:1/5 to jseigh on Thu Aug 1 14:58:33 2024
    jseigh <jseigh_es00@xemaps.com> writes:
    It's claimed that array traversal is faster than linked list traversal. What would be the reasons for that?


    https://en.wikipedia.org/wiki/Locality_of_reference

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From jseigh@21:1/5 to All on Thu Aug 1 10:55:57 2024
    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?

    Joe Seigh

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Anton Ertl@21:1/5 to jseigh on Thu Aug 1 15:40:30 2024
    jseigh <jseigh_es00@xemaps.com> writes:
    Array elements being in cache, assuming the element size is small
    enough to fit multiple elements in a cache line?

    Yes. Even without, hardware branch predictors will see the stride and
    prefetch the cache lines appropriately.

    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.

    Depends on how much work you have to do per element. If it's just a
    little work, like adding up one field of each element, or searching
    for a particular value of a field, the linked-list will mean that each iteration takes 4-5 cycles on a modern CPU even on a D-cache hit,
    while such loops may take 1 cycle/iteration or less if an array is
    used. If you have more than 5 cycles of work per element, then that's
    not an issue (as long as the elements are in the D-cache or the
    linked-list layout works for the hardware prefetchers), but modern
    CPUs can do a lot in 5 cycles.

    Rearranging the load of the next pointer will typically not make a big difference on OoO CPUs, unless you have a lot of branch
    mispredictions.

    Something else?

    Please limit your lines to around 70 characters. I reformatted the
    quoted material.

    - anton
    --
    'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
    Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From MitchAlsup1@21:1/5 to jseigh on Thu Aug 1 15:49:35 2024
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Stefan Ram@21:1/5 to jseigh on Thu Aug 1 19:14:48 2024
    jseigh <jseigh_es00@xemaps.com> wrote or quoted:
    It's claimed that array traversal is faster than linked list
    traversal. What would be the reasons for that?

    Array traversal is hella faster than linked list traversal for a few
    key reasons:

    Cache Magic: Arrays stack elements right next to each other in
    memory, so when you hit one element, the CPU cache scoops up the
    neighbors too. It's like grabbing a whole burrito instead of just
    one bean at a time.

    Linked lists are all over the place, so you're constantly
    reaching for new bites.

    Pointer Drag: Linked lists are like following a treasure map -
    you got to read the clue, then go to the spot. Arrays? It's more
    like counting houses on Rodeo Drive - you know exactly where
    everything is.

    CPU Crystal Ball: Arrays are predictable, like traffic on the
    405 at rush hour. The CPU can see it coming. Linked lists are
    more like navigating Santa Monica on a holiday weekend - you
    never know what's around the corner.

    Speed Demon: Figuring out where to go next in an array is quick,
    like zipping down PCH. Linked lists are more stop-and-go, like
    cruising through Hollywood Boulevard.

    Bottom line, arrays crush it for traversal 'cause they're all
    about that efficient memory use, fewer pit stops, and a smooth
    ride the CPU can really groove with.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Lawrence D'Oliveiro@21:1/5 to All on Thu Aug 1 23:14:40 2024
    On Thu, 1 Aug 2024 15:49:35 +0000, MitchAlsup1 wrote:

    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

    Hence the term, “pointer-chasing”.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Stephen Fuld@21:1/5 to Stefan Ram on Thu Aug 1 22:54:07 2024
    On 8/1/2024 12:14 PM, Stefan Ram wrote:
    jseigh <jseigh_es00@xemaps.com> wrote or quoted:
    It's claimed that array traversal is faster than linked list
    traversal. What would be the reasons for that?

    Array traversal is hella faster than linked list traversal for a few
    key reasons:

    Cache Magic: Arrays stack elements right next to each other in
    memory, so when you hit one element, the CPU cache scoops up the
    neighbors too. It's like grabbing a whole burrito instead of just
    one bean at a time.

    Linked lists are all over the place, so you're constantly
    reaching for new bites.

    Pointer Drag: Linked lists are like following a treasure map -
    you got to read the clue, then go to the spot. Arrays? It's more
    like counting houses on Rodeo Drive - you know exactly where
    everything is.

    CPU Crystal Ball: Arrays are predictable, like traffic on the
    405 at rush hour. The CPU can see it coming. Linked lists are
    more like navigating Santa Monica on a holiday weekend - you
    never know what's around the corner.

    Speed Demon: Figuring out where to go next in an array is quick,
    like zipping down PCH. Linked lists are more stop-and-go, like
    cruising through Hollywood Boulevard.

    Bottom line, arrays crush it for traversal 'cause they're all
    about that efficient memory use, fewer pit stops, and a smooth
    ride the CPU can really groove with.

    WOW!!! I have never seen so many Los Angeles area references in a
    comp.arch post! And from someone with a Berlin, Germany e-mail address
    no less!

    At least one person gets and appreciates them!



    --
    - Stephen Fuld
    (e-mail address disguised to prevent spam)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)