Cachelokalitet

Cachelokalitet avser hur väl ett programs åtkomstmönster till data och instruktioner utnyttjar processor- och minnescacheminnens egenskaper. God lokalitet minskar antalet dyra åtkomstfel mot huvudminnet och ökar prestanda genom högre cache-hitrate och lägre latens.

Två grundtyper är temporal lokalitet, där nyligen åtkomna objekt sannolikt används igen inom kort tid, och spatial lokalitet, där närliggande adresser ofta åtkoms i följd. Både hårdvarucache (nivå L1–L3) och mjukvarunivåer som sidbyte och TLB påverkas av dessa mönster.

Praktiska konsekvenser syns i val av datastrukturer och algoritmer. Sekventiell traversering av arrayer ger god spatial lokalitet, medan slumpmässiga pekarstrukturer kan ge dålig lokalitet. Optimeringar som loopblocking (tiling), omordning av fält (array-of-structures vs structure-of-arrays) och prefetching är vanliga för att förbättra lokalitet. Cache-oblivious algoritmer designas för att fungera effektivt över flera cachenivåer utan hårdkodade blockstorlekar.

Mätning sker ofta via cache-hitrate, miss-typer (compulsory, capacity, conflict) och profileringsverktyg som hardware performance counters. Modern hårdvara kompletterar programoptimering med associativitet, inkrementell prefetch och större linjestorlekar, men grundprinciperna förblir desamma.

Förståelse för cachelokalitet är central i prestandakritisk utveckling, högpresterande beräkning och systemdesign, eftersom den styr hur effektivt beräkningar översätts till verklig exekveringstid.