程序性能优化-局部性原理

2019/01/17 13:14
阅读数 74

## [更多文章](https://github.com/woai3c/Front-end-articles)

### 概念
一个编写良好的计算机程序常常具有良好的局部性,它们倾向于引用最近引用过的数据项附近的数据项,或者最近引用过的数据项本身,这种倾向性,被称为局部性原理。有良好局部性的程序比局部性差的程序运行得更快。

### 局部性通常有两种不同的形式:
* 时间局部性:在一个具有良好时间局部性的程序中,被引用过一次的内存位置很可能在不远的将来被多次引用。
* 空间局部性 :在一个具有良好空间局部性的程序中,如果一个内存位置被引用了一次,那么程序很可能在不远的将来引用附近的一个内存位置。

时间局部性示例
```
function sum(arry) {
let i, sum = 0
let len = arry.length

for (i = 0; i < len; i++) {
sum += arry[i]
}

return sum
}
```
在这个例子中,变量sum在每次循环迭代中被引用一次,因此,对于sum来说,具有良好的时间局部性

空间局部性示例

**具有良好空间局部性的程序**
```
// 二维数组
function sum1(arry, rows, cols) {
let i, j, sum = 0

for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
sum += arry[i][j]
}
}
return sum
}
```
**空间局部性差的程序**
```
// 二维数组
function sum2(arry, rows, cols) {
let i, j, sum = 0

for (j = 0; j < cols; j++) {
for (i = 0; i < rows; i++) {
sum += arry[i][j]
}
}
return sum
}
```
看一下上面的两个空间局部性示例,像示例中从每行开始按顺序访问数组每个元素的方式,称为具有步长为1的引用模式。
如果在数组中,每隔k个元素进行访问,就称为步长为k的引用模式。
一般而言,随着步长的增加,空间局部性下降。

这两个例子有什么区别?区别在于第一个示例是按行扫描数组,每扫描完一行再去扫下一行;第二个示例是按列来扫描数组,扫完一行中的一个元素,马上就去扫下一行中的同一列元素。

数组在内存中是按照行顺序来存放的,结果就是逐行扫描数组的示例得到了步长为 1 引用模式,具有良好的空间局部性;而另一个示例步长为 rows,空间局部性极差。

### 性能测试
**运行环境:**
* cpu: i5-7400
* 浏览器: chrome 70.0.3538.110

对一个长度为9000的二维数组(子数组长度也为9000)进行10次空间局部性测试,时间(毫秒)取平均值,结果如下:<br>

所用示例为上述两个空间局部性示例

|步长为 1|步长为 9000|
|-|-|
|124|2316|

从以上测试结果来看,步长为 1 的数组执行时间比步长为 9000 的数组快了一个数量级。

### 总结:
* 重复引用相同变量的程序具有良好的时间局部性
* 对于具有步长为 k 的引用模式的程序,步长越小,空间局部性越好;而在内存中以大步长跳来跳去的程序空间局部性会很差

参考资料:
* [深入理解计算机系统](https://book.douban.com/subject/26912767/)

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部