[C 语言笔记--Day02] locality

上一篇：[C 语言笔记--Day01] Hello World

大纲

什麽是 memory hierarchy?
cache 的运作方式
因为 cache 如此运作，所以写程序时该注意的事情
程序码范例
结论

什麽是 memory hierarchy?

在 memory hierarchy 中：
愈上层，速度快、容量小、贵
愈下层，速度慢、容量大、便宜

用个比喻来说明：

假如我有 1000 本书，不过我只有 10 本书是比较常用到的，

把常用到的 10 本书放到我的书桌旁的书架上（memory hierarchy 较高的地方）
其他的 990 本书放到纸箱里（memory hieraarchy 较低的地方）

当我要找书时

先看书桌旁的书架上有没有我要的书
如果没有，再去纸箱里找
从书架上找到书後，就把找到的书放到书架上
并且挑一本比较不常用到的书放到纸箱里

在写 c 语言时，通常了解图中 L0, L1 的层级大概就行了

层级	名称	注记
L0	register	存在於 cpu 的东西，比 main memory 快
L4	main memory	要了解 array, struct, pointer 如何存在於在 main memory

不过 register 跟 main memory 的速度差太多了，所以需要图中 L1~L3 的 cache 来进行加速

cache 的运作方式

cache 的目标在於加速最上层（register）抓取到资料的动作

cache 的设计建立在以下的想法：

曾经使用过的资料/指令会有很大的机率再次使用
当我使用了某个资料/指令有很大的机率再次使用在他附近的资料/指令
加速以上 1、2 这两种情况
所谓的加速，其实就是把他们放到 memory hierarchy 中较高的位置

所以当我们抓取了记忆体中的某一份资料，这份资料以及在他附近的资料也会一起背放到 cache 中

因为 cache 如此运作，所以写程序时该注意的事情

写程序时要注意尽量抓资料时要抓取附近的资料，这样才符合 cache 的运作方式
这称为 locality ，而 locality 又分为以下两种

temporal locality：使用之前使用过的资料
spatial locality：使用附近的资料

程序码范例：

范例一

// good locality
int sum_array_rows(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;
}

// bad locality
int sum_array_cols(int a[M][N])
{
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

sum_array_rows 的 locality 比较好，因为他抓取资料时是照着记忆体的位置的顺序抓取

sum_array_cols 的 locality 比较差，因为他抓取资料时是跳着抓取的

虽然说以复杂度的观点而言，这两个 function 的复杂度是一样的，

但是 sum_array_rows 在抓取资料时，会有比较高的机率在 memory hierarchy 中比较高的 level 抓取到，

所以他的执行效率会比较好

范例二

定义以下资料结构：

#define N 1000
 typedef struct {
     int vel[3];
     int acc[3];
 } point;

point p[N];

假如要把 point 中的 val, acc 全部都设为 0 了话
以下式最好的方式，因为他完全依寻 address 的顺序：

// good locality

void clear1(point *p, int n)
{
    int i, j;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++)
            p[i].vel[j] = 0;
        for (j = 0; j < 3; j++)
            p[i].acc[j] = 0;
    }
}

这个方式虽然写起来比较方便，但 locality 比较差：

// bad locality

void clear2(point *p, int n)
{
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++) {
            p[i].vel[j] = 0;
            p[i].acc[j] = 0;
        }
    }
}