编译运行以下程序初始化一个数组 每个元素都为1两种遍历方式 1.行优先 2.列优先只有循环的顺序不同但性能差异却很大i*Nj i是行 j是列行优先一行一行遍历列优先一列一列遍历#includeiostream#includechrono#includevectorusingnamespacestd;constexprintN8192;volatilelonglongsink;doubletest(constint*a,boolrow){autot0chrono::steady_clock::now();longlongsum0;if(row)for(inti0;iN;i)for(intj0;jN;j)suma[i*Nj];elsefor(intj0;jN;j)for(inti0;iN;i)suma[i*Nj];sinksum;returnchrono::durationdouble(chrono::steady_clock::now()-t0).count();}intmain(){vectorinta((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 LocalityCache LineCache Missthink:数组下标与空间 内存与缓存内存就是用来临时存放数据核心访问内存行优先遍历内存地址连续递增。每次读入一个cache line通常 64 字节 16 个 int后面 15 次访问都命中缓存几乎不访问主存。列优先相邻两次访问地址相隔 N 个 intN*4 32KB。每次访问都跳到很远的内存几乎每次都cache miss。更糟的是一个 cache line 里那 16 个 int 这次只用 1 个等下次循环j1再用到时早已被换出缓存。所以缓存完全没有被利用。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[i1]。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 少干活、少等待、跑得更快。
