Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.arch
Subject: Re: Array vs. Linked List Traversal
Date: Thu, 1 Aug 2024 14:12:06 -0700
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <v8gtn7$2cpd9$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: Thu, 01 Aug 2024 23:12:08 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f3137d7092590c84c7f4c9bd393a8434";
	logging-data="2516393"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/2mqL7w9pwh+4Et1/cIFhrTkIF6Y5TiuM="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:dsntkihpEU9mpDqNcOP2WDjhM9I=
Content-Language: en-US
In-Reply-To: <arrays-20240801201407@ram.dialup.fu-berlin.de>
Bytes: 2796

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.
[...]

Fwiw, wrt a "special case" a linked list that is "sorted" can sometimes 
be pretty fast for traversal. ;^)

l2 = cache line

An array aligned on a cache line boundary { l2, l2, l2 }

a linked list

n(&array[0])->n(&array[1])->n(&array[2])->nullptr

If you can use an array, use an array. Fwiw, here is a tweak I did to a 
pretty darn nice bounded multi-producer/consumer FIFO queue:

https://groups.google.com/g/lock-free/c/acjQ3-89abE/m/a6-Di0GZsyEJ


Wrt region allocators, properly align a bunch of cache lines in an 
array. Feed off that array if a local node cannot be allocated or until 
its all used up. Something akin to:

node* allocate()
{
     node* local = allocate_local();

     if (! local)
     {
         local = allocate_global();

         if (! local)
         {
             local = allocate_region();

             if (! local)
             {
                 local = allocate_region_expand();

                 if (! local)
                 {
                     // humm... really out of memory here?
                 }
             }
         }
     }

     return local;
}

Just a quick outline.