Scala Option[Collection] benchmark

Scala Option[Collection] benchmark

/*
 * Benchmarks of answers posted to http://stackoverflow.com/questions/23914713
 * "How do you stop building an Option[Collection] upon reaching the first None?"
 *
 * Results:
 *
 * version                  ms per iteration
 * -------                  ----------------
 * allPartsIterator:        0.001022
 * allPartsMatchReturn:     0.001544
 * allPartsReturn:          0.002187
 * allPartsWithView:        0.002808
 * allPartsBruteForce:      0.003159
 * allPartsWithMutableFlag: 0.003345
 * allPartsRecursive:       0.003753
 * allPartsFoldLeft:        0.003873
 * allPartsWithStream:      0.008794
 *
 * Environment:
 *   Scala 2.11.1
 *   JVM 1.7.0_55
 *   Intel(R) Core(TM)2 Duo CPU     E8400  @ 3.00GHz
 *   Red Hat Enterprise Linux Workstation release 6.5 (Santiago) 
 */

import scala.annotation.tailrec
import java.lang.management.ManagementFactory

object benchmark {
  val mxbean = ManagementFactory.getThreadMXBean()

  def timeMillis[A](func: => A): Double = {
    val startTime = mxbean.getCurrentThreadCpuTime()
    func
    val endTime = mxbean.getCurrentThreadCpuTime()
    (endTime - startTime) / 1e6
  }

  case class Part(name: String)

  val partNames = List(
    "steering wheel", "rudder", "pointy thing at front",
    "captain's chair", "the box", "large, helium-filled part",
    "propeller", "cigarette lighter", "ashtray", "Zeppelin logo"
  )

  def findPartByName(name: String): Option[Part] =
    // linear search & object creation to make this function a little bit
    // expensive
    partNames.find(_ == name) flatMap { name => Some(Part(name)) }

  def allPartsTime(allFinder: Seq[String] => Option[Seq[Part]]): Double = {
    val numReps = 2000000
    timeMillis {
      for (i <- 1 to numReps) {
        allFinder(Seq(
          "steering wheel", "rudder", "pointy thing at front",
          "captain's chair", "the box", "large, helium-filled part",
          "propeller", "cigarette lighter", "ashtray", "Zeppelin logo"
        ))
        allFinder(Seq.empty)
        allFinder(Seq(
          "non-existent Gothic cathedral",
          "steering wheel", "rudder", "pointy thing at front",
          "captain's chair", "the box", "large, helium-filled part",
          "propeller", "cigarette lighter", "ashtray", "Zeppelin logo"
        ))
      }
    } / numReps
  }

  def allPartsFoldLeft(names: Seq[String]): Option[Seq[Part]] =
    names.foldLeft(Some(Seq.empty): Option[Seq[Part]]) {
      (result, name) => result match {
        case Some(parts) =>
          findPartByName(name) flatMap { part => Some(parts :+ part) }
        case None => None
      }
    }

  def allPartsMatchReturn(names: Seq[String]): Option[Seq[Part]] = Some(
    for (name <- names) yield findPartByName(name) match {
      case Some(part) => part
      case None => return None
    }
  )

  def allPartsIterator(names: Seq[String]): Option[Seq[Part]] = {
    val iterator = names.iterator
    var accum = List.empty[Part]
    while (iterator.hasNext) {
      findPartByName(iterator.next) match {
        case Some(part) => accum +:= part
        case None => return None
      }
    }
    Some(accum.reverse)
  }

  def allPartsRecursive(names: Seq[String]): Option[Seq[Part]] = {
    @tailrec
    def allPartsRec(names: Seq[String], acc: Seq[Part]):
        Option[Seq[Part]] = names match {
      case Seq(x, xs@_*) => findPartByName(x) match {
        case Some(part) => allPartsRec(xs, acc :+ part)
        case None => None
      }
      case _ => Some(acc)
    }

    allPartsRec(names, Seq.empty)
  }
  
  def allPartsWithView(names: Seq[String]): Option[Seq[Part]] = {
      val successes = names.view.map(findPartByName)
                                .takeWhile(!_.isEmpty)
                                .map(_.get)
                                .force
      if (!names.isDefinedAt(successes.size)) Some(successes)
      else None
  }

  def allPartsWithStream(names: Seq[String]): Option[Seq[Part]] = {
      val (good, bad) = names.toStream.map(findPartByName)
                                      .span(!_.isEmpty)
      if (bad.isEmpty) Some(good.map(_.get).toList)
      else None
  }

  def allPartsReturn(names: Seq[String]): Option[Seq[Part]] = Some(
    names.map(findPartByName(_) getOrElse { return None })
  )

  def allPartsWithMutableFlag(names: Seq[String]): Option[Seq[Part]] = {
    var failed = false
    val parts = names map { name => findPartByName(name) match {
      case Some(part) => Some(part)
      case None => failed = true; None
    }} takeWhile(_.nonEmpty)
    if (failed) None else Some(parts.flatten)
  }

  def allPartsBruteForce(names: Seq[String]): Option[Seq[Part]] = {
    val parts = names.map(findPartByName(_))
    if (parts contains None) None else Some(parts.flatten)
  }

  def singleTest(allFinder: Seq[String] => Option[Seq[Part]]) {
    println(allFinder(Seq(
      "steering wheel", "rudder", "pointy thing at front",
      "captain's chair", "the box", "large, helium-filled part",
      "propeller", "cigarette lighter", "ashtray", "Zeppelin logo"
    )))
    println(allFinder(Seq.empty))
    println(allFinder(Seq(
      "non-existent Gothic cathedral",
      "steering wheel", "rudder", "pointy thing at front",
      "captain's chair", "the box", "large, helium-filled part",
      "propeller", "cigarette lighter", "ashtray", "Zeppelin logo"
    )))
  }

  def main(args: Array[String]) {
    val funcs = Seq(
      ("allPartsFoldLeft", allPartsFoldLeft _),
      ("allPartsMatchReturn", allPartsMatchReturn _),
      ("allPartsIterator", allPartsIterator _),
      ("allPartsRecursive", allPartsRecursive _),
      ("allPartsWithView", allPartsWithView _),
      ("allPartsWithStream", allPartsWithStream _),
      ("allPartsWithMutableFlag", allPartsWithMutableFlag _),
      ("allPartsReturn", allPartsReturn _),
      ("allPartsBruteForce", allPartsBruteForce _)
    )
    val results = funcs.map(pair =>
       (pair._1, allPartsTime(pair._2))).sortBy(_._2)
    for (result <- results)
      println(f"${result._1 + ':'}%-24s ${result._2}%8.6f")
  }
}