使用OCaml等功能语言实现直接线程解释器

Question

在C/C++中,您可以使用函数指针数组实现直接线程解释器.该数组代表您的程序 - 一系列操作.每个操作函数必须以调用数组中的下一个函数结束,例如:

void op_plus(size_t pc, uint8_t* data) {
  *data += 1;
  BytecodeArray[pc+1](pc+1, data); //call the next operation in the array
}

该BytecodeArray是函数指针阵列.如果我们有一个这些op_plus操作的数组,那么数组的长度将决定我们如何增加数据的内容.(当然,您需要添加某种终止操作作为数组中的最后一个操作).

如何在OCaml中实现类似的功能呢？我可能试图翻译这个代码:我在C++中使用OCaml函数数组.问题在于我最终会遇到类似的问题:

let op_plus pc data = Printf.printf "pc: %d, data_i: %d \n" pc data;
                        let f = (op_array.(pc+1)) in         
                        f (pc+1) (data+1) ;;

其中op_array是在上面的作用域中定义的数组,然后稍后重新定义它以填充一堆op_plus函数...但是,op_plus函数使用op_array的先前定义.这是鸡和蛋的问题.

Answer 1

另一种选择是使用CPS并完全避免使用显式函数数组.在这种情况下,尾调用优化仍然适用.

我不知道你是如何生成代码的,但是让我们做出不合理的假设,即在某些时候你有一堆你想要准备执行的VM指令.每个指令仍然表示为一个函数,但它不是程序计数器,而是接收延续函数.

这是最简单的例子:

type opcode = Add of int | Sub of int

let make_instr opcode cont =
    match opcode with
    | Add x -> fun data -> Printf.printf "add %d %d\n" data x; cont (data + x)
    | Sub x -> fun data -> Printf.printf "sub %d %d\n" data x; cont (data - x)

let compile opcodes =
    Array.fold_right make_instr opcodes (fun x -> x)

用法(查看推断类型):

# #use "cpsvm.ml";;
type opcode = Add of int | Sub of int
val make_instr : opcode -> (int -> 'a) -> int -> 'a = <fun>
val compile : opcode array -> int -> int = <fun>
# let code = [| Add 13; Add 42; Sub 7 |];;
val code : opcode array = [|Add 13; Add 42; Sub 7|]
# let fn = compile code;;
val fn : int -> int = <fun>
# fn 0;;
add 0 13
add 13 42
sub 55 7
- : int = 48

更新:

在这个模型中引入[条件]分支很容易.ifcontinuation由两个参数构成:iftrue-continuation和iffalse-continuation,但与其他每个continuation函数具有相同的类型.问题是我们不知道在向后分支的情况下是什么构成了这些延续(向后,因为我们从尾部到头部编译).这很容易通过破坏性更新来克服(尽管如果您使用高级语言进行编译,可能会有更优雅的解决方案):只需留下"漏洞"并在编译器达到分支目标时填写它们.

示例实现(我使用了字符串标签而不是整数指令指针,但这几乎不重要):

type label = string

type opcode =
      Add of int | Sub of int
    | Label of label | Jmp of label | Phi of (int -> bool) * label * label

let make_instr labels opcode cont =
    match opcode with
    | Add x -> fun data -> Printf.printf "add %d %d\n" data x; cont (data + x)
    | Sub x -> fun data -> Printf.printf "sub %d %d\n" data x; cont (data - x)
    | Label label -> (Hashtbl.find labels label) := cont; cont
    | Jmp label ->
        let target = Hashtbl.find labels label in
        (fun data -> Printf.printf "jmp %s\n" label; !target data)
    | Phi (cond, tlabel, flabel) ->
        let tcont = Hashtbl.find labels tlabel
        and fcont = Hashtbl.find labels flabel in
        (fun data ->
            let b = cond data in
            Printf.printf "branch on %d to %s\n"
                data (if b then tlabel else flabel);
            (if b then !tcont else !fcont) data)

let compile opcodes =
    let id = fun x -> x in
    let labels = Hashtbl.create 17 in
    Array.iter (function
        | Label label -> Hashtbl.add labels label (ref id)
        | _ -> ())
        opcodes;
    Array.fold_right (make_instr labels) opcodes id

为了清晰起见,我使用了两次传球,但很容易看出它可以一次完成.

这是一个简单的循环,可以通过上面的代码编译和执行:

let code = [|
    Label "entry";
    Phi (((<) 0), "body", "exit");
    Label "body";
    Sub 1;
    Jmp "entry";
    Label "exit" |]

执行追踪:

# let fn = compile code;;
val fn : int -> int = <fun>
# fn 3;;
branch on 3 to body
sub 3 1
jmp entry
branch on 2 to body
sub 2 1
jmp entry
branch on 1 to body
sub 1 1
jmp entry
branch on 0 to exit
- : int = 0

更新2:

在性能方面,CPS表示可能比基于数组更快,因为在线性执行的情况下没有间接.延续函数直接存储在指令闭包中.在基于数组的实现中,它必须首先递增程序计数器并执行数组访问(带有额外的边界检查开销).

我做了一些基准测试来证明它.这是基于数组的解释器的实现:

type opcode =
      Add of int | Sub of int
    | Jmp of int | Phi of (int -> bool) * int * int
    | Ret

let compile opcodes =
    let instr_array = Array.make (Array.length opcodes) (fun _ data -> data)
    in Array.iteri (fun i opcode ->
        instr_array.(i) <- match opcode with
        | Add x -> (fun pc data ->
            let cont = instr_array.(pc + 1) in cont (pc + 1) (data + x))
        | Sub x -> (fun pc data ->
            let cont = instr_array.(pc + 1) in cont (pc + 1) (data - x))
        | Jmp pc -> (fun _ data ->
            let cont = instr_array.(pc) in cont (pc + 1) data)
        | Phi (cond, tbranch, fbranch) ->
            (fun _ data ->
                let pc = (if cond data then tbranch else fbranch) in
                let cont = instr_array.(pc) in
                cont pc data)
        | Ret -> fun _ data -> data)
        opcodes;
    instr_array

let code = [|
    Phi (((<) 0), 1, 3);
    Sub 1;
    Jmp 0;
    Ret
    |]

let () =
    let fn = compile code in
    let result = fn.(0) 0 500_000_000 in
    Printf.printf "%d\n" result

让我们看看它与上面基于CPS的解释器的比较(当然,所有调试跟踪都被剥离).我在Linux/amd64上使用了OCaml 3.12.0本机编译器.每个程序运行5次.

array: mean = 13.7 s, stddev = 0.24
CPS: mean = 11.4 s, stddev = 0.20

因此,即使在紧密循环中,CPS的性能也远远优于阵列.如果我们展开循环并将一条sub指令替换为五条,则数字会发生变化:

array: mean = 5.28 s, stddev = 0.065
CPS: mean = 4.14 s, stddev = 0.309

有趣的是,这两个实现实际上都击败了OCaml字节码解释器.以下循环在我的机器上执行需要17秒:

for i = 500_000_000 downto 0 do () done

Answer 2

另一种选择（如果事先知道大小）- 最初用 void 指令填充数组：

let op_array = Array.create size (fun _ _ -> assert false)
let op_plus = ...
let () = op_array.(0) <- op_plus; ...