Monday, March 11, 2013

A More Efficient Option

Updated: 2013-03-12

Scala's Option type is a big improvement in type safety over Java's null checking and NullPointerException's. Unfortunately when wrapping a value in Some there is a quite big overhead: creation of one additional object containing a reference to the value. It would be more efficient if we could represent Some as the unboxed pointer value and encode None as the null value, but at the same time preserving the type safety as we get with the Option type (for example Kotlin uses this approach in it's builtin support for nullable types). Well, we can do exactly this with value classes introduced in Scala 2.10:

final case class Option[+T](value: Any = null) extends AnyVal with Product with Serializable {
  private def unsafeGet = value.asInstanceOf[T]
  def isEmpty: Boolean = value == null

The reason that the class parameter is of type Any and not T is that it's not allowed to create a value of type Nothing. We still want to be able to create a None value of type Option[Nothing] though so we delay the unsafe cast to T (using the unsafeGet method) until the value is actually required and we've checked that it's actually there using the isEmpty method.

The code is on GitHub if someone wants to try it out. It's pretty much a dropin replacement for the standard Scala Option type.

Memory Usage Comparisons

Below is a comparison in memory usage between the scala.Option type and the unboxed AnyVal option type when allocating 1M objects each containing one optional value:

scala.Some: 33 MB
scala.None: 19 MB
scala.Some : Any: 34 MB
scala.None : Any: 19 MB
AnyVal Some: 19 MB
AnyVal None: 19 MB
AnyVal Some : Any: 34 MB
AnyVal None : Any: 34 MB

As one would expect, memory usage for Some is almost halved and for None the memory usage is unchanged. The downside of using the AnyVal option is that it uses more memory when a None is upcasted to a super type because then the compiler will box the reference. I would assume this is a quite rare case though.


decodeideas said...

Is there any reason why this should not be the default option?

Jesper Nordenberg said...

One disadvantage is that it takes more memory when a None value is upcasted because then the reference is boxed by the compiler (I've updated the memory comparison to include this case). However, this is not a very common case, and in the other cases it's more efficient. Other than that I don't see why the scala.Option class couldn't be turned into a value class.

Dan said...

One detail that is missed compared to the default scala Option is the Option.apply utility method. The case class that you have created will lose the type parameter if you try to use it like the original apply method, so you'd have to add in the type explicitly.

Unknown said...

A problem with this implementation is that it can not handle Some(null), which is very common. E.g. call get on a Map[String,String] containing a null value.

It is possible to cover that case using a private guard value for Some(null) or for None.

See github.