跳到主要内容

局部性原理

什么是局部性？​

  • 局部性原理: 程序倾向于引用最近引用过的数据项, 或与它们相邻的数据项;
  • 时间局部性: 一个内存位置被引用后, 很可能在不久后再次被引用;
  • 空间局部性: 一个内存位置被引用后, 其邻近位置很可能在不久后被引用;

程序的数据引用有哪些局部性规律？​

  • 重复引用同一变量: 时间局部性好;
  • 按固定步长遍历: 步长越小, 空间局部性越好;
  • 结论: 局部性越好的程序运行速度越快;

怎样写出缓存友好的代码？​

  • 关注点: 函数中的循环, 程序的大部分访存都发生在这里;
  • 做法: 对数组等连续存储的数据结构, 按内存地址的顺序依次访问;
/* 行优先存储的多维数组, 按行求和 */
int sumarrayrows(int a[M][N]) {
  int i, j, sum = 0;
  for (i = 0; i < M; i++)
    for (j = 0; j < N; j++)
      sum += a[i][j];
  return sum;
}