01mf02 / jaq

A jq clone focussed on correctness, speed, and simplicity
MIT License
2.7k stars 67 forks source link

Tail-recursion optimisation (TCO) #126

Closed 01mf02 closed 10 months ago

01mf02 commented 10 months ago

This PR implements tail-recursion optimisation, as announced in #111.

This change seems to massively improve the performance of paths and repeat, because both are now implemented using tail-recursion. (This can be seen by the impact on tree-paths and ex-implode.) Unfortunately, flatten seems to have become a bit slower. This is probably due to the lower performance of recurse, which is now implemented by definition instead of as native filter. Most other benchmarks remain roughly the same. ack is a bit slower, which might be because it is identified as mixed-tail-recursive (containing tail-recursive and non-tail-recursive calls).

Benchmark n jaq-1.1 jaq-1.2
empty 512 650 700
bf-fib 13 390 410
reverse 1048576 40 40
sort 1048576 120 120
group-by 1048576 400 380
min-max 1048576 200 180
add 1048576 450 470
kv 131072 170 160
kv-update 131072 190 180
kv-entries 131072 590 580
ex-implode 1048576 690 510
reduce 1048576 740 730
try-catch 1048576 160 160
tree-flatten 17 590 650
tree-update 17 400 400
tree-paths 17 1280 470
to-fromjson 65536 30 40
ack 7 540 570

Furthermore, this PR now enables more lazy evaluation of arrays. Previously, running

def f: 1, [f]; limit(1; f)

would result in a stack overflow, because it evaluated [f] eagerly. Now, this yields just 1, as expected.