Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Stephen Fuld <sfuld@alumni.cmu.edu.invalid>
Newsgroups: comp.arch
Subject: Re: Array vs. Linked List Traversal
Date: Thu, 1 Aug 2024 22:54:07 -0700
Organization: A noiseless patient Spider
Lines: 45
Message-ID: <v8hs9v$2alm0$1@dont-email.me>
References: <v8g7lr$27dq5$1@dont-email.me>
 <arrays-20240801201407@ram.dialup.fu-berlin.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 02 Aug 2024 07:54:07 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0dfdc06a3db5844c0ef7f71f039cee4b";
	logging-data="2447040"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX182LzFul+XMV5w7634XirYIqCMRO0H8nzo="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:4elwQmwXGwmEBgyCHXtcYyhqRpo=
In-Reply-To: <arrays-20240801201407@ram.dialup.fu-berlin.de>
Content-Language: en-US
Bytes: 2874

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)