我們來(lái)看一個(gè)簡(jiǎn)單地問(wèn)題：生成N個(gè)隨機(jī)數(shù)雅倒，把他們插入到一個(gè)序列里面，保證他們按照數(shù)字的大小排序。例如震放，如果隨機(jī)數(shù)是5,1,4,2 那么序列的生成過(guò)程如下所示：
5
1,5
1,4,5
1,2,4,5
這個(gè)時(shí)候N個(gè)隨機(jī)數(shù)已經(jīng)排好序了比默，然后我們按照序列的長(zhǎng)度生成隨機(jī)數(shù)幻捏，然后移除對(duì)應(yīng)的元素。例如命咐，我們選擇的移除位置分別是1,2,0,0 (這里0是原點(diǎn))篡九，序列的變化順序如下所示：
1,2,4,5
1,4,5
1,4
4
對(duì)于上面這個(gè)例子，數(shù)組和鏈表哪個(gè)更適合實(shí)現(xiàn)這個(gè)序列呢醋奠？從算法的復(fù)雜度角度來(lái)講榛臼，鏈表更適合這個(gè)問(wèn)題，因?yàn)殒湵碓趧h除和增加元素的時(shí)候窜司，不需要移動(dòng)其他的元素沛善。數(shù)組相反，每次增加和刪除都需要移動(dòng)一部分元素例证。更為可怕的是路呜，如果你事先不了解最大的元素個(gè)數(shù)，那你可能因?yàn)橐粋€(gè)元素，要移動(dòng)整個(gè)數(shù)組胀葱。
鏈表的實(shí)現(xiàn)代碼：
// Linked list node representation
type node struct {
element int
next *node
}
func insert(n int) *node {
rand.Seed(0)
var root *node
for i := 0; i < n; i++ {
randVal := rand.Intn(n)
var previous *node
var current = root
for current != nil && current.element < randVal {
previous, current = current, current.next
}
newNode := &node{next: current, element: randVal}
if previous != nil {
previous.next = newNode
} else {
root = newNode
}
}
return root
}
func delete(root *node, size int) {
for root != nil {
randIndex := rand.Intn(size)
var previous *node
var current = root
for i := 0; i < randIndex; i++ {
previous, current = current, current.next
}
if previous != nil {
previous.next = current.next
} else {
root = current.next
}
size--
}
}
數(shù)組的實(shí)現(xiàn)代碼：
func insert(n int) []int {
rand.Seed(0)
var array []int
for i := 0; i < n; i++ {
randVal := rand.Intn(n)
idx := sort.Search(len(array), func(j int) bool { return array[j] >= randVal })
array = append(array, 0)
copy(array[idx+1:], array[idx:])
array[idx] = randVal
}
return array
}
func delete(array []int) {
for len(array) > 0 {
randIndex := rand.Intn(len(array))
array = array[:randIndex+copy(array[randIndex:], array[randIndex+1:])]
}
}
性能測(cè)試
從圖片上面可以看出漠秋，數(shù)組比鏈表的速度更快。想要理解為什么會(huì)這樣的話抵屿，我們可能要了解一下CPU緩存庆锦。
摩爾定律曾經(jīng)指出，集成電路上面的可容納晶體管數(shù)量轧葛，每18個(gè)月就可以翻一倍搂抒。但是單核的性能已然到達(dá)了瓶頸。為了增加性能尿扯，我們往往會(huì)增加內(nèi)核數(shù)求晶。下圖展示了RAM速度的增長(zhǎng)速度已然放緩。因此處理器增加了緩存級(jí)別來(lái)隱藏這種巨大的速度差異衷笋。
谷歌統(tǒng)計(jì)的延遲時(shí)間
- L1 cache reference 0.5 ns // HL
- Branch mispredict 5 ns
- L2 cache reference 7 ns 14x L1 cache // HL
- Mutex lock/unlock 25 ns
- Main memory reference 100 ns 20x L2 cache, 200x L1 cache // HL
- Compress 1K bytes with Zippy 3,000 ns 3 us
- Send 1K bytes over 1 Gbps network 10,000 ns 10 us
- Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD
- Read 1 MB sequentially from memory 250,000 ns 250 us
- Round trip within same datacenter 500,000 ns 500 us
- Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory
- Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
- Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD
- Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms
列表上展示了不同CPU緩存層的延遲時(shí)間間隔芳杏，每增大一個(gè)級(jí)別，也會(huì)慢一個(gè)數(shù)量級(jí)辟宗【粽裕基于上面的統(tǒng)計(jì)結(jié)果，假設(shè)你有一個(gè)3GHz處理器泊脐，每納秒有3次遍歷循環(huán)空幻。如果你的處理器每次循環(huán)可以處理4條指令，那么在100ns內(nèi)容客，從主存中取出緩存內(nèi)容并可以處理1200條指令秕铛。1200條指令可以完成很多的工作內(nèi)容。因此缩挑，數(shù)據(jù)傳輸?shù)教幚砥鞯乃俣仍娇烊缤保翘幚砉ぷ鞯乃俣纫簿驮娇欤幚砥鱾鬏敂?shù)據(jù)成為了性能的一個(gè)瓶頸调煎。這意味著，不同緩存層之間協(xié)作更好的話己肮，可以加快程序的運(yùn)行速度士袄。
所以鏈表速度慢的主要原因是：第一點(diǎn)數(shù)組存儲(chǔ)每個(gè)整數(shù)需要4個(gè)字節(jié)，但是鏈表需要16個(gè)字節(jié)谎僻，鏈表的內(nèi)存大小是數(shù)組的4倍娄柳。不僅鏈表的空間很大，而且分散在內(nèi)存中艘绍，這意味著當(dāng)我們遍歷鏈表找到插入和刪除的數(shù)據(jù)的時(shí)候赤拒，會(huì)隨機(jī)訪問(wèn)存儲(chǔ)鏈表的整個(gè)內(nèi)存空間，導(dǎo)致CPU緩存無(wú)法命中。從另一份方面來(lái)講挎挖，硬件通常都喜歡像數(shù)組一樣的內(nèi)存連續(xù)空間这敬，而且CPU在復(fù)制內(nèi)存方面非常擅長(zhǎng)。
結(jié)論
- 存儲(chǔ)有必要存儲(chǔ)的數(shù)據(jù)蕉朵，并保證數(shù)據(jù)緊湊
- 采用可以預(yù)知的方式訪問(wèn)內(nèi)存(譯者注：鏈表元素內(nèi)存不連續(xù)崔涂，所以不可預(yù)知下一個(gè)元素的位置)
- 算法復(fù)雜度的常量因子。盡管歸并排序始衅、快速排序和堆排序的時(shí)間復(fù)雜度都是O(nlogn),但是快排仍然是最快的冷蚂，主要原因是他的常量因子最小。
原文鏈接：Understanding CPU cache friendliness
作者：Kishore Karunakaran
譯者：JYSDeveloper
