在 Boost 上，我阅读了有关将信息屏蔽为指针以节省内存的信息（此处：https ://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/set_multiset.html，optimize_size ）。这怎么可能？我在某处读到指针仅使用 48 位，但长度为 64 位，因此您可以通过位移将信息推送到更高位。那是对的吗？
为什么他们使用整数来存储 rb-trees 的颜色信息？使用字符不是更有效吗？
问问题
71 次
1 回答
1
在 Boost 上，我阅读了有关将信息屏蔽为指针以节省内存的信息（此处：https ://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/set_multiset.html，optimize_size ）。这怎么可能？
答案在您发布的链接中给出：
如果指针对齐是偶数，钩子会将红黑树节点的颜色位嵌入到父指针中。
当对齐为偶数时，指针值的最低位始终为零，可用于存储颜色位。每当需要加载指针或颜色时，都需要清除其他位，这会增加轻微的性能影响，但作为回报，它会在挂钩中节省指针的空间。但在实践中，性能开销通常被 CPU 中指令的并行执行所隐藏。
我在某处读到指针仅使用 48 位，但长度为 64 位，因此您可以通过位移将信息推送到更高位。那是对的吗？
在 64 位系统上，指针的大小是 64 位，但有些系统没有实现全宽指针，而是使用更少的位进行寻址。当高位未使用时，它们需要具有特定值（x86 中的值）。Wikipedia很好地概述了不同的 CPU，包括 x86。您会看到不同的架构有不同的限制，有些甚至实现了全宽 64 位寻址。因此，虽然可以在高位存储附加数据，但并非在所有架构上都可以，并且不同 CPU 架构上的清除逻辑可能不同。
为什么他们使用整数来存储 rb-trees 的颜色信息？使用字符不是更有效吗？
Achar是一个整数。颜色信息实际上是一位（红色或黑色节点）。其他位，无论是在 achar还是 anint中，都未使用。要回答您的问题，char在某些情况下使用 a 可能会更有效，但在 Boost.Intrusive 挂钩的情况下则不然。optimize_size因此，当启用时，Boost 不会使用这两种类型来存储颜色。未启用时，枚举（通常与int) 用于存储颜色标签，但这并不重要，因为由于对齐，一个指针的空间值被添加到钩子。（在基本钩子的情况下，一些添加的填充可用于其他有用的数据，但仅在非常特殊的情况下，当节点二进制布局中紧跟钩子的第一个非静态数据成员对齐较小时。）
于 2020-01-26T07:59:43.623 回答