OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

Lua设计与实现笔记

原作者: [db:作者] 来自: [db:来源] 收藏邀请

Lua虚拟机工作流程：Lua代码是通过翻译成Lua虚拟机能识别的字节码运行的，分两部分：

翻译代码以及编译为字节码部分：将Lua代码进行词法分析、语法分析，最终生成字节码。
Lua虚拟机相关部分：将上面生成的字节码装载到虚拟机中执行。

Lua只有字符串和表两种最基本的数据结构。
Lua同时采用了两种方式来做到数据统一：

具体类型中有CommonHeader,用来存放所有数据类型都通用的字段；
TValue作为统一表示所有数据的数据结构，内部使用了联合体Value将所有数据都包起来。

字符串：

在Lua虚拟机中存在一个全局的数据区，用来存放当前系统中的所有字符串。
同一个字符串数据，在Lua虚拟机中只可能有一份副本，一个字符串一旦创建，将是不可变更的。
变量存放在仅是字符串的引用，而不是其实际内容。
传统的字符串比较是逐位对比，但Lua对比不会逐位对比，而是仅比较字符串的哈希值。

Table:

Lua表分为数组和哈希表部分，数组部分从索引1开始；哈希表部分可以存储任何其它不能存放在数组部分的数据。

查找：

如果输入的key是一个正整数，并且它的值>0&&<=数组大小，尝试在数组部分查找；
否则尝试在哈希表部分查找：计算出该key的哈希值，根据此哈希值访问Node数组得到哈希表的位置，遍历该哈希表所有链表元素，直到找到该key为止。

插入：涉及重新分配表中数组和哈希表部分的流程。

先计算数据key所在桶数组位置，这个位置称为mainposition,相同mainposition的数据以链表形式组织;
根据key来查找其所在哈希表的mainposition,如果该Node的值为nil,那么直接将key赋值并且返回Node的TValue指针就可以；
否则说明该mainposition上已经有其它数据了，需要重新分配空间给这个新的key,然后将这个新的Node串联对应的哈希表上;
遍历Lua表中数组部分，计算元素数量，更新对应的nums数组中的元素数量；
遍历lua表中哈希表部分，也可能存放正整数，根据正整数数量更新对应的nums数组元素数量;
此时num数组已经有了当前Table所有正整数的分配统计，逐个遍历nums数组,获得其东园区间内所包含的整数数量大于50%的最大索引，作为重新哈希之后的数组大小，超过范围的正整数就分配到哈希表；
根据上面计算得到的调整后的数组和哈希表大小调整表。（每个元素存放的key在2(i-1)和2i之间）

其实就是计算整数数组长度在2的阶数中，找到一个最大的可以容纳50%索引的值。然后符合的就放在连续的数组中，不符合的就放在哈希表中，主要是为了数组的长度中不要浪费太多的空间。

迭代：

在数组部分查找数据，查找成功，返回该key的下一个数据；
否则在哈希表部分查找数据，查找成功，则返回该key的下一个。

取长度：

如果表存在数组部分，在数组部分二分查找位置；
否则进入哈希表查找。

总结：

尽量不要将一个表混用数组和哈希表部分，即一个表最好只存放一类数据。
尽量避免进行重新哈希操作，因为重新哈希操作的代价极大。通过预分配（初始化时定义好长度）、只使用数组部分能提升不少效率。

虚拟机：

脚本语言通常都是解释执行的，每一门脚本语言都会有自己定义的OpCode(operation code,也称为bytecode,一般叫"操作码"或者"字节码")。即为门程序定义的"汇编语言"，一般的编译型语言，比如c等，经编译后，生成是与当前硬件环境匹配的汇编代码；而脚本型语言编译器处理后，生成的就是字节码，再将该字节码放在这门语言的虚拟机中逐个执行。

脚本语言和编译语言区别：

多平台，不用修改脚本代码，就能运行各个平台上，硬件、软件平台的差异都由语言自身的虚拟机解决；
由于脚本语言的字节码需要由虚拟机执行，而不像机器代码能够直接执行，所以运行速度比编译型语言差。

虚拟机是中间层，对上，负责解释执行字节码；对下，屏蔽了平台相关内容，多平台运行。
虚拟机需要完成工作：

将源代码编译成虚拟机可以识别执行的字节码；
为函数调用准备调用栈；
内部维持一个IP(Instruction Pointer,指令指针)来保存下一个将执行的指令地址。在Lua代码中，IP对应的是PC指针;
模拟一个CPU的运行：循环拿出由IP指向的字节码，根据字节码格式进行解码，然后执行字节码。

虚拟机实现方式：

基于栈的虚拟机（java，.Net)
基于寄存器的虚拟机（Lua)

栈操作：

缺点：执行一条加法操作需要4条字节码，先出栈两个数，计算，结果压进栈；
优点：指令不需要关心操作数的地址，在执行操作前已经将操作数准备在栈顶上了。

寄存器操作：

操作数是放在“CPU的寄存器”(不是物理意义上的寄存器)，字节码带上具体操作数所在的寄存器地址，只要一条指令就可以将结果放到所需的地址上。

实现脚本语言解释器：

设计一套字节码，分析源代码文件生成字节码
在虚拟机中执行字节码
如何在整个执行过程中保存整个执行环境

虚拟机主要扮演的是CPU和内存的角色，CPU用来执行指令，内存负责数据的存取读写。

GC算法：Lua采用标记清除算法

原理：遍历系统中的所有对象，看哪些对象没有被引用，没有引用关系的就认为是可以回收的对象，可以删除。

引用计数：引用加一，反之减一。优点：不需要扫描每个对象；缺点：会有循环引用问题。
标记清除算法（白、黑（使用））：每一次做GC的时候，首先扫描并且标记系统中的所有对象，被扫描并且标记到的对象认为是可达的，不会被回收；反之没有被标记的对象认为可以回收。
双色标记清除算法（白（待访问）、黑（使用）、灰（待扫描））：缺点：每个对象的状态是“二元”的，只能有一种状态，所以要求这个算法每次做GC操作时不可被打断地一次性扫描并清除完所有对象。
三色标记清除算法：一个“双白色”，第一次GC和后面GC,每次都交替使用。