关于常数优化

代码层面

由于现在考试都开 O2，所以只讨论有 O2 的情况。

循环展开

由于 CPU 处理分支的能力很烂，所以循环展开加速的一部分原因在于减少了分支。

测试标准为 $10^5$ 次随机区间求和，大小 $10^5$，以下代码用时 572ms，for 循环用时 1192ms

for(int i=1;i<=m;i++){
    long long sum[4]={0,0,0,0};
    int j;
    for(j=l[i];j+3<=r[i];j+=4){
        sum[0]+=a[j+0];
        sum[1]+=a[j+1];
        sum[2]+=a[j+2];
        sum[3]+=a[j+3];
    }
    for(;j<=r[i];j++){
    	sum[0]+=a[j];
    }
    ans^=sum[0]+sum[1]+sum[2]+sum[3];
}

将 sum 数组替换为多个局部变量，效果不变。

测试了其它展开位数，开 8 位效果最佳，约 520ms。

16 位会出现寄存器溢出效率下降。

如果用的求和变量较多，最好开 4 位。

顺便一提，开 Ofast/O3 后会帮你展开。

如果你写了假的循环展开，那么效率提升只有约 $50\%$，这是假的循环展开，但是开了 O3 就是真的了：

long long calc(int* begin, int* end) {
	long long res = 0;
	if ((size_t)begin & 4) res = *begin++;
    unsigned long long sum[4];
	while (begin + 7 <= end) {
        auto addr = (unsigned long long*)begin;
        sum[0] += addr[0];
        sum[1] += addr[1];
        sum[2] += addr[2];
        sum[3] += addr[3];
        begin += 8;
    }
    for (int i = 0; i < 4; i++) res += (sum[i] >> 32) + unsigned(sum[i]);
    while (begin < end) res += *begin++;
    return res;
}

for(int i=1;i<=m;i++){
    long long sum=0;
    int j;
    for(j=l[i];j+3<=r[i];j+=4){
        sum+=a[j+0];
        sum+=a[j+1];
        sum+=a[j+2];
        sum+=a[j+3];
    }
    for(;j<=r[i];j++){
    	sum+=a[j];
    }
    ans^=sum;
}

用时 832ms。

减少分支

这个减少分支主要指减少内层循环的分支，尤其是理论预测成功率很低的分支。

CPU 的分支预测，可以视为一种很智能的找规律，在几乎不执行，几乎执行的情况下，或者是否成功具有循环节之类的情况，具有极高的预测效率。

当分支预测失败时，有较大可能会从内存中重新读取对应代码块，

一般可以采用乘法等算术方式。

不建议写偏向条件赋值的代码，因为高版本编译器可能会弄成条件执行，它以认为它读懂了你的代码，但是它就是个蠢逼。

在一些比较极端的情况，甚至能带来 $5$ 倍的效率差异！

这里的 $k=10$。

例子：

for(int mask=0;mask<1<<(k+1);mask++){
    int final=0;
    for(j=0;j<k;j++)if(bool((1<<j)&mask))
        final^=stat[mask>>k][j];
    dp[(i+1)&1][final]+=dp[i&1][mask&((1<<k)-1)];
}

可以换成：

for(int mask=0;mask<1<<(k+1);mask++){
    int final=0;
    for(j=0;j<k;j++)final^=bool((1<<j)&mask)*stat[mask>>k][j];
    dp[(i+1)&1][final]+=dp[i&1][mask&((1<<k)-1)];
}

或者更理想的：

for(int mask=0;mask<1<<(k+1);mask++){
    int final=0;
    for(int w=mask;w;w-=w&(-w))final^=stat[mask>>k][__builtin_ctz(w)];
    dp[(i+1)&1][final]+=dp[i&1][mask&((1<<k)-1)];
}

__builtin_clz() 返回一个数二进制下前导 0 的个数，对于负数，返回值是 0

__builtin_ctz() 返回二进制末尾连续 0 的个数。

三份代码的运行时间分别为 1200ms 213ms 150ms。

高速缓存

一般情况

用一句话来说，能滚动的数组要滚动。

可以看看这两个提交，效率改进因子为 1.6。

无滚动数组，390ms。

滚动数组，150ms。

互踢缓存

如果遍历数组的顺序和数组的大小都不太理想，很容易出现互踢缓存的特殊情况，在一些极端情况可能会带来 10 倍甚至 20 倍的常数差距。

缓存存储的基本单位是 cacheline，大小为 64Byte，将一个数据物理地址的末六位抹掉，可以得到它的缓存行编号，缓存行编号视高速缓存大小和分组策略取末 $k$ 位，作为高速缓存使用区域编号。同一高速缓存使用区一般可以存储 16 个 cacheline，如果超出，则踢出最早进入的。

举例来说，如果以 256Byte 作为步长遍历数组，那么由于抹掉 $6$ 位后末 $2$ 位是一样的，所以实际被利用的高速缓存仅有 $\frac{1}{4}$，会出现非常阴间的情况，需要避免。

访问连续

访问连续有两个层面，缓存行连续访问，页的访问连续。

一般强调前者。

幻影彭的彩虹