缓存行局部性差是主因：朴素转置按行读a、按列写b，导致写bj频繁cache miss；分块转置选tile_size=16或32，兼顾l1缓存容量与对齐友好性。
为什么直接遍历转置在大数组上很慢
缓存行（cache line）局部性差是主因。普通 transpose(A, B) 按行读 A、按列写 B，每次写 B[j][i] 都大概率触发 cache miss——尤其当矩阵宽 > 64 字节（典型 cache line 大小）时，相邻写入地址相距一整行，完全跳着访问。
这和内存带宽无关，是硬件预取器失效 + 多次 DRAM 行激活导致的延迟放大。实测 4096×4096 float 矩阵，朴素转置比分块慢 3–5 倍。
分块大小选多少才合适
核心约束是：一个块必须能完整放进 L1 数据缓存（通常 32 KiB），且避免 bank conflict 和 false sharing。
- 单个
float占 4 字节，L1d 缓存 ≈ 32 KiB → 最多容纳约 8192 个元素 - 若用正方形块
TILE_SIZE × TILE_SIZE，则TILE_SIZE² ≤ 8192→TILE_SIZE ≤ 90 - 但还要留空间给临时寄存器、循环变量、以及避免跨 cache line 拆分——实践中
TILE_SIZE = 16或32更稳 -
TILE_SIZE = 16：块占 1024 字节（16×16×4），刚好 16 行 cache line，对齐友好，LLVM/GCC 向量化也容易识别
不要盲目设成 64：它会让单块达 16 KiB，留给其他数据的空间太紧，反而增加 cache pressure。
分块转置的 C++ 实现要点
关键不是“把循环拆成四层”，而是保证每个内层块操作都具备空间局部性：
- 外两层遍历块坐标（
ii,jj），内两层遍历块内偏移（i,j） - 先将
A[ii + i][jj + j]读入寄存器或小数组，再批量写入B[jj + j][ii + i] - 必须用
restrict或__restrict提示编译器指针不重叠，否则 GCC/Clang 不敢重排访存
void transpose_blocked(float* __restrict A, float* __restrict B,
int N, int TILE_SIZE = 32) {
for (int ii = 0; ii <p>注意：这里用一维数组模拟二维（<code>A[i<em>N + j]</em></code>），避免 <code>operator[]</code> 多级指针跳转；索引计算必须用 <code>(jj+j)N + (ii+i)</code> 而非 <code>B[jj+j][ii+i]</code> —— 后者隐含二级指针解引用，在非 <code>-O3</code> 下开销明显。</p><h3>哪些情况分块反而更慢<ul>
<li>矩阵很小（如 <code>N ）：分块引入的循环开销和分支预测失败压倒收益 </code>
</li>
<li>非方阵且长宽悬殊（如 <code>1024×16</code>）：块内大量越界检查（<code>ii+i ）拖慢内层，此时更适合按源矩阵行连续读、目标矩阵列连续写 + 手动 prefetch </code>
</li>
<li>使用 <code>std::vector<:vector>></:vector></code> 存储：每行堆分配、地址不连续，分块失去意义；必须用扁平 <code>std::vector<float></float></code> 或裸 <code>new float[N*N]</code> </li>
<li>开启 <code>-O0</code> 编译：分块代码的循环嵌套会让未优化代码雪上加霜；至少要 <code>-O2</code> </li>
</ul>
</h3><p>真正起效的前提是：数据连续 + 编译器能识别访存模式 + 矩阵足够大（建议 > 256×256）。</p><p>分块本身不难写，难的是确认你面对的是 cache miss 主导的瓶颈——先跑一下 perf record -e cache-misses,instructions ./a.out，看 cache miss rate 是否 > 15%。不是所有“慢”都该用分块解决。</p>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
