2

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

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

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

是什么导致了这2 个数量级的差异？我不完全确定“JVM/集合库优化”可以涵盖全部差异；否则它必须是一个 JVM/java 标准库优化的地狱。

4

3 回答 3

3

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

对于具有两个引用的节点

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，它为您提供逐字节的内存帐户（以牺牲一些性能为代价）

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

于 2015-02-25T08:54:23.847 回答
2

很难看出为什么有任何区别。

首先请注意，Java 对象在其标头中具有显着的开销。这降低了你 50% 的期望值。

接下来，当您考虑到引用通常是 4 字节宽时（给定 64 位 HotSpot 上的压缩 OOP），但内存总是分配在大小可以被 8 整除的块中，您可以看到剩下的未使用的 4一个结构末尾的字节成为 DLL 示例中的第三个引用。

于 2015-02-24T14:02:51.733 回答
2

除了 Marko 所说的每个链表节点对象的内存开销之外，存储在这些节点中的“整数值对象”可能并不像您想象的那么小。Java DLL 的元素类型是泛型参数，Java 中的泛型参数始终是对象，（绝不是原始数据），因此即使您可能将ints 添加到 Java 的 DLL 中，它们也会被转换为对象（参见装箱/拆箱）并存储作为对象。

如果您学生的 SLL 存储实际int的原语，那么我实际上希望他们的类占用的空间比 Java 的 DLL 少得多。如果您的学生存储Integer对象，那么您应该考虑这样一个事实，即这些对象占用的空间进一步稀释了两个班级占用的预期空间之间存在的任何差异。

于 2015-02-24T14:14:42.583 回答