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

Question

3

我有：

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并行处理，但那是以后的事情。

- Albert Hendriks

你想做什么？除非我更了解你试图通过优化解决的问题，否则我无法回答。 - Jason

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Karol S · Accepted Answer

在我看来，交换行和列一定会有帮助。

这个数组的布局大致如下：[0][0]、[0][1]、[0][2]、…… [1][0]、[1][1]、…… 以此类推。在你的代码中，每列是连续的内存块，而每行却不是。

由于每列都有800000个字节，在你的xor方法中，你要访问它们所有，这就会导致更多的缓存未命中。

转置后，每行变成了连续的内存块，而且由于你通常对行进行操作，所以应该会更快。

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

但是，由于我的说法大部分是基于理论的，所以请尝试对两种变体进行基准测试，并找出哪一个真正更快。