Rewrite manifestJson to execute "stacklessly" inside evaluate() - #1142
Draft
johnbartholomew wants to merge 9 commits into
Draft
Rewrite manifestJson to execute "stacklessly" inside evaluate()#1142johnbartholomew wants to merge 9 commits into
johnbartholomew wants to merge 9 commits into
Conversation
Copy link
Copy Markdown
Collaborator
Sorry, something went wrong.
Closed
sbarzowski
approved these changes
Jun 23, 2024
Copy link
Copy Markdown
Contributor
|
I think it's a good idea and the code looks reasonable. What is missing? |
Sorry, something went wrong.
MrG9090
approved these changes
Nov 6, 2024
MrG9090
approved these changes
Nov 10, 2024
This gets rid of the mutual recursion between manifestJson() and evaluate(), turning the manifestJson processing into a part of the interpreter's main loop. It should remove one avenue for native stack overflows during execution. The Interpreter needed to be able to convert things to JSON anyway, as this is the behaviour of string coercion (for string concatenation), and also the behaviour when using the 'error' operator/statement.
johnbartholomew
force-pushed
the
stackess-manifest
branch
from
becdd87 to
28eb1c9
Compare
March 1, 2026 11:26
This was referenced Mar 1, 2026
Copy link
Copy Markdown
Contributor
|
@johnbartholomew In the pr in sjsonnet, My implementation uses the JVM's native stack when the nesting is shallow, and uses an ArrayDequeue when the nesting depth exceeds a certain limit, which is based on your solution. |
Sorry, something went wrong.
stephenamar-db
pushed a commit
to databricks/sjsonnet
that referenced
this pull request
Mar 4, 2026
Motivation: This can reduce some stack usage of the jvm native frame refs:google/jsonnet#1142 on main ``` 125] Benchmark (path) Mode Cnt Score Error Units 125] RegressionBenchmark.main bench/resources/bug_suite/assertions.jsonnet avgt 0.271 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.01.jsonnet avgt 0.067 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.02.jsonnet avgt 42.941 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.03.jsonnet avgt 12.480 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.04.jsonnet avgt 31.739 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.06.jsonnet avgt 0.397 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.07.jsonnet avgt 3.589 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.08.jsonnet avgt 0.056 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.09.jsonnet avgt 0.063 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/gen_big_object.jsonnet avgt 0.936 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/large_string_join.jsonnet avgt 2.312 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/large_string_template.jsonnet avgt 2.288 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/realistic1.jsonnet avgt 2.965 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/realistic2.jsonnet avgt 71.454 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64.jsonnet avgt 0.787 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64Decode.jsonnet avgt 0.595 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64DecodeBytes.jsonnet avgt 9.178 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64_byte_array.jsonnet avgt 1.416 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/comparison.jsonnet avgt 23.242 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/comparison2.jsonnet avgt 72.070 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/escapeStringJson.jsonnet avgt 0.048 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/foldl.jsonnet avgt 9.089 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/lstripChars.jsonnet avgt 0.609 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/manifestJsonEx.jsonnet avgt 0.069 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/manifestTomlEx.jsonnet avgt 0.085 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/manifestYamlDoc.jsonnet avgt 0.072 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/member.jsonnet avgt 0.707 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/parseInt.jsonnet avgt 0.050 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/reverse.jsonnet avgt 11.035 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/rstripChars.jsonnet avgt 0.590 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/stripChars.jsonnet avgt 0.584 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/substr.jsonnet avgt 0.159 ms/op 125] RegressionBenchmark.main bench/resources/sjsonnet_suite/setDiff.jsonnet avgt 0.485 ms/op 125] RegressionBenchmark.main bench/resources/sjsonnet_suite/setInter.jsonnet avgt 0.435 ms/op 125] RegressionBenchmark.main bench/resources/sjsonnet_suite/setUnion.jsonnet avgt 0.723 ms/op 125/125, SUCCESS] ./mill bench.runRegressions 434s ``` with this ``` 125] Benchmark (path) Mode Cnt Score Error Units 125] RegressionBenchmark.main bench/resources/bug_suite/assertions.jsonnet avgt 0.297 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.01.jsonnet avgt 0.068 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.02.jsonnet avgt 39.359 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.03.jsonnet avgt 12.130 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.04.jsonnet avgt 30.164 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.06.jsonnet avgt 0.418 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.07.jsonnet avgt 3.256 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.08.jsonnet avgt 0.057 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/bench.09.jsonnet avgt 0.064 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/gen_big_object.jsonnet avgt 0.982 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/large_string_join.jsonnet avgt 2.111 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/large_string_template.jsonnet avgt 2.250 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/realistic1.jsonnet avgt 2.945 ms/op 125] RegressionBenchmark.main bench/resources/cpp_suite/realistic2.jsonnet avgt 65.150 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64.jsonnet avgt 0.815 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64Decode.jsonnet avgt 0.626 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64DecodeBytes.jsonnet avgt 9.380 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/base64_byte_array.jsonnet avgt 1.443 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/comparison.jsonnet avgt 22.236 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/comparison2.jsonnet avgt 76.674 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/escapeStringJson.jsonnet avgt 0.049 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/foldl.jsonnet avgt 9.004 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/lstripChars.jsonnet avgt 0.643 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/manifestJsonEx.jsonnet avgt 0.069 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/manifestTomlEx.jsonnet avgt 0.084 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/manifestYamlDoc.jsonnet avgt 0.073 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/member.jsonnet avgt 0.708 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/parseInt.jsonnet avgt 0.051 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/reverse.jsonnet avgt 11.257 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/rstripChars.jsonnet avgt 0.641 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/stripChars.jsonnet avgt 0.624 ms/op 125] RegressionBenchmark.main bench/resources/go_suite/substr.jsonnet avgt 0.159 ms/op 125] RegressionBenchmark.main bench/resources/sjsonnet_suite/setDiff.jsonnet avgt 0.488 ms/op 125] RegressionBenchmark.main bench/resources/sjsonnet_suite/setInter.jsonnet avgt 0.423 ms/op 125] RegressionBenchmark.main bench/resources/sjsonnet_suite/setUnion.jsonnet avgt 0.743 ms/op 125/125, SUCCESS] ./mill bench.runRegressions 434s ```
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Reviewers
2 more reviewers4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This gets rid of the mutual recursion between manifestJson and evaluate, turning the manifestJson processing into a part of the interpreter's main loop. It should remove one avenue for native stack overflows during execution. Of course, the runtime still tracks its own internal call stack depth and can safely abort.
The Interpreter needed to be able to convert things to JSON anyway, as this is the behaviour of string coercion (for string concatenation), and also the behaviour when using the error operator/statement.
Some general notes:
TL;DR: This is not ready yet, and might never be ready. But hey, it's been fun to make. Consider it just a sketch or prototype for now.
Edit - Note that there is still potentially deep recursion in some other pieces of the interpreter code. For example, code dealing with HeapExtendedObject (e.g., objectFieldsAux, objectInvariants, countLeaves, findObject) needs to recurse through the object inheritance tree. Not sure that's a problem though.