【计算机基础】程序的局部性简介
共 785字，需浏览 2分钟
·
2021-01-19 16:30
什么是局部性？
局部性分类
局部性有什么作用？
局部性举例
数据引用的局部性
取指令的局部性
结论
完整代码
什么是局部性？
程序倾向于使用它们最近使用的地址接近或相等的数据和指令。
局部性分类
局部性主要分为时间局部性和空间局部性。
时间局部性：最近使用过的数据和指令在不久的将来可能再次被使用。具体如下图所示。
空间局部性：某个地址或者某个地址附近的数据和指令可能在不久的将来再次被引用。具体如下图所示。
局部性有什么作用？
在现代计算机的软硬件中，处处体现着局部性原理。在硬件上，计算机通过引入称为高速缓存来保存最近被使用的指令和数据。在软件上，操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块。在应用程序的设计中，Web浏览器将最近被引用的文档放在本地磁盘上，利用的就是时间局部性。作为程序员应该理解局部性原理，一般来说，有良好局部性的程序比局部性差的程序运行得更快。
局部性举例
数据引用的局部性
看下下面两个函数。都是计算数组a的和。唯一的区别在于行列的访问先后顺序不同。那么这两个程序运行起来会有什么差别呢？我们测试下。
/**
* @Description: 行优先方式求二维数组a的和
* @Param: 整型数组a
* @Return: 数组a的和sum
* @Author: 嵌入式与Linux那些事
*/
int SumArrRow(int aarr[ROW][COL])
{
//1393.166487us
int i,j,sum = 0;
for(i = 0;i < ROW;i++)
for(j = 0;j < COL;j++)
sum +=a[i][j];
printf("%d\r\n",sum);
return sum;
}
/**
* @Description: 列优先方式求二维数组a的和
* @Param: 整型数组a
* @Return: 数组a的和sum
* @Author: 嵌入式与Linux那些事
*/
int SumArrCol(int a[ROW][COL])
{
//2083.776579us
int i,j,sum = 0;
for(j = 0;j < COL;j++)
for(i = 0;i < ROW;i++)
sum +=a[i][j];
printf("%d\r\n",sum);
return sum;
}
运算的数组为2 * 3大小。测试结果如下。
15
SumArrRow run_time:1039.612803us
15
SumArrCol run_time:2011.529889us
SumArrCol函数的运行时间是SumArrRow运行时间的将近2倍。原因是什么呢？
首先我们要知道数组在内存中是以行优先的方式存储的。SumArrRow函数在for循环中访问a的顺序如下。
地址 0 4 8 12 16 20
内容 a00 a01 a02 a10 a11 a12
访问顺序 1 2 3 4 5 6
而SumArrRow函数中，双重嵌套循环按照行优先顺序读数组的元素。也就是，内层循环读第一行的元素，然后读第二行，依此类推。元素被访问的步长为1。和数组在内存中的存储方式是一样的，因此具有很好的空间局部性。
SumArrCol函数和SumArrRow函数，唯一的区别是我们交换了i和j的循环。这样交换循环对它的局部性有何影响？因为它按照列顺序来扫描数组，而不是按照行顺序。因为C数组在内存中是按照行顺序来存放的，元素被访问的步长为COL。所以其空间局部性较差。
SumArrCol函数在内存中的存放方式如下所示。
地址 0 4 8 12 16 20
内容 a00 a01 a02 a10 a11 a12
访问顺序 1 3 5 2 4 6
下面再看一个时间局部性的例子。
/**
* @Description: 求一维数组a的和
* @Param: 整型数组a
* @Return: 数组a的和sum
* @Author: 嵌入式与Linux那些事
*/
int SumArr(int a[MAX])
{
int i,sum = 0;
for(i = 0;i < MAX;i++)
sum +=a[MAX];
printf("%d\r\n",sum);
return sum;
}
SumArr单函数，它对一个向量的元素求和。这个程序有良好的局部性吗？要回答这个问题，我们来看看每个变量的引用模式。
地址 0 4 8 12 16 20
内容 a0 a1 a2 a3 a4 a5
访问顺序 1 2 3 4 5 6
在这个例子中，变量sum在每次循环迭代中被引用一次，因此，对于sum来说，有好的时间局部性。另一方面，因为sum是标量，对于sum来说，没有空间局部性。
数组a的元素是被顺序读取的，一个接一个，按照它们存储在内存中的顺序（为了方便，我们假设数组是从地址0开始的）。因此，对于数组a，函数有很好的空间局部性，但是时间局部性很差，因为每个数组元素只被访问一次。对于循坏体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性，所以我们可以断定 SumArr函数有良好的局部性。
取指令的局部性
因为程序的指令是放在内存中的，程序运行时，CPU必须取出这些指令。SumArr中for循环体中的指令是按照连续的内存顺序执行的。因此具有很好的空间局部性。而且，循环体又被执行很多次，所以也有很好的时间局部性。
取指令的局部性和数据引用的局部性的区别在于，在程序运行时，指令是不可修改的。程序只能对指令读。
结论
上面我们介绍了局部性的概念，并给出了程序示例。现将以上内容总结如下。
重复引用相同变量的程序有良好的时间局部性。 对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。在内存中以大步长跳来跳去的程序空间局部性会很差。 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。
完整代码
/*
* @Description: 【计算机基础】程序的局部性简介
* @Version: V1.0
* @Autor: 嵌入式与Linux那些事
* @Date: 2020-12-21 21:40:12
* @LastEditors: 嵌入式与Linux那些事
* @LastEditTime: 2020-12-23 23:11:58
*/
#include
#include
#include
#define ROW 2
#define COL 3
/**
* @Description: 行优先方式求数组a的和
* @Param: 整型数组a
* @Return: 数组a的和sum
* @Author: 嵌入式与Linux那些事
*/
int SumArrRow(int aarr[ROW][COL])
{
//1393.166487us
int i,j,sum = 0;
for(i = 0;i < ROW;i++)
for(j = 0;j < COL;j++)
sum +=a[i][j];
printf("%d\r\n",sum);
return sum;
}
/**
* @Description: 列优先方式求数组a的和
* @Param: 整型数组a
* @Return: 数组a的和sum
* @Author: 嵌入式与Linux那些事
*/
int SumArrCol(int a[ROW][COL])
{
//2083.776579us
int i,j,sum = 0;
for(j = 0;j < COL;j++)
for(i = 0;i < ROW;i++)
sum +=a[i][j];
printf("%d\r\n",sum);
return sum;
}
/**
* @Description: 求一维数组a的和
* @Param: 整型数组a
* @Return: 数组a的和sum
* @Author: 嵌入式与Linux那些事
*/
int SumArr(int arr[MAX])
{
int i,sum = 0;
for(i = 0;i < MAX;i++)
sum +=a[MAX];
printf("%d\r\n",sum);
return sum;
}
int main()
{
int a[ROW][COL] = {0,1,2,3,4,5};
double run_time;
LARGE_INTEGER time_start; //开始时间
LARGE_INTEGER time_over; //结束时间
double dqFreq; //计时器频率
LARGE_INTEGER f; //计时器频率
QueryPerformanceFrequency(&f);
dqFreq=(double)f.QuadPart;
QueryPerformanceCounter(&time_start); //计时开始
SumArrRow(a);
QueryPerformanceCounter(&time_over); //计时结束
run_time=1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;//乘以1000000把单位由秒化为微秒，精度为1000 000/（cpu主频）微秒
printf("\nSumArrRow run_time：%fus\n",run_time);
return 0;
}
养成习惯，先赞后看！如果觉得写的不错，欢迎关注，点赞，在看，转发，谢谢！