Faster implementation of Option.isEmpty?

Question

The implementation of isEmpty in Option is straightforward - here's a sketch:

abstract class Option[+A]           { def isEmpty:Boolean  }
object None extends Option[Nothing] { def isEmpty=true }
final class Some extends Option[+A] { def isEmpty=false }

isEmpty is used extremely heavily, including inside Option itself, so its performance is significant, even though it is so trivial.

I suspect it would be faster to implement it as:

abstract class Option[+A] { final def isEmpty = this eq None  }

This implementation shouldn't require dereferencing the option or calling any methods on it, AFAIK - just a straightforward reference comparison.

I'd performance-test this, but JVM microbenchmarks are so tricky that I really have no confidence in my ability to create a meaningful result.

Are there any factors I'm overlooking?

Answer 1

Actually, you might be right. Using the following code:

sealed abstract class Opshun[+A] {
  final def isEmpty = this eq Nun
  def get: A 
}
object Nun extends Opshun[Nothing] { def get = ??? }
case class Summ[+A](get: A) extends Opshun[A] {}

on the simplest possible test case (array of Option or Opshun), if all you do is test isEmpty, the pattern you suggested is 5x (!) faster, and you can verify this if you manually replace .isEmpty with eq None or a pattern match picking out None.

If you move to a more complex case where you test not-isEmpty and then get a stored value, the difference is less impressive (a third faster).

So the suggestion has merit; it's worth testing in a more official setting.

Note added in edit: this is with arrays large enough so that not everything fits in L2 cache. Either way is equally fast when it fits in L2.

Answer 2

(Based on Eugenes Zhulenev's comment)

It seems HotSpot compiler will do this optimization automatically, as there are only two subclasses of Option:

Polymorphism Performance Mysteries Explained:

The Server HotSpot compiler, according to Cliff Click, deals with bi-morphism as a special case of poly-morphism: "Where the server compiler can prove only two classes reach a call site, it will insert a type-check and then statically call both targets (which may then further inline, etc)."