11

我在 Java 中编写了两个矩阵类，只是为了比较它们的矩阵乘法的性能。一个类 (Mat1) 存储一个double[][] A成员，其中i矩阵的行是A[i]。另一个类 (Mat2) 存储A以及的转置T在哪里。TA

假设我们有一个方阵 M，我们想要 的乘积M.mult(M)。致电产品P。

当 M 是 Mat1 实例时，使用的算法很简单：

P[i][j] += M.A[i][k] * M.A[k][j]
    for k in range(0, M.A.length)

在 M 是 Mat2 的情况下，我使用：

P[i][j] += M.A[i][k] * M.T[j][k]

这是相同的算法，因为T[j][k]==A[k][j]. 在 1000x1000 矩阵上，第二个算法在我的机器上大约需要 1.2 秒，而第一个算法至少需要 25 秒。我期待第二个更快，但不是这么快。问题是，为什么速度这么快？

我唯一的猜测是第二个算法更好地利用了 CPU 缓存，因为数据以大于 1 个字的块的形式被拉入缓存，第二个算法通过仅遍历行从中受益，而第一个算法忽略了拉入的数据通过立即转到下面的行来缓存（在内存中大约有 1000 个字，因为数组是按行主要顺序存储的），没有任何数据被缓存。

我问过某人，他认为这是因为更友好的内存访问模式（即第二个版本会导致更少的 TLB 软故障）。我根本没有想到这一点，但我可以看出它是如何减少 TLB 错误的。

那么，它是什么？还是有其他原因导致性能差异？

4

4 回答 4

5

这是因为您的数据的局部性。

在 RAM 中，矩阵虽然从您的角度来看是二维的，但它当然存储为连续的字节数组。与一维数组的唯一区别是偏移量是通过插入您使用的两个索引来计算的。

这意味着如果您在位置访问元素，x,y它将计算x*row_length + y并且这将是用于引用指定位置的元素的偏移量。

发生的情况是，一个大矩阵不仅仅存储在一个内存页面中（这是您的操作系统管理 RAM 的方式，通过将其拆分为块），因此如果您尝试访问，它必须在 CPU 缓存中加载正确的页面尚不存在的元素。

只要您连续进行乘法运算，就不会产生任何问题，因为您主要使用页面的所有系数，然后切换到下一个系数，但是如果反转索引，则会发生每个单个元素都可能包含在不同的内存页面，所以每次它需​​要向 RAM 请求不同的页面，这几乎适用于你所做的每一次乘法，这就是为什么差异如此之大的原因。

（我相当简化了整个解释，只是为了给你关于这个问题的基本概念）

无论如何，我不认为这是由 JVM 本身引起的。它可能与您的操作系统如何管理 Java 进程的内存有关。

于 2010-10-27T00:53:57.653 回答
0

缓存和 TLB 假设都是合理的，但我想看看你的基准测试的完整代码......而不仅仅是伪代码片段。

另一种可能性是，性能差异是由于您的应用程序在转置版本中为数据数组使用了 50% 以上的内存。如果您的 JVM 的堆大小很小，这可能会导致 GC 运行过于频繁。这很可能是使用默认堆大小的结果。（三个很多1000 x 1000 x 8字节是~24Mb）

尝试将初始和最大堆大小设置为（例如）当前最大大小的两倍。如果这没有区别，那么这不是一个简单的堆大小问题。

于 2010-10-27T00:51:52.977 回答
0

很容易猜测问题可能出在局部性上，也许确实如此，但这仍然是一个猜测。

没有必要猜测。两种技术可能会给您答案——单步执行和随机暂停。

如果您单步执行缓慢的代码，您可能会发现它正在做很多您从未梦想过的事情。比如，你问？试一试就知道了。在机器语言级别上，您应该看到它正在做的事情是有效地通过内部循环而没有浪费动作。

如果它实际上是在没有浪费动作的情况下通过内部循环，那么随机暂停将为您提供信息。由于慢的比快的要花 20 倍的时间，这意味着 95% 的时间它在做一些它不需要做的事情。所以看看它是什么。每次你暂停它，你有 95% 的机会看到那是什么，以及为什么。

如果在慢速情况下，它正在执行的指令看起来与快速情况一样有效，那么缓存局部性是对其缓慢原因的合理猜测。我敢肯定，一旦您消除了可能发生的任何其他愚蠢行为，缓存位置将占主导地位。

于 2010-10-27T01:47:28.887 回答
0

鉴于这组结果，您可以尝试比较 JDK6 和 OpenJDK7 之间的性能......

于 2010-10-27T05:53:31.947 回答