X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938号

【译】Threaded Code


本文用于记录有关 Threaded Code 的一些内容,翻译自“这里”。此文原文较老(2003),仅供参考。

Threaded Code 有什么好处?

Threaded Code 是一种用于实现虚拟机解释器(interpreter)的技术。事实上,有很多种方法可以用来实现解释器,其中比较常用的一些方法有:

如果你看重性能,则可以采用第三种“虚拟机字节码”的方式(因为获取和解码更简单,因此也更快)。如果你暂时对性能不感兴趣,也同样可以考虑使用虚拟机字节码的方式,因为它通常与其他方法一样简单。

“Threaded Code” 如同其本意一样,是实现虚拟机解释器的技术之一。如今,至少 Forth 社区已经将 “threading” 一词用于指代任何实现 Forth 虚拟机所使用的技术。

什么是 Threaded Code?

让我们看一段由虚拟机指令 A、B 和 C 组成的线性代码。假设我们编写汇编例程(routine)Ar、Br 和 Cr,以执行虚拟机指令对应的动作。然后,我们可以编写以下汇编代码来执行这些虚拟机指令:

call Ar
call Br
call Cr

尽管它不是原本意义上的 Threaded Code,但它通常也被称为 subroutine-threaded code。实际上,基于例程的 threading 甚至都不是一种“解释性”的技术。

现在,让我们消除例程的调用过程(call):

Ar
Br
Cr

比如,将一系列的代码地址当做虚拟机指令。

结果就是,我们无法通过跳转到它的开头部分来执行这段代码。我们还必须在单独的寄存器中跟踪指向当前指令的指针(而不是使用 CPU 的 PC 寄存器以及相关存有调用返回地址的堆栈/寄存器)。

那我们如何执行下一条指令呢?假设指令指针寄存器(ip)始终指向代码序列中紧接当前指令字的字(地址)。然后我们只需要加载这个指令字,跳转到它所指向的例程,然后递增指令指针。例如,使用 MIPS 汇编语言:

lw   $2,0($4) # 获取下一条指令到 $2,$4=指令所在地址(指针);
addu $4,$4,4  # 递增 ip 寄存器 4 个字节;
j    $2       # 跳转到对应地址执行指令;
nop           # 填补分支延迟间隙(Branch Delayed Slot,MIPS / SPARC 专有);

该例程是一个解释器(在 Forth 社区中也称为“内部解释器”)。它也被称为 “NEXT” 例程。 在每个虚拟机指令例程的末尾都会有一个 NEXT 的副本,或者它们共享同一个 NEXT 副本,并跳转到该副本。对于现代处理器,使用共享的 NEXT 例程不仅会消耗一个 “jump” 指令,而且还会极大地提高具有 BTB(Branch Target Predictor)和类似间接分支预测器的 CPU,在预测间接跳转时的错误预测率。因此,建议不要使用共享的 NEXT 例程

上述方法一般被称为 direct-threaded code。一个基于 C 语言的实现如下所示:

#define NEXT goto **ip++
#define guard(n) asm("#" #n)

main() {
  /* this has 50% mispredictions (50-60% is typical in large benchmarks) */
  static void* prog[] = {&&next1, &&next2, &&next1, &&next3, &&next1, &&next4, &&next1, &&next5, &&next1, &&loop};
  void** ip = prog;
  int count = 10000000;
  NEXT;
 next1:
  guard(1);
  NEXT;
 next2:
  guard(2);
  NEXT;
 next3:
  guard(3);
  NEXT;
 next4:
  guard(4);
  NEXT;
 next5:
  guard(5);
  NEXT;
 loop:
  if (count > 0) {
    count--;
    ip = prog;
    NEXT;
  }
  exit(0);
}

请注意,与流行的说法相反,subroutine-threaded code 通常比 direct-threaded code 慢。

Threading 技术

将介绍基于上述 direct-threaded code 的几种变体:

Indirect Threaded Code

让我们考虑常量:它们可以由虚拟机指令 lit(用于字面量)表示,后跟常量的值。如果该常量频繁出现,则为该常量提供虚拟机指令则会在一定程度上节省空间。如果我们有几个常量,则对于它们的虚拟机指令代码将看起来非常相似。因此,我们更希望共享代码,但同时拥有独立的数据。

为此,我们可以在 NEXT 中添加一个“间接级别”(indirect-threaded code)。每个指令字(虚拟机指令的一般化)都有一个代码字段和一个参数字段,例如,下面这个关于常量的例子:

code-field:      docon # 共享的,用于定义常量的代码对应的代码段地址;
parameter-field: value # 常量的值;

现在,虚拟机代码由一系列“代码段地址”而不是代码地址表示。简单的虚拟机指令(原语)通常表示如下:

code-field2:      parameter-field2
parameter-field2: code # 原语对应的机器代码;

基于 indirect-threaded code 的 NEXT 可由如下 MIPS 汇编语言表示:

