refactor speedy.Compiler.freeVars to be functional #6542
Conversation
garyverhaegen-da
requested review from
hurryabit and
remyhaemmerle-da
as code owners
garyverhaegen-da
force-pushed
the
random-refactoring
branch
from
8ff63a7 to
6502a5c
Compare
|
I’ll leave it to someone else to judge whether we want to merge this (code looks reasonable to me) but I can’t help but point to the Ben’s excellent blog post on efficient variable traversals in Haskell https://www.haskell.org/ghc/blog/20190728-free-variable-traversals.html (yes I know Haskell performance characteristics are different so it doesn’t necessarily apply here but it’s still interesting) |
There was a problem hiding this comment.
I am not sure it is very worthwhile to refactor this piece of code in a functional way.
since the imperative part is properly confined inside the body of a function.
Saying that, I have no objection about rewriting the code in a functional way.
You code seems however quadratic in the number of free variables, because of the set union (++) potentially made at each iterations.
I suggest you add an accumulator to the go method to track the free variables seen so far. I have made some change suggestions to give you an idea of what I mean.
daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala
Outdated
Show resolved
Hide resolved
| var free = Set.empty[Int] | ||
|
|
||
| def go(expr: SExpr): Unit = | ||
| def go(expr: SExpr, bound: Int): Set[Int] = |
There was a problem hiding this comment.
| def go(expr: SExpr, bound: Int): Set[Int] = | |
| def go(expr: SExpr, bound: Int, free: Set[Int]): Set[Int] = |
There was a problem hiding this comment.
It looks like if you accept all @remyhaemmerle-da's changes, you can add @tailrec to this function too.
There was a problem hiding this comment.
Unfortunately you can't because we are traversing a tree.
There was a problem hiding this comment.
It's a tree traversal so I don't think that will be possible. args.foldLeft(free)((free, arg) => go(arg, bound, free)) for example is not a (recursive) tail call.
daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala
Outdated
Show resolved
Hide resolved
daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala
Outdated
Show resolved
Hide resolved
| go(scrut, bound) ++ alts | ||
| .map { case SCaseAlt(pat, body) => go(body, bound + patternNArgs(pat)) } | ||
| .reduce(_ ++ _) |
There was a problem hiding this comment.
| go(scrut, bound) ++ alts | |
| .map { case SCaseAlt(pat, body) => go(body, bound + patternNArgs(pat)) } | |
| .reduce(_ ++ _) | |
| alts.foldLeft(go(scrut, bound, free)) { | |
| case (free, SCaseAlt(pat, body)) => go(body, bound + patternNArgs(pat), free) | |
| } |
daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala
Outdated
Show resolved
Hide resolved
garyverhaegen-da
force-pushed
the
random-refactoring
branch
from
6502a5c to
4119e28
Compare
|
@remyhaemmerle-da I made the change you requested, AFAICT this is now doing exactly one set insertion operation per free variable (and no set union at all). |
I was trying to track down what looks like a new source of flakiness in the ANF work (#6440), which manifested in a stack overflow on the recursion of the `go` function in speedy.Compiler. I spent a bit of time refactoring this to be functional in order to then trampoline it, only to realize afterwards that I had worked on `freeVars/go` whereas the one blowing up the stack was `validate/go`. Obviously, it did nothing to reduce the rate of flakiness on the stack overflow issue I was trying to address, as it's a separate function. So there isn't really a good reason for this change, except I had done it and I do believe the code looks marginally nicer, so might as well submit it. CHANGELOG_BEGIN CHANGELOG_END
garyverhaegen-da
force-pushed
the
random-refactoring
branch
from
4119e28 to
65fd270
Compare
After careful consideration, we decided that the change in evaluation order that was accidentally introduced by the ANF changes should be considered a breaking change or arguably even a bug and should not land in 1.3.0. Therefore, this PR reverts the following commits: 1. 353d0da 2. a45b510 3. 04c7b2a 4. a624dd7 5. b3aab72 Other PRs mostly had trivial merge conflicts that I resolved. The two most interesting ones here are probably 1. #6576 which was easy to resolve and the change to return SEValue instead of SExpr is still nice and useful even if we do not need the guarantees. 2. it #6542 which required some changes since the constructors changed. If you want to review those changes in detail (they are pretty straightforward so not too important), it’s probably easiest to check out this PR and run ``` git diff 2cd2a8f daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala ``` to see the diff to the parent commit of the first commit that introduced ANF. changelog_begin changelog_end
* Revert ANF changes and add a testcase for evaluation order After careful consideration, we decided that the change in evaluation order that was accidentally introduced by the ANF changes should be considered a breaking change or arguably even a bug and should not land in 1.3.0. Therefore, this PR reverts the following commits: 1. 353d0da 2. a45b510 3. 04c7b2a 4. a624dd7 5. b3aab72 Other PRs mostly had trivial merge conflicts that I resolved. The two most interesting ones here are probably 1. #6576 which was easy to resolve and the change to return SEValue instead of SExpr is still nice and useful even if we do not need the guarantees. 2. it #6542 which required some changes since the constructors changed. If you want to review those changes in detail (they are pretty straightforward so not too important), it’s probably easiest to check out this PR and run ``` git diff 2cd2a8f daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala ``` to see the diff to the parent commit of the first commit that introduced ANF. changelog_begin changelog_end
I was trying to track down what looks like a new source of flakiness in the ANF work (#6440), which manifested in a stack overflow on the recursion of the
gofunction in speedy.Compiler. I spent a bit of time refactoring this to be functional in order to then trampoline it, only to realize afterwards that I had worked onfreeVars/gowhereas the one blowing up the stack wasvalidate/go.Obviously, it did nothing to reduce the rate of flakiness on the stack overflow issue I was trying to address, as it's a separate function.
So there isn't really a good reason for this change, except I had done it and I do believe the code looks marginally nicer, so might as well submit it.
CHANGELOG_BEGIN
CHANGELOG_END