Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: mitchalsup@aol.com (MitchAlsup1)
Newsgroups: comp.arch
Subject: Re: Array vs. Linked List Traversal
Date: Thu, 1 Aug 2024 15:49:35 +0000
Organization: Rocksolid Light
Message-ID: <785fcf1ed0f5cd2700c9fd4970b4ef79@www.novabbs.org>
References: <v8g7lr$27dq5$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: i2pn2.org;
	logging-data="1114712"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="65wTazMNTleAJDh/pRqmKE7ADni/0wesT78+pyiDW8A";
User-Agent: Rocksolid Light
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Rslight-Site: $2y$10$u3IEbPrjk8P1ZZWAL1DkPe/15wx9GzY95Fh5gaBYIyx4FFjNfCRwG
X-Rslight-Posting-User: ac58ceb75ea22753186dae54d967fed894c3dce8
Bytes: 1939
Lines: 27

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