lw   $2,0($4) # 获取下一条指令字的代码段地址, $4=指令字代码段所在地址(指针);
nop
lw   $3,0($2) # 获取指令字的实际指令地址;
addu $4,$4,4  # 递增 ip 寄存器 4 个字节;
j    $3       # 跳转到对应地址执行指令;
nop

传统上,Forth 是使用 indirect-threaded code 实现的。因此,direct-threaded codeindirect-threaded code 两者在实现上有很多共同点:非原语(Non-primitive)具有一个代码段(code-field),但是现在它包含一个跳转到实际代码的 “jump”,而不是其地址信息。在大多数处理器上,此跳转比 indirect-threaded code 的额外负载花费更多的时间,因此 direct-threaded code 在执行原语(primitive)时会具有性能优势。在 486 上,相对的提速是 2%-8%。(原语和非原语的区别?)

一个基于 C 语言的简单实现如下所示:

#define NEXT goto ***ip++
#define guard(n) asm("#" #n)

main() {
  /* this has 50% mispredictions (50-60% is typical in large benchmarks) */
  static void* cf[] = {&&next1, &&next2, &&next3, &&next4, &&next5, &&loop};
  static void** prog[] = {cf, (cf + 1), cf, (cf + 2), cf, (cf + 3), cf, (cf + 4), cf, (cf + 5)};
  void*** ip = prog;
  int count = 10000000;
  NEXT;
 next1:
  guard(1);
  NEXT;
 next2:
  guard(2);
  NEXT;
 next3:
  guard(3);
  NEXT;
 next4:
  guard(4);
  NEXT;
 next5:
  guard(5);
  NEXT;
 loop:
  if (count > 0) {
    count--;
    ip = prog;
    NEXT;
  }
  exit(0);
}

Token Threaded Code

direct-threaded code 不能简单地从一台计算机移植到到另一台计算机,因为它包含有平台独立的“代码地址”信息。token-threaded code 使用固定的虚拟机指令编码,从而以在每个 NEXT 中进行表查找(将指令编码映射到其实际代码地址)为代价,来实现代码的可移植性。indirect-threadingtoken-threading 是正交的,因此可以将它们组合为 indirect-token-threading(但相对来说会有更慢的 NEXT 分发过程)。

其他类型

一种使用类似 C 语言实现虚拟机解释器的方法。

switch-threaded code 使用 C 的 switch-case 语句(或其他语言的类似语句)。其结果具有与 token-threaded code 相同的优势;与其相比的缺点是,由于大多数 C 编译器为 switch-case 语句生成了范围检查,因此指令分发速度较慢。

现代 CPU 上的 switch-threading 的主要性能缺点是它使用一个共享的间接跳转分支。而这会导致许多现代 CPU 上的 BTB 中的错误分支预测率接近 100%。而具有单独 NEXT 的线程代码仅存在约 50% 的错误预测。

#define NEXT break
#define guard(n) asm("#" #n)

main() {
  static int prog[] = {0, 1, 0, 2, 0, 3, 0, 4, 0, 5};
  int* ip = prog;
  int count = 10000000;

  for (;;) {
    switch (*ip++) {
    case 0:
      guard(0);
      NEXT;
    case 1:
      guard(1);
      NEXT;
    case 2:
      guard(2);
      NEXT;
    case 3:
      guard(3);
      NEXT;
    case 4:
      guard(4);
      NEXT;
    case 5:
      if (count > 0) {
        count--;
        ip = prog;
        NEXT;
        /* the rest is to get gcc to make a realistic switch statement */
      }
      else
    exit(0);
    case 12:
    case 8:
      count = 25;
      NEXT;
    case 10:
      count--;
      NEXT;
    }
  }
}

一种用于 8086 架构的技术。该代码由一个段序列而不是一个代码地址序列组成。这允许将 8086 的整个地址空间用于带有 16 位“指针”的线程代码,但所有字都需要 16 字节对齐。

call-threaded code 使用函数间接调用(大多数编程语言都具有)而不是间接跳转。对于每个函数调用,还必须有一个相应的返回(尾递归优化除外)。因此,此方法的成本是使用 “call-return” 序列而不是简单的跳转。

此外,每个虚拟机指令由一个函数(过程)表示。这看起来很优雅,并且允许单独编译,但是这意味着必须将全局变量用于作为虚拟机寄存器(例如,指令指针 ip),大多数编译器会将其分配到内存(读取过程相对较慢)中;相反,使用 switch-threaded code,我们可以使用局部变量,这些局部变量将有可能会被分配到寄存器中。

typedef void (*Inst)();
#define guard(n) asm("#" #n)

Inst* ip;
extern Inst prog[];

#define NEXT ((*ip++)())

void next1() {
  guard(1);
}

void next2() {
  guard(2);
}

void next3() {
  guard(3);
}

void next4() {
  guard(4);
}

void next5() {
  guard(5);
}

void loop() {
  static int count = 10000000;

  if (count <= 0)
    exit(0);
  count--;
  ip = prog;
}

Inst prog[] = {next1, next2, next1, next3, next1, next4, next1, next5, next1, loop};

main() {
  ip = prog;
  for (;;)
    NEXT;
}


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)