# 字节码 “通过将行为编码成虚拟机指令，而使其具备数据的灵活性” ## 解释器模式 先了解下抽象语法树，例如数学表达式 ```cpp (1+2) * (3-4) * /\ + - /\ /\ 1 2 3 4 ``` ```cpp class Expression { public: 　virtual ~Expression() {} 　virtual double evaluate() = 0; }; ``` ```cpp class NumberExpression : public Expression { public: 　 NumberExpression(double value)　 　 : value_(value) 　 {} 　 virtual double evaluate()　 { return value_;　 } private: 　double value_; }; ``` 加法表达式 ```cpp class AdditionExpression : public Expression { public: 　AdditionExpression(Expression* left, 　　　　　　　　　　　　Expression* right) : left_(left), 　　right_(right) 　{} 　virtual double evaluate() 　{ 　 //Evaluate the operands. 　　double left = left_−>evaluate(); 　　double right = right_−>evaluate(); 　 //Add them. 　　return left + right; 　} private: 　Expression* left_; 　Expression* right_; }; ``` Ruby在大概很久以前就是这么实现的，到了1.9版本改成了字节码。 * 从磁盘加载它需要进行实例化并串联成堆的小对象。 * 这些对象和它们之间的指针占用大量内存。在32位机上，即使不考虑内存对齐，这个小小的表达式也要占用68字节（4字节/指针*17个指针）。 * 从每个指针遍历子表达式都会大量消耗数据缓存，而虚函数调用也会对指令缓存造成很大压力。 * 算上虚函数表指针更浪费空间 ## 字节码模式 指令集定义了一套可以执行的底层操作。一系列指令被编码为字节序列，虚拟机逐条执行指令栈上 这些指令。通过组合指令，即可完成很多高级行为。 假设我们要直接用C++代码去实现各种法术，那么我们需要让代码调用哪些API呢？ 绝大多数法术会改变巫师身上的某个状态， ```cpp void setHealth(int wizard, int amount); void setWisdom(int wizard, int amount); void setAgility(int wizard, int amount); ``` 第一个参数定义受到影响的巫师，比如说用0代表玩家，用1代表对手。这样一来，治疗法术就能够施加到玩家自己的 巫师身上，同时也可以伤害到对手。 ```cpp void playSound(int soundId); void spawnParticles(int particleType); ``` 法术指令集 ```cpp enum Instruction { 　 INST_SET_HEALTH = 0x00, 　 INST_SET_WISDOM = 0x01, 　 INST_SET_AGILITY = 0x02, 　 INST_PLAY_SOUND = 0x03, 　 INST_SPAWN_PARTICLES = 0x04 }; ``` 执行一条指令时，先找到对应的基础属性，然后调用正确的API ```cpp switch (instruction) { 　case INST_SET_HEALTH: 　　setHealth(0, 100); 　　break; 　case INST_SET_WISDOM: 　　setWisdom(0, 100); 　　break; 　case INST_SET_AGILITY: 　　setAgility(0, 100); 　　break; 　case INST_PLAY_SOUND: 　　playSound(SOUND_BANG); 　　break; 　case INST_SPAWN_PARTICLES: 　　spawnParticles(PARTICLE_FLAME); 　　break; } ``` 封装成一个小型虚拟机 ```cpp class VM { public: 　void interpret(char bytecode[], int size) 　{ 　　for (int i = 0; i < size; i++) 　　{ 　　　char instruction = bytecode[i]; 　　　switch (instruction) 　　　{ 　　　　// Cases for each instruction... 　　　} 　　} 　} }; ``` 为了多一点真正语言的感觉，我们需要引入参数。 ### 栈机 要执行一个复杂的嵌套表达式，你得从最内层的子表达式开始。内层表达式的结果在计算完后，将被作为包含它的外层表达式的参数传给外层表达式以供其继续计算，以此类推直至整个表达式计算完毕。 ```cpp class VM { public: 　VM() : stackSize_(0) {} 　　//Other stuff... 　void push(int value) 　{ 　 //Check for stack overflow. 　　assert(stackSize_ < MAX_STACK); 　　stack_[stackSize_++] = value; 　} 　int pop() 　{ 　 //Make sure the stack isn't empty. 　　assert(stackSize_ > 0); 　　return stack_[--stackSize_]; 　} private: 　static const int MAX_STACK = 128; }; ``` 当某个指令需要输入参数时，它会按照下面的方式从堆栈中弹出来。 ```cpp switch (instruction) { 　case INST_SET_HEALTH: 　{ 　　int amount = pop(); 　　int wizard = pop(); 　　setHealth(wizard, amount); 　　break; } //Similar for SET_WISDOM and SET_AGILITY... case INST_PLAY_SOUND: 　playSound(pop()); 　break; case INST_SPAWN_PARTICLES: 　spawnParticles(pop()); 　break; } ``` 参数输入 ```cpp switch (instruction) { //Other instruction cases... 　case INST_LITERAL: 　{ //Read the next byte from the bytecode. 　　int value = bytecode[++i]; 　　push(value); 　　break; 　} } ``` ```cpp // 入栈 wizard INST_LITERAL 0 // 入栈 amount INST_LITERAL 10 // 调用 INST_SET_HEALTH ``` ### 组合就能得到行为 如果将我们的虚拟机看做是一种编程语言，它目前所支持的仅是些内置函数，以及它们的常量参数。 为了让字节码更接近行为，我们得进行组合。 ```cpp case INST_GET_HEALTH: { 　int wizard = pop(); 　push(getHealth(wizard)); 　break; } case INST_GET_WISDOM: case INST_GET_AGILITY: // You get the idea... ``` 例如支持加法 ```cpp case INST_ADD: { 　int b = pop(); 　int a = pop(); 　push(a + b); 　break; } ``` 在代码里面，是这样的 ```cpp setHealth(0, getHealth(0) +　　 　　 (getAgility(0) + getWisdom(0)) / 2); ``` 上面得运算过程 1. 取出并保存巫师当前的生命值 2. 取出并保存巫师当前的敏捷度 3. 取出并保存巫师当前的智力值 4. 取出保存的敏捷度和智力值，将它们相加并保留结果 5. 将4的结果除以2保存结果 6. 取出巫师的生命值并加到结果里面去 7. 取出6的结果值，并将其赋值给巫师的生命值属性 翻译为字节码 ```cpp LITERAL 0 [0] # Wizard index LITERAL 0 [0, 0] # Wizard index GET_HEALTH [0, 45] # getHealth() LITERAL 0 [0, 45, 0] # Wizard index GET_AGILITY [0, 45, 7] # getAgility() LITERAL 0 [0, 45, 7, 0] # Wizard index GET_WISDOM [0, 45, 7, 11] # getWisdom() ADD [0, 45, 18] # Add agility and wisdom LITERAL 2 [0, 45, 18, 2] # Divisor DIVIDE [0, 45, 9] # Average them ADD [0, 54] # Add average to health SET_HEALTH [] # Set health to result ``` 只剩下一个问题了：真正去创建字节码。眼下我们将一段伪代码编译成了字节码。除非你真的很闲，否则这在实践中根本行不通。 ### 语法转换工具 文本编程语言 转为 字节码。 并不一定非得建立自己的脚本语言，完全可以是做一个图形界面来让用户定义行为。 这让你免于为一个小语言设计语法并编写语法分析器。 ## 基于栈的虚拟机 * 指令很小。因为每个指令都隐式从栈顶寻找它的参数，你无需对任何数据做编码。这意味着每个指令都非常小，通常只采用一个字节。 * 代码生成更简单。当你要编写一个编译器或生成字节码输出的工具时，你会发现基于栈的虚拟机更简单。每个指令都隐式操作栈顶，你只需要以正确的顺序输出指令，就能实现参数传递。 * 指令数更多。每个指令都只操作栈顶。这意味着生成类似`a = b + c` 这样的代码，你就得分别用指令把b 和c 各自放到栈顶，执行操作，最后将结果存入a 。 ## 基于寄存器的虚拟机 * 指令更大。因为它需要记录参数在栈中的偏移量，单个指令需要更多的位数。例如，在众所周知的寄存器式虚拟机Lua中，每个指令占用32位。其中6位存储指令类型，剩下的存储参数。 * 指令更少。因为每个指令都能做更多的事情，其数量相应就会少些。因为你无需把堆栈中的值挪来挪去，所以也可以说你获得了性能提升。 建议是实现基于栈的虚拟机。它们更容易实现，生成代码也更加简单。寄存器虚拟机因为Lua转换为它的格式之后执行效率更高而受到称赞，但这实际上深切依赖于你虚拟机的实际指令集设计和其他很多细节。 ## 应该有哪些指令 * 外部基本操作：它们是位于虚拟机之外、引擎内部的，做一些玩家能看到的事情的东西。它们决定字节码能够表达的真正行为。如果没有它们，你的虚拟机除了在循环中烧CPU之外，没有任何用处。 * 内部基本操作： 它们操作虚拟机内部的值——例如字面值、算术运算符、比较运算符和操作栈的指令。 * 控制流： 我们的例子中没有这部分，但如果你想要让指令有选择地执行或是循环重复执行，那你就需要控制流。在字节码的底层语言部分中，它们极其简单——跳转。 * 抽象化：如果你的用户开始往数据中定义很多内容，那最终他们会希望能重用字节码而不是反复复制粘贴。你也许会用到可调用过程。 ## 值应当如何表示 一个功能完善的虚拟机应当支持不同的数据类型：数字、字符串、对象、列表等。 ```cpp enum ValueType { 　TYPE_INT, 　TYPE_DOUBLE, 　TYPE_STRING }; ``` ```cpp struct Value { 　ValueType type; 　union 　{ 　　int intValue; 　　double doubleValue; 　　char*　stringValue; 　}; }; ``` 当前你可以把union替换成自己的一块空间，自己去设计去操作不用union，可能设计出更紧凑的方案。 还有利用多态实现的 ```cpp class Value { public: 　virtual ~Value() {} 　virtual ValueType type() = 0; 　virtual int asInt() { 　 // Can only call this on ints. 　　assert(false); 　　return 0; 　} 　// Other conversion methods... }; ``` ```cpp class IntValue : public Value { public: 　IntValue(int value) 　: value_(value) 　{} 　virtual ValueType type() { return TYPE_INT; } 　virtual int asInt() { return value_; } private: 　int value_; }; ``` 他们各有优缺点。 ## 如何生成字节码 * 定义一种基于文本的语言，像Lua那样 * 设计一个图形化编辑工具