java - 我可以通过转置二维数组来优化我的 java 程序吗？

Question

我有:

final int ROWS = 100000;
final int COLS = 2000;
long[][] m = new long[COLS][ROWS];

然后:

public void xor(int row1, int row2) {
    for (int col=0; col<COLS; col++) {
        m[col][row1] ^= m[col][row2];
    }
}

上面的函数是经过简化的，它在运行中花费了大部分时间。我想知道我是否应该花时间重构我的整个程序以读取“m = new long[ROWS][COLS]”(而不是相反)以获得更好的 RAM 访问。或者我不会用它赢得很多时间吗？

我知道我可以将它与 GPU 并行化，但那是以后的事了。

Answer 1

在我看来，它肯定有助于交换 ROWS 和 COLS。

这个数组的布局(大致)是这样的:[0][0]、[0][1]、[0][2]、... [1][0]、[1][ 1],...等等。在您的代码中，每一列都是连续的内存块，而一行不是。

由于每列是 800000 字节，并且在您的 xor 中如果您访问所有这些方法，则会导致更多缓存未命中。

转置之后，每一行都变成了一 block 连续的内存，而且由于你倾向于对行进行操作，所以它应该会更快。

如果你有 long[][] m = new long[ROWS][COLS];和 for (int col=0; col<COLS; col++) m[row1][col] ^= m[row2][col]; ，在 xor 执行期间，您只需要将两个 16000 字节长的行放在缓存中方法。

但由于我所说的主要基于理论，因此请尝试对两种变体进行基准测试并检查哪一个真正更快。