### 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:

- pf3(“hello”)
- pf2.isDefinedAt(“hello”)
- pf1.isDefinedAt(“hello”)
- pf.isDefinedAt(“hello”)

—

- pf2(“hello”)
- pf1.isDefinedAt(“hello”)
- pf.isDefinedAt(“hello”)

—

- pf1(“hello”)
- pf.isDefinedAt(“hello”)

—

- 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”?

- pf3(“hell”)
- pf2.isDefinedAt(“hell”) || pf.isDefinedAt(“hell”)
- pf1.isDefinedAt(“hell”) || pf.isDefinedAt(“hell”)
- pf.isDefinedAt(“hell”) || pf.isDefinedAt(“hell”)

—

- 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.