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.

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