201930200

やる気が出ないので 201930100 を試して遊ぶ。整数の四則演算とループができる程度のスタックマシンを作って、 CPS による命令分岐と match による分岐を比較する。 CPS の方はこんな感じのコード。

union Op {
  op: unsafe fn(*const Op, *mut isize),
  imm: isize,
}

unsafe fn add(code: *const Op, stack: *mut isize) {
  let stack = stack.sub(1);
  *stack.sub(1) += *stack;
  let code = code.add(1);
  ((*code).op)(code, stack)
}

LLVM IR をみるとちゃんと tail call になっている。速度は処理内容によるけれど、おおむね 1.0 .. 1.3 倍といったところ。おそらくループ内に同じ命令がたくさんあると、分岐予測が多少効きやすくなるという threaded dispatch のご利益が薄くなってほとんど差がなくなる。

はまった点として

unsafe fn print(code: *const Op, stack: *mut isize) {
  let stack = stack.sub(1);
  println!("{}", *stack);
  let code = code.add(1);
  ((*code).op)(code, stack)
}

これが tail call にならない。

unsafe fn print(code: *const Op, stack: *mut isize) {
  ...
  print_isize(x);
  ...
}

fn print_isize(x: isize) {
  println!("{}", x);
}

これでもだめで、

#[inline(never)]
fn print_isize(x: isize) {
  println!("{}", x);
}

これでやっと tail call になった。ううむ。 IR に llvm.lifetime.end なるものが挟まってしまうのが原因にみえるがよく分からない。

LLVM Language Reference Manual — LLVM 10 documentation