Lua 数据类型及源码分析

一、Lua 数据类型

Lua是动态类型语言,一共有8种数据类型:

  1. nil: 标记类型,只有一个值也叫nil;
  2. boolean: 布尔类型,有true和false两种类型;
  3. number: 数字类型,默认为C的double类型;
  4. string: 字符串类型,只读,不能修改;
  5. table: 联想数组类型,能被任意类型(除了nil)索引,值可以为任意类型;
  6. function: 函数类型,可以是按照Lua虚拟机定义的接口来写的Lua函数或C函数;
  7. userdata: 指向用户内存块的指针类型,分为两种flavors:
    1. heavy: 内存块由Lua分配并由垃圾回收器管理;
    2. light: 内存块由用户分配并释放;
  8. thread: 协同程序(coroutines)类型

以上8种类型为第一类型(first-class):这些类型能存储在全局变量、局部变量和table表里,能够作为参数传递给参数和从函数返回等等。这8种中的以下几种:string,table,function,thread和heavy userdata在vm(Virtual Memory)中以引用方式共享,是需要被GC(Garbage Collection)管理回收的对象。其它类型都以值形式存在。

二、Lua解释器中数据类型源码1

Lua解释器中数据类型定义如下:

// "lobject.h"
// Tagged Values
#define TValuefields	Value value; int tt
typedef struct lua_TValue {
  TValuefields;
} TValue;
其中TValue是Lua中数据类型的结构。tt是value的类型标签,value存放了真正类型值。

// "lobject.h"
// Union of all Lua values
typedef union {
    GCObject *gc;               /* string, table, function, heavy userdata, thread */
    void *p;                    /* light userdata */
    lua_Number n;               /* number,默认为double */
    int b;                      /* boolean */
} Value;

Value通过联合体来实现,每种类型对应结构如上段解释。

其中 nil只有一个值。 boolean和number的作为拆箱值(unboxed value)2直接保存在union中。 string, table, function, thread and userdata在union中被设计成指向这些类型具体实现结构的指针。 其中GCObject类型为可回收结构的联合体,定义如下:

// "lstate.h"
// Union of all collectable objects
union GCObject {
  GCheader gch;
  union TString ts;
  union Udata u;
  union Closure cl;
  struct Table h;
  struct Proto p;
  struct UpVal uv;
  struct lua_State th;  /* thread */
};
每种GCObject类型都有头部GCheader,这个头部保存着垃圾回收器需要的信息:

#define CommonHeader	GCObject *next; lu_byte tt; lu_byte marked
// Common header in struct form
typedef struct GCheader {
  CommonHeader;
} GCheader;

从上面我们可以看到,所有的 GCObject 都用一个单向链表串了起来。每个对象都以 tt 来识别其类型。marked 域用于标记清除的工作。3

GCObject的其余部分是各个类型的具体部分,比如后面讲到的String类型。

TValue的大小

使用带标签的联合体(tagged unions)来表示Lua数据的结果就是拷贝数据的代价有点昂贵:TValue大约有12bytes(Value:double 8B; tt:int 4B),这样拷贝一个数据需要3个机器字。 但是使用ANSI C并没有更好的实现方法。ANSI C并不容易实现在一些动态类型语言解释器中实现的在指针中共享位(spare bits)的方法,以便存储类型标签(int->bit)。

另一种减小TValue尺寸的方法是不把double类型直接存放在union中,而是把它作为在堆中分配的对象(Python解释器采取了这种方法),这会使得数据操作缓慢。这种方法的一个改进是:把整型值做为拆箱值存放在union中,而浮点型的值放在堆中。这个方法增加了数学操作的复杂性。

从Lua 5.2开始,提供一个编译选项,通过NaN Trick的方法把TValue压缩到8字节。 这种方法首先把数字类型(double)单独列出,即TValue的内容要不就是double,要不就是标签int+其它类型value,每种都是8个字节。

#define TValuefields  \   
    union { struct { Value v__; int tt__; } i; double d__; } u
然后借助浮点数IEEE754标准来区别这两类,因为double的64位表示空间有一段是无意义的,通过前32位就能找出这段空间。如果TValue的前32位落在这段空间,就是其它类型,否则就是double类型。 这种方法在32位系统上比较有效。

三、String类型

// lobject.h
typedef union TString {
     L_Umaxalign dummy;
     struct {
          CommonHeader;
          lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
          unsigned int hash;
          size_t len;      /* number of characters in string */
     } tsv;
}TString;

// llimits.h
typedef unsigned char lu_byte;

先来说说L_Umaxalign,L_Umaxalign用来使GCObject字节对齐, 使得GCObject至少占一个word大小。

// llimits.h
/* type to ensure maximum alignment */
#if !defined(LUAI_USER_ALIGNMENT_T)
#define LUAI_USER_ALIGNMENT_T   union { double u; void *s; long l; }
#endif
   
typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;

再看TString, extra字段0表示字符串没有被hash,大于0表示已经被hash。 并且在大于0时,如果字符串是短字符串,则保存着保留字的下标(?)。

Lua使用hash表保持string类型的拷贝。这样的结果是string不可修改,改变string的操作只是新建了一个string而删除了原来的。并且这也保证了系统中不会有值相同的 string 被创建两份。每个string的hash值通过一个函数计算并保存在TSting的hash成员中。这样保证了string能够快速索引和string之间能快速比较。 hash值计算函数并不读取整个string,而只读一部分,这样减少了操作长string时的性能损失。

所有的 string 则以 stringtable 结构保存在 stringtable strt 域。string 的值类型为 TString ,它和其它 GCObject 一样,拥有 CommonHeader 。但需要注意,CommonHeader 中的 next 域却和其它类型的单向链表意义不同。它被挂接在 stringtable 这个 hash 表中。

四、Heavy Userdata类型

typedef union Udata {
  L_Umaxalign dummy;  /* ensures maximum alignment for `local' udata */
  struct {
    CommonHeader;
    struct Table *metatable;
    struct Table *env;
    size_t len;
  } uv;
} Udata;

定义如上,先不讨论。

脚注:

1.:参考:The Implementation of Lua 5.0, R.I, L.H.F, W.C。

2.:装箱(box)是指将值的类型转换为引用类型的过程。相反的过程就叫拆箱(unbox)。拆箱值(unboxed value)指变量的值就是真正的元素的值。

3. Lua GC 的源码剖析 (1)

发表评论