事情的起因是本人发现T1开O2可以多30pts，于是整个机房开始了激烈的卡常大赛。👀️

这时，出现了一段神秘的代码，这段代码没有快读，没有使用奇怪的卡常技巧，仅仅是打开了O2就比原来多了50pts，成为了T1的第一个AC代码。在此之后的相当长一段时间，这段代码是本题的唯一一个AC。

奇怪的是，这段代码的算法和其他代码并无差别。究竟是什么导致了如此大的性能差距呢？在进行了详细的测试之后，我发现了一个经常被忽略，但是对性能存在极大影响的代码性能瓶颈：缓存性能。

接下来，我将从本题出发，简要讲解一下缓存性能是如何影响整体性能。

免责声明：本文内容基于个人理解，不保证其正确性，请读者注意辨别。 使用CC BY-NC-ND协议。

起点

首先，我们先欣赏一下这段代码，来自ppx同学：

#include<bits/stdc++.h>
using namespace std;
long long ans;
long n,q;
long r,c,l,s;
long long dif[1010][1010];
int main(){
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	scanf("%ld%ld",&n,&q);
	while(q--){
		scanf("%ld%ld%ld%ld",&r,&c,&l,&s);
		for(long i=0;i<l;++i){
			
			if(r+i<=n&&c+i<=n)dif[r+i][c+i]+=s;
			if(r+l<=n&&c+i<=n)dif[r+l][c+i]-=s;
		}
	}
	for(long i=1;i<=n;++i){
		for(long j=1;j<=n;++j){
			dif[i][j]+=dif[i-1][j];
			if(i==1&&j==1)ans=dif[i][j];
			else ans=(ans^dif[i][j]);
		}
	}
	printf("%lld",ans);
	return 0;
}

然后贴一下我的80pts代码

#include<bits/stdc++.h>
int n, q, r, c, l, s;
int64_t ans;
int64_t m[1010][1010];
int main(){
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	
	scanf("%d%d", &n, &q);
	while(q--){
		scanf("%d%d%d%d", &r, &c, &l, &s);
		for(int j=0; j<l && j+r<=n; ++j){
			m[r + j][c] += s;
			if(c + j + 1 <= n) m[r + j][c + j + 1] -= s; 
		}
	}
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			m[i][j] += m[i][j-1];
			ans ^= m[i][j];
		}
	}
	printf("%lld", ans);
	return 0;
}

我在自己的电脑上造了一个高强度数据（$n=1000, q=300000$）并分别为这两个代码计时

[xor1] 1669ms
[xor2] 3026ms

可以发现，后者运行时间几乎是前者的2倍，但是这两段代码几乎一样。

对比

那么问题究竟出在什么地方呢？

经过对比，我们可以发现，这两段代码最大的差别，就是差分数组的维度顺序。也就是说，前者的dif[i]表示第i列的差分数组，后者的dif[i]表示第i行的差分数组。

如果我们将后者代码中的差分数组维度的顺序调换再进行测试，会怎么样呢？

#include<bits/stdc++.h>
int n, q, r, c, l, s;
int64_t ans;
int64_t m[1010][1010];
int main(){
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	
	scanf("%d%d", &n, &q);
	while(q--){
		scanf("%d%d%d%d", &r, &c, &l, &s);
		for(int j = 0; j < l; ++j){
			if(r + j <= n){
				if(c + j + 1 <= n) m[c + j + 1][r + j] -= s; 
				m[c][r + j] += s;
			}
		}
	}
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=n; ++j){
			m[i][j] += m[i-1][j];
			ans ^= m[i][j];
		}
	}
	printf("%lld", ans);
	return 0;
}

测试结果：

[xor1] 1765ms
[xor2] 1771ms

wtf？仅仅调整了数组维度顺序，为什么会对性能影响这么大？一个尘封多年的知识出现在我的脑中——缓存性能。

缓存性能

我们知道，我们在程序中使用的变量等数据，大多是储存在电脑的内存中。然而，有一些数据会被储存在CPU的缓存中，而读写CPU缓存的速度远远高于读写内存的速度（这就是为什么将循环变量register可以加速代码的运行，此时循环变量直接储存在CPU缓存上）。

但是，CPU缓存的空间是有限的，这部分空间应该用来储存使用频率最高，或者最有可能使用的数据。CPU内部还有L1, L2, L3等多个缓存级别，本文不讨论这部分内容。

其中一个场景，就是在读写一个变量的时候，CPU会帮我们把在内存中临近的数据一并拷贝到缓存中，最典型的例子就是数组读写。当你读取a[1]时，a[2], a[3], ..., a[n]都会被读取进CPU缓存，读取多少取决于缓存大小。如果接下来需要对它们进行操作，只需要在CPU的缓存中读写而不是跑到内存中进行操作。如果下一个要访问的东西不在缓存里，就只好重新从内存中读取内容，而这个操作对现在CPU来说简直慢得令人发指。正因如此，连续访问的速度要优于随机访问的速度。

回到T1。我们发现，以第二份代码（80pts）为参考，对于每一次操作，我们都需要写入m[r + j][c]和m[r + j][c + j + 1]，其中我们遍历j从0到l。我们遍历的是m的第一维，那么对于其中一次操作我们访问m[r+j][c]，CPU缓存的内容应该是m[r+j][c], m[r+j][c+1], ..., m[r+j][c+n]。然而我们下一个想要的操作的内存位于m[r+j+1][c]，和缓存的内容之间有1000个数，这样CPU缓存是很难命中的。

但是如果稍微改一下遍历的顺序，对于其中一次操作，我们访问的是m[c][r+j]，那么缓存的内容应该是m[c][r+j], m[c][r+j+1], ..., m[c][r+j+n]。我们下一次想要访问的应该是m[c][r+j+1]，此时缓存中大概率会有这个数。速度自然就提高了。

但是我们真的需要这几微秒吗？

现在CPU和内存的操作几乎都是微秒级别的，这一点点的差距似乎没有很大影响。然而，九层之台，起于累土。在进行大量内存的访问中，缓存性能是非常重要的性能瓶颈。你也看到了，就T1而言，这种差别是极大的。

资料

what is cpu cache 【C/C++ 性能优化】提高C++程序的缓存命中率以优化性能