ChangLi's Blog

发表于 更新于
本文字数： 414 阅读时长 ≈ 1 分钟

查看如下代码：

1
2
3
4
5
6
7
8
9
10
#define SIZE 10000
int arr[SIZE][SIZE];

int main()
{
    for (int i = 0; i < SIZE; ++ i)
        for (int j = 0; j < SIZE; ++ j)
            arr[i][j] = 1;
    return 0;
}

通过sudo perf stat -e cache-references,cache-misses ./a.out的检测结果：

将arr[i][j] = 1替换为arr[j][i] = 1后的检测结果：

随着CPU核心速度和数量的不断提升，内存访问成为大多数程序性能的瓶颈（Latency Numbers Every Programmer Should Know），并且这种情况在未来一段时间内仍将持续。硬件设计人员已经开发出越来越复杂的内存处理和加速技术——例如CPU缓存——但如果没有程序员的辅助，这些技术就像上面的代码无法发挥最佳性能。

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

C语言类型系统中的每一个独立类型都有若干该类型的限定版本，对应const、volatile以及（针对对象类型指针的）restrict限定符中的一种、两种或全部三种组合。

只有指向对象类型或其（可能多维的）数组（C23起）的指针才能被restrict限定；特别地，以下情况是错误的：

  • int restrict *p
  • float (*restrict f9) (void)

restrict语义仅适用于左值表达式；例如，转换为restrict限定指针或返回restrict限定指针的函数调用均非左值，此时限定符不产生任何效果。

在声明了受限指针P的代码块（通常是P作为函数参数的函数体）的每次执行期间，如果通过P（直接或间接）可访问的某个对象被以任何方式修改，那么该代码块中对该对象的所有访问（包括读取和写入）都必须通过P（直接或间接）进行，否则行为是未定义的：

1
2
3
4
5
6
7
8
9
10
11
12
13
int f(int *restrict p, int *restrict q)
{
    *p = 30; // 通过*p修改的对象与通过*q修改的对象不存在重叠
    *q = 40; // 编译器可自由进行优化、向量化、内存分页等操作
    return *p + *p + *q;
}
void g()
{
    int x = 10;
    int y = 20;
    f(&x, &y); // 正确
    f(&y, &y); // 未定义行为：y在函数f中同时通过p和q被访问
}

未使用restrict类型限定符的clang编译结果：

使用后通过clang -std=c2x -O2的编译结果：

使用后通过gcc -std=c2x -O2的编译结果：

对比两次clang编译结果，第一次因为编译器无法确定(%rdi)和(%rsi)是否是重叠对象，此时(%rdi)可能为$30，也可能为$40，所以在第113c行需要再从(%rdi)取值，第1140行是否是重叠对象都不影响值为$40，因此直接使用立即数加入返回值。

第二次因为使用restrict限定(%rdi)和(%rsi)不是重叠对象，所以在第113c行返回值在编译阶段由编译器计算后赋值，最后gcc编译结果需要留意第1146与114b行指令重排。

通过clang -std=c2x -O2 -fsanitize=address,undefined -g运行时检查restrict限定符是否存在未定义行为。

如果对象从未被修改，它可能会被别名化并通过不同的restrict限定指针访问（请注意、若被别名化的restrict限定指针所指向的对象本身也是指针，这种别名化可能会抑制优化）。

从一个受限指针向另一个受限指针赋值是未定义行为，除非是从外层代码块的指针向内层代码块指针赋值（包括在调用带有受限指针参数的函数时使用受限指针实参），或从函数返回时（以及在其他情况下当源指针所在代码块已结束时）：

1
2
3
int *restrict p1 = &a;
int *restrict p2 = &b;
p1 = p2; // 未定义行为

受限指针可以自由赋值给非受限指针，只要编译器能够分析代码，优化机会就仍然存在：

1
2
3
4
5
6
7
void f(int *restrict r, int *restrict s)
{
    int *p = r, *q = s; // 正确
    *p = 30;
    *q = 40;
    return *p + *p + *q; // 几乎确定会像*r + *r + *s一样被优化
}

若数组类型通过typedef使用restrict类型限定符声明，则数组类型本身不具有restrict限定，但其元素类型具有restrict限定：（C23前）

数组类型与其元素类型始终被视为具有相同的restrict限定：（C23后）

1
2
3
4
5
typedef int *array_t[10];
restrict array_t a; // a的类型是int *restrict[10]
// 注意：clang和icc基于array_t不是指针类型的原则拒绝此用法
void *unqual_ptr = &a; // C23之前有效；C23起报错
// 注意：clang即使在C89-C17模式下也采用C++/C23的规则

在函数声明中，关键字restrict可以出现在用于声明函数参数数组类型的方括号内。它限定数组类型转换后的指针类型：

1
2
3
4
5
6
void f(int m, int n, int a[restrict m][n], int b[restrict m][n]);
void g(int n, int (*p)[n])
{
    f(10, n, p, p+10); // 正确
    f(20, n, p, p+10); // 可能出现未定义行为（取决于函数f的具体实现）
}