開篇
一個(gè)優(yōu)秀的程序、優(yōu)美的代碼，一般都具有良好的局部性。簡(jiǎn)潔、高效是每個(gè)程序員的追求。了解程序的局部性，能編寫出更高效的代碼。
因?yàn)橛辛己镁植啃缘某绦蚰芨玫睦镁彺?。不過這方面的只是將在以后的文章中介紹。
這篇文章就簡(jiǎn)單的介紹以下程序的局部性原理。
什么是局部性
局部性通常有兩種形式：
時(shí)間局部性(temporal locality)
時(shí)間局部性指的是：被引用過一次的存儲(chǔ)器位置在未來會(huì)被多次引用（通常在循環(huán)中）。
空間局部性(spatial locality)
如果一個(gè)存儲(chǔ)器的位置被引用，那么將來他附近的位置也會(huì)被引用。
（這樣說過于理論了些，在下面的論述中會(huì)有例子說明）
數(shù)據(jù)引用局部性
例子是最好說明問題的途徑~
看圖a）中的 for 循環(huán)，可以判斷：循環(huán)中的 sum 有良好的時(shí)間局部性。因?yàn)樵趂or循環(huán)結(jié)束之前，每次執(zhí)行循環(huán)體都有對(duì) sum 的訪問。
而 sum 沒有空間局部性。因?yàn)閟um 是標(biāo)量（也就是說通過 sum 這個(gè)地址（可認(rèn)為是基址，只能得到一個(gè)值）
對(duì)于循環(huán)體中的 v 則有良好的空間局部性?？梢钥吹?圖 b） 中，向量 v 是按順序存儲(chǔ)的（在實(shí)際中多數(shù)情況也按順序存儲(chǔ)）。
每次訪問 v[i]總是在 v[i-1] 的下一個(gè)位置。而 v 沒有時(shí)間局部性。因?yàn)槊總€(gè)元素只被訪問一次。
步長(zhǎng)
向上面例子中按順序、連續(xù)的對(duì) v 的引用，我們稱為步長(zhǎng)為1的引用模式。同理，在一個(gè)連續(xù)的向量中，每隔k個(gè)元素對(duì)向量進(jìn)行訪問，稱為步長(zhǎng)為k的引用。一般來說，隨著步長(zhǎng)的增加，空間局部性會(huì)下降。
對(duì)于多維數(shù)組而言，步長(zhǎng)對(duì)空間局部性的影響顯得尤為重要。
考慮上面的例子，是對(duì)一個(gè)二維數(shù)組的求和。
可以看到，for循環(huán)體中，是以行序?yàn)橹餍驅(qū)υ剡M(jìn)行遍歷。也就是說內(nèi)層循環(huán)先訪問第一行的元素，然后第二行。。。
圖 b）中是二維數(shù)組存儲(chǔ)情況?？梢钥闯?，在存儲(chǔ)器中也是按照行序?yàn)橹餍騺磉M(jìn)行存儲(chǔ)的。也就是說先存儲(chǔ)第一行，然后第二行。。。
現(xiàn)在我們已經(jīng)知道了，本例中存儲(chǔ)順序和訪問順序一致。所以可以該程序?qū)[][]的引用有良好的空間局部性。
對(duì)a[][]實(shí)行的是步長(zhǎng)為1 的引用。
繼續(xù)看下面的例子：
可以看出，相對(duì)于上面的例子，該例的for 循環(huán)中交換了 索引 i j 的位置。
也就是說在對(duì)a[][]進(jìn)行遍歷的時(shí)候，以列序?yàn)橹餍?。即先訪問第一列，在訪問第二列。。。
而b）中，對(duì)a[][]的存儲(chǔ)仍是行序?yàn)橹餍?。這意味著沒訪問一個(gè)元素，就要跳過k個(gè)存儲(chǔ)器才能訪問下一個(gè)。于是得到一個(gè)簡(jiǎn)單的結(jié)論：該例中對(duì)a[][]的訪問是以步長(zhǎng)為k 的模式（k 為每行的元素個(gè)數(shù)）沒有良好的時(shí)間局部性。
通過上面的例子我們知道:在對(duì)向量的訪問中，如果訪問數(shù)序和存儲(chǔ)順序一致，并且是連續(xù)訪問，那么這種訪問具有良好的空間局部性。
取指令的局部性
指令存在于存儲(chǔ)器中，cpu 要讀指令就必須取出指令。所以也能評(píng)價(jià)對(duì)于取指令的局部性。
在for 循環(huán)中，循環(huán)體內(nèi)的指令多次被執(zhí)行，所以有良好的時(shí)間局部性。
循環(huán)體中的指令是桉順序執(zhí)行的，有良好的空間局部性(指令在存儲(chǔ)器中是順序存放的)。
局部性小結(jié)
評(píng)價(jià)局部性的簡(jiǎn)單原則：
1、重復(fù)引用同一個(gè)變量有良好的時(shí)間局部性
2、對(duì)于步長(zhǎng)為k 的引用的程序，步長(zhǎng)越小，空間局部性越小。步長(zhǎng)為1 的引用具有良好的空間局部性。k越大，空間局部性越差。
3、對(duì)于取指令來說、循環(huán)有較好的時(shí)間和空間局部性。
后記
這篇文章只是簡(jiǎn)單的介紹了什么是局部性，局部性原理的應(yīng)有，即為什么有良好局部性的程序有更好的性能，局部性和告訴緩存的關(guān)系是如何的，將在后面的文章中介紹。這篇文章且當(dāng)作后文的鋪墊吧。
本人認(rèn)知有限，如上述文章有不足之處歡迎指正交流。
參看資料：computer systems
如有轉(zhuǎn)載請(qǐng)注明出處：http://www.cnblogs.com/yanlingyin/
一條魚、yanlingyin@ 博客園 2012-2-11
E-mail：yanlingyin@yeah.net
