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

Question

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

"在C中,下一个字段是指针.由于与处理器上的内存子系统相关的性能原因,内存分配在字边界上,并且(至少)下一个指针中的两个最低有效位为0."

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

Answer 1

设计了许多处理器体系结构,以便应该在字对齐的地址上执行操作.例如,设计了一些32位处理器,以便任何字操作必须在4字节(32位)的倍数的地址上完成,例如地址0,4,8,12,16,20等.类似地,某些64位处理器只允许在8字节倍数的地址上进行字操作.这在硬件中具有各种优点,例如能够更容易地检测两个不同的指令是否指向存储器中的相同字,这使得处理器更快.在某些处理器中,如果您尝试执行非对齐读取,则会出现总线错误,而在其他处理器中,这样做是合法的,但性能会显着降低.

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

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

希望这可以帮助!