闲扯 Tagged Pointer

上学期的编译原理课程设计是要求做一个使用算符优先分析法实现的表达式求值解释器，当时自己在设计时，决定数值同时支持整数和小数，于是采用 C 语言的 long 类型作为整型，double 类型作为浮点数，在对同一个值的处理上，使用 union，表示如下：

#define LONG 1
#define DOUBLE 2

typedef struct {
    int vtype;
    union {
        long vlong;
        double vdouble;
    } num;   
} value;

这样就可以使用一个结构表示两种不同类型的数了，其中 vtype 用来标识这个结构表示的是什么数，比如可以这样打印一个 value 值:

void printf_value(value *v)
{
    if (v->vtype == LONG) {
        printf("%ld\n", v->num.vlong);
    } else {
        printf("%f\n", v->num.vdouble);
    }
}

在一些编程语言的实现上，也是这样使用的，这种用法被称为 Tagged Union，顾名思义，就是“给联合打上标签”，不过这个标签的代价有点过于昂贵了，union 占用的内存空间是它最大字段的大小，无论是在32位还是64位机器上，int 类型和 double 类型都分别是4个和8个字节，也就是说，在这个结构 value 中，真正需要的信息只占用了 66.7%，这是十分不必要的浪费。

考虑到在现在决大部分计算机平台上，在内存中对数据的存放都使用了对齐规则，要求某种类型对象的地址必须是某个值（通常是2、4、8）的倍数，也就是说，在 C 语言中，指向某个类型值的指针最后一位、两位或者三位都是0,具体对齐的要求是操作系统所约定的，你可以自己写段小程序，打印一下 C 中常用类型值的地址，这里是一个简单的示例：

int main(int argc, char **argv)
{
    int a = 0;
    long b = 128899;
    double c = 12.3849;
    value v;

    printf("int a:    %p\n", &a);
    printf("long b:   %p\n", &b);
    printf("double c: %p\n", &c);
    printf("value v:  %p\n", &v);
    return 0;
}

下面是在我的电脑是执行的结果（系统是 Ubuntu 12.04 x86-64):

int a:    0x7fff35a3eb1c
long b:   0x7fff35a3eb08
double c: 0x7fff35a3eb10
value v:  0x7fff35a3eaf0

可以看出，采用的是4字节对齐，也就是说，每个地址最后两位肯定是0,于是就有了这样的想法，反正最后两位都是0,何不用起来，比如上面的那个例子，我们将指向 double 类型值的指针最后添1,这样通过检测指针最后一位就可以判断出值所代表的真实类型了。于是可以定义一组宏：

#define IS_DOUBLE(p) (((unsigned long) (p) & 0x1) != 0)
#define MAKE_DOUBLE(p) ((void *)((unsigned long) (p) | 0x1))
#define GET_DOUBLE(p) ((unsigned long) (p) & ~0x1)

其中假设 p 是指向 long 或者 double 值的指针，而之所以使用 (unsigned long) (p) 进行强制类型转换，是因为对地址不能进行位操作，必须转换成整数，而无论在32位还是64位平台上，unsigned long 都是和指针类型长度相同的。现在可以这样改写打印 value 的函数了：

void printf_value(void *p)
{
    if (IS_DOUBLE(p)) {
        printf("%f\n", *(double *)(GET_DOUBLE(p)));
    } else {
        printf("%ld\n", *(long *)(p));
    }
}

这里传入的是指向值的指针，下面是一个完整的应用示例：

int main(int argc, char **argv)
{
    /* 首先是 long，这个是默认，不用处理 */
    long vlong = 717;
    printf_value(&vlong);

    /* double 类型，将指向它的指针的值最后一位设置为 1,这样就可以和 long 类型值区分 */
    double vdouble = 7.17;
    void *v = &vdouble;
    v = MAKE_DOUBLE(v);
    printf_value(v);

    return 0;
}

这样，我们只需要维护一个指向值的指针就可以确定值的类型了，这样就比使用联合减少了很多空间，而比较繁杂一点的就是使用了太多的强制类型转换，这点看起来似乎有点心惊肉跳。使用指针的值来区分一些东西，其实是非常常用的，比如 C 中的空指针 NULL 的大小就是0,这点利用了在虚拟内存中，地址0处的内存是不可用的。而这种使用指针来区分的方法就叫做 Tagged Pointer，在一些编程语言的实现中，使用的就是这种方法。

在Ruby中，所有数据都是对象，包括整数。在实现底层，对象是使用 C 中的结构体来实现的，当新建许多不同的整数实例时，就需要进行大量的内存操作，这是十分耗时的。比如有一个循环，从0到50000,这样需要创建50000个对象，这样就太扯了。于是 Ruby 将小整数特殊对待，因为其它对象都是使用指向其的指针来引用，而就像上面所展示的一样，地址其实就是一个无符号长整型数，因此可以将地址拿来表示小整数。

#define INT2FIX(i) ((VALUE)(((SIGNED_VALUE)(i))<<1 | FIXNUM_FLAG))

上面一段代码就是 Ruby 对 Tagged Pointer 的运用，因为地址肯定是偶数，将值左移添一成为奇数，这样以后判断一个值是奇数，那么它所代表的就是一个小整数，否则就是指向一个对象的地址。