Minneslokalitet

Minneslokalitet är ett begrepp inom datorarkitektur som beskriver hur program tenderar att komma åt en relativt liten del av huvudminnet under en viss tidsperiod och hur ofta data som ligger nära varandra i minnesadressen används igen inom kort. Principen ligger till grund för hur minneshierarkin och cacheminnen presterar.

Principen kallas ofta för lokalitetens princip och delas upp i två huvudtyper: temporär lokalitet och rumslig lokalitet. Temporär lokalitet innebär att nyligen hämtad data sannolikt används igen inom kort. Rumslig lokalitet innebär att data som ligger nära varandra i minnesadressen sannolikt hämtas i följd.

Moderna processorer använder flera nivåer av cache (L1, L2 och ofta L3) för att dra nytta av lokaliteten. När programmet följer en god lokalitet upplever det färre cachemissar och lägre latens, vilket ökar genomströmningen och minskar energiförbrukningen.

För att förbättra minneslokaliteten kan man utforma datastrukturer och algoritmer så att minnet åtkoms i sekventiell ordning eller i den ordning som data är allokerad. Exempel inkluderar att undvika länkade listor för stora datasamlingar och istället använda kontinuerliga block, iterera i den ordning som data är lagrad, samt använda loop-tiling och val av lämplig data-layout (till exempel array of structures kontra structure of arrays) för bättre rumslig respektiv temporär lokalitet. Kompiler och utvecklingsverktyg kan också erbjuda prefetch-stöd.

Betydelsen av minneslokalitet sträcker sig över prestandaoptimeringar i program som bearbetar stora dataset eller kör långa loopar, och den påverkar både hastighet och energieffektivitet i moderna datorer.