爪哇：多維數組對一維

Question

例如：

• 一個）int [x][y][z]

  VS

• B）int[x*y*z]

最初以爲我會去a）爲簡單起見

我知道Java不像C那樣在內存中線性存儲數組。但是這對我的程序有什麼影響？

Answer 1

通常情況下，最好的東西對於這樣的問題，搜索anwers時做的是看選用的是如何編譯成JVM字節碼：

multi = new int[50][50]; 
single = new int[2500]; 

這被翻譯成：

BIPUSH 50 
BIPUSH 50 
MULTIANEWARRAY int[][] 2 
ASTORE 1 
SIPUSH 2500 
NEWARRAY T_INT 
ASTORE 2 

因此，如您所見，JVM已知道我們正在討論多維數組。

進一步保持它：

for (int i = 0; i < 50; ++i) 
    for (int j = 0; j < 50; ++j) 
    { 
     multi[i][j] = 20; 
     single[i*50+j] = 20; 
    } 

這被翻譯（跳過週期）分爲：

ALOAD 1: multi 
ILOAD 3: i 
AALOAD 
ILOAD 4: j 
BIPUSH 20 
IASTORE 

ALOAD 2: single 
ILOAD 3: i 
BIPUSH 50 
IMUL 
ILOAD 4: j 
IADD 
BIPUSH 20 
IASTORE 

所以， 你可以看到， 多維陣列在內部處理中虛擬機， 無用的指令產生的開銷， 而使用單一的指令使用更多的指令，因爲抵消是手工計算。

我不認爲表現會是這樣的問題。

編輯：

我做了一些簡單的基準測試，看看是怎麼回事了這裏。 我選擇嘗試不同的例子： 線性讀取， 線性寫入， 和隨機存取。 時間以毫秒錶示（並使用System.nanoTime()計算。 下面是結果：

線性寫

• 尺寸：100×100（10000） 多：5.786591 單：6.131748
• 尺寸：200×200（40000） 多：1.216366 單：0.782041
• 尺寸：500×500（250000） 多：7.177029 單：3.667017
• 尺寸：1000x100 0（1000000） 多：30.508131 單個：18.064592
• 尺寸：2000×2000（400萬） 多：185.3548 單個：155.590313
• 尺寸：5000x5000（25000000） 多：955.5299 單個：923.264417
• 尺寸：10000x10000（100000000） 多：4084.798753 單個：4015.448829

線性讀

• 尺寸：100×100（10000） 多：5.241338 單：5.135957
• 尺寸：200×200（40000） 多：0.080209 單：0.044371
• 尺寸：500×500（250000） 多：0.088742 單：0.084476
• 尺寸：1000×1000（1000000） 多：0.232095 單：0.167671
• 尺寸：2000×2000（400萬） 多：0.481683 單：0.33321
• 尺寸：5000x5000（25000000） 多：1.222339 單：0.828118 大小：10000x10000（100000000） 多：2.496302 單：1.650691

隨機讀

• 尺寸：100x100（10000） Multi：22.317393 Single：8.546134
• 尺寸：200×200（40000） 多：32.287669 單個：11.022383
• 尺寸：500×500（250000） 多：189.542751 單個：68.181343
• 尺寸：1000×1000（1000000） 多：1124.78609 單個：272.235584
• 尺寸：2000×2000（400萬） 多：6814.477101 單：1091.998395
• 尺寸：5000x5000（25000000） 多：50051.306239 單：7028。422262

隨機的一個有點誤導，因爲它爲多維數組生成2個隨機數，而對於單維（和PNRG可能消耗一些CPU）只產生一個隨機數。

請注意，我試圖讓JIT在同一循環的第20次運行後才通過基準測試工作。爲了完整我的Java VM如下：

Java版本 「1.6.0_17」 的Java（TM）SE運行時環境（建立1.6.0_17-B04） 的HotSpot的Java（TM）64位服務器VM（構建14.3-B01，混合模式）

Answer 2

如果你選擇後一種路線，那麼你將不得不爲每一個數組訪問執行算術。這將是一個痛苦和錯誤的傾向（除非你把它包裝在提供這種功能的類中）。

我不認爲在選擇平面數組時有任何（顯着的）優化（尤其是考慮到用於索引的算術）。與優化一樣，您需要執行一些測量並確定它是否真的值得。

Answer 3

使用第一變體（3維），因爲它是更容易理解並有機會少做一些邏輯錯誤（特別是如果你使用它的造型3維空間）

Answer 4

在當前的CPU，非緩存存儲器訪問是幾百倍算術（見this presentation和讀What every programmer should know about memory）慢。 a）選項將導致大約3次內存查找，而b）選項將導致大約1次內存查找。此外，CPU的預取算法也可能無法正常工作。所以b）選項在某些情況下可能會更快（這是一個熱點，並且陣列不適合CPU的緩存）。快多少？ - 這取決於應用程序。

我個人會首先使用a）選項，因爲它會導致更簡單的代碼。如果剖析器顯示數組訪問是一個瓶頸，那麼我會將它轉換爲b）選項，以便有一對幫助器方法用於讀取和寫入數組值（這樣混亂的代碼將被限制爲這兩個方法）。

我做了一個比較3維int數組（「多」列）與等效1維int數組（「單」列）的基準。代碼是here和測試here。我使用JVM選項-server -Xmx3G -verbose:gc -XX:+PrintCompilation（我從以下結果中刪除了調試輸出）將它運行在64位jdk1.6.0_18，Windows 7 x64，Core 2 Quad Q6600 @ 3.0 GHz，4 GB DDR2上。結果如下：

Out of 20 repeats, the minimum time in milliseconds is reported. 

Array dimensions: 100x100x100 (1000000) 
      Multi Single 
Seq Write 1  1 
Seq Read 1  1 
Random Read 99  90 (of which generating random numbers 59 ms) 

Array dimensions: 200x200x200 (8000000) 
      Multi Single 
Seq Write 14  13 
Seq Read 11  8 
Random Read 1482 1239 (of which generating random numbers 474 ms) 

Array dimensions: 300x300x300 (27000000) 
      Multi Single 
Seq Write 53  46 
Seq Read 34  24 
Random Read 5915 4418 (of which generating random numbers 1557 ms) 

Array dimensions: 400x400x400 (64000000) 
      Multi Single 
Seq Write 123  111 
Seq Read 71  55 
Random Read 16326 11144 (of which generating random numbers 3693 ms) 

這表明1維陣列要快一些。雖然差異非常小，但對於99％的應用程序而言，它並不會引人注目。

我也做了一些測量，以便通過用preventOptimizingAway += x * y * z;代替preventOptimizingAway += array.get(x, y, z);來估計在Random Read基準中產生隨機數的開銷，並手動將測量結果添加到上述結果表中。生成隨機數佔隨機讀取基準測試總時間的1/3或更少，所以內存訪問如預期般支配基準。用4維和更多維的數組重複這個基準將會很有趣。可能會使速度差異更大，因爲多維數組的最高級別將適合CPU的高速緩存，並且只有其他級別需要查找內存。