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对象，那么您应该考虑这样一个事实，即这些对象所占用的空间会进一步减弱这两个类别占用的预期空间之间的差异。