用于小型计算机的字节码解释器 ⁑ Dercuano

  • Introduction: Density Is King (With a Tiny VM):认为现代世界除为获得更紧凑代码外,使用字节码理由不足,探讨能生成更紧凑代码的字节码引擎。以 Smalltalk 和 Squeak 字节码为例对比 CPU 指令集和字节码解释器的优劣,列举字节码解释器能做而硬件 CPU 较难处理的事情。
  • Indirect Threaded 16-bit FORTH: Not Great For Density:以 FORTH 语言为例,其定义的 FIB 函数在间接线程 FORTH 中编译后有 18 个线程槽,36 字节,加上字典结构开销,不如 PowerPC 汇编和 Squeak 字节码。
  • Naive Lisp: Terrible for Density:用简单 Lisp 解释器解释 fib 函数,其表示形式简单但占用空间大,cdr 编码效果不佳。
  • Lua's VM: Four-Byte Register-Based Instructions:Lua 的虚拟机自 2003 年起为寄存器式,其四字节寄存器指令在空间上不比栈式指令多太多,其虚拟机较小,有 35 条指令,如 MOVE、LOADK 等,CALL 可传递和存储寄存器范围,比较指令在成功时跳过下一条指令。文中还讨论了闭包的有趣实现。
  • The MuP21 and F21 instruction sets:MuP21 用 6000 个晶体管实现,指令集包括转移、内存、ALU 和寄存器等指令,F21 有 27 条指令,是 MuP21 的扩展,文中给出 F21 指令的描述及将 dumb fib 基准测试用 F21 代码表示,发现其在字面量处理上表现不佳。
  • Local Variables: Registers Or Stacks?:双栈可消除局部参数向量的需求,通过在调用和返回栈间移动变量来获取所需值,研究 Smalltalk 中真实代码的局部变量分布,发现大部分方法的参数和临时变量较少,使用双栈的字节码设计可能是可行的。
  • Adapting the MuP21 Instruction Set to a Smalltalk-Like System:可借鉴 MuP21 的五比特零操作数指令用于双栈抽象机,以实现更紧凑的代码,如对 sample fib 程序的优化,还讨论了 Smalltalk 块在该环境中的困难及解决方法,如省略字面量表等。
  • Speculative Case Study: An F21-like Squeak:通过对 Squeak 的选择器和常量使用情况进行分析,估计新机制下的字面量表大小并手动翻译一些方法,发现双栈机器设计在代码密度上不如带有局部变量向量的设计,如对 CompiledMethod>>copyWithTrailerBytes: bytes 方法的翻译比较。
  • Steve Wozniak's SWEET 16 Dream Machine:Steve Wozniak 的 SWEET16 16 位虚拟机将 6502 的代码密度提高一倍,但其在与 Squeak 字节码的比较中表现不佳,如对 fib 微基准测试和 CompiledMethod>>copyWithTrailerBytes: bytes 方法的翻译。
  • NanoVM: Java Bytecodes on the AVR:NanoVM 是 AVR 上的 Java 字节码实现,约 7100 字节,包括垃圾回收等功能,支持部分 Java 语言,字节码文件格式可能有开销,可能可将类似 Squeak 的字节码引擎放入 8 千字节 ROM 。
  • Code-Compact Data Structures:在代码空间有限的机器上,需要内置常见数据结构的表示方式,如数字、字符串、字典、列表等,文中给出 OCaml 和 Squeak 中可增长数组和哈希表的实现及代码大小比较。
  • Library Design:历史上人们常认为计算机用于计算(算术和数字),但许多程序的数字处理在较低层次,统计 Squeak 中的方法使用情况,发现 transcendental 函数不太受欢迎,系统应更注重灵活的集合类。
  • Other Existing Small Interpreters:介绍其他现有的小型解释器,如 S21(187KB MS-DOS EXE 文件,包含模拟器等)、Squeak(Intel Mac 上 967868 字节)、pepsi/Albert(144 行 C 代码编译后 1451 或 1602 字节)、The Basic STAMP(PIC 上的字节码,相关资料大小不一)、UCSD P-System(不同架构的字节码解释器,大小从几千到上万行不等)、PICBIT(PIC 微控制器的字节码 Scheme 实现,字节码大小较大)、F-83(1983 年的间接线程 FORTH 系统)等。
  • Conclusions: Squeak Rules, We Should Be Able To Do Python In A Few K:多数方法在 toy "fib"问题上比 PowerPC 机器码更紧凑,Squeak 字节码表现较好,认为 Squeak 的方法(栈用于表达式中间结果,局部变量向量用于长期使用,局部字面量表用于常量和链接)是紧凑字节码的最佳方法之一,断言多态性可增加代码密度,提出用小的机器码内核实现更 Squeak 式的虚拟机以减少运行时代码大小,通过这种方法可将类似 Python 的语言放入 2000 - 6000 字节的微控制器 ROM 中。

Topics:涵盖多个与文章相关的主题,如 Electronics、History、Microcontrollers、Compression、Python、Stacks 等。

阅读 17
0 条评论