zig-lox icon indicating copy to clipboard operation
zig-lox copied to clipboard

Switch to a tail-call based dispatch loop instead of switch-inside-while

Open jwmerrill opened this issue 1 year ago • 2 comments

Inspired by https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html

Unfortunately, the Zig compiler doesn't yet support tail calls when targeting WASM, so merging this would break WASM support.

jwmerrill avatar May 09 '23 20:05 jwmerrill

Benchmark results at various stages of this work:

cf7c6c74c04479d14036fe57daf46b18302524d4

test/benchmark/equality.lox
  min: 6458 mean: 6530
test/benchmark/binary_trees.lox
  min: 3290 mean: 3374
test/benchmark/properties.lox
  min: 704 mean: 766
test/benchmark/invocation.lox
  min: 484 mean: 564
test/benchmark/fib.lox
  min: 1761 mean: 1847
test/benchmark/trees.lox
  min: 3863 mean: 3929
test/benchmark/instantiation.lox
  min: 1540 mean: 1585
test/benchmark/method_call.lox
  min: 328 mean: 374
test/benchmark/zoo.lox
  min: 504 mean: 633

06107062696dad6ce2857b1a8bedee8a1538855e

test/benchmark/equality.lox
  min: 5015 mean: 5114
test/benchmark/binary_trees.lox
  min: 3199 mean: 3237
test/benchmark/properties.lox
  min: 713 mean: 750
test/benchmark/invocation.lox
  min: 555 mean: 563
test/benchmark/fib.lox
  min: 1550 mean: 1629
test/benchmark/trees.lox
  min: 3521 mean: 3683
test/benchmark/instantiation.lox
  min: 1508 mean: 1549
test/benchmark/method_call.lox
  min: 317 mean: 350
test/benchmark/zoo.lox
  min: 580 mean: 624

aec43dc80c4c86e3ff60459a9549faa9a8efc634

test/benchmark/equality.lox
  min: 3698 mean: 4035
test/benchmark/binary_trees.lox
  min: 2721 mean: 2864
test/benchmark/properties.lox
  min: 504 mean: 630
test/benchmark/invocation.lox
  min: 399 mean: 461
test/benchmark/fib.lox
  min: 1382 mean: 1430
test/benchmark/trees.lox
  min: 2768 mean: 2943
test/benchmark/instantiation.lox
  min: 1524 mean: 1575
test/benchmark/method_call.lox
  min: 226 mean: 268
test/benchmark/zoo.lox
  min: 432 mean: 511

a5859ce4c70482f74dc4bf16d8d506fc413f9ea6

test/benchmark/equality.lox
  min: 3183 mean: 3327
test/benchmark/binary_trees.lox
  min: 2794 mean: 2812
test/benchmark/properties.lox
  min: 570 mean: 595
test/benchmark/invocation.lox
  min: 439 mean: 446
test/benchmark/fib.lox
  min: 1284 mean: 1522
test/benchmark/trees.lox
  min: 2749 mean: 2909
test/benchmark/instantiation.lox
  min: 1446 mean: 1484
test/benchmark/method_call.lox
  min: 234 mean: 243
test/benchmark/zoo.lox
  min: 450 mean: 465

aec43dc80c4c86e3ff60459a9549faa9a8efc634

test/benchmark/equality.lox
  min: 2769 mean: 2880
test/benchmark/binary_trees.lox
  min: 2701 mean: 2792
test/benchmark/properties.lox
  min: 531 mean: 551
test/benchmark/invocation.lox
  min: 412 mean: 418
test/benchmark/fib.lox
  min: 1186 mean: 1249
test/benchmark/trees.lox
  min: 2674 mean: 2798
test/benchmark/instantiation.lox
  min: 1490 mean: 1538
test/benchmark/method_call.lox
  min: 236 mean: 248
test/benchmark/zoo.lox
  min: 421 mean: 453

e23d6ae64095ad618db220e8c6975c9098f93967

test/benchmark/equality.lox
  min: 2329 mean: 2480
test/benchmark/binary_trees.lox
  min: 2635 mean: 2816
test/benchmark/properties.lox
  min: 510 mean: 527
test/benchmark/invocation.lox
  min: 393 mean: 413
test/benchmark/fib.lox
  min: 1158 mean: 1256
test/benchmark/trees.lox
  min: 2614 mean: 2737
test/benchmark/instantiation.lox
  min: 1392 mean: 1429
test/benchmark/method_call.lox
  min: 216 mean: 231
test/benchmark/zoo.lox
  min: 428 mean: 440

772db3d74378af51f12c873c3a68b3965129a69e

test/benchmark/equality.lox
  min: 2315 mean: 2372
test/benchmark/binary_trees.lox
  min: 2569 mean: 2623
test/benchmark/properties.lox
  min: 460 mean: 489
test/benchmark/invocation.lox
  min: 374 mean: 381
test/benchmark/fib.lox
  min: 1118 mean: 1213
test/benchmark/trees.lox
  min: 2554 mean: 2697
test/benchmark/instantiation.lox
  min: 1378 mean: 1407
test/benchmark/method_call.lox
  min: 201 mean: 210
test/benchmark/zoo.lox
  min: 362 mean: 377

0de73034171a4fcc43abe801a1f31146b9225788

test/benchmark/equality.lox
  min: 2189 mean: 2250
test/benchmark/binary_trees.lox
  min: 2591 mean: 2681
test/benchmark/properties.lox
  min: 431 mean: 460
test/benchmark/invocation.lox
  min: 341 mean: 343
test/benchmark/fib.lox
  min: 895 mean: 938
test/benchmark/trees.lox
  min: 2704 mean: 2813
test/benchmark/instantiation.lox
  min: 1246 mean: 1288
test/benchmark/method_call.lox
  min: 199 mean: 201
test/benchmark/zoo.lox
  min: 355 mean: 370

jwmerrill avatar May 09 '23 20:05 jwmerrill

This is a big performance improvement across all benchmarks, but for some reason, clox from the crafting interpreters book is still faster on most benchmarks.

jwmerrill avatar May 09 '23 20:05 jwmerrill