Re: Array vs. Linked List Traversal

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)