Tony Huang & Tech

7Oct/110

高效动态语言虚拟机的设计（十一） – 函数调用（一）

前面我们已经实现了一个简单的虚拟机，但是它的功能非常的弱，甚至连最基本的函数调用的功能都不具备。
在接下来的几章中，我们将会实现函数调用的功能，并探索优化函数调用性能的方法

Python的语言特性

Python作为一个非常灵活和优雅的动态语言，在函数调用方面提供了非常多的特性，包括：

可选参数

在Python中，我们可以通过给末尾的参数设定默认值的方式来实现可选参数的功能，例如：

def func_with_optional_parameter(a, b = 2):
    print a, b

func_with_optional_parameter(1, 2)
func_with_optional_parameter(1)
# 这两行代码具有相同的效果，都会在屏幕上打印“1 2”

可变长的参数
在实现类似c语言中的printf（或者说python中的str.format函数）之类的函数的时候，能够传入可变长的参数将会非常的必要。
而在python中也提供了非常丰富的语言特性来支持这样的代码，示例如下：
```
def func_with_varargs(a, *args):
    print a, args

func_with_varargs(1) # 这行代码会打印“1 ()”
func_with_varargs(1, 2, 3, 4) # 这行代码会打印“1 (2, 3, 4)”
```
可以看到，这里args是一个tuple
命名的可选参数
当我们的可选参数非常多，而我们只想要指定其中特定的几个的值，其余的保留其默认值的情况下，我们可以使用命名的可选参数，示例如下：
```
def func_with_multiargs(a, b = 1, c = 2, d = 3):
    print a, b, c, d

func_with_multiargs(1, c=3)
# 这行代码的输出是“1 1 3 3”
```
关键词
我也不知道为何python要把这个语言特性命名成这样，但是这确实是个非常好用的功能，它可以为函数传入一些未知的命名参数，示例如下：
```
def func_with_kwds(a, **kwds):
    print a, kwds

func_with_kwds(1, hello='world')
将会打印“1 {'hello': 'world'}”
```
可变长实参
这是一个很抽象的名词，什么叫做实参呢？和实参相对的是形参。所谓实参就是实际的参数值，而形参指的实形式上的参数。这还是很抽象，我们举个例子大家就明了了：
```
def hello(a, b):
    print a, b
hello(1, 2)
```
在这段代码里面，hello的2个参数a、b就是形参，而下面调用函数时，传递进来的参数“1，2”就是实参，这样大家就理解了吧：）

那么什么叫做可变长的实参呢？其实就是我们在调用某个函数时，也无法知晓需要用几个参数来调用它的时候，就要用到这个可变长实参特性了，示例如下：
```
def func(a, b, c, d):
    print a, b, c, d
args = (2, 3)
func(0, 1, *args)
# 输出结果为"0, 1, 2, 3"
```
这里的效果就是args的值被展开成了调用func函数时的后2个参数

我们可以看到Python提供的语言特性非常丰富，而这丰富的语言特性也给性能的优化带来了非常大的压力。

修改虚拟机设计

为了实现如此丰富的语言特性，我们需要修改虚拟机的很多设计，包括数据类型和指令集。

数据类型的修改

在我们之前的虚拟机中，我们只有一种数据类型，那就是int32型，现在我们加入几种新的数据：

类型	说明
func	函数。用以保存对某个函数的引用。
tuple	元组。用以保存函数调用的参数。
dict	字典。用以保存函数调用的关键词和命名可选参数。

这些数据类型的简单实现会随着系列文章的推进逐渐优化，所以在此之前，我们会用最简单的方式代替之。

虚拟机的指令集

我们回顾一下我们的虚拟机的指令集：

指令助记符	指令opcode	指令说明
load r c	0	将常量c的值赋给第r号寄存器
mov r0 r1	1	r0 = r1
add r0 r1 r2	2	将寄存器r1和r2中值的和存入寄存器r0 （r0 = r1+r2）
sub r0 r1 r2	3	r0 = r1 - r2
inc r	4	将寄存器r中的值加一（r = r + 1）
dec r	5	将寄存器r中的值减一（r = r - 1）
cmp r0 r1 r2	6	比较r1和r2寄存器中的值，并将比较结果存入r0中（如果r1>r2则r0=1, 如果r1
b addr	7	直接跳转到相对地址addr执行
bnl r addr	8	如果寄存器r的值不为-1则跳转到相对地址addr执行

我们现在需要增加几条新的指令以实现函数调用，但是本着逐渐深入的原则，我们第一步只增加1条指令，就是call指令，同时把上一个话题中的OP_EXIT指令重命名成OP_RETNONE，作为函数返回的指令，那么指令集就变成了：

指令助记符	指令opcode	指令说明
load r c	0	将常量c的值赋给第r号寄存器
mov r0 r1	1	r0 = r1
add r0 r1 r2	2	将寄存器r1和r2中值的和存入寄存器r0 （r0 = r1+r2）
sub r0 r1 r2	3	r0 = r1 - r2
inc r	4	将寄存器r中的值加一（r = r + 1）
dec r	5	将寄存器r中的值减一（r = r - 1）
cmp r0 r1 r2	6	比较r1和r2寄存器中的值，并将比较结果存入r0中（如果r1>r2则r0=1, 如果r1
b addr	7	直接跳转到相对地址addr执行
bnl r addr	8	如果寄存器r的值不为-1则跳转到相对地址addr执行
retnone	9	退出函数的执行，并返回None作为函数的执行结果
call func argc arg0 arg1...	10	调用函数，有argc个参数，其值分别在后面的那些寄存器中

从下一节开始我们会先着手实现一个简单的函数调用功能。

Filed under: VM No Comments

30Sep/110

高效动态语言虚拟机的设计（十） – 预解码与直接Threaded解释执行

题外话

这篇文章的内容比较少，所以可以抽空介绍一下，为什么这个过程被称为指令解码（或者指令译码）。
说起这个可以展开的有很多，我们可以先回顾一下重点：
学电子工程类专业的同学们一定学过《数字电路》这门课吧！这门课的内容就是这个名词来的关键。
这门课里面会提到一种数字电路，被称为译码器（比如74LS138就是一个典型的3-8译码器），一个3位的译码器的真值表如下：

