Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Correct tail recursion & improve compiler complexity #223

Merged
merged 26 commits into from
Nov 5, 2024
Merged

Correct tail recursion & improve compiler complexity #223

merged 26 commits into from
Nov 5, 2024

Conversation

01mf02
Copy link
Owner

@01mf02 01mf02 commented Nov 4, 2024 •
edited
Loading

In #216, @wader found an expression t that would not yield the same result as t | ..
This boiled down to a bug in tail-call optimisation (TCO).

This PR corrects this bug. At the same time, it makes compilation more efficient, in particular when there are many definitions, variables, or labels. For example:

$ (echo 'def a: 1;'; for i in `seq 100000`; do echo 'def b: a;'; done; echo b) > bla.jq
$ jaq -n -f bla.jq
1

Previously, this would have taken quadratic time (with increasing values of seq ...); now, this takes n * log n time.
On the downside, the startup time becomes slightly longer for very small programs.

$ ./bench.sh target/release/jaq-tco-*
{"name": "empty", "n": 512, "time": {"target/release/jaq-tco-bug": [0.28], "target/release/jaq-tco-fix": [0.32]}}
{"name": "bf-fib", "n": 13, "time": {"target/release/jaq-tco-bug": [0.51], "target/release/jaq-tco-fix": [0.52]}}
{"name": "defs", "n": 100000, "time": {"target/release/jaq-tco-bug": [0.04], "target/release/jaq-tco-fix": [0.05]}}
{"name": "reduce-update", "n": 16384, "time": {"target/release/jaq-tco-bug": [0.01, 0.01, 0.01], "target/release/jaq-tco-fix": [0.01, 0.01, 0.01]}}
{"name": "reverse", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.09, 0.08, 0.07], "target/release/jaq-tco-fix": [0.08, 0.08, 0.08]}}
{"name": "sort", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.16, 0.16, 0.16], "target/release/jaq-tco-fix": [0.16, 0.16, 0.15]}}
{"name": "group-by", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.55, 0.55, 0.53], "target/release/jaq-tco-fix": [0.54, 0.54, 0.54]}}
{"name": "min-max", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.25, 0.25, 0.25], "target/release/jaq-tco-fix": [0.25, 0.25, 0.26]}}
{"name": "add", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.55, 0.52, 0.54], "target/release/jaq-tco-fix": [0.53, 0.54, 0.53]}}
{"name": "kv", "n": 131072, "time": {"target/release/jaq-tco-bug": [0.13, 0.13, 0.14], "target/release/jaq-tco-fix": [0.14, 0.14, 0.14]}}
{"name": "kv-update", "n": 131072, "time": {"target/release/jaq-tco-bug": [0.15, 0.15, 0.15], "target/release/jaq-tco-fix": [0.15, 0.15, 0.14]}}
{"name": "kv-entries", "n": 131072, "time": {"target/release/jaq-tco-bug": [0.62, 0.61, 0.61], "target/release/jaq-tco-fix": [0.61, 0.60, 0.61]}}
{"name": "ex-implode", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.56, 0.56, 0.56], "target/release/jaq-tco-fix": [0.56, 0.53, 0.54]}}
{"name": "reduce", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.82, 0.80, 0.83], "target/release/jaq-tco-fix": [0.81, 0.81, 0.81]}}
{"name": "try-catch", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.35, 0.35, 0.36], "target/release/jaq-tco-fix": [0.35, 0.36, 0.36]}}
{"name": "tree-contains", "n": 23, "time": {"target/release/jaq-tco-bug": [0.07, 0.07, 0.07], "target/release/jaq-tco-fix": [0.07, 0.07, 0.07]}}
{"name": "tree-flatten", "n": 17, "time": {"target/release/jaq-tco-bug": [0.89, 0.89, 0.90], "target/release/jaq-tco-fix": [0.89, 0.88, 0.86]}}
{"name": "tree-update", "n": 17, "time": {"target/release/jaq-tco-bug": [0.72, 0.72, 0.71], "target/release/jaq-tco-fix": [0.72, 0.72, 0.72]}}
{"name": "tree-paths", "n": 17, "time": {"target/release/jaq-tco-bug": [0.46, 0.47, 0.45], "target/release/jaq-tco-fix": [0.47, 0.46, 0.47]}}
{"name": "to-fromjson", "n": 65536, "time": {"target/release/jaq-tco-bug": [0.04, 0.04, 0.04], "target/release/jaq-tco-fix": [0.04, 0.04, 0.04]}}
{"name": "ack", "n": 7, "time": {"target/release/jaq-tco-bug": [0.53, 0.53, 0.53], "target/release/jaq-tco-fix": [0.49, 0.49, 0.50]}}
{"name": "range-prop", "n": 128, "time": {"target/release/jaq-tco-bug": [0.38, 0.38, 0.38], "target/release/jaq-tco-fix": [0.38, 0.39, 0.39]}}
{"name": "cumsum", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.31, 0.33, 0.32], "target/release/jaq-tco-fix": [0.33, 0.34, 0.32]}}
{"name": "cumsum-xy", "n": 1048576, "time": {"target/release/jaq-tco-bug": [0.54, 0.54, 0.53], "target/release/jaq-tco-fix": [0.55, 0.54, 0.53]}}

