转置一个矩阵需要什么
文章摘要
这篇文章通过”矩阵转置”这个看似平凡的操作（把 src[r,c] 复制到 dst[c,r]），揭示了 CPU 架构层面的深刻挑战：内存延迟、缓存组织、以及编译器自动向量化的局限。文章最终把最优实现做到了比朴素实现快约 25 倍。
朴素实现（3.90 周期/元素）：按行优先扫描源矩阵，同时按列优先写入目标矩阵。这里有两条数据流：读流是顺序访问，非常高效（处理器加载 64 字节缓存行，硬件预取器识别线性模式，约 1.25 周期/元素）；写流则是跨步访问（元素间隔 N 字节），无法有效缓存，处理器必须反复加载-修改-存储缓存行，代价高达 5–40 周期/元素，具体取决于矩阵相对缓存层级的大小。
缓存别名问题：某些矩阵尺寸（2 的幂）会触发性能”悬崖”，因为跨步访问会把多个元素映射到同一个缓存组（cache set），实际减少了可用缓存容量。解决办法是给矩阵填充（padding）到”步长 = 缓存行大小 × 奇数”的维度，让访问均匀分布到各缓存组。
分块/平铺优化（1.46 周期/元素）：把矩阵分解成 64×64 的块。由于”转置保持二维数据局部性”，每个块可以独立处理，其工作集完全装进 L1d 缓存（8KB），从而无论矩阵总大小如何都能消除缓存未命中。
软件预取（1.35 周期/元素）：用 _mm_prefetch() 手动指示处理器提前加载下一个块，把停顿从 22% 降到 9.6%。
64 位 SIMD（0.74 周期/元素）：用 64 位寄存器一次处理 8 字节，需要把块递归分解成 8×8 矩阵（8→4→2→1 三层），用位运算（掩码、移位、或运算）并行转置多个 2×2 块矩阵，相比纯分块转置再提速 1.8 倍。
256 位 SIMD（0.49 周期/元素）：用 AVX2 实现 32×32 转置（五层分解），主要靠 _mm256_shuffle_epi8、_mm256_permute2x128_si256、_mm256_blendv_epi8 三条指令。生成的代码有 393 条以上指令，需要在 16 个 AVX 寄存器间平衡指令交错以最大化执行单元利用率。
缓冲输出（0.35 周期/元素）：最后的优化涉及存储缓冲策略。
关键结论：内存访问模式（而非计算）主导性能，顺序读远胜跨步写；分块分解是根本，多层分解分别服务于缓存优化、寄存器利用和并行计算；对大多数应用而言，仅用分块转置就能获得”稳定良好的性能”，而 25 倍加速需要专门知识和大量实现复杂度。
HN 评论精华
asplake 提出疑问：转置是否常见到值得通过”隐式转置”的操作版本来避免它？rhdunn 回答：numpy 和 pytorch 之类的库已经这么做了——它们把矩阵存为带步长（stride）信息的一维数组，转置只需修改步长等参数而无需移动数据。但 threatripper 和 yccs27 指出，对某些操作（如 A + A^T），显式或隐式的转置访问模式是绕不开的。
darkinvisible 问是否用了原地交换的 XOR 技巧。adrian_b 给出权威纠正：对于存储在内存中的数据，原地交换是低效的——最高效的内存值交换是”两次加载 + 两次存储”，因此在整个自动计算机的历史上，XOR 技巧从未对内存值交换有用过；只有在 CPU 向量寄存器/矩阵寄存器内交换时，才用专门的 shuffle 指令。
amelius 注意到最后那个图”看起来几乎像 FFT 的洗牌”。yccs27 确认：”拓扑结构完全相同！把每个 shuffle/blend 换成乘以单位根再相加，你就得到了 FFT！”
关于”有没有语言或优化器能简化这种繁琐工作”：mlochbaum 推荐 Singeli，并贴出了自己用它实现的通用 AVX2 转置内核（用 unpack 指令而非 shuffle+blend，可能更快）；也有人提到 MATLAB、CUDA 及其库。
usernametaken29 感慨线性代数”纸上简单、实践极难”：理论上的简单想法，实现时几乎总会撞上二次方运行时，在 CPU 上做好非常困难。bsoles 附和：基础线性代数理论容易，但正确的工程实践极难，有人用整个职业生涯研究矩阵运算中的误差传播、QR 分解、SVD 等求逆方法。
Const-me 认为 AVX2 SIMD 版本并非最优（指令太多、需要常量向量），并给出了自己的 godbolt 实现。peterabbitcook 补充：文章对 padding 重要性强调不足，BLAS/LAPACK 的 LDA/LDB 参数可以针对系统页大小调优，而且常常可以通过”重塑问题”而非”重塑数据”来彻底避免转置。多位评论者盛赞文章配图精美、技术深入，认为这类公开技术写作”价值连城”。