缓存友好矩阵移位函数

Question

我想将二维方阵的第一行移动到最后一行。所以如果我有一个像 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;
        }
    }
}

但我希望尽可能少的缓存未命中。关于如何做到这一点的任何提示？

Answer 1

/* 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
}

这使它变得简单并且依赖于应该在任何通用平台上高度优化的例程。复制了一个额外的行，但这在方阵的上述情况下效率不高。