为什么这个AVL树实现将位包装成64位但不是32位实现的指针？

Question

在Solaris的这个AVL树实现中,如果编译32位库,则以明显的方式定义struct avl_node.

但是对于64库,指向节点父节点的指针被打包到"avl_pcb"中.看起来只有61位的ponter存储起来.

1. 为什么这样做有用？
2. 为什么不为32位做类似的事情？

Answer 1

在64位机器上,指针通常与字边界对齐,字边界为八字节的倍数.结果,指针的最低三位将为零.因此,如果数据结构需要三位信息,它可以将它们打包到指针的最低三位.那样:

• 要跟随指针,清除指针值的最低三位,然后取消引用它.
• 要读取这三个位中的任何一个,请屏蔽指针中的其余位并直接读取它们.

这种方法非常标准,并且不会失去任何指向地址的能力,因为通常出于性能或硬件原因,您不希望无论如何都要使用非对齐指针.

我不确定的是他们为什么不在32位情况下这样做,因为使用三个指针他们可以使用相同的技巧轻松隐藏必要的位,但每个指针有两位.我的猜测是它是一个性能问题:如果你将位打包到指针的底部,你会增加跟踪指针的成本,因为清除位需要计算.例如,请注意,在64位情况下,这些位被打包到父指针中,该指针仅用于非常规操作,例如计算顺序后继或在插入或删除时进行旋转.这样可以快速查找.在32位情况下,要隐藏3位,实现将需要使用两个指针的低位,其中一个指针必须是左指针或右指针.我的猜测是,减慢树搜索的性能损失不值得节省空间,所以他们决定只记住内存并将它们分开存储.这只是猜测,因为如果他们愿意的话,他们绝对可以将这些位存储在指针的底部.

旁注:如果实现使用的是红色/黑色树而不是AVL树,那么只需要两位信息:一个用于判断节点是红色还是黑色的位,以及一个用于判断是否为节点是左或右孩子.在这种情况下,所需的两个位总是可以打包成32位指针.这是红黑树受欢迎的原因之一.

希望这可以帮助!