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

Question

我用Java编写了两个矩阵类,只是为了比较矩阵乘法的性能.一个类(Mat1)存储矩阵double[][] A行所在的成员.其他类(MAT2)存储和其中是的转置.iA[i]ATTA

假设我们有一个方矩阵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故障.

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

Answer 1

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

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

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

会发生的事情是,一个大矩阵不会存储在一个内存页面中(这是操作系统管理RAM的方式,通过将其拆分为块),因此如果您尝试访问一个内存,它必须在CPU缓存中加载正确的页面尚未出现的元素.

只要你连续地进行乘法就不会产生任何问题,因为你主要使用页面的所有系数然后切换到下一个系数,但是如果你反转索引,那么每个元素都可以包含在不同的内存页面,所以每次它需​​要向RAM请求一个不同的页面,这几乎是你做的每一次乘法,这就是为什么差异如此整洁.

(我宁愿简化整个解释,只是为了给你解决这个问题的基本思路)

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