锐客网

  1. 首页 > it技术 > >

理解程序的局部性原理

1.1 什么是程序局部性？ 良好的计算机程序通常有良好的局部性，局部性主要有：

  • 时间局部性 ：指的是同一个内存位置，从时间维度来看，它能够在较短时间内被多次引用。
  • 空间局部性 ：指的是同一个内存位置，从空间维度来看，它附近的内存位置能够被引用 。
1.2 数据引用局部性 请看下面程序：
#例1 int sumvec(intv[N]) { int i,sum=0; for(i=0; i

对于例1的程序，是否有良好的局部性？要回答这个问题就要看看程序中变量的引用模式。
变量sum被能在较短时间内多次引用，所以具有很好的时间局部性，但是没有引用到sum附近的内存位置，所以没有空间局部性可言。对于数据v，数据是顺序存储的，程序中也是按顺序取元素(步长为1的引用模式，步长越大，空间局部性越差 )，元素附近的位置能够被引用，所以具有良好的空间局部性，但是对于同一个内存位置，只能被引用一次，所以时间局部性很差。对于函数中每个变量 ，要么有时间局部性，要么有空间局部性，所以说这个函数具有良好的局部性 。
在看下面的例子：
#例2 int sumvec(intv[M][N]) { int i,j,sum=0; for(i=0; i

二维数是按照行优先顺序存储的，而例2程序中，也是按照行优先读取元素 ，所以有很好的空间局部性，但是每个元素的内存位置只被引用一次，所以时间局部性很差，再看例3。
#例3 int sumvec(intv[M][N]) { int i,j,sum=0; for(i=0; i

例3按照列优先读取元素(程序具有步长为N的引用模式，读取下一个元素时候需要跳到步长N的位置)，空间局部较差，所以例3的程序空间局部性和时间局部性都比较差。
1.3 取指令局部性 指令存放在内存中，CPU需要将取出指令，在例2，例3的循环体中，放在同一个内存位置的程序指令在短时间内会被多次读取，其附近的指令也会被多次读取，所以具有很好的局部性。
【理解程序的局部性原理】先留个问题，程序指令如何存放在内存中？

    推荐阅读


    上一篇：测试目录

    下一篇：CMDA-4654