缓存友好的矩阵位移功能 [英] Cache friendly matrix shift function

问题描述

欲二维正方形矩阵的第一行移位到最后一行。所以，如果我有一个像一个矩阵，我想获得B点。

我可以做到这一点使用两个简单的for循环。例如。

  void移动（INT男，诠释N，int类型的[M] [N]）{
    INT I，J，温度;
    对于（i = 1; I＆LT;米;我++）{
        为（J = 0; J＆LT; N; J ++）{
            TEMP = A [I] [J]。
            A [I] [J] = A [I-1] [J]。
            A [I-1] [J] =温度;
        }
    }
}
 

但我希望得到尽可能少的高速缓存未命中越好。如何做任何提示？

解决方案

  / * M是行数; N是列数。 * /
无效matrix_shift（INT男，诠释N，int类型的[M] [N]）{
    为size_t rowbytes = N * sizeof的（INT）;
    INT temprow [N];
    的memcpy（temprow，A，rowbytes）; //商店第一行
    memmove与（A，A + 1，（M-1）* rowbytes）; // 上移
    的memcpy（A +（M-1），temprow，rowbytes）; //替换最后一行
}
 

这保持它简单依赖于它应该在任何公共平台进行高度优化的程序。还有一个额外的行复制，但是这是在一个方阵的陈述的情况下一个次要低效率。

I want to shift the first row of a 2D square matrix to the last row. So if I have a matrix like A, I want to get B.

I can do this using two simple for loops. E.g.

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;
        }
    }
}

But I want to get as few cache misses as possible. Any tip on how to do that?

解决方案

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

This keeps it simple and relies on routines which should be highly optimized on any common platform. There is one extra row copied, but this is a minor inefficiency in the stated case of a square matrix.

这篇关于缓存友好的矩阵位移功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！