虚拟机解释器——权衡更大的指令集和调度循环的性能优劣。

9
我正在开发一个简单的虚拟机,目前遇到了困难。
我的最初目标是使用一字节长的指令,在小循环和快速计算跳转分派中实现。但现实与此完全不同-256远远不足以覆盖带符号和无符号的8、16、32和64位整数、浮点数和双精度浮点数、指针操作、不同寻址组合等。一种选择是不实现字节和短整型,但目标是要创建一个支持完整C子集以及向量操作的虚拟机,因为它们几乎无处不在,尽管实现方式不同。
所以我将指令切换为16位,现在我还能添加可移植的SIMD内部函数和更多编译常见例程,通过避免解释而真正提高性能。还有全局地址缓存,最初编译为基址指针偏移量,第一次地址被编译时,它只是覆盖偏移量和指令,这样下次就是直接跳转,每个指令使用全局变量时需要额外的指令成本。

由于我还没有进入分析阶段,所以我陷入了两难境地:额外的指令是否值得更大的灵活性?更多的指令是否意味着减少了来回复制指令的次数,从而弥补了增加的调度循环大小?请记住,这些指令只是一些汇编指令,例如:

    .globl  __Z20assign_i8u_reg8_imm8v
    .def    __Z20assign_i8u_reg8_imm8v; .scl    2;  .type   32; .endef
__Z20assign_i8u_reg8_imm8v:
LFB13:
    .cfi_startproc
    movl    _ip, %eax
    movb    3(%eax), %cl
    movzbl  2(%eax), %eax
    movl    _sp, %edx
    movb    %cl, (%edx,%eax)
    addl    $4, _ip
    ret
    .cfi_endproc
LFE13:
    .p2align 2,,3
    .globl  __Z18assign_i8u_reg_regv
    .def    __Z18assign_i8u_reg_regv;   .scl    2;  .type   32; .endef
__Z18assign_i8u_reg_regv:
LFB14:
    .cfi_startproc
    movl    _ip, %edx
    movl    _sp, %eax
    movzbl  3(%edx), %ecx
    movb    (%ecx,%eax), %cl
    movzbl  2(%edx), %edx
    movb    %cl, (%eax,%edx)
    addl    $4, _ip
    ret
    .cfi_endproc
LFE14:
    .p2align 2,,3
    .globl  __Z24assign_i8u_reg_globCachev
    .def    __Z24assign_i8u_reg_globCachev; .scl    2;  .type   32; .endef
__Z24assign_i8u_reg_globCachev:
LFB15:
    .cfi_startproc
    movl    _ip, %eax
    movl    _sp, %edx
    movl    4(%eax), %ecx
    addl    %edx, %ecx
    movl    %ecx, 4(%eax)
    movb    (%ecx), %cl
    movzwl  2(%eax), %eax
    movb    %cl, (%eax,%edx)
    addl    $8, _ip
    ret
    .cfi_endproc
LFE15:
    .p2align 2,,3
    .globl  __Z19assign_i8u_reg_globv
    .def    __Z19assign_i8u_reg_globv;  .scl    2;  .type   32; .endef
__Z19assign_i8u_reg_globv:
LFB16:
    .cfi_startproc
    movl    _ip, %eax
    movl    4(%eax), %edx
    movb    (%edx), %cl
    movzwl  2(%eax), %eax
    movl    _sp, %edx
    movb    %cl, (%edx,%eax)
    addl    $8, _ip
    ret
    .cfi_endproc

这个例子包含以下指令:

  • 将立即值的无符号字节赋给寄存器
  • 将寄存器的无符号字节赋给寄存器
  • 将全局偏移量的无符号字节赋给寄存器,并缓存并更改为直接指令
  • 将全局偏移量的无符号字节赋给寄存器(现在是缓存的先前版本)
  • ...等等...

