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

Question

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

“在 C 中，下一个字段是一个指针。出于与处理器上的内存子系统相关的性能原因，内存是在字边界上分配的，并且（至少）下一个指针中的两个最低有效位为 0。”

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

Answer 1

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

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

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

希望这可以帮助！

Answer 2

这是因为当您请求一块内存时，它会在与架构字对齐的块中交付给您，换句话说，它将从一个是字的倍数的内存地址开始。如果它在字的倍数上，它是偶数，排除第一个最低有效位。在 32 位机器上，字长块将为 4，二进制中的 4 为 100，因此第二个最低有效位被关闭。

这是我所说的与这个词对齐的一个例子。考虑以下结构（假设为 32 位）：

struct sample {
  char a;
  int b;
  char c;
  char d;
};

... 需要 8 个字节，而不是 7 个（由于数据结构对齐）。

备注：编译器必须遵守这一点，但这不是必需的。大多数人这样做，或者可以选择这样做。