Skip to content

Commit

Permalink
better let ANF transform (#6606)
Browse files Browse the repository at this point in the history
Ask @nickchapman-da for details on what this transform does and why it's
better. I have no clue.

What I do understand is that current master has a stack-consuming
behaviour that just so happens to not reach the 1mb default stack size
on the tests we run, and that this presumably better version of a let
transform had been left out from the original ANF PR because it was
pushing the stack consumption over that 1mb limit.

Besides reintroducing the "better" let version, this PR applies an
almost full CPS transform to the set of mutually recursive functions
that grow the stack. Combined with the trampoline, this should mean the
ANF transform itself is done in (almost) constant stack space.

The one exception to that is the `flattenAlts` function, which has been
left as a plain imperative loop. This does mean that we consume stack
linearly with the nesting level of alts, so conceivably this could still
blow the stack. There is no fundamental reason that makes this hard, it
just seemed unnecessary for the stack consumption and potentially
damaging to performance (changing a native Java loop on an array to a
recursive list consumption).

To verify the stack-consuming behaviour on master, one can apply this
patch:

```patch
diff --git a/ledger/sandbox/BUILD.bazel b/ledger/sandbox/BUILD.bazel
index a717e66fb..4c953b3ea 100644
--- a/ledger/sandbox/BUILD.bazel
+++ b/ledger/sandbox/BUILD.bazel
@@ -124,6 +124,7 @@ da_scala_library(

 da_scala_binary(
     name = "sandbox-binary",
+    jvm_flags = ["-Xss256k"],
     main_class = "com.daml.platform.sandbox.SandboxMain",
     resources = ["src/main/resources/logback.xml"],
     visibility = ["//visibility:public"],
```

then run

```
bazel test -t- //ledger/sandbox:conformance-test-contract-id-seeding-memory
```

The same process can be repeated on this branch to verify that, at
least, this now runs under 256kb of stack for all our tests. I don't
know of a good way to get a stronger guarantee on stack allocations.

While my primary motivation here is correctness (and termination, I
guess), this does seem to yield a modest performance improvement. On a
test machine, I got the following results as confidence intervals:

* `master` (b4915a4): 54.00, 54.56
* this branch: 52.54, 53.11

I've only ran the benchmark once on each and don't have enough
experience with it to know how reliable those numbers are. I'll try to
run some more.

CHANGELOG_BEGIN
CHANGELOG_END
  • Loading branch information
garyverhaegen-da authored Jul 6, 2020
1 parent 303d047 commit b3aab72
Showing 1 changed file with 261 additions and 168 deletions.
Loading

0 comments on commit b3aab72

Please sign in to comment.