JVM space 复杂性细节：单链表与双链表
JVM space complexity details: Singly Linked Lists vs Doubly Linked Lists
我遇到了一个奇怪的情况，学生（我是这方面的助教）必须实现他们自己的单向链表 (SLL) 版本，并根据经验将其与 Java双向链表的标准库实现。
这就是它变得奇怪的地方：我看到多名学生注意到，与包含相同数量的相同类型元素的 SLL 相比，DLL 配置文件的利用率大约高出 0.5% space。一直以来，对数据结构的基本分析告诉我，SLL 每个节点有 2 个引用（1 个指向下一个元素，1 个指向包含的值），而 DLL 有 3 个（对前一个元素的附加引用）。换句话说，每个节点的使用量增加了 50% space（忽略包含值的大小）。
包含的值主要是整数值对象，所以我认为包含值的大小在这里并不重要。
是什么导致了这种 2 个数量级 的差异？我不完全确定 "JVM/collections libraries optimization" 可以弥补全部差异；否则它必须是 JVM/java std lib 优化的地狱。
很难看出为什么会有 任何 差异。
首先请注意，Java object 以其 header 的形式具有显着的开销。这会降低您 50% 的期望值。
接下来，当您考虑到引用通常为 4 字节宽（给定 64 位 HotSpot 上的压缩 OOP），但内存总是分配在大小可被 8 整除的块中时，您可以看到什么在一个结构的末尾留下未使用的 4 个字节成为您在 DLL 示例中的第三个引用。
除了Marko所说的每个链表节点对象的内存开销，你在这些节点中存储的"Integer value objects"可能并没有你想象的那么小。 java 的 DLL 的元素类型是一个泛型参数，java 中的泛型参数始终是对象（绝不是基元），因此即使您可能将 int 添加到 Java 的 DLL，它们被转换为对象（参见 boxing/unboxing）并存储为对象。
如果您学生的 SLL 存储实际原始 ints，那么我实际上希望他们的 类 占用的 space 比 Java 的要少得多动态链接库。如果你的学生存储 Integer 个对象，那么你应该考虑这样一个事实，即这些对象所占用的 space 进一步淡化了两个 类 所占用的预期 space 之间存在的任何差异。 .
对于具有 32 位引用（压缩 oops）的 64 位 JVM，Oracle JVM/OpenJDK 上使用的 space 应该相同
对于有两个引用的节点
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 中的线程获取内存块并从这些块中并发分配。不利的一面是，您只能看到从公共伊甸园 space 使用了多少内存，即您不知道每个块使用了多少。
解决此问题的一个简单方法是关闭 TLAB，它为您提供逐字节的内存帐户（以牺牲一些性能为代价）
i.g。尝试在命令行上 -XX:-UseTLAB 禁用 TLAB，您将看到分配的每个对象的大小。
我遇到了一个奇怪的情况，学生（我是这方面的助教）必须实现他们自己的单向链表 (SLL) 版本，并根据经验将其与 Java双向链表的标准库实现。
这就是它变得奇怪的地方：我看到多名学生注意到，与包含相同数量的相同类型元素的 SLL 相比，DLL 配置文件的利用率大约高出 0.5% space。一直以来，对数据结构的基本分析告诉我，SLL 每个节点有 2 个引用（1 个指向下一个元素，1 个指向包含的值），而 DLL 有 3 个（对前一个元素的附加引用）。换句话说，每个节点的使用量增加了 50% space（忽略包含值的大小）。
包含的值主要是整数值对象，所以我认为包含值的大小在这里并不重要。
是什么导致了这种 2 个数量级 的差异？我不完全确定 "JVM/collections libraries optimization" 可以弥补全部差异；否则它必须是 JVM/java std lib 优化的地狱。
很难看出为什么会有 任何 差异。
首先请注意，Java object 以其 header 的形式具有显着的开销。这会降低您 50% 的期望值。
接下来，当您考虑到引用通常为 4 字节宽（给定 64 位 HotSpot 上的压缩 OOP），但内存总是分配在大小可被 8 整除的块中时，您可以看到什么在一个结构的末尾留下未使用的 4 个字节成为您在 DLL 示例中的第三个引用。
除了Marko所说的每个链表节点对象的内存开销，你在这些节点中存储的"Integer value objects"可能并没有你想象的那么小。 java 的 DLL 的元素类型是一个泛型参数，java 中的泛型参数始终是对象（绝不是基元），因此即使您可能将 int 添加到 Java 的 DLL，它们被转换为对象（参见 boxing/unboxing）并存储为对象。
如果您学生的 SLL 存储实际原始 ints，那么我实际上希望他们的 类 占用的 space 比 Java 的要少得多动态链接库。如果你的学生存储 Integer 个对象，那么你应该考虑这样一个事实，即这些对象所占用的 space 进一步淡化了两个 类 所占用的预期 space 之间存在的任何差异。 .
对于具有 32 位引用（压缩 oops）的 64 位 JVM，Oracle JVM/OpenJDK 上使用的 space 应该相同
对于有两个引用的节点
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 中的线程获取内存块并从这些块中并发分配。不利的一面是，您只能看到从公共伊甸园 space 使用了多少内存，即您不知道每个块使用了多少。
解决此问题的一个简单方法是关闭 TLAB，它为您提供逐字节的内存帐户（以牺牲一些性能为代价）
i.g。尝试在命令行上 -XX:-UseTLAB 禁用 TLAB，您将看到分配的每个对象的大小。