我们来看一个简单地问题：生成N个随机数，把他们插入到一个序列里面，保证他们按照数字的大小排序。例如，如果随机数是5,1,4,2 那么序列的生成过程如下所示：
5
1,5
1,4,5
1,2,4,5
这个时候N个随机数已经排好序了，然后我们按照序列的长度生成随机数，然后移除对应的元素。例如，我们选择的移除位置分别是1,2,0,0 (这里0是原点)，序列的变化顺序如下所示：
1,2,4,5
1,4,5
1,4
4
对于上面这个例子，数组和链表哪个更适合实现这个序列呢？从算法的复杂度角度来讲，链表更适合这个问题，因为链表在删除和增加元素的时候，不需要移动其他的元素。数组相反，每次增加和删除都需要移动一部分元素。更为可怕的是，如果你事先不了解最大的元素个数，那你可能因为一个元素，要移动整个数组。
链表的实现代码：
// 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--
}
}
数组的实现代码：
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:])]
}
}
性能测试
从图片上面可以看出，数组比链表的速度更快。想要理解为什么会这样的话，我们可能要了解一下CPU缓存。
摩尔定律曾经指出，集成电路上面的可容纳晶体管数量，每18个月就可以翻一倍。但是单核的性能已然到达了瓶颈。为了增加性能，我们往往会增加内核数。下图展示了RAM速度的增长速度已然放缓。因此处理器增加了缓存级别来隐藏这种巨大的速度差异。
谷歌统计的延迟时间
- 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缓存层的延迟时间间隔，每增大一个级别，也会慢一个数量级。基于上面的统计结果，假设你有一个3GHz处理器，每纳秒有3次遍历循环。如果你的处理器每次循环可以处理4条指令，那么在100ns内，从主存中取出缓存内容并可以处理1200条指令。1200条指令可以完成很多的工作内容。因此，数据传输到处理器的速度越快，那处理工作的速度也就越快，处理器传输数据成为了性能的一个瓶颈。这意味着，不同缓存层之间协作更好的话，可以加快程序的运行速度。
所以链表速度慢的主要原因是：第一点数组存储每个整数需要4个字节，但是链表需要16个字节，链表的内存大小是数组的4倍。不仅链表的空间很大，而且分散在内存中，这意味着当我们遍历链表找到插入和删除的数据的时候，会随机访问存储链表的整个内存空间，导致CPU缓存无法命中。从另一份方面来讲，硬件通常都喜欢像数组一样的内存连续空间，而且CPU在复制内存方面非常擅长。
结论
- 存储有必要存储的数据，并保证数据紧凑
- 采用可以预知的方式访问内存(译者注：链表元素内存不连续，所以不可预知下一个元素的位置)
- 算法复杂度的常量因子。尽管归并排序、快速排序和堆排序的时间复杂度都是O(nlogn),但是快排仍然是最快的，主要原因是他的常量因子最小。
原文链接：Understanding CPU cache friendliness
作者：Kishore Karunakaran
译者：JYSDeveloper
