From f6d72991bbba9a9610a9873424b3506f2b26be3f Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Wed, 8 Oct 2014 11:30:23 +1000 Subject: SI-8893 Restore linear perf in TailCalls with nested matches Compilation perfomance of the enclosed test regressed when the new pattern matcher was introduced, specifically when the tail call elimination phase was made aware of its tree shapes in cd3d34203. The code added in that commit detects an application to a tail label in order to treat recursive calls in the argument as in tail position. If the transform of that argument makes no change, it falls back to `rewriteApply`, which transforms the argument again (although this time on a non-tail-position context.) This commit avoids the second transform by introducing a flag to `rewriteApply` to mark the arguments are pre-transformed. I don't yet see how that fixes the exponential performance, as on the surface it seems like a constant factor improvement. But the numbers don't lie, and we can now compile the test case in seconds, rather than before when it was running for > 10 minutes. This test case was based on a code pattern generated by the Avro serializer macro in: https://github.com/paytronix/utils-open/tree/release/2014/ernststavrosgrouper The exponential performance in that context is visualed here: https://twitter.com/dridus/status/519544110173007872 Thanks for @rmacleod2 for minimizing the problem. --- test/files/pos/t8893.scala | 129 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) create mode 100644 test/files/pos/t8893.scala (limited to 'test') diff --git a/test/files/pos/t8893.scala b/test/files/pos/t8893.scala new file mode 100644 index 0000000000..b87c8bdd3c --- /dev/null +++ b/test/files/pos/t8893.scala @@ -0,0 +1,129 @@ +// Took > 10 minutes to run the tail call phase. +object Test { + def a(): Option[String] = Some("a") + + def main(args: Array[String]) { + a() match { + case Some(b1) => + a() match { + case Some(b2) => + a() match { + case Some(b3) => + a() match { + case Some(b4) => + a() match { + case Some(b5) => + a() match { + case Some(b6) => + a() match { + case Some(b7) => + a() match { + case Some(b8) => + a() match { + case Some(b9) => + a() match { + case Some(b10) => + a() match { + case Some(b11) => + a() match { + case Some(b12) => + a() match { + case Some(b13) => + a() match { + case Some(b14) => + a() match { + case Some(b15) => + a() match { + case Some(b16) => + a() match { + case Some(b17) => + a() match { + case Some(b18) => + a() match { + case Some(b19) => + a() match { + case Some(b20) => + a() match { + case Some(b21) => + a() match { + case Some(b22) => + a() match { + case Some(b23) => + a() match { + case Some(b24) => + a() match { + case Some(b25) => + a() match { + case Some(b26) => + a() match { + case Some(b27) => + a() match { + case Some(b28) => + a() match { + case Some(b29) => + a() match { + case Some(b30) => + println("yay") + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + case None => None + } + } +} + -- cgit v1.2.3 From cae09d760d8778c03d09957786522d766430b218 Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Sun, 2 Nov 2014 21:39:41 +1000 Subject: SI-8893 Test case to show that tailrec continues to work As suggested during code review, this test checks that the tailcalls phase recurses appropriately below a method that doesn and does not itself tail call. The test case is based on the pattern of code that to trigger super-linear performance in this transform. --- test/files/run/t8893.scala | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 test/files/run/t8893.scala (limited to 'test') diff --git a/test/files/run/t8893.scala b/test/files/run/t8893.scala new file mode 100644 index 0000000000..6fef8ae912 --- /dev/null +++ b/test/files/run/t8893.scala @@ -0,0 +1,40 @@ +import annotation.tailrec + +object Test { + def a(): Option[String] = Some("a") + + def test1: Any = { + a() match { + case Some(b1) => + a() match { + case Some(b2) => + @tailrec + def tick(i: Int): Unit = if (i < 0) () else tick(i - 1) + tick(10000000) // testing that this doesn't SOE + case None => None + } + case None => None + } + } + + def test2: Any = { + a() match { + case Some(b1) => + a() match { + case Some(b2) => + @tailrec + def tick(i: Int): Unit = if (i < 0) () else tick(i - 1) + tick(10000000) // testing that this doesn't SOE + case None => test1 + } + case None => + test1 // not a tail call + test1 + } + } + + def main(args: Array[String]) { + test1 + test2 + } +} -- cgit v1.2.3 From c6c58071a785af3a55e7e51339461e86c58ae876 Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Mon, 3 Nov 2014 11:11:28 +1000 Subject: SI-8893 Test tailcall transform for mix of tail/non-tail recursion Another excellent test suggestion by Dear Reviewer. After tail calls, the transform results in: ``` def tick(i: Int): Unit = { val _$this: Test.type = Test.this; _tick(_$this: Test.type, i: Int){ if (i.==(0)) () else if (i.==(42)) { Test.this.tick(0); _tick(Test.this, i.-(1).asInstanceOf[Int]()) } else _tick(Test.this, i.-(1).asInstanceOf[Int]()).asInstanceOf[Unit]() } }; ``` We test this by mostly exercising the tail-recursive code path with a level of recursion that would overflow the stack if we weren't using jumps. --- test/files/run/t8893b.scala | 15 +++++++++++++++ 1 file changed, 15 insertions(+) create mode 100644 test/files/run/t8893b.scala (limited to 'test') diff --git a/test/files/run/t8893b.scala b/test/files/run/t8893b.scala new file mode 100644 index 0000000000..19120871aa --- /dev/null +++ b/test/files/run/t8893b.scala @@ -0,0 +1,15 @@ +// Testing that recursive calls in tail positions are replaced with +// jumps, even though the method contains recursive calls outside +// of the tail position. +object Test { + def tick(i : Int): Unit = + if (i == 0) () + else if (i == 42) { + tick(0) /*not in tail posiiton*/ + tick(i - 1) + } else tick(i - 1) + + def main(args: Array[String]): Unit = { + tick(1000000) + } +} -- cgit v1.2.3