低位减法到底是什么

Question

我正在阅读 this article 并认为一切都非常清楚，直到我偶然发现这个：

Again, most real Scheme systems use a slightly different implementation; for example, if GET_PAIR subtracts off the low bits of x, instead of masking them off, the optimizer will often be able to combine that subtraction with the addition of the offset of the structure member we are referencing, making a modified pointer as fast to use as an unmodified pointer.

如何才能实现这种减法，优化器将如何施展魔法，使修改指针的速度与未修改的指针一样快？

Answer 1

文章中介绍的技巧是将类型信息编码到 8 字节对齐指针的未使用的三个最低位中。使用此信息找出类型后，

#define PAIR_P(x) (((int) (x) & 7) == 2)

在再次使用指针作为地址之前必须清除那些额外的位。

#define GET_PAIR(x) ((struct pair *) ((int) (x) & ~7))

注意，此时我们已经知道了类型，所以我们知道了三个最低有效位的值。它们将始终为 0b010（十进制 2）。因此，作者建议不要写 ((int) (x) & ~7)，而是写 ((int) (x) - 2)。这个想法是，如果你这样写代码，

if (PAIR_P(x))
  {
    SCM * thing = GET_PAIR(x)->cdr;
    /* Use the thing… */
  }

因为我们访问的是x所指向的struct pair内部的cdr成员（清空低位后），编译器会生成调整指针的代码适当地。像这样。

SCM * thing = (SCM *) ((char *)((int) (x) - 2)) + offsetof(struct pair, cdr));

由于整数加减法的结合性，我们可以省略一层括号并得到（不显示无论如何都不会产生机器代码的外部指针转换）

(int) (x) - 2 + offsetof(struct pair, cdr)

其中，2 和 offsetof(struct pair, cdr) 都是编译时常量，可以合并为一个常量。如果我们要求 car 成员（偏移量为 0），这个技巧就无济于事，但每隔一段时间提供帮助也不错。

现代优化器可能会自己弄清楚，在我们刚刚测试完 (x & 7) == 2、x & ~7 等同于 x - 2 之后，可能就不需要这个技巧了这些天没有了。不过，您希望在依赖它之前对其进行测量。

低位减法到底是什么

What exactly is low bits subtraction

c

micro-optimization

guile