企业官网建设流程全解析

编译运行以下程序：
初始化一个数组 每个元素都为1
两种遍历方式 1.行优先 2.列优先
只有循环的顺序不同，但性能差异却很大
i*N+j i是行 j是列
行优先，一行一行遍历；列优先，一列一列遍历

#include<iostream>#include<chrono>#include<vector>usingnamespacestd;constexprintN=8192;volatilelonglongsink;doubletest(constint*a,boolrow){autot0=chrono::steady_clock::now();longlongsum=0;if(row)for(inti=0;i<N;++i)for(intj=0;j<N;++j)sum+=a[i*N+j];elsefor(intj=0;j<N;++j)for(inti=0;i<N;++i)sum+=a[i*N+j];sink=sum;returnchrono::duration<double>(chrono::steady_clock::now()-t0).count();}intmain(){vector<int>a((size_t)N*N,1);cout<<"行优先: "<<test(a.data(),true)<<" s\n";cout<<"列优先: "<<test(a.data(),false)<<" s\n";}

得到结果：

行优先: 0.0988227 s 列优先: 0.746619 s

为什么列优先明显慢这么多？

KeyWord：
空间局部性（Spatial Locality）
Cache Line
Cache Miss

think:
数组下标与空间 内存与缓存

内存就是用来临时存放数据

核心：访问内存

• 行优先遍历：内存地址连续递增。每次读入一个cache line（通常 64 字节 = 16 个 int），后面 15 次访问都命中缓存，几乎不访问主存。

• 列优先：相邻两次访问地址相隔 N 个 int（N*4 = 32KB）。每次访问都跳到很远的内存，几乎每次都cache miss。
  更糟的是：一个 cache line 里那 16 个 int 这次只用 1 个，等下次循环（j+1）再用到时，早已被换出缓存。所以缓存完全没有被利用。

1.主存与缓存

问题：CPU从主存读取数据比执行一条命令要慢几十倍。

解决：引入缓存——在 CPU 和主存之间放几层又小又快的存储器，把最近用过的数据留在里面。
本质是一个赌注——程序倾向于重复访问刚用过或附近的数据（时间局部性 + 空间局部性）。这个赌注在实践中成功率极高（90%+）。

1.1存储层级

存储器的访问速度，主要取决于CPU 要"走多远"去拿数据。——信号在导线里传播需要时间，物理距离越远，延迟越高。

容量 速度 成本/字节 寄存器 几十字节 ~0.3 ns 最高 ↓ L1 缓存 ~32 KB ~1 ns 很高 ↓ L2 缓存 ~256KB~1MB ~4 ns 高 ↓ L3 缓存 ~几MB~几十MB ~15 ns 中 ↓ 主存DRAM ~几GB~几百GB ~80 ns 低 ↓ SSD/磁盘 TB级 微秒~毫秒 最低

越往上越快、越小、越贵。CPU 访问数据时逐层往下找，找到就停。

1.2 cache miss

当 CPU 要的数据不在当前缓存层，就叫一次 cache miss。它必须去下一层（甚至主存）取，取回来的路上 CPU 可能就停在那里等（stall）
类型：

• 冷miss ： 第一次访问，缓存中没有
• 容量miss ： 缓存装不下（比L3还大），自然miss
• 冲突miss ：

2.空间局部性（Spatial Locality）

局部性（locality） 是程序访问内存时的一种统计规律，分为：

• 时间局部性：如果一个数据刚被访问过，那它很可能马上又被访问。（比如循环里的计数器变量 sum，每次迭代都用。）
• 空间局部性：如果一个数据被访问了，那它附近的地址很可能很快也被访问。（比如遍历数组，访问了 a[i]，紧接着就访问 a[i+1]。）

2.1 cache line

由于程序通常有空间局部性这个规律，硬件（CPU 的缓存控制器）通常按 64 字节的cache line整块搬。

缓存行——缓存的最小搬运单位
CPU 不是按一个字节或一个 int 来搬运数据的，而是按固定大小的块整块搬运，这个块叫 cache line（缓存行），主流大小是64 字节。

3.优美的代码

列优先代码是劣质代码，容量 miss + 空间局部性 完全浪费。

4.编译器优化

g++ 程序文件-O2-fno-loop-interchange -fno-tree-vectorize -fno-unroll-loops-o执行文件

这样编译使差距更大
——关闭三个针对列优先遍历的优化

编译器优化：重新安排代码的执行方式，让 CPU 少干活、少等待、跑得更快。