Skip to content

Commit

Permalink
Speedy Tail Call Optimization (digital-asset#6003)
Browse files Browse the repository at this point in the history 
* Speedy Tail call optimization

The goal of this PR is to achieve Tail call optimization digital-asset#5767

Tail call optimization means that tail-calls execute without consuming resources. In particular, they must not consume stack space.

Speedy has two stacks: The `env`-stack and the `kontStack`. For an optimized tail call in Speedy, we must not extend either. In Speedy, all function calls are executed via the code `enterFullyAppliedFunction`. The behaviour of this code (prior to this PR) is as follows:

(1) Push the values of all args and free-variables on the env-stack (because that's where the code expects to find them), and
(2) Push a KPop continuation on the kontStack, which will restore the env-stack to its original size before returning to the code which made the function call.

We must stop doing both these things. We achieve this as follows:

(1) We address function args and free-vars via a new machine component: the current `frame`.
(2) We make continuations responsible for restoring their own environment.

As well as achieving proper tail calls, we also gain a performance improvement by (a) removing the many pushes to the env-stack, and (b) never having to push (and then later re-enter) a KPop continuation. The args array and the free-vars array already existed, so there is no additional cost associated with constructing these array. The only extra costs (which are smaller than the gains) are that we must manage the new `frame` component of the machine, and we must record frame/env-size information in continuations so they can restore their environment.

To make use of the frame, we need to identify (at compile time) the run-time location for every variable in a speedy expression. This is done during the `closureConvert` phase. At run-time, an environment is now composed of both the existing env-stack and the frame. The only values which now live on the env-stack are those introduced by let-bindings and pattern-match-destructuring. All other are found in the frame.

Changes to SEExpr:
- Introduce a new expression form `SELoc`, with 3 sub classes: SELocS/SELocA/SELocF to represent the run-time location of a variable.
- SELocS/A/F execute by calling corresponding lookup function in Speedy: getEnv(Stack,Arg,Free).
- SEMakeClo takes a list of SELoc instead of list of int.
- During closure conversion all SEVar are replaced by an SELocS/A/F.
- SEVar are not allowed to exist at run-time (just as SEAbs may not exist).
- We adapt the synthesised code for SEBuiltinRecursiveDefinition: FoldL, FoldR, EqualList

It is worth noting the prior code also had the notion of before/after closureConvert, but SEVar was used for both meanings: Prior to closureConvert it meant the relative-index of the enclosing binder (lambda,let,..). After closureConvert it meant the relative-offset from the top of the env-stack where the value would be found at run-time. These are not quite the same! Now we have different sub-types (SEVar vs SELoc), this change of mode is made more explicit.

Run-time changes:
- Use the existing `KFun` continuation as the new `Frame` component.
- `KFun` allows access to both the args of the current application, and the free-vars of the current closure.
- A variable is looked up by it's run-time location (SELocS/A/F)
- A function application is executed (`enterFullyAppliedFunction`), by setting the machine's `frame` component to the new current `KFun`.
- When a continuation (KArg, KMatch, KPushTo, KCatch) is pushed, we record the current Frame and current stack depth within the continuation, so when it is entered, it can call `restoreEnv` to restore the environment to the state when the continuation was pushed.

Changes to Compiler:

- The required changes are to the `closureConvert` and `validate`.
- `closureConvert` `remaps` is now a `Map` from the `SEVar`s relative-index to `SELoc`
- `validate` now tracks 3-ints (maxS,masA,maxF)

changelog_begin
changelog_end

* changes for Remy

* Changes for Martin

* test designed explicitly to blow if the free variables are captured incorrectly

* address more comments

* improve comment about shift in Compiler
  • Loading branch information
@nickchapman-da
nickchapman-da authored May 20, 2020
1 parent 4882327 commit ee4f893
Show file tree
Hide file tree
Showing 11 changed files with 386 additions and 204 deletions.
84 changes: 63 additions & 21 deletions daml-lf/interpreter/perf/src/main/scala/com/daml/lf/explore/Explore.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -24,35 +24,42 @@ object PlaySpeedy {
val config: Config = parseArgs(args0)
val compiler: Compiler = Compiler(Map.empty, Compiler.NoProfile)

val e: SExpr = compiler.unsafeClosureConvert(examples(config.exampleName))
val m: Machine = makeMachine(e)
runMachine(config, m)
val names: List[String] = config.names match {
case Nil => examples.toList.map(_._1)
case xs => xs
}

names.foreach { name =>
val (expected, expr) = examples(name)
val converted = compiler.unsafeClosureConvert(expr)
val machine = makeMachine(converted)
runMachine(name, machine, expected)
}
}

final case class Config(
exampleName: String,
names: List[String],
)

def usage(): Unit = {
println("""
|usage: explore [EXAMPLE-NAME]
|usage: explore [EXAMPLES]
|default: run all known examples
""".stripMargin)
}

def parseArgs(args0: List[String]): Config = {

var exampleName: String = "thrice-thrice"

var names: List[String] = Nil
def loop(args: List[String]): Unit = args match {
case Nil => {}
case "-h" :: _ => usage()
case "--help" :: _ => usage()
case name :: args =>
exampleName = name
names = names ++ List(name)
loop(args)
}
loop(args0)
Config(exampleName)
Config(names)
}

private val txSeed = crypto.Hash.hashPrivateKey("SpeedyExplore")
Expand All @@ -69,22 +76,29 @@ object PlaySpeedy {
)
}

def runMachine(config: Config, machine: Machine): Unit = {
def runMachine(name: String, machine: Machine, expected: Int): Unit = {

println(s"example name: ${config.exampleName}")
println(s"example name: $name")

machine.run() match {
case SResultFinalValue(value) => {
case SResultFinalValue(value) =>
println(s"final-value: $value")
}
value match {
case SInt64(got) =>
if (got != expected) {
throw new MachineProblem(s"Expected final integer to be $expected, but got $got")
}
case _ =>
throw new MachineProblem(s"Expected final-value to be an integer")
}
case res =>
throw new MachineProblem(s"Unexpected result from machine $res")
}
}

final case class MachineProblem(s: String) extends RuntimeException(s, null, false, false)

def examples: Map[String, SExpr] = {
def examples: Map[String, (Int, SExpr)] = {

def num(n: Long): SExpr = SEValue(SInt64(n))

Expand All @@ -102,13 +116,41 @@ object PlaySpeedy {
def thrice2(f: SExpr, x: SExpr): SExpr = SEApp(f, Array(SEApp(f, Array(SEApp(f, Array(x))))))
val thrice = SEAbs(2, thrice2(SEVar(2), SEVar(1)))

Map(
"sub" -> subtract2(num(11), num(33)),
"sub/sub" -> subtract2(subtract2(num(1), num(3)), subtract2(num(5), num(10))),
"subF" -> SEApp(subtract, Array(num(88), num(55))),
"thrice" -> SEApp(thrice, Array(decrement, num(0))),
"thrice-thrice" -> SEApp(thrice, Array(thrice, decrement, num(0))),
val examples = List(
(
"sub", //11-33
-22,
subtract2(num(11), num(33))),
(
"sub/sub", // (1-3)-(5-10)
3,
subtract2(subtract2(num(1), num(3)), subtract2(num(5), num(10)))),
(
"subF", //88-55
33,
SEApp(subtract, Array(num(88), num(55)))),
(
"thrice", // thrice (\x -> x - 1) 0
-3,
SEApp(thrice, Array(decrement, num(0)))),
(
"thrice-thrice", //thrice thrice (\x -> x - 1) 0
-27,
SEApp(thrice, Array(thrice, decrement, num(0)))),
(
"free", // let (a,b,c) = (30,100,21) in twice (\x -> x - (a-c)) b
82,
SELet(
Array(num(30), num(100), num(21)),
SEApp(
twice,
Array(SEAbs(1, subtract2(SEVar(1), subtract2(SEVar(4), SEVar(2)))), SEVar(2)))) //100
)
)

val res = examples.map { case (k, x, e) => (k, (x, e)) }.toMap

res
}

}
28 changes: 16 additions & 12 deletions daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Classify.scala
View file
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 +14,9 @@ object Classify { // classify the machine state w.r.t what step occurs next
var ctrlValue: Int,
// expression classification (ctrlExpr)
var evalue: Int,
var evar: Int,
var evarS: Int,
var evarA: Int,
var evarF: Int,
var eapp: Int,
var eclose: Int,
var ebuiltin: Int,
Expand All @@ -28,7 +30,6 @@ object Classify { // classify the machine state w.r.t what step occurs next
var ewronglytypedcontractid: Int,
// kont classification (ctrlValue)
var kfinished: Int,
var kpop: Int,
var karg: Int,
var kfun: Int,
var kpushto: Int,
Expand All @@ -42,7 +43,9 @@ object Classify { // classify the machine state w.r.t what step occurs next
List(
("CtrlExpr:", ctrlExpr),
("- evalue", evalue),
("- evar", evar),
("- evarS", evarS),
("- evarA", evarA),
("- evarF", evarF),
("- eapp", eapp),
("- eclose", eclose),
("- ebuiltin", ebuiltin),
Expand All @@ -55,7 +58,6 @@ object Classify { // classify the machine state w.r.t what step occurs next
("- eimportvalue", eimportvalue),
("CtrlValue:", ctrlValue),
("- kfinished", kfinished),
("- kpop", kpop),
("- karg", karg),
("- kfun", kfun),
("- kpushto", kpushto),
Expand All @@ -68,7 +70,7 @@ object Classify { // classify the machine state w.r.t what step occurs next
}

def newEmptyCounts(): Counts = {
Counts(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Counts(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
}

def classifyMachine(machine: Machine, counts: Counts): Unit = {
Expand All @@ -86,7 +88,10 @@ object Classify { // classify the machine state w.r.t what step occurs next
def classifyExpr(exp: SExpr, counts: Counts): Unit = {
exp match {
case SEValue(_) => counts.evalue += 1
case SEVar(_) => counts.evar += 1
case SEVar(_) => //not expected at runtime
case SELocS(_) => counts.evarS += 1
case SELocA(_) => counts.evarA += 1
case SELocF(_) => counts.evarF += 1
case SEApp(_, _) => counts.eapp += 1
case SEMakeClo(_, _, _) => counts.eclose += 1
case SEBuiltin(_) => counts.ebuiltin += 1
Expand All @@ -96,7 +101,7 @@ object Classify { // classify the machine state w.r.t what step occurs next
case SECase(_, _) => counts.ecase += 1
case SEBuiltinRecursiveDefinition(_) => counts.ebuiltinrecursivedefinition += 1
case SECatch(_, _, _) => counts.ecatch += 1
case SEAbs(_, _) => //never expect these!
case SEAbs(_, _) => //not expected at runtime
case SELabelClosure(_, _) => ()
case SEImportValue(_) => counts.eimportvalue += 1
case SEWronglyTypeContractId(_, _, _) => counts.ewronglytypedcontractid += 1
Expand All @@ -105,14 +110,13 @@ object Classify { // classify the machine state w.r.t what step occurs next

def classifyKont(kont: Kont, counts: Counts): Unit = {
kont match {
case KPop(_) => counts.kpop += 1
case KArg(_) => counts.karg += 1
case KArg(_, _, _) => counts.karg += 1
case KFun(_, _, _) => counts.kfun += 1
case KPushTo(_, _) => counts.kpushto += 1
case KPushTo(_, _, _, _) => counts.kpushto += 1
case KCacheVal(_, _) => counts.kcacheval += 1
case KLocation(_) => counts.klocation += 1
case KMatch(_) => counts.kmatch += 1
case KCatch(_, _, _) => counts.kcatch += 1
case KMatch(_, _, _) => counts.kmatch += 1
case KCatch(_, _, _, _) => counts.kcatch += 1
case KFinished => counts.kfinished += 1
case KLabelClosure(_) | KLeaveClosure(_) => ()
}
Expand Down
Loading

0 comments on commit ee4f893

Please sign in to comment.