I2	I1	I0	O7	O6	O5	O4	O3	O2	O1	O0
0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	1	0	0	0	0	0	0	1	0	0
0	1	1	0	0	0	0	1	0	0	0
1	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0
1	1	0	0	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	0

备注：标准的译码器的输出是D非，类似11111110这样的。
还记得数字电路实验中，老师让我们用一个计数器和一个3-8译码器来搭的跑马灯电路不？
其实CPU内部也差不多，基本上就是一个时钟连接着一个计数器（也就是传说中的PC寄存器，Program Counter程序计数器），而计数器的输出指向了内存中某一个指令，而这个指令的数据会通过一个类似3-8译码器（具体要看指令的数量）这样的译码电路来控制具体的逻辑电路。
所以指令解码就是这么来的，其含义就是根据指令的opcode来找到具体执行这个指令的逻辑。

难道还有优化的余地？

我们的代码已经简单到了只有一句，怎么还能优化呢？

goto opcode_lbls[*pc++];

然而就算只有1行的c语言代码，执行的时候还是会有很多工作要做：

int opcode = *pc;
void* label = opcode_lbls[opcode];
pc++;
goto label

这里面第2行就是传说中的指令解码阶段。
本章的目标就是把这个时间也节约下来。

预解码

很多看官一定会很疑惑，为什么只有区区9条指令，我却使用了一个32位的整数来保存。其实主要有两个考虑：

由于cpu访问内存的特点，对齐到其字长的内存访问要比非对其访问快许多，而在大多数系统中，这个数字是32位
由于32位机器的地址也是32位的，所以，我们可以预先解码指令，并把对应的label地址保存到opcode字段中

在预处理环节，我们可以：

*pc = opcode_lbls[*pc];

而在执行的时候，可以直接使用opcode中保存的地址，这就是所谓的预解码与直接Threaded解释执行。

goto *reinterpet_cast<void*>(*pc++);

这样就可以使得运算速度更进一步。

性能测试

编译器	编译参数	prototype	threaded_opexit	direct_threaded	相对prototype减少	相对threaded_opexit减少
gcc	-O3	347.4ms	195.9ms	175.3ms	49.5%	10.5%
llvm-gcc	-O3	355.4ms	195.0ms	172.9ms	48.6%	11.3%
llvm	-O3	276.8ms	196.6ms	174.5ms	37.0%	11.2%

最近在看何帆法官翻译的《批评官员的尺度：《纽约时报》诉警察局长沙利文案》，引用其中的一句话：
“这是值得当街起舞的时刻”
在三个编译器里面性能都有了差不多40%～50%的提升。
（题外话，感谢何帆法官带来如此精彩的译作，教人受益匪浅，欢欣鼓舞）

示例代码

这次我在SConstruct脚本中加入了“-m32”参数以便将代码变异成32位的格式。
请猛击这里下载

Filed under: VM No Comments

29Sep/110

高效动态语言虚拟机的设计（九） – Threaded解释执行（下）

热点

我们回顾一下上一章的代码，就会发现，解码部分的执行是最频繁的（next_inst的内容），执行任何一条指令的时候都必然会执行这段代码。那么如果优化了这段代码，执行的性能会高很多。
我们先来看看这段有哪些代码：

next_inst:
    if (pc >= pend) goto end;
    opcode = *pc++;
    if (opcode < 0 | opcode > OP_BNL) goto op_unknown;
    goto *opcode_lbls[opcode];

嗯，没错，这段代码确实又臭又长，里面的关键代码就是goto *opcode_lbls[opcode]，大量的时间都浪费在了判断代码是否执行结束和指令的opcode是否合法上面。接下来，我们的目标就是把这两个判断给去掉。

去除指令合法性验证

我们设想一下，在什么情况下会遇到指令不合法的问题呢？

编译器产生了不合法的opcode，这种情况下opcode会超出合法范围
编译器产生的跳转指令跳转到了指令的中间（而非指令的开始处），这样就错误的将数据当做指令来解码了

而这两种错误，都可以通过执行前的静态验证来探测，所以，如果我们在执行代码前进行了验证，就没有必要在代码中判断指令是否合法了。
由于本文的内容比较多，相关的代码我就不贴出来了，请大家参考源代码中的threaded_validate.cc中的validate函数的代码。

去除代码结束判断

这个似乎是比较困难，我们很难去判断到底什么时候它会跳转到结束位置，但是我们可以看到一点，就是当程序执行结束时，必然是跳转到最后一条指令之后来执行的，这是就触发了上文中所属的那个判断，从而结束程序的运行。
知道了这一点以后，我们可以专门设计一条退出指令：

#define OP_EXIT 9   // 之前的最后一条指令是 OP_BNL = 8

这样，对应的修改一下跳转表的代码：

...
void* opcode_lbls[10];
...
op_exit:
goto end;
...
opcode_lbls[9] = &&op_exit;
...

这样就可以把那最后的一个判断也去掉了。
这样，next_inst就变成了这样：

next_inst:
    goto *opcode_lbls[*pc++];

美吧～～这部分代码的实现在threaded_opexit.cc里面，有兴趣的朋友可以自己看。

内联next_inst

虽然这已经很短了，但是在执行每个指令的时候都必须执行2次跳转：

op_load:
    i0 = *pc++;
    i1 = *pc++;
    locals[i0] = i1;
    goto next_inst;
...
next_inst:
    goto *opcode_lbls[*pc++];

所以这很没有必要，可以直接把goto指令放到每个指令的label的最后面，如：

op_load:
    i0 = *pc++;
    i1 = *pc++;
    locals[i0] = i1;
    goto *opcode_lbls[*pc++];

相关的实现可以直接参考代码包中的 threaded_id.cc (inline decoding)

性能测试

ok，看看我们做了那么多工作能带来多大的性能提升：

