• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Lua设计与实现笔记

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

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

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

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

  1. 具体类型中有CommonHeader,用来存放所有数据类型都通用的字段;
  2. 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采用标记清除算法

  • 原理:遍历系统中的所有对象,看哪些对象没有被引用,没有引用关系的就认为是可以回收的对象,可以删除。
  1. 引用计数:引用加一,反之减一。优点:不需要扫描每个对象;缺点:会有循环引用问题。
  2. 标记清除算法(白、黑(使用)):每一次做GC的时候,首先扫描并且标记系统中的所有对象,被扫描并且标记到的对象认为是可达的,不会被回收;反之没有被标记的对象认为可以回收。
  3. 双色标记清除算法(白(待访问)、黑(使用)、灰(待扫描)):缺点:每个对象的状态是“二元”的,只能有一种状态,所以要求这个算法每次做GC操作时不可被打断地一次性扫描并清除完所有对象。
  4. 三色标记清除算法:一个“双白色”,第一次GC和后面GC,每次都交替使用。

 

环境与模块:

  • Global表存放在lua_State结构体,也称为G表,这个表是存放全局变量。
  • env表存放在Closure结构体,也就是每个函数有自己独立的一个环境。
  • registry表是全局唯一的,存放在global_State结构体中,这个结构体在整个运行环境中只有一个。

热更新:

能不重启程序或者发布新版本的情况更新脚本,给调试和线上解决问题带来很大便得,对开发效率有很大的提升。
require函数来实现模块的加载,如果加载过则返回,避免重复加载某个模块代码,package.loaded[] = nil,动态更新某个模块的代码。

协程:

  • 进程:定义是“正在运行的程序的实例”,是由操作系统内核分配资源来执行程序的基本单位。在执行前,操作系统内核需要为之分配相应的资源,如内存、CPU等。有了进程,操作系统才会允许在上面有多个任务“同时”执行,这样才能复用多核的优势。

不同进程之间的资源是隔离的,导致进程间的通信非常复杂,于是有了线程的概念。

  • 线程:同一个进程内的不同线程共享了这个进程的内存,使用朴素间数据沟通简单了许多。

进程和线程,其调度都是由操作系统内核来完成的,创建成本很大。

协程更轻量,可以由用户态的程度来调度。

  • 协程:协程可以保留运行时的状态数据;

协程可以让出自己的执行权,当重新获得执行权时从上一次暂停的位置继续执行。
协程不能像进程、线程那样复用其多核,多个协程只能跑在同一个CPU上。

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
关于LUA中的随机数问题发布时间:2022-07-22
下一篇:
写lua时需要注意的地方发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap