乐趣区

关于自动驾驶:理解程序的局部性原理

jiezi

1.1 什么是程序局部性？

良好的计算机程序通常有良好的局部性，局部性次要有：

  • 工夫局部性：指的是同一个内存地位，从工夫维度来看，它可能在 较短时间 内被屡次援用。
  • 空间局部性：指的是同一个内存地位，从空间维度来看，它 左近的内存地位 可能被援用。

1.2 数据援用局部性

请看上面程序：

# 例 1
int sumvec(int  v[N])
{
    int i,sum=0;
    for(i=0;i<N;i++)
    {sum+=v[i];
    }
}

对于例 1 的程序，是否有良好的局部性？要答复这个问题就要看看程序中变量的援用模式。

变量 sum 被能在较短时间内屡次援用，所以具备很好的工夫局部性，然而没有援用到 sum 左近的内存地位，所以没有空间局部性可言。对于数据 v，数据是顺序存储的，程序中也是按程序取元素(步长为 1 的援用模式，步长越大，空间局部性越差)，元素左近的地位可能被援用，所以具备良好的空间局部性，然而对于同一个内存地位，只能被援用一次，所以工夫局部性很差。对于函数中每个变量，要么有工夫局部性，要么有空间局部性，所以说这个函数具备良好的局部性。

在看上面的例子：

# 例 2 
int sumvec(int  v[M][N])
{
    int i,j,sum=0;
    for(i=0;i<M;i++)
    {for(j=0;j<N;j++)
        {sum+=v[i][j];}
    }
}

二维数是依照行优先顺序存储的，而例 2 程序中，也是依照行优先读取元素，所以有很好的空间局部性，然而每个元素的内存地位只被援用一次，所以工夫局部性很差，再看例 3。

# 例 3
int sumvec(int  v[M][N])
{
    int i,j,sum=0;
    for(i=0;i<N;i++)
    {for(j=0;j<M;j++)
        {sum+=v[j][i];}
    }
}

例 3 依照列优先读取元素(程序具备步长为 N 的援用模式，读取下一个元素时候须要跳到步长 N 的地位)，空间部分较差，所以例 3 的程序空间局部性和工夫局部性都比拟差。

1.3 取指令局部性

指令寄存在内存中，CPU 须要将取出指令，在例 2，例 3 的循环体中，放在同一个内存地位的程序指令在短时间内会被屡次读取，其左近的指令也会被屡次读取，所以具备很好的局部性。

先留个问题，程序指令如何寄存在内存中？

退出移动版