Here, we can see slightly worse values for empty, but improvements for ack.

@01mf02 01mf02 mentioned this pull request Nov 4, 2024
Open
@01mf02 01mf02 merged commit 13077e0 into main Nov 5, 2024
1 check passed
@01mf02 01mf02 deleted the tailrec-again branch November 5, 2024 11:33
wader added a commit to wader/jqjq that referenced this pull request Nov 5, 2024
@wader
WIP: jaq support
91b48f5 
Useful snippets and refrenses:

jaq -L . -n 'include "jqjq"; _builtins_src | lex'
jaq -n -L . -rRs 'include "jqjq"; . | jqjq(["", "--run-tests"]; {})' < jqjq.test
jaq -n -L . 'include "jqjq"; eval("1+2")'
Disable TCO 01mf02/jaq#223 (comment)
wader added a commit to wader/jqjq that referenced this pull request Nov 5, 2024
@wader
WIP: jaq support
6337bcd 
Useful snippets and referencses:

jaq -L . -n 'include "jqjq"; _builtins_src | lex'
jaq -n -L . -rRs 'include "jqjq"; . | jqjq(["", "--run-tests"]; {})' < jqjq.test
jaq -n -L . 'include "jqjq"; eval("1+2")'
Disable TCO 01mf02/jaq#223 (comment)
wader added a commit to wader/jqjq that referenced this pull request Nov 5, 2024
@wader
WIP: jaq support
7e96a58 
Useful snippets and references:

jaq -L . -n 'include "jqjq"; _builtins_src | lex'
jaq -n -L . -rRs 'include "jqjq"; . | jqjq(["", "--run-tests"]; {})' < jqjq.test
jaq -n -L . 'include "jqjq"; eval("1+2")'
Disable TCO 01mf02/jaq#223 (comment)
wader added a commit to wader/jqjq that referenced this pull request Nov 5, 2024
@wader
Add jaq support
ea420fe 
Useful snippets and references:

jaq -L . -n 'include "jqjq"; _builtins_src | lex'
jaq -n -L . -rRs 'include "jqjq"; . | jqjq(["", "--run-tests"]; {})' < jqjq.test
jaq -n -L . 'include "jqjq"; eval("1+2")'
Disable TCO 01mf02/jaq#223 (comment)
wader added a commit to wader/jqjq that referenced this pull request Nov 5, 2024
@wader
Add jaq support
d14de66 
Useful snippets and references:

jaq -L . -n 'include "jqjq"; _builtins_src | lex'
jaq -n -L . -rRs 'include "jqjq"; . | jqjq(["", "--run-tests"]; {})' < jqjq.test
jaq -n -L . 'include "jqjq"; eval("1+2")'
Disable TCO 01mf02/jaq#223 (comment)
@wader wader mentioned this pull request Nov 5, 2024
Draft
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@wader wader wader left review comments

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@01mf02 @wader