JVM空間複雜度的細節：單鏈表VS雙向鏈表

Question

我所遇到的一個奇怪的情況：學生（我在這方面的教學助理）必須實現自己的單鏈表（SLL）的版本，根據經驗與雙鏈表的Java標準庫實現進行比較。

而這正是這樣會很奇怪：我已經看到多個學生注意，DLL型材在大約0.5％的額外空間利用率與含有相同類型的元素相等數量的SLL。所有的數據結構的基本分析都告訴我SLL每個節點有2個引用（1到下一個元素，1到包含的值），而DLL有3個（對前一個元素的額外引用）。換句話說，每個節點的空間使用量增加了50％（不考慮包含值的大小）。

所包含的值大多是整數值的對象，所以我不認爲包含的值的大小事務太多了這裏。

是什麼原因導致幅度差這2的訂單？我不完全確定「JVM /集合庫優化」可以覆蓋整個差異;否則它必須是JVM/java標準庫優化的一個地獄。

Answer 1

使用應該是在Oracle JVM/OpenJDK的同樣爲64位JVM使用32位的引用（壓縮的糟糕）

對於具有兩個引用

header: 12 bytes 
two references: 8 bytes 
alignment padding: 4 bytes 

總節點的空間每個節點爲24個字節，因爲默認情況下所有對象都按8字節偏移對齊。

對於節點具有三個引用

header: 12 bytes 
three references: 12 bytes 
alignment padding: 0 bytes 

總再次24個字節。

真正的問題是你爲什麼看到任何差異。這很可能是由於內存記帳不準確。

JVM使用TLAB（線程本地分配緩衝區）這允許JVM中的線程抓取內存塊並從這些塊併發分配。不利的一面是，你只能看到普通Eden空間使用了多少內存，即你不知道每個塊的使用量。

對此的一種簡單的方法是關閉，讓你逐字節的記憶賬戶（在某些性能爲代價）

胃內的TLAB請在命令行上嘗試-XX:-UseTLAB以禁用TLAB，您將看到分配的每個對象的大小。

Answer 2

很難看出爲什麼有任何差異可言。

首先注意到Java對象的頭部形式具有相當大的開銷。這減少了你50％的期望。接下來，當您考慮引用通常是4個字節寬（在64位HotSpot上給定壓縮的OOP）時，但該內存始終以大小可被8整除的塊分配，您可以看到什麼是保留爲未使用的4個字節在一個結構的末尾成爲您在DLL示例中的第三個參考。

Answer 3

除了什麼馬爾科說，大約每個鏈表節點對象的內存開銷，存儲在這些節點的「整型值對象」可能不會像你想象的那麼小。 java的DLL的元素類型是一個通用參數，並且java中的通用參數始終是對象（從來不是原語），所以即使您可能將其添加到Java的DLL，它們也會轉換爲對象（請參閱裝箱/取消裝箱）以及存儲爲對象。

如果你的學生的SLL存儲實際的原始文件ints，那麼我實際上會希望他們的類佔用的空間比Java的DLL少得多。如果您的學生存儲Integer對象，那麼您應該考慮這樣一個事實，即這些對象所佔用的空間會進一步減弱這兩個類別佔用的預期空間之間的差異。