编译器	参数	prototype	threaded	threaded_validate	threaded_opexit	threaded_id
gcc	-O3	354.2ms	274.9ms	293.2ms	183.8ms	200.4ms
gcc	-O0	1214.3ms	1249.9ms	1213.8ms	1087.2ms	1113.4ms
llvm-gcc	-O3	355.3ms	272.5ms	294.2ms	182.1ms	200.1ms
llvm-gcc	-O0	1193.0ms	1215.1ms	1174.2ms	1068.5ms	1068.5ms
llvm	-O3	272.9ms	805.4ms	293.4ms	177.5ms	192.7
llvm	-O0	1098.4ms	1224.3ms	1168.6ms	1097.3ms	1109.2ms

我们可以看到性能的提升还是非常显著的。

在下一章中，我们将继续讨论解释执行的更高效的方式《预解码与直接Threaded解释执行》，尽请期待哦～

Filed under: VM No Comments

29Sep/113

高效动态语言虚拟机的设计（八） – Threaded解释执行（上）

古老的编译器实现

在很久很久以前，编译器的优化功能还不完善（甚至完全不存在）的时候，上一张中的那个巨大的switch…case…块会被编译成类似这样的代码：

if (opcode == OP_LOAD) {
    // load
} else if (opcode == OP_MOV {
    // mov
} ...

如果假设每种指令出现的频率是一样的（均匀分布），那么在指令解码阶段，平均需要4.5个判断才能完成解码工作（一共9条指令），这种算法的复杂度就是O(N)级别的。
那么如果参照系列文章对象模型部分的想法，把指令解码阶段的时间复杂度降低到O(1)级别，那么性能将会有显著的提高。

使用跳转表

我们的指令集总共只有9条指令，而这些指令的opcode又正好是从0开始，一直到8为止，那么我们可以设想，把每条指令都使用label标示出来，然后将他们的地址存到一个数组中，当执行的时候，可以直接使用opcode查表得到对应指令标签的地址，再使用jmp指令跳转过去就可以了。
而这种方法在专业领域被称为Threaded Interpreting，请恕我才疏学浅，不知道该怎么翻译……
然而在标准的C语法中，并不存在获取标签地址的功能，也不支持跳转到保存在变量中的标签地址。要实现这样的功能，就必须借助汇编语言实现。而现代编译器一般情况下如果源代码内嵌了汇编，就会自动采用完全不优化的方式编译（相当于那个文件使用-O0编译）。

GCC的扩展语法

估计是gcc的用户中，从事虚拟机工作的人实在太多了，以至于gcc专门扩充了语法来支持方便的访问标签，这样又能享受使用标签带来的灵活性，又可以优化性能。
它的语法是这样的：

void* label_pointer = &&label;

可以看到label的指针采用的是void*作为数据类型，使用&&来获得label的地址。
对应的，goto到这个指针的格式就是：

goto *label_pointer;

改写代码

在解释执行的部分的代码就可以变成：

    void* opcode_lbls[9];
    int opcode;

    goto prepare;
#define NEXT_INST do { goto next_inst; } while(0)

op_load:
    i0 = *pc++;
    i1 = *pc++;
    locals[i0] = i1;
    NEXT_INST;

op_mov:
    i0 = *pc++;
    i1 = *pc++;
    locals[i0] = locals[i1];
    NEXT_INST;

op_add:
    i0 = *pc++;
    i1 = *pc++;
    i2 = *pc++;
    locals[i0] = locals[i1] + locals[i2];
    NEXT_INST;

op_sub:
    i0 = *pc++;
    i1 = *pc++;
    i2 = *pc++;
    locals[i0] = locals[i1] - locals[i2];
    NEXT_INST;

op_inc:
    i0 = *pc++;
    locals[i0]++;
    NEXT_INST;

op_dec:
    i0 = *pc++;
    locals[i0]--;
    NEXT_INST;

op_cmp:
    i0 = *pc++;
    i1 = *pc++;
    i2 = *pc++;
    i1 = locals[i1];
    i2 = locals[i2];
    if (i1 > i2)
        locals[i0] = 1;
    else if (i1 < i2)
        locals[i0] = -1;
    else
        locals[i0] = 0;
    NEXT_INST;

op_b:
    i0 = *pc++;
    pc = (int*)((unsigned char*)pc + i0);
    NEXT_INST;

op_bnl:
    i0 = *pc++;
    i1 = *pc++;
    if (locals[i0] != -1)
        pc = (int*)((unsigned char*)pc + i1);
    NEXT_INST;

op_unknown:
    printf("Unknown opcode %d\n", *(pc-1));
    exit(1);
    goto end;

prepare:
    opcode_lbls[0] = &&op_load;
    opcode_lbls[1] = &&op_mov;
    opcode_lbls[2] = &&op_add;
    opcode_lbls[3] = &&op_sub;
    opcode_lbls[4] = &&op_inc;
    opcode_lbls[5] = &&op_dec;
    opcode_lbls[6] = &&op_cmp;
    opcode_lbls[7] = &&op_b;
    opcode_lbls[8] = &&op_bnl;

next_inst:
    if (pc >= pend) goto end;
    opcode = *pc++;
    if (opcode < 0 | opcode > OP_BNL) goto op_unknown;
    goto *opcode_lbls[opcode];

end:
    free(locals);

在一开始就直接goto到prepare处，以准备label表，然后就执行next_inst以解码下一条指令，并跳转到对应指令的label，在每条指令的末尾又跳转到next_inst，以实现原来的那个while循环。

测试性能

编译器	优化参数	prototype	threaded
gcc 4.2.1	-O3	343.3ms	268.4ms
gcc 4.2.1	-O0	1175.2ms	1201.4ms
llvm-gcc (gcc 4.2.1, llvm 2336.1.0)	-O3	348.2ms	266.0ms
llvm-gcc (gcc 4.2.1, llvm 2336.1.0)	-O0	1191.5ms	1221.3ms
llvm clang 3.0	-O3	266.0ms	798.9ms
llvm clang 3.0	-O0	1080.0ms	1182.7ms

测试环境

机器	Apple Mac Book Pro MC700 2011Q1
CPU	Core i5 2.3G
Memory	DDR3 1333 4GB (2*2GB)

出乎意料

从测试结果我们可以看到，大部分情况下，这只是略微的快于原型，甚至于在某些测试中比原型还要漫出许多；其实这是由于现代编译器的设计决定的。
现代编译器编译switch语句的时候会根据具体的情况选择不同的实现方式。
在我们的例子中由于switch的条目比较少，且分布又非常连续，编译器就会采用jumptable的方式来实现switch，这也就解释了为什么大部分情况下，性能差异比较小。

进一步的优化

然而就算是这个threaded的版本，还是有很多优化的空间，在下一节中我会详细的讲解优化的方式。

示例代码

这次就直接放出了这一章和下一章两张的示例代码，请猛击这里下载。
这次我为编译脚本加入了两个参数：

scheme参数用于设定编译的模式，可以取的值为“debug”和“release”，默认情况下为release
compiler参数用于指定编译器的类型，可以取的值为"gcc", "llvm-gcc", "llvm"，默认情况下为gcc

如果我想要用debug方式，使用llvm编译器来编译代码，那么我应该使用如下指令：

scons compiler=llvm scheme=debug

玩的开心~

Filed under: VM 3 Comments

26Sep/112

高性能动态语言虚拟机的设计（七） – 跑起来！

各位看官久等了，不好意思，周末去朱家角旅游了，哈哈～～
这篇文章会以贴代码为主，主要是为了接下来几篇文章中提到的优化虚拟机性能的时候有一个参照的对象，同时呢，这篇文章开始也会提动一个简单的虚拟机的实现的源码下载。

接下来，就是见证奇迹的时刻，我们通过一小段代码，来实现这个小小的虚拟机。

声明指令的opcode

这个很显然，直接把第六章中设计的指令集翻译成C语言代码就好了，直接贴代码：

enum OPCODE {
    OP_LOAD     = 0,
    OP_MOV      = 1,
    OP_ADD      = 2,
    OP_SUB      = 3,
    OP_INC      = 4,
    OP_DEC      = 5,
    OP_CMP      = 6,
    OP_B        = 7,
    OP_BNL      = 8
};

使用经典的 while() { switch {} } 实现

废话不多，先贴代码：

void prototype_exec(int localCount, void* code, int codeSize) {
    int* locals = (int*)malloc(sizeof(int) * localCount);

    int i0, i1, i2;     // predefined integers to be used to store oprand

    int* pc = (int*)code;
    int* pend = (int*)((unsigned char*)code + codeSize);

    while(pc < pend) {
        switch (*pc++) {
            case OP_LOAD:
                i0 = *pc++;
                i1 = *pc++;
                locals[i0] = i1;
                break;
            case OP_MOV:
                i0 = *pc++;
                i1 = *pc++;
                locals[i0] = locals[i1];
                break;
            case OP_ADD:
                i0 = *pc++;
                i1 = *pc++;
                i2 = *pc++;
                locals[i0] = locals[i1] + locals[i2];
                break;
            case OP_SUB:
                i0 = *pc++;
                i1 = *pc++;
                i2 = *pc++;
                locals[i0] = locals[i1] - locals[i2];
                break;
            case OP_INC:
                i0 = *pc++;
                locals[i0]++;
                break;
            case OP_DEC:
                i0 = *pc++;
                locals[i0]--;
                break;
            case OP_CMP:
                i0 = *pc++;
                i1 = *pc++;
                i2 = *pc++;
                i1 = locals[i1];
                i2 = locals[i2];
                if (i1 > i2)
                    locals[i0] = 1;
                else if (i1 < i2)
                    locals[i0] = -1;
                else
                    locals[i0] = 0;
                break;
            case OP_B:
                i0 = *pc++;
                pc = (int*)((unsigned char*)pc + i0);
                break;
            case OP_BNL:
                i0 = *pc++;
                i1 = *pc++;
                if (locals[i0] != -1)
                    pc = (int*)((unsigned char*)pc + i1);
                break;
            default:
                printf("Unknown opcode %d\n", *(pc-1));
                exit(1);
                break;
        }
    }

    free(locals);
}

代码比较长（对于一个vm来说这样的代码已经非常短了。。。）
不过结构也很清晰了，所以在此不做赘述其原理。
由于这种解释执行的方式非常的简单粗暴，性能也比较差，所以被称为Basic Interpreting（基本解释执行），但是很不幸的，在CPython中，正是使用的这种方式来执行Python bytecode。
在本文中之所以实现一个这样的虚拟机，主要用以作为测试的基准，看看不同的方法能够带来多大的性能提升。

整个vm的源代码

我将这个原型实现的源代码打了个包，发上来供大家参考。
身为一个Python控，自然要使用一种不同以往的编译方式。
这个项目使用SCons构建，所以需要自己编译的童鞋们请安装SCons 2.1.0
下载 sample_vm.prototype.tar.bz2
在后续的文章中呢，我们会探讨不同的解释方式对虚拟机性能产生的影响。

大家如果希望看到最新的动态，可以关注我的新浪微薄@黄珏珅。

Filed under: VM 2 Comments

21Sep/112

高效动态语言虚拟机的设计（六） – 实验室原型

在接下来的几个章节里，我将会讨论虚拟机的执行模型，但是在具体讨论执行模型之前，我觉得有必要设计一个最简单的虚拟机来验证后面各种执行模型的性能。

概览

这个虚拟机只有一种数据类型，也就是有符号32位整型（下称int型），同时它的指令集只能操作它进行运算，不能做诸如函数调用之类的功能。这个虚拟机可以根据具体程序的需求，具有无限个寄存器（当然，寄存器的数量是受到内存大小和寄存器指针的限制的）
我们把VM的执行函数的签名规定如下：

void exec(int locals, void* code, int codeSize);

为了消除内存对齐对执行性能的影响（这块内容的讨论会在以后的文章中具体说明，在此先略过不表），所有的指令的opcode都使用32位整型来保存，所有指令的参数都是用单独的32位整型来保存。
为了便于说明，本文及后文中的所有数值都采用小头表示法，例如十六进制0x12345678在内存中将会表示为0x78 0x56 0x34 0x12。

指令集

这个虚拟机的指令集我们也设定的尽量简单，只需要完成基本的数据加载保存、数值运算、控制流等等功能就可以了。

指令助记符	指令opcode	指令说明
load r c	0	将常量c的值赋给第r号寄存器
mov r0 r1	1	r0 = r1
add r0 r1 r2	2	将寄存器r1和r2中值的和存入寄存器r0 （r0 = r1+r2）
sub r0 r1 r2	3	r0 = r1 - r2
inc r	4	将寄存器r中的值加一（r = r + 1）
dec r	5	将寄存器r中的值减一（r = r - 1）
cmp r0 r1 r2	6	比较r1和r2寄存器中的值，并将比较结果存入r0中（如果r1>r2则r0=1, 如果r1
b addr	7	直接跳转到相对地址addr执行
bnl r addr	8	如果寄存器r的值不为-1则跳转到相对地址addr执行

一段测试程序

为了测试虚拟机的性能，我们需要一段简单的代码来测试，代码如下：

int finalSum = 0;
for(int i = 0; i < 100000; i++) {
   int sum = 0;
   for(int j = 0; j < 255; j++) {
      sum += j;
   }
   finalSum = sum;
}

没错，这是一段很无谓的代码，但是这样的代码挺适合用来测试虚拟机中执行指令的性能的 ^.^

纯手工编译

既然我们还没有编译器，那么就纯手工的将这段代码编译成虚拟机的代码吧：
首先分析程序中所有的局部变量，一共有：finalSum,i,sum,j四个变量,100000,255两个常量,用来保存比较结果的2个变量。
给这些变量分配一下寄存器：

变量	寄存器
finalSum	0
i	1
sum	2
j	3
100000	4
255	5
i<100000	6
j<255	7

将上述代码写成汇编：

// init consts
load 4 100000
load 5 255

// int finalSum = 0;
load 0 0

// for (int i = 0; i < 100000; i++) {
// int i = 0
load 1 0

// i < 100000
loop0:
cmp 6 1 4
bnl 6 loop0_exit

// int sum = 0
load 2 0

// for(int j = 0; j < 255; j++) {
// j = 0
load 3 0
// j < 255
loop1:
cmp 7 3 5
bnl 7 loop1_exit

// sum += j
add 2 2 3

// j++
inc 3
b loop1

loop1_exit:
// finalSum = sum
mov 0 2

// i++
inc 1
b loop0

loop0_exit:

接着将这段汇编代码编译成字节码：

0000: 00 00 00 00 04 00 00 00 a0 86 01 00
000c: 00 00 00 00 05 00 00 00 ff 00 00 00
0018: 00 00 00 00 00 00 00 00 00 00 00 00
0024: 00 00 00 00 01 00 00 00 00 00 00 00
loop0:
0030: 06 00 00 00 06 00 00 00 01 00 00 00 04 00 00 00
0040: 08 00 00 00 06 00 00 00 loop0_exit
004c: 00 00 00 00 02 00 00 00 00 00 00 00
0058: 00 00 00 00 03 00 00 00 00 00 00 00
loop1:
0064: 06 00 00 00 07 00 00 00 03 00 00 00 05 00 00 00
0074: 08 00 00 00 07 00 00 00 loop1_exit
0080: 02 00 00 00 02 00 00 00 02 00 00 00 03 00 00 00
0090: 04 00 00 00 03 00 00 00
0098: 07 00 00 00 loop1
loop1_exit:
00a0: 01 00 00 00 00 00 00 00 02 00 00 00
00ac: 04 00 00 00 01 00 00 00
00b4: 07 00 00 00 loop0
loop0_exit:
00bc:

手工连接

0000: 00 00 00 00 04 00 00 00 a0 86 01 00
000c: 00 00 00 00 05 00 00 00 ff 00 00 00
0018: 00 00 00 00 00 00 00 00 00 00 00 00
0024: 00 00 00 00 01 00 00 00 00 00 00 00
0030: 06 00 00 00 06 00 00 00 01 00 00 00 04 00 00 00
0040: 08 00 00 00 06 00 00 00 70 00 00 00
004c: 00 00 00 00 02 00 00 00 00 00 00 00
0058: 00 00 00 00 03 00 00 00 00 00 00 00
0064: 06 00 00 00 07 00 00 00 03 00 00 00 05 00 00 00
0074: 08 00 00 00 07 00 00 00 20 00 00 00
0080: 02 00 00 00 02 00 00 00 02 00 00 00 03 00 00 00
0090: 04 00 00 00 03 00 00 00
0098: 07 00 00 00 c4 ff ff ff
00a0: 01 00 00 00 00 00 00 00 02 00 00 00
00ac: 04 00 00 00 01 00 00 00
00b4: 07 00 00 00 74 ff ff ff

OK，从下一章开始，我们让它跑起来~

Filed under: VM 2 Comments

20Sep/116

高效动态语言虚拟机的设计（五） – 对象模型（下）

各位看官们，对象模型终于进入到了最后一个章节，在这个章节里，我会设计一个适用于Python的高性能的对象模型。

一段典型的Python代码

import math

class Point(object):
  def __init__(self, x, y):
    self.x = x
    self.y = y
  def getOffset(self):
    return math.sqrt(self.x * self.x + self.y * self.y)

Python与JavaScript的不同

由于JavaScript中不存在直接的类的概念，在编译阶段，我们很难直接分析一个类的实例需要会用到哪些属性，所以V8中采用了比较复杂的隐藏类的实现，具体的实现方式请参见上一篇文章。
在Python中有native的类的概念，编译器可以很方便的分析出哪些类的成员函数会访问实例的哪些变量，那么利用这个特点，我们就可以配合编译器来实现一种更简单的高效的对象模型。

更简单的模型

这个设计我就直接用代码来表示：

class Object;

typedef struct {
    int type;
    union {
        Object* o;
        long i;
        double d;
        int b;
        void* p;
    } value;
} Variable;

class TypeObject;

class Object {
    public:
        TypeObject* typeObject;
        Variable* slots;
        HashMap otherProps;
};

class TypeObject : public Object {
    public:
        int slotCount;
        HashMap slotMap;
};

内行的朋友们看到这个一定会说：
这一刻，Lua&V8&Python完成了合体。
没错，这个设计就是博采众家之所长，为Python量身定制。

解释一下

ok，贴完代码以后要解释一下设计的意图。
首先，和Lua类似，将值类型和引用类型分开，值类型的变量在栈上分配，引用类型的对象在堆上分配。
这里Variable结构体的设计就跟Lua的设计如出一撤，这样可以大大降低数值计算时的访存开销。
其次，给对象设计了slot机制，但是并不采用类似V8的隐藏类的设计，而是直接通过编译来分析得出slot的数量和定义，以上文中的Point类为例，slot的分配就是这样的：

序号	定义
0	__init__函数
1	getOffset函数
2	x属性
3	y属性

这样，Point类的TypeObject对象就是这样的定义(伪代码)：

TypeObject PointTypeObject = new TypeObject {
    slotCount = 4,
    slotMap = {
        "__init__": 0,
        "getOffset": 1,
        "x": 2,
        "y": 3
    }
};

当创建一个Point类的对象的时候，就生成一个slots可以容纳4个元素的对象，而上文中的__init__函数的代码也可以编译成（伪代码）：

.locals 3  # 需要用到三个寄存器，用于保存self, x, y三个参数
setprop 0 Point 2 x 1 # 如果self（0）是Point类的示例，那么给他的2号slot（x）赋以寄存器1的值（x）
setprop 0 Point 3 y 2

setprop指令的说明和实现如下：

static void setprop(int obj, TypeObject* type, int slot, StringObject* name, int value) {
    Variable* varObj = &locals[obj];
    if (varObj->type == VARIABLE_OBJECT && varObj->value.o->typeObject == type) {
        varObj->value.o->slots[slot] = locals[value];
    } else {
        setprop_slow(varObj, name, value);
    }
}

这段代码的意思就是如果self是Point类型，那么就直接使用slot号来访问对象的属性，如果不是Point类型的对象，就采用慢的（也是相对而言的，不过是查找hash表而已）算法来访问。
这样，对象属性的访问性能就很强大了。

Filed under: VM 6 Comments

19Sep/115

高效动态语言虚拟机的设计（四） – 对象模型（中）

在上一节中，我们已经分析了采用不同的变量保存方式对虚拟机性能的影响，在本片文章中，我们将深入到对象的内存模型内部，探索内存模型对性能的影响。

动态变化的属性的实现

动态语言的基本特点就是，变量的类型是可变的，而大部分动态语言的对象的属性也是可以变的，那么如何让一个对象的属性可以动态变化呢？
最简单的方式自然是通过使用std::map的方式来实现，也就是通过一个红黑树来保存一个对象的所有字段，以下是一段简要的代码：

struct TypeObject;

struct Object {
    struct TypeObject* typeObject;
    std::map<std::string, struct Object*> properties;
};

作为一个红黑树，它具有非常好的查询性能，其时间复杂度为O(logN)，这样的性能听起来已经非常高效了，但是当面对虚拟机中每秒数以万记的property find操作的时候，O(logN)的性能显然是无法令人感到满意的。

哈希表

于是聪明的人们发明了一种数据结构，被称为hashtable，利用hashtable O(1)的高性能来实现动态的property的性能，它的原理呢就是：

设计一个字符串的哈希函数，将从字符串中提取出1个32bit的哈希值
利用一个哈希表来保存哈希值到具体字段的map信息

那么对应的对象就变成了：

struct Object {
    struct TypeObject* typeObject;
    std::hash_map<std::string, struct Object*> properties;
};

这样，查找对象时，其时间复杂度就为O(1)。
很多朋友一定会想，这一定已经是性能的极致了吧，然而事实并非如此，我们需要深入到两个方面来看待这个过程：

字符串的Hash算法
哈希表的大小

字符串的Hash算法

我们首先设计一个最简单的字符串的hash算法，亦即一个简单的一次扫描算法：

typedef union {
   int hash;
   unsigned char bytes[4];
} hash_t;

int hash(const char* string) {
  hash_t h;
  h.hash = 0;

  int i = 0;
  while(*string) {
    unsigned char c = (unsigned char)(*string);
    h.bytes[i] ^= c;
    i++;
    if (i == 4) i = 0;
    string++;
  }

  return h.hash;
}

这个算法会扫描整个字符串，然后每四个字节做一次异或。
这个算法我们可以看到其消耗还是比较大的，如果每次执行查询的时候都重新计算一次hash，其代价会非常巨大，甚至会抵消从RBT转换到hashtable上得到的收益，所以，通常情况下，动态语言的虚拟机会缓存这个hash值，这样，对象的声明就会变成类似：

struct Object {
    struct TypeObject* typeObject;
    int hash;
    HashMap props;
}

然而，即使如此，去查找hash表时，还有其他的开销。

哈希表的大小

我们的hash的范围是32位整型，其取值范围从-2147483648~2147483647，如果我们的hash表的尺寸也这么大的话，每个对象都至少要占用4*4G=16G的内存，这显然不可能，所以通常情况下，一个对象的初始hash表都很小，比如在Python中，就是可以存放8个条目的哈希表。
那么查找的时候，就会先将hash值除以8取余数，那么这个取余的过程也会消耗cpu的时钟周期，所以就有了V8中采用的一个猥琐方法。

V8中的快速属性访问法

V8的作者觉得自己的这个想法实在是太天才了，以至于，直接把这个想法写到了项目的主页上，在这篇文章中有很详细的论述：
V8 Design Elements
这篇文章从一个基本的类出发来剖析了V8中高速访问属性的机制：
这个类就是大名鼎鼎的Point类：

function Point(x, y) {
    this.x = x;
    this.y = y;
}

当你的代码中调用：

new Point(x,y);

的时候，会首先产生一个Point对象，在这同时，V8会创建Point类的初始隐藏类，称之为C0，让这个对象的类指针指向这个隐藏类。

当执行到

this.x = x;

时，V8会给对象的Slot0赋值成x，并创建一个新的隐藏类C1，其结构可见下图：

这里包含几条信息：

对象的Slot0被赋予了一个值x
C0类内部加入了一条逻辑：如果这个类的对象新加入了一个x字段，则自动转变成C1类
创建了C1类，其内部的逻辑是，如果需要访问字段x，则它的位置在Slot0

当再执行到

this.y = y;

时，状态就转变成了这样：

其含义是：

在对象的Slot1中，保存了y的值
在隐藏类C1中，加入新的逻辑，当加入一个y字段时，应当转变成C2
创建新的隐藏类C2，其中的逻辑是如果需要访问x，则参见Slot0，如果需要访问y则参见Slot1

这种神奇的模式再配合上V8的JIT引擎就可以实现比Hashtable还要高的空间效率和时间效率。

由于我的主要目的是设计一个高效的python解释器，所以在配合了python本身的语言特性的情况下，我设计了另外一种对象模型，既能得到v8虚拟机这样的高性能，又不需要JIT的支持（特指对象属性的访问方面），敬请期待对象模型（下）。

Filed under: VM 5 Comments

15Sep/110

高效动态语言虚拟机的设计（三） – 对象模型（上）

面向对象的纯粹性

在很久很久以前，C++还被称为面向对象语言（现在一般称为多范式通用语言），人们就对C++的面向对象的纯粹性提出了质疑，主要有以下几点：

并非所有的对象都是对象（很拗口？），比如指针本身不是对象，函数不是对象，基本数据类型不是对象。
C++对于面向对象中“消息传递”的设计采用的是方法调用的形式，这种方式不能完整的表达“消息传递”的语义。

对于第一点，我们最直观的感受就是，我们无法写如下的代码：

int a = 10;
string b = a.toString();

我们能做的只是：

int a = 10;
char buffer[MAX_STRING];
itoa(a, buffer, MAX_STRING];
string b(buffer);

所以这里a是一个值，而非一个对象，它只是数据，而没有与之相关的操作。
我们看看Lua和Python的设计，就可以更加明了的理解值类型的设计的差异个中差异。

Lua和Python的差异

在Python中，所有的对象都继承自PyObject类（Python本身是使用C语言编写的，Python在C语言中模拟了一套类似C++的OO机制，支持继承、多态等面向对象特性），在所有需要操作变量的地方，都统一使用PyObject*来访问，例如，在函数调用时，为函数分配堆栈空间的时候，代码就类似这个样子：

PyObject** stack = (PyObject**)malloc(sizeof(PyObject*)*maxStack);

所以，本质上来说，所有的对象都是在堆上分配的，我们访问的都是对象的指针。
再来看看Lua的设计，在Lua中，使用一个结构体来保存对象：

typedef struct {
  int t;
  Value v;
} TObject;
typedef union {
  GCObject* gc;
  void* p;
  lua_Number n;
  int b;
} Value;

所以，保存一个变量，在32bit的机器上，Lua使用12个字节。对于值类型（lua_Number）之类的变量，并不会从堆中分配，而是直接在栈上分配（事实上也是从堆上分配，但是是一次性分配的），例如在函数调用的时候，要分配寄存器的空间的时候，相当于这样的代码：

TObject* locals = (TObject*)malloc(sizeof(TObject)*localCount);

这样看起来似乎都是一条malloc调用，那么性能差异在哪里呢？

分配空间时的性能差异

假设我们在两个虚拟机里面都需要分配一个4个数值类型的栈上变量或者寄存器的空间，那么在Python中，等效代码是：

PyObject** stack = (PyObject**)malloc(sizeof(PyObject*)*4);
for (int i = 0; i < 4; i++)
  stack[i] = (PyObject*)malloc(sizeof(PyIntObject));

这里的代码只包含分配空间，不包括初始化变量的部分。对应在lua虚拟机中的相对代码就是：

TObject* locals = (TObject*)malloc(sizeof(TObject)*4);

可以看到，Lua的模式在处理数值变量的时候，将会少4次内存分配操作，这对于每秒执行数以万级的函数调用的时候，对性能的影响非常明显。

执行运算时的性能差异

现在我们再看看执行数值运算的时候性能会有怎样的差异，我们还是以上一篇文章中说到的，1+2的数学运算为例，将相应的bytecode翻译成实际执行的C代码来做：
Python ByteCode

push 1
push 2
add

对应的C代码

// 为堆栈分配内存
PyObject** stack = (PyObject**)malloc(sizeof(PyObject*)*2); // 一次内存分配

// push 1
STACK_ADJ(1);
STACK_TOP = PyInt_FromLong(1);  // 一次内存分配

// push 2
STACK_ADJ(1);
STACK_TOP = PyInt_FromLong(2);  // 一次内存分配

// add
PyObject* result = PyNumber_Add(STACK_SECOND, STACK_TOP); // 一次内存分类
STACK_ADJ(-1);
STACK_TOP = result;

我们可以看到，这样一次简单的计算，进行了4次内存分配操作（其实还有2次内存释放操作）。
我们再来看看Lua的ByteCode:

loadk 0 1
loadk 1 2
add 2 0 1

对应的C代码是：

TObject* locals = (TObject*)malloc(sizeof(TObject)*3); // 一次内存分配

// loadk 0 1
locals[0] = lua_Number(1); // 没有内存分配

// loadk 1 2
locals[1] = lua_Number(2);

// add 2 0 1
locals[2] = lua_Number(locals[0].v.n + locals[1].v.n);

只有1次内存分配操作，没有内存释放操作，这样，速度的差异就非常明显了。

在下一篇文章中，我将会阐述，动态语言中最重要的数据类型Object类（v8::Object, PyObject, GCObject）的设计，以及它对性能的影响。

Filed under: VM No Comments

14Sep/112

高效动态语言虚拟机的设计（二） – 堆栈机vs状态机

在上一篇文章中，我已经提到了Lua虚拟机的指令集要比其他的动态语言的虚拟机的指令集小很多，而它的执行性能要略强于Python，那么是什么导致这种的差异的呢？
我阅读了Lua的一篇论文，也就是鼎鼎大名的《The Implementation of Lua 5.0》这篇paper，阅读之后恍然大悟。

题外话

似乎Lua社区和Python社区有世仇啊，整篇paper除了鼓吹自己有多高效外，还顺便在吐槽Python的效率有多低。

一些背景知识

在正式介绍Lua的猥琐之前，我想先和大家一起复习一些基础知识。

图灵机
众所周知，图灵是一个聪明到变态的家伙，以至于计算机科学界最nb的奖就是以他的名字命名的。长话短说。所谓图灵机，就是图灵在1936年提出的一个计算模型，它可以模拟人类所有的计算行为。如果你对它的细节有兴趣，可以参见维基百科的页面图灵机
图灵完整
图灵完整也是计算机行业中非常重要的一个概念，所谓图灵完整就是指一种计算模型能够完整的模拟图灵机的所有功能

好吧，这些概念好玄乎啊，说点实际的吧!
其实所谓的图灵完整很好理解，就是他能做任何电脑应该能做的运算，那么它就是图灵完整的。

两种计算模型

有了上面的基础只是，我们就知道，堆栈机和状态机不过是两种不同的图灵完整的计算模型而已。

堆栈机

所谓堆栈机，就是计算机的状态是存在于堆栈之中，通过对堆栈中的元素进行运算和调整，来实现计算功能的计算机。
例如，要进行一个1+2的加法运算，那么就：

操作	堆栈状态
初始状态
将1压入栈中	1
将2压入栈中	1, 2
调用加法运算	3

其典型代表就是Python的虚拟机，代码如下：

push 1
push 2
add

状态机

状态机的基本原理就在于，它可以有有限种状态，指令能够让它在不同的状态之间进行转换。
听起来很抽象？
但其实，我们大部分写代码的时候都是对状态机编程，比如c代码：

int a = 1;
int b = 2;
int c = a + b;

其实这个状态机有2^96种状态（假设int是32位的），因为变量a有2^32种状态（-2147483648~2147483647），b、c亦然。

操作	a的状态	b的状态	c的状态
初始状态	0	0	0
a=1	1	0	0
b=2	1	2	0
c=a+b	1	2	3

典型代表就是Lua的虚拟机，应的代码就是：

loadk 0 1
loadk 1 2
add 2 0 1

意思就是：

register[0] = 1
register[1] = 2
register[2] = register[0] + register[1]

为什么状态机比堆栈机快呢？

既然他们是图灵等价的，那大家一定会很疑惑，为何状态机比堆栈机快呢？
那么我们要深入到虚拟机内部，看看这些指令都是怎么实现的。
为了便于大家理解，我所有的代码都不是vm中的实际代码，而是伪代码。
首先来看看堆栈机：

switch(op) {
case PUSH:
   STACK_ADJ(1);
   STACK_TOP = oprand;
   break;
case ADD:
   STACK_SECOND = STACK_TOP + STACK_SECOND;
   STACK_ADJ(-1);
   break;
}

我们可以看到，大部分情况下，执行一条指令，除了原始的赋值操作外，还需要调整堆栈的栈顶指针（那些STACK_ADJ宏定义），再看看状态机的实现：

switch(op) {
case LOADK:
   REGISTER[oprand0] = oprand1;
   break;
case ADD:
   REGISTER[oprand0] = REGISTER[oprand1] + REGISTER[oprand2];
   break;
}

大家可以看到，在执行大部分指令时，状态机虚拟机会比堆栈机要少一次调整堆栈的操作，这对性能会有很明显的影响。
当然这也主要适用于Interpreting的情况，在Jit的情况下，会有很多深度优化，从而使得堆栈机的性能也能和状态机一样。

小结

细心的朋友们可能发现，这篇文章主要讨论的是两个Interpreter引擎的情况，JIT虚拟机的讨论会放到系列文章的后半部，在下一篇文章中，我将会讨论，对象模型的差异造成的虚拟机性能的差异，尽情期待哦~

Filed under: VM 2 Comments

Older Entries »

I2	I1	I0	O7	O6	O5	O4	O3	O2	O1	O0
0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	1	0	0	0	0	0	0	1	0	0
0	1	1	0	0	0	0	1	0	0	0
1	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0
1	1	0	0	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	0

I2	I1	I0	O7	O6	O5	O4	O3	O2	O1	O0
0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	1	0	0	0	0	0	0	1	0	0
0	1	1	0	0	0	0	1	0	0	0
1	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0
1	1	0	0	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	0

Tony Huang & Tech A technical blog about .Net, Flash, Web Games, Sns Games from Tony Huang

Python的语言特性

修改虚拟机设计

数据类型的修改

虚拟机的指令集

题外话

难道还有优化的余地？

预解码

性能测试

示例代码

热点

去除指令合法性验证

去除代码结束判断

内联next_inst

性能测试

古老的编译器实现

使用跳转表

GCC的扩展语法

改写代码

测试性能

出乎意料

进一步的优化

示例代码

声明指令的opcode

使用经典的 while() { switch {} } 实现

整个vm的源代码

概览

指令集

一段测试程序

纯手工编译

手工连接

一段典型的Python代码

Python与JavaScript的不同

更简单的模型

解释一下

动态变化的属性的实现

哈希表

字符串的Hash算法

哈希表的大小

V8中的快速属性访问法

面向对象的纯粹性

Lua和Python的差异

分配空间时的性能差异

执行运算时的性能差异

题外话

一些背景知识

两种计算模型

堆栈机

状态机

为什么状态机比堆栈机快呢？

小结

Pages

Categories

Blogroll

Archive

Meta

I2	I1	I0	O7	O6	O5	O4	O3	O2	O1	O0
0	0	0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	0	1	0
0	1	0	0	0	0	0	0	1	0	0
0	1	1	0	0	0	0	1	0	0	0
1	0	0	0	0	0	1	0	0	0	0
1	0	1	0	0	1	0	0	0	0	0
1	1	0	0	1	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	0