我用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故障.
那么,这是什么？还是有其他原因导致性能差异？
这基本上是对这个问题的重述:Java:多维数组与一维数,但对于C#.
我有一定数量的元素可以作为网格存储.我应该使用数组[x*y]还是数组[x] [y]？
编辑:哦,所以有一维数组[x*y],多维数组[x,y]和锯齿状数组[x] [y],我可能想要锯齿状？
当我在大学里使用C++时,我被告知尽可能使用多维数组(特此是MDA),因为它表现出更好的内存局部性,因为它分配在一个大块中.另一方面,阵列阵列(AoA)被分配在多个较小的块中,可能散布在物理存储器中的任何位置,无论何处发现空位.
所以我想第一个问题是:这是一个神话,还是值得关注的建议？
假设它是后者,那么接下来的问题就是如Java这样没有真正MDA的语言.当然,用1DA模拟MDA并不难.从本质上讲,具有MDA的语言的语法糖可以实现为对没有MDA的语言的库支持.
这值得努力吗？对于像Java这样的语言来说,这是一个太低的优化问题吗？我们应该放弃数组并使用Lists甚至原语吗？
另一个问题:在Java中,一次分配AoA(new int[M][N])可能会产生不同的内存分配(而不是分层次地)(new int[M][]; for (... new int[N])