Другой альтернативой будет использование 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
UPDATE:
В этой модели легко ввести [условное] ветвление. if продолжение строится из двух аргументов: iftrue-продолжение и iffalse-продолжение, но имеет тот же тип, что и любая другая функция продолжения. Проблема в том, что мы не знаем, что составляет эти продолжения в случае обратного ветвления (назад, потому что мы компилируем от хвоста до головы). Это легко преодолеть с помощью деструктивных обновлений (хотя, возможно, более элегантное решение возможно, если вы компилируете из языка высокого уровня): просто оставьте «дыры» и заполните их позже, когда компилятором будет достигнута цель ветвления.
Пример реализации (я использовал строковые метки вместо целочисленных указателей команд, но это вряд ли имеет значение):
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, описанным выше (разумеется, со всей трассировкой отладки). Я использовал собственный компилятор OCaml 3.12.0 в Linux / amd64. Каждая программа была запущена 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