I was working on Kokkos course that talks about data layout in memory.
I searched a bit about that and i find an interesting document that say : "The memory latency of random memory accesses due to pointer chasing through linked lists will not be reduced by the prefetch mechanisms."
It is very amazing the harware optimisation in modern processors , it is well explained in the full article:
This is true as far as it goes, but, in a performance-conscious Scheme or Lisp implementation (unlike in a naïve C program), the cons cells comprising a linked list are unlikely to be scattered at random locations in memory. Instead, the system will try to store the cons cells near each other, ideally in a contiguous block of memory. In some cases the allocator may be able to do this directly, but, even if not, a copying GC gives a second chance: after copying the skeleton of a cons cell, it can recur on the cdr, copying it to the next location in memory, before proceeding to recur on the car.
That’s not to say linked lists don’t have downsides, like the overhead of storing all of the cdrs. For many purposes, something like racket/treelist will be a more flexible choice if data structure. Still, the Lisp family of languages knows a lot about how to get the most from our historic, elegant data structure.
yes you're right, and i probably had still in mind our historic university course (slide 3):
http://jean.paul.roy.free.fr/PCPS/PF1/cours7-4p.pdf
which showed the cons cells scattered for a pedagogic goal, i suppose.