我用 Java 编写了两个矩阵类,只是为了比较它们的矩阵乘法的性能。一个类(Mat1)存储一个double[][] A
成员所在行i
矩阵的值为A[i]
。其他类(Mat2)存储A
and T
where 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 个字的块的形式被拉入缓存,而第二个算法通过仅遍历行而受益,而第一个算法则忽略拉入的数据通过立即转到下面的行(内存中约 1000 个字,因为数组按行主要顺序存储)来进行缓存,没有缓存任何数据。
我问过某人,他认为这是因为更友好的内存访问模式(即第二个版本会导致更少的 TLB 软故障)。我根本没有想到这一点,但我可以看出它是如何减少 TLB 错误的。
那么,是哪一个呢?或者还有其他原因导致性能差异?
这是因为您的数据的位置。
在 RAM 中,矩阵虽然从您的角度来看是二维的,但它当然存储为连续的字节数组。与一维数组的唯一区别是偏移量是通过对您使用的两个索引进行插值来计算的。
这意味着如果您访问位置处的元素x,y
它会计算x*row_length + y
这将是用于引用指定位置处的元素的偏移量。
发生的情况是,一个大矩阵不仅仅存储在内存页面中(这就是操作系统管理 RAM 的方式,通过将其分割成块),因此如果您尝试访问某个内存页面,它必须在 CPU 缓存内加载正确的页面。尚不存在的元素。
只要您连续进行乘法,就不会产生任何问题,因为您主要使用一页的所有系数,然后切换到下一页,但如果您反转索引,会发生的情况是每个元素都可能包含在不同的内存页面,因此每次它都需要向 RAM 请求不同的页面,这几乎对于您执行的每一次乘法都是如此,这就是差异如此巧妙的原因。
(我相当简化了整个解释,只是为了给您围绕这个问题的基本想法)
无论如何,我不认为这是 JVM 本身造成的。它可能与您的操作系统如何管理 Java 进程的内存有关。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)