c - 关于C中链表的下一个字段中最低有效位的声明

Question

我在 C 语言中找到了以下关于链表的下一个字段中最低有效位的语句:

"In C, the next field is a pointer. For performance reason related to memory subsystem on a processor, memory is allocated on word boundaries, and (at least) two least significant bits in the next pointers are 0."

这是真的吗？我不明白为什么会这样。请帮忙。

Answer 1

许多处理器体系结构的设计使得操作应该在字对齐地址上执行。例如，某些 32 位处理器的设计使得任何字操作都必须在 4 字节(32 位)的倍数的地址处进行，例如地址 0、4、8、12、16、20 等。类似地，一些 64 位处理器只允许在 8 字节的倍数的地址上进行字操作。这在硬件方面具有多种优势，例如能够更轻松地检测两条不同的指令是否引用内存中的同一个字，从而使处理器更快。在某些处理器中，如果您尝试进行非对齐读取，您将遇到总线错误，而在其他处理器中，这样做是合法的，但性能会显着下降。

正因为如此，大多数内存分配库都设计为在字边界对齐所有分配。这意味着在 32 位系统上，地址的低两位将为 0(因为数字是四的倍数)，而在 64 位系统上，地址的低三位将为0. 许多数据结构通过使用这些低位来存储额外信息来压缩它们的表示。例如，一些红/黑树的实现会将存储节点是红色还是黑色的位放在其中一个指针的低位中，而一些AVL树(需要存储两位信息)会打包那些位到这些指针的低位。一些垃圾收集算法使用类似的技术来存储标记位。

编辑:在 C 语言中，一些编译器支持 uintptr_t 类型，它表示一个大到足以容纳指针的整数。您可以将指针转换为 uintptr_t，然后在 uintptr_t 变量上使用标准按位运算符来设置或清除位，然后转换回指针以存储结果。在 C++ 中，据我所知，这会产生未定义的行为。

希望这对您有所帮助!