Unfiltered uses pattern matching to route incoming requests, so we're pretty sensitive to the performance of partial functions in Scala. Lately I've been looking at the `orElse` method of [PartialFunction][pf] as part of a potential refactoring and saw some surprising results. [pf]: http://www.scala-lang.org/api/rc/scala/PartialFunction.html Say you have these two partial functions defined: val pf: PartialFunction[String, Boolean] = { case "hello" => true } val fallback: PartialFunction[String, Boolean] = { case _ => false } And then you create a chained partial function: val std = pf.orElse(pf).orElse(pf).orElse(fallback) The second and third `pf` add no value; we just want to see how they affect performance. And since it is better to be able to test arbitrary numbers of things, instead of the above you would use a fold. Sort of like this... def std(n: Int) = (pf /: (1 to n)) { (a,_) => a.orElse(pf) }.orElse(fallback) (Don't worry about pasting this into your repl, I'll link to the github in a bit.) For an *n* of 50 you might expect to see some difference in performance between the application of a value in the domain of `pf` compared to one that must be "orElsed" all the way until `fallback`. Conjure a few more functions, one to `time` a block in milliseconds and one to repeat it `alot`, then see what happens: scala> val std50 = std(50) std50: Test.PF = scala> time { alot { std50("hello") } } res1: Long = 446 scala> time { alot { std50("hell") } } res2: Long = 60 I don't know about you, but I was expecting "hello" to be faster, since it matches the first `pf` and doesn't have to be tested against all any of the others. Instead it's an order of magnitude slower. What gives? **A nesting we go** It's probably a good idea at this point to review the definition of the `PartialFunction#orElse` method in Scala. def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]) = new PartialFunction[A1, B1] { def isDefinedAt(x: A1): Boolean = PartialFunction.this.isDefinedAt(x) || that.isDefinedAt(x) def apply(x: A1): B1 = if (PartialFunction.this.isDefinedAt(x)) PartialFunction.this.apply(x) else that.apply(x) } A new partial function is produced each time you call `orElse`, and yes it does look like it's short-circuiting in the right places. It's not apparent why the "hello" case would be so much slower, instead of a little bit faster. To see what's really happening, consider a tiny example: val pf1 = pf.orElse(pf) val pf2 = pf1.orElse(pf) val pf3 = pf2.orElse(fallback) So what happens when we apply this? pf3("hello") First, the merged partial function `pf3` must check if `pf2` is defined for "hello". Then `pf2` must check with `pf1`, and finally `pf1` can say that yes `pf` is defined for "hello". Done? Not at all! `pf3` can safely call `pf2("hello")`, but then we are back in the same `apply` method defined above. `pf2` must check (again) whether `pf1` is defined, and `pf1` will check `pf`. And then we can call `pf1("hello")`... The calls look like this: 1. pf3("hello") 2. pf2.isDefinedAt("hello") 3. pf1.isDefinedAt("hello") 4. pf.isDefinedAt("hello") -- 1. pf2("hello") 2. pf1.isDefinedAt("hello") 3. pf.isDefinedAt("hello") -- 1. pf1("hello") 2. pf.isDefinedAt("hello") -- 1. pf("hello") And that's what we used to call exponential quadratic (*it's been a while!*) complexity, back in programming school. It explains why "hello" is so ungodly slow. But what about "hell"? 1. pf3("hell") 2. pf2.isDefinedAt("hell") || pf.isDefinedAt("hell") 3. pf1.isDefinedAt("hell") || pf.isDefinedAt("hell") 4. pf.isDefinedAt("hell") || pf.isDefinedAt("hell") -- 1. fallback("hell") As the stack unwinds we have to make a call that was short circuited in the "hello" case. But since the nested partial functions are not applied, we avoid rechecking `isDefined` for all lower levels, at each level. As a result, this case is much faster for larger values of *n*. **The Crowbar** Most people probably aren't using large values of *n* where `orElse` is concerned, but as I said we're a bit touchy with this stuff in Unfiltered. I wanted to come up with an alternative implementation that has the linear complexity that most of us assumed `orElse` had all along. The problem is, `PartialFunction` does not give you much to work with. Its only fundamental difference from a standard function is `isDefinedAt`; all its other methods, like `lift`, are conveniences built on top of it. If only there were some way to tentatively apply the function such that we get the value back if it succeeds, to avoid all this mad disassembling and reassembling of the `orElse` russian doll. If only we had the interface that `lift` provides, on partial functions themselves. Well, there is one way. trait PartialAttempt[-A,+B] extends PartialFunction[A,B] { def attempt(x: A): Option[B] } Then toss in a few bat wings, ground up sudafed, and old Java books: def asAttempt[A,B](pf: PartialFunction[A,B]): PartialAttempt[A,B] = pf match { case pa: PartialAttempt[_,_] => pa case pf => new AttemptWrapper(pf) } class AttemptWrapper[-A,+B](underlying: PartialFunction[A,B]) extends PartialAttempt[A,B] { val lifted = underlying.lift def isDefinedAt(x: A) = underlying.isDefinedAt(x) def apply(x: A) = underlying.apply(x) def attempt(x: A) = lifted(x) } Finally, nesting doll class that knows about `attempt`: class OrElse[A,B,A1 <: A, B1 >: B]( left: PartialAttempt[A,B], right: PartialAttempt[A1,B1] ) extends PartialAttempt[A1,B1] { def isDefinedAt(x: A1): Boolean = { left.isDefinedAt(x) || right.isDefinedAt(x) } def apply(x: A1): B1 = { left.attempt(x) orElse { right.attempt(x) } getOrElse { throw new MatchError(x) } } def attempt(x: A1): Option[B1] = { left.attempt(x).orElse { right.attempt(x) } } } And now we can define our replacement `orElse`: def orElse[A, B, A1 <: A, B1 >: B]( left: PartialFunction[A,B], right: PartialFunction[A1, B1] ): PartialFunction[A1, B1] = new OrElse(asAttempt(left), asAttempt(right)) Does it work? n= 45 std: 402, 46 opt: 21, 51 n= 46 std: 418, 44 opt: 22, 53 n= 47 std: 436, 46 opt: 24, 53 n= 48 std: 454, 50 opt: 23, 55 n= 49 std: 474, 47 opt: 25, 55 n= 50 std: 503, 50 opt: 26, 58 It works! *std* is the standard library `orElse`, *opt* is the one implemented as above. The first timing is for "hello", the second for "hell". With opt we avoid the nasty worst case behavior on "hello", and in fact it's faster than for "hell" which is what we originally expected to happen. You can try it yourself, see [n8han/orelse on github][gh]. [gh]: https://github.com/n8han/orelse You might be thinking, couldn't I just `lift` all my `PartialFunctions` and implement a similar `orElse` without the ugly matching on a subtype? Sure! Just rewrite your code to use the type `(A => Option[B])` everywhere instead of partial functions. But as it stands partial functions have valuable support in the language, particularly the ability to be defined with a pattern matching block. And with Unfiltered, I'm reluctant to clutter the type pool when we already have an interface that people seem to like and understand. So yeah, we might incorporate something sneaky like this, with a package private extension of `PartialFunction`. It can be our linearly complex secret.
