Or else, it’s [rilly] complex

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 as part of a potential refactoring and saw some surprising results.

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 = <function1>

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.

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.