java - 为什么这些矩阵乘法的性能如此不同？

Question

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

假设我们有一个方阵 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 个字的 block 的形式被拉入缓存，第二种算法通过仅遍历行从中受益，而第一种算法忽略数据通过立即转到下面的行(在内存中约 1000 个字，因为数组按行主要顺序存储)被拉入缓存，没有缓存的数据。

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

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

Answer 1

这是因为您的数据的位置。

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

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

发生的事情是一个大矩阵不只存储在一页内存中(这是你的操作系统管理 RAM 的方式，通过将它分成 block )所以如果你尝试它必须在 CPU 缓存中加载正确的页面访问一个不存在的元素。

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

(我简化了整个解释，只是为了给你围绕这个问题的基本思路)

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