Länkade listor ger i de allra, allra, allra flesta fall sämre prestanda, om du inte är helt säker på (genom prestandatester) att en länkad lista är snabbare så är det bättre med en array. En länkad lista kan vara bättre (nåja, åtminstone inte mycket långsammare i alla fall) om du något har väldigt specifikt användningsmönster, exempelvis att du vill lagra element i en speciell ordning samt inte läsa av dessa element förrän prestanda inte spelar någon roll och du dessutom har förallokerat allt minne i en pool så att du slipper den kostnaden.
Anledningen till detta grundar sig iatt det är fruktansvärt hög fördröjning att läsa ram-minnet i förhållande till processorns klockfrekvens. Man brukar räkna med att det tar ungefär 300-400 klockcykler att hämta någonting från ram-minnet. Därför har processorer en eller flera nivåer av caches, moderna processorer har oftast 3 nivåer, där data kan lagras för att kunna användas snabbare. Dessa caches är mycket små, den första nivån brukar vara i storleksordningen (beror på modell av CPU, dessa siffror är mycket grova, ta dem med en nypa salt) 32kB, nästa nivå 256kB och sista nivån 4MB. En del av detta utrymme är delat mellan kärnor och andra har eget cache. Flera olika nivåer har man för att större minne innebär högre latency.
När data läses in i cachen görs detta i hela s.k. cache-lines. Det gör att det blir lättare för CPUn att hålla reda på vilken data som är cachead samt så gillar minnet att läsa mycket data samtidigt. Storleken på en cache-line beror på vilken nivå av cachen som den lagras i.
En CPU har en enhet som heter prefetcher, denna studerar (enkla) mönster för minnesåtkomst och försöker läsa in data till cachen innan programmet efterfrågar datan. Denna prefetcher kan tydligt se sekventiell minnesåtkomst och förutse denna mycket bra så att påverkan av fördröjningen mot minnet blir minimal. Om man läser från slumpmässiga ställen av minnet kan inte prefetchern läsa in datan i förväg.
När man då itererar genom en länkad lista måste datorn jaga reda på en ny minnesplats för varje element i listan, har man otur får man väldigt många cache missar som går ändå till ramminnet vilket innebär 400 klockcykler per miss. Även om man träffar relativt mycket i den tredje nivån av cacheminnet kan man räkna med ca 50 klockcykler i fördröjning per minnesaccess (första nivån av cachen har ca 2-5 klockcykler fördröjning, andra nivån ~20 klockcykler). Beroende på hur stora ens element är kanske de inte ens tar upp en hel cache-line vilket dessutom innebär att man läser in en massa minne i onödan.
En array å andra sidan ligger som en rad i minnet och kan itereras igenom i full fart. I värsta fall får man en cache-miss på första elementet, sedan kommer CPUn prefetcher att redan ha laddat så mycket som möjligt av arrayen till cache och det tar bara ett par klockcykler per element att hämta datan.
Följande klipp handlar om C++ vector vs list, vector är "bara" en array som kan växa genom att allokera om sig, och har testat det hela lite: http://www.youtube.com/watch?v=YQs6IC-vgmo
Notera att samtliga siffror i detta inlägget bara är ungefärliga och från mitt huvud, det är tänkt att de bara ska visa på storleksordningen, inte ett exakt värde. De beror dessutom mycket på vilken hårdvara man kör på.
