java - JVM 空间复杂度详细信息 : Singly Linked Lists vs Doubly Linked Lists

Question

我遇到过一个奇怪的情况，学生(我在这方面是一名助教)必须实现他们自己的单向链表 (SLL) 版本，并将其与双链表的 Java 标准库实现进行经验比较链表。

这就是它变得奇怪的地方:我看到多名学生注意到，与包含相同数量的相同类型元素的 SLL 相比，DLL 配置文件的额外空间利用率大约为 0.5%。一直以来，对数据结构的基本分析告诉我，SLL 每个节点有 2 个引用(1 个指向下一个元素，1 个指向包含的值)，而 DLL 有 3 个(对前一个元素的附加引用)。换句话说，每个节点的空间使用量增加了 50%(不考虑包含值的大小)。

包含的值主要是整数值对象，所以我认为包含值的大小在这里并不重要。

是什么导致了这种2 个数量级 的差异？我不完全确定“JVM/集合库优化”是否可以涵盖所有差异；否则它必须是 JVM/java std lib 优化的 hell 。

Answer 1

对于具有 32 位引用(压缩 oops)的 64 位 JVM，在 Oracle JVM/OpenJDK 上使用的空间应该相同

对于有两个引用的节点

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 中的线程获取内存块并从这些 block 中并发分配。不利的一面是，您只能看到公共(public) Eden 空间使用了多少内存，即您不知道每个 block 使用了多少。

解决此问题的一个简单方法是关闭 TLAB，它为您提供逐字节的内存帐户(以牺牲一些性能为代价)

即尝试在命令行上使用 -XX:-UseTLAB 来禁用 TLAB，您将看到分配的每个对象的大小。