缓存友好的矩阵移位function
我想将2D方阵的第一行移到最后一行。 所以如果我有像A这样的矩阵，我想得到B.
我可以使用两个简单的for循环来做到这一点。 例如
void shift(int M, int N, int A[M][N]){ int i, j,temp; for (i = 1; i < M; i++){ for (j = 0; j < N; j++){ temp=A[i][j]; A[i][j]=A[i-1][j]; A[i-1][j]=temp; } } } 但我希望尽可能少地缓存未命中数。 有关如何做到这一点的任何提示？
/* M is the number of rows; N is the number of columns. */ void matrix_shift(int M, int N, int A[M][N]) { size_t rowbytes = N * sizeof(int); int temprow[N]; memcpy(temprow, A, rowbytes); // store first row memmove(A, A + 1, (M-1) * rowbytes); // shift up memcpy(A + (M-1), temprow, rowbytes); // replace last row }
这样可以保持简单并依赖于应该在任何通用平台上进行高度优化的例程。 复制了一个额外的行，但在方阵的所述情况下这是一个次要的低效率。
我刚刚看到你对4×4矩阵的评论。 一个4×4 int数组适合单个缓存行（在现代x86 CPU上，缓存行为64B）。 在这种情况下，您希望编译器生成类似的东西
## matrix address in [rdi] movups xmm0, [rdi] movups xmm1, [rdi+16] movups xmm2, [rdi+32] movups xmm3, [rdi+48] movups [rdi], xmm1 ; doing all the stores after all the loads avoids any possible false dependency movups [rdi+16], xmm2 movups [rdi+32], xmm3 movups [rdi+48], xmm0
或者可能更少的AVX 256b加载/存储，但未对齐的AVX可能会更糟。 如果arrays是64B对齐的，则所有加载/存储都不会跨越缓存线边界。 所以2x vmovups ymm加载，一个vmovups ymm存储，一个vmovups xmm存储（到最后），和一个vextractf128存储（到开始）。
如果你很幸运，当函数内联到一个编译时间常数值为4的调用者时，John的memcpy会优化到类似的东西。
对于微小的arrays，问题不是缓存未命中，而是如何以尽可能少的开销实现整个副本。 我在下面提到的关于引入间接级别的想法并不是一个好主意，因为加载所有数据并将其存储回来真的很便宜。
对于大型矩阵：
如果你在矩阵的末尾留出另一行的空间，你可以将第一行复制到这个额外的空间，并将指针传递给第二行。
这使您可以暂时拥有矩阵的不同视图，但这不是一个可重复的过程。
如果你有一个大的缓冲区，你可以继续以这种方式旋转矩阵行，直到你到达保留空间的末尾并且必须将数组复制回缓冲区的顶部。 这可以最大限度地减少复制开销，但确实意味着您正在触摸一些新内存。
如果行复制开销是一个大问题，引入一个间接级别可能是个好主意。 根据在对行进行洗牌后使用它的代码的访问模式，这可能会更糟。 这可能是指向行指针数组的用例，而不是普通的2D数组。
您可以而且应该使用一个大的分配为矩阵分配存储，而不是分别分配每一行。 std::vector的C ++ std::vector并不理想。 初始化你的int *rows[M]只需要一个&A[i][0]的循环，所以它只是数学，而不是多次加载或分配。
通过这个间接表访问数组用指针追逐替换i*N + j数学：加载rows[i] ，然后用j索引。
当您不需要数组的混乱视图时，您可以直接访问它，但是如果您希望能够对数组进行永久性重排，则它的所有用户始终必须通过间接层。