当然,当我为它制作编译器时,我将能够测试生产代码中的指令流,并优化指令在内存中的排列,以打包频繁使用的指令并获得更多的缓存命中。

我只是很难确定这样的策略是否是一个好主意,膨胀会弥补灵活性,但性能如何?更多的编译例程是否可以弥补更大的调度循环?值得缓存全局地址吗?

我还希望有人,精通汇编语言,对GCC生成的代码质量表达意见 - 是否存在明显的低效率和优化空间?为了使情况清楚,有一个sp指针,它指向实现寄存器的堆栈(没有其他堆栈),ip在逻辑上是当前指令指针,而gp是全局指针(未被引用,作为偏移量访问)。

注:此外,我正在实施指令的基本格式如下:

INSTRUCTION assign_i8u_reg16_glob() { // assign unsigned byte to reg from global offset
    FETCH(globallAddressCache);
    REG(quint8, i.d16_1) = GLOB(quint8);
    INC(globallAddressCache);
}

FETCH返回一个结构体的引用,该指令基于操作码使用该结构体。

REG从偏移量返回寄存器值T的引用。

GLOB从缓存的全局偏移量(实际上是绝对地址)返回全局值的引用。

INC只是将指令指针增加指令大小。

有些人可能会建议不使用宏,但使用模板会使代码更难懂。这样代码就很明显。

编辑:我想在问题中添加一些要点:

我可以选择“仅寄存器操作”的解决方案,该方案只能在寄存器和“内存”之间移动数据 - 无论是全局还是堆。在这种情况下,每个“全局”和堆访问都必须复制值,修改或使用它,并将其移回以进行更新。这样,我就有了一个更短的调度循环,但对于每个寻址非寄存器数据的指令,需要额外的几条指令。因此,两难的问题是:更多次本地代码,较长的直接跳转,还是更多次解释指令,较短的调度循环。短调度循环是否会给我足够的性能以弥补额外且昂贵的内存操作?也许短和长调度循环之间的差异不足以产生真正的差别?就缓存命中而言,在汇编跳转成本方面考虑。

  • 我可以选择附加解码和仅8位宽指令,但这可能会添加另一个跳转 - 跳转到处理该指令的位置,然后浪费时间跳转到特定寻址方案处理的情况或解码操作和更复杂的执行方法。而在第一种情况下,调度循环仍然增长,并添加另一个跳转。第二个选项 - 可以使用寄存器操作来解码寻址,但需要更复杂的指令以处理任何内容。我不确定这如何与较短的调度循环相比,再次不确定我的“较短和较长的调度循环”与在汇编指令方面被认为是短或长的相关性,它们需要的内存和执行速度。

  • 我可以选择“许多指令”的解决方案 - 调度循环大几倍,但仍使用预先计算的直接跳转。复杂的寻址对于每个指令都是特定的并进行优化,并编译为本机代码,因此“仅寄存器”方法所需的额外内存操作将被编译并大多在寄存器上执行,这对性能有好处。通常,想法是增加指令集的内容,但也增加可以预先编译并在单个“指令”中完成的工作量。更长的指令集还意味着更长的调度循环,更长的跳转(虽然可以进行最小化优化),更少的缓存命中,但问题是BY HOW MUCH?考虑到每个“指令”只是几条汇编指令,大约7-8k指令的汇编片段是否被认为是正常的,或者太多?考虑到平均指令大小约为2-3b,这应该不超过20k的内存,足以完全适合大多数L1缓存。但这并非具体的计算,只是我在Google上找到的东西,所以也许我的“计算”有误?还是可能不起作用?我对缓存机制不是很有经验。

  • 在我权衡各种论点后,采用“多指令”方法似乎有最大的性能优势,当然,前提是我的理论关于将“扩展分发循环”适配到L1缓存中是否成立。在这里,您的专业知识和经验就派上用场了。现在,由于语境已经缩小,并且提出了一些支持性想法,也许更容易给出一个更具体的答案,即一个更大的指令集是否比通过减少较慢的解释代码的数量来降低本机代码量所带来的好处。

    我的指令大小数据基于这些统计数据

    5个回答

    5

    您可能考虑将虚拟机指令集架构(VM ISA)和其实现分离。

    比如在我写的一种虚拟机中,我有一个“直接加载值”指令。指令流中的下一个值不会被解码为指令,而是被加载为一个值到一个寄存器中。你可以把这看作一个宏指令,或者看成两个独立的操作。

    我还实现了另一条指令,“加载常量”,它从内存中加载一个常量(使用常量表的基地址和偏移量)。因此,在指令流中的一个常见模式是: load value direct (index); load constant value。您的虚拟机实现可以识别这种模式,并使用单个优化实现来处理这对指令。

    显然,如果您有足够的位数,您可以使用其中一些位来标识一个寄存器。但是,如果只有8位,可能需要为所有操作使用单个寄存器。但是,您可以添加另一条指令with register X 来修改下一条指令。在您的C++代码中,该指令仅设置其他指令使用的currentRegister指针。


    3
    更多编译的程序能弥补更大的分派循环吗?
    我想你不喜欢对某些指令使用第二个字节的扩展操作码,是吗?如果额外的字节不太常见或者不太难以解码,那么16位操作码的解码效率可能不如8位加额外的字节。如果是我,我会用一组相当有限的“指令”让编译器(不一定是具有“全部”功能的完整编译器,而是基本模型)运行起来。将代码生成部分保持相当灵活,这样改变实际编码后将很容易。一旦你做到了这一点,你可以尝试各种编码方式,看看在性能和其他方面的结果如何。
    许多你提出的小问题非常难回答,除非有人做过这两种选择。我从未以这种意义编写过虚拟机,但我曾经参与开发过多个反汇编器、指令集模拟器和类似的工具。我还实现过几种不同类型的语言,作为解释语言的实现。
    你可能还需要考虑JIT方法,其中你解释字节码并为相关体系结构生成直接的机器码,而不是加载字节码。
    GCC代码看起来还不错,但有几个地方的代码依赖于紧接着的指令的值——这在现代处理器中不是很好。不幸的是,我看不到任何解决方法——这是一个“代码太短,无法重新排列”的问题——添加更多的指令显然行不通。
    我确实看到一个小问题:加载32位常量需要最佳性能时对齐32位。我不知道Java虚拟机如何处理它。

    我现在不进行任何解码,发现这是提高性能的最佳方式。之前我尝试过位打包指令,但“解码”的开销太大了。此外,由于指令大小为8位,我需要包含太多填充。由于目标是实现C的子集,所以我不是用自己的编译器通过自己的代码进行JIT,而是生成C代码,编译并动态链接它,使本地执行与VM“插件”兼容。VM可用于原型设计和脚本编写,关键部分可以编译为本机代码。 - user2341104
    好的,指令将由16位操作码、16位寄存器偏移和32位立即值组成。总共64位。 - user2341104
    是的,但如果您有奇数个“简单”的16位指令(我认为有一些指令只有一个操作码而已),您的下一个16+16+32位集将不对齐,除非您添加填充。 - Mats Petersson
    我曾计划使用仅操作码的指令,但决定不使用。这种指令没有太多用处,只会完全扰乱对齐或需要更复杂的填充。现在我使用结构体和便携式固定宽度字段来“寻址”指令成员并递增到下一条指令,因此编译器填充所有内容,唯一的缺点是偶尔出现64位对齐为32位的情况,但这不值得解决。 因此,我最小的指令是32位,有16位操作码和16位或2个8位字面量。 - user2341104
    因为我想解决现代编程语言所引入的问题——不同的语言/工具以及与本地二进制文件的繁琐集成。我计划创建一种语言,其中编译和动态范式是相同的,相同的语法,它只是个人决定是否将代码块编译或解释。在静态和动态中都可以使用相同的API,而且还可以原生链接到C和C++代码,无需像JNI或ActiveX之类的笨拙接口。基本上,我正在创建一种类似于C风格的编程语言,具有“模拟”的OOP和其他高阶结构。 - user2341104
    显示剩余10条评论

    1

    我认为你问错了问题,不是因为这是一个不好的问题,相反,它是一个有趣的主题,我怀疑许多人都像我一样对结果感兴趣。

    然而,目前没有人分享类似的经验,所以我想你可能需要开创一些先河。不要纠结于使用哪种方法并浪费时间实现样板代码,而是专注于创建一个“反射”组件来描述语言的结构和属性,创建一个带有虚方法的漂亮的多态结构,不必担心性能,创建可在运行时组装的模块化组件,甚至可以在建立对象层次结构后使用声明性语言。由于你似乎使用Qt,因此你已经完成了一半的工作。然后,你可以使用树形结构来分析和生成各种不同的代码——用于编译的C代码或特定VM实现的字节码,其中你可以创建多个,你甚至可以使用它来以编程方式生成你的VM的C代码,而不是手动输入所有内容。

    我认为这些建议将更有益于你在没有预先确定答案的情况下进行先驱探索,它将使你能够轻松测试所有场景,并根据实际性能而非个人假设和他人的假设来做出决策。然后,也许你可以分享结果并用性能数据回答你的问题。


    0

    你需要决定的一件事是在代码文件大小效率、缓存效率和原始执行速度效率之间取得什么样的平衡。根据你正在解释的代码的编码模式,将每个指令(无论其在代码文件中的长度如何)转换为包含指针和整数的结构可能会有所帮助。第一个指针将指向一个函数,该函数接受指向指令信息结构以及执行上下文的指针。主执行循环因此可能如下:

    do
    {
      pc = pc->func(pc, &context);
    } while(pc);
    

    与“添加短立即指令”相关的函数可能是这样的:

    INSTRUCTION *add_instruction(INSTRUCTION *pc, EXECUTION_CONTEXT *context)
    {
      context->op_stack[0] += pc->operand;
      return pc+1;
    }
    

    而“添加长立即数”将是:

    INSTRUCTION *add_instruction(INSTRUCTION *pc, EXECUTION_CONTEXT *context) { context->op_stack[0] += (uint32_t)pc->operand + ((int64_t)(pc[1].operand) << 32); return pc+2; }

    与“添加本地变量”指令相关联的函数将是:

    INSTRUCTION *add_instruction(INSTRUCTION *pc, EXECUTION_CONTEXT *context)
    {
      CONTEXT_ITEM *op_stack = context->op_stack;
      op_stack[0].asInt64 += op_stack[pc->operand].asInt64;
      return pc+1;
    }
    

    你的“可执行文件”将由压缩的字节码格式组成,但在运行时,它们将被转换为指令表,从而消除了解码指令时的间接层级。


    0

    指令长度以字节为单位已经有一段时间以来采用相同的处理方式。显然,当您希望执行许多类型的操作时,被限制在256个指令内是不好的。

    这就是为什么有一个前缀值。回到Gameboy架构,没有足够的空间来包含所需的256位控制指令,这就是为什么一个操作码被用作前缀指令的原因。这保留了原始的256个操作码以及如果以该前缀字节开头,则还有256个操作码。

    例如: 一个操作可能看起来像这样:D6 FF = SUB A,0xFF 但是带前缀的指令将被表示为:CB D6 FF = SET 2,(HL) 如果处理器读取CB,它会立即开始查找另一个256个操作码指令集。
    今天的x86架构也是如此。任何以0F为前缀的指令都将成为另一个指令集的一部分。
    对于您的模拟器使用的执行方式,这是扩展指令集的最佳方法。 16位操作码将占用比必要空间更多的空间,而前缀不提供如此长的搜索范围。

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接