c - 优化数组转置功能

Question

我正在做家庭作业，我已经在我的解决方案上停留了几个小时。给我们的问题是优化下面的代码，让它运行得更快，不管它变得多么困惑。我们应该使用诸如利用缓存 block 和循环展开之类的东西。

问题:

//transpose a dim x dim matrix into dist by swapping all i,j with j,i
void transpose(int *dst, int *src, int dim) {
    int i, j;

    for(i = 0; i < dim; i++) {
        for(j = 0; j < dim; j++) {
                dst[j*dim + i] = src[i*dim + j];
        }
    }
}

我目前拥有的:

//attempt 1
void transpose(int *dst, int *src, int dim) {
    int i, j, id, jd;

    id = 0;
    for(i = 0; i < dim; i++, id+=dim) {
        jd = 0;
        for(j = 0; j < dim; j++, jd+=dim) {
                dst[jd + i] = src[id + j];
        }
    }
}

//attempt 2
void transpose(int *dst, int *src, int dim) {
    int i, j, id;
    int *pd, *ps;
    id = 0;
    for(i = 0; i < dim; i++, id+=dim) {
        pd = dst + i;
        ps = src + id;
        for(j = 0; j < dim; j++) {
                *pd = *ps++;
                pd += dim;
        }
    }
}

一些想法，如有错误请指正:

我考虑过循环展开，但我认为这不会有帮助，因为我们不知道 NxN 矩阵是否具有素数维度。如果我检查它，它会包含过多的计算，这只会减慢函数的速度。

缓存 block 不是很有用，因为无论如何，我们将线性访问一个数组 (1,2,3,4)，而另一个我们将以 N 的跳跃访问。虽然我们可以得到函数滥用缓存并更快地访问 src block ，将它们放入 dst 矩阵仍然需要很长时间。

我也尝试过使用指针而不是数组访问器，但我不认为这实际上以任何方式加速了程序。

如有任何帮助，我们将不胜感激。

谢谢

Answer 1

缓存阻塞很有用。例如，假设我们有一个 64 字节大小的缓存行(这是 x86 现在使用的大小)。因此，对于一个足够大的矩阵，使其大于缓存大小，那么如果我们转置一个 16x16 block (因为 sizeof(int) == 4，因此 16 个整数适合缓存行，假设矩阵在缓存行边界上对齐) 我们需要从内存中加载 32 个缓存行(源矩阵中有 16 个，目标矩阵中有 16 个，然后我们才能弄脏它们)并存储另外 16 行(即使存储不是连续的)。相比之下，在没有缓存阻塞的情况下，转置等效的 16*16 元素需要我们从源矩阵加载 16 个缓存行，但为目标矩阵加载并存储 16*16=256 个缓存行。