Benchmarking WorkArrayBuffer vs. WorkList for Akka issue #1789 (https://github.com/akka/akka/pull/1789)

gistfile1.scala

import scala.collection.mutable
import scala.annotation.tailrec

class Entry[T](val ref: Option[T], val permanent: Boolean) {
  var next: Entry[T] = null
  var isDeleted = false
}

object WorkList {
  def empty[T] = new WorkList[T]
}

/**
 * Fast, small, and dirty implementation of a linked list that removes transient work entries once they are processed.
 * The list is not thread safe! However it is expected to be reentrant. This means a processing function can add/remove
 * entries from the list while processing. Most important, a processing function can remove its own entry from the list.
 * The first remove must return true and any subsequent removes must return false.
 * @tparam T The type of the item
 */
class WorkList[T] {

  import WorkList._

  val head = new Entry[T](None, true)
  var tail = head

  /**
   * Appends an entry to the work list.
   * @param ref The entry.
   * @return The updated work list.
   */
  def add(ref: T, permanent: Boolean) = {
    if (tail == head) {
      tail = new Entry[T](Some(ref), permanent)
      head.next = tail
    } else {
      tail.next = new Entry[T](Some(ref), permanent)
      tail = tail.next
    }
    this
  }

  /**
   * Removes an entry from the work list
   * @param ref The entry.
   * @return True if the entry is removed, false if the entry is not found.
   */
  def remove(ref: T): Boolean = {

    @tailrec
    def remove(parent: Entry[T], entry: Entry[T]): Boolean = {
      if (entry.ref.get == ref) {
        parent.next = entry.next // Remove entry
        if (tail == entry) tail = parent
        entry.isDeleted = true
        true
      } else if (entry.next != null) remove(entry, entry.next)
      else false
    }

    if (head.next == null) false else remove(head, head.next)
  }

  /**
   * Tries to process each entry using the processing function. Stops at the first entry processing succeeds.
   * If the entry is not permanent, the entry is removed.
   * @param processFn The processing function, returns true if processing succeeds.
   * @return true if an entry has been processed, false if no entries are processed successfully.
   */
  def process(processFn: T ⇒ Boolean): Boolean = {

    @tailrec
    def process(parent: Entry[T], entry: Entry[T]): Boolean = {
      val processed = processFn(entry.ref.get)
      if (processed) {
        if (!entry.permanent && !entry.isDeleted) {
          parent.next = entry.next // Remove entry
          if (tail == entry) tail = parent
          entry.isDeleted = true
        }
        true // Handled
      } else if (entry.next != null) process(entry, entry.next)
      else false
    }

    if (head.next == null) false else process(head, head.next)
  }

  /**
   * Appends another WorkList to this WorkList.
   * @param other The other WorkList
   * @return This WorkList
   */
  def addAll(other: WorkList[T]) = {
    if (other.head.next != null) {
      tail.next = other.head.next
      tail = other.tail
    }
    this
  }

  /**
   * Removes all entries from this WorkList
   * @return True if at least one entry is removed. False if none is removed.
   */
  def removeAll() = {
    if (head.next == null) false
    else {
      head.next = null
      tail = head
      true
    }
  }
}

class Status[A](val item: A, val permanent: Boolean) { var isDeleted = false }

object WorkArrayBuffer {
  def empty[A]: WorkArrayBuffer[A] = new WorkArrayBuffer[A]
}

class WorkArrayBuffer[A] {
  import WorkArrayBuffer._

  private val underlying = mutable.ArrayBuffer.empty[Status[A]]

  def add(item: A, permanent: Boolean): WorkArrayBuffer[A] = {
    underlying += new Status(item, permanent)
    this
  }

  def remove(item: A): Boolean = {
    underlying.indexWhere { _.item == item } match {
      case -1 ⇒ false
      case idx ⇒
        val status = underlying(idx)
        status.isDeleted = true
        underlying.remove(idx)
        true
    }
  }

  def process(f: A ⇒ Boolean): Boolean = {
    underlying.indexWhere { s ⇒ f(s.item) } match {
      case -1 => false
      case idx ⇒
        val status = underlying(idx)
        if (!status.permanent && !status.isDeleted) {
          underlying.remove(idx)
          status.isDeleted = true
        }
        true
    }
  }

  def addAll(other: WorkArrayBuffer[A]): WorkArrayBuffer[A] = {
    underlying ++= other.underlying
    this
  }

  def removeAll(): WorkArrayBuffer[A] = {
    underlying.clear()
    this
  }

  def size: Int = underlying.size
}

val REPS = 100000
var total = 0L
var i = 0

def banner(s: String) = {
  println()
  println(s)
}

def time[A](f: => A): (Long, A) = {
  val t0 = System.nanoTime
  val rv = f
  (System.nanoTime - t0, rv)
}

def mkWorkArrayBuffer(numEntries: Int): WorkArrayBuffer[Int] = {
  val map = WorkArrayBuffer.empty[Int]
  (1 to numEntries).foreach { i => map.add(i, permanent = false) }
  map
}

def mkList(numEntries: Int): WorkList[Int] = {
  val list = WorkList.empty[Int]
  (1 to numEntries).foreach { i => list.add(i, permanent = false) }
  list
}

// ADD
banner("WorkArrayBuffer#add")
i = 0
total = time { 
  while (i < REPS) {
    mkWorkArrayBuffer(1000)
    i += 1
  }
}._1
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#add")
total = 0L
i = 0
total = time { 
  while (i < REPS) {
    mkList(1000)
    i += 1
  }
}._1
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

// REMOVE

banner("WorkArrayBuffer#remove(head)")
total = 0L
i = 0
while (i < REPS) {
  val m = mkWorkArrayBuffer(1000)
  total += time { m.remove(1) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#remove(head)")
total = 0L
i = 0
while (i < REPS) {
  val m = mkList(1000)
  total += time { m.remove(1) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkArrayBuffer#remove(middle)")
total = 0L
i = 0
while (i < REPS) {
  val m = mkWorkArrayBuffer(1000)
  total += time { m.remove(500) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#remove(middle)")
total = 0L
i = 0
while (i < REPS) {
  val m = mkList(1000)
  total += time { m.remove(500) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkArrayBuffer#remove(last)")
total = 0L
i = 0
while (i < REPS) {
  val m = mkWorkArrayBuffer(1000)
  total += time { m.remove(1000) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#remove(last)")
total = 0L
i = 0
while (i < REPS) {
  val m = mkList(1000)
  total += time { m.remove(1000) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

// process
banner("WorkArrayBuffer#process")
total = 0L
i = 0
while (i < REPS) {
  val m = mkWorkArrayBuffer(1000)
  total += time { 
    m.process { _ == 500 }
  }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#process")
total = 0L
i = 0
while (i < REPS) {
  val m = mkList(1000)
  total += time { 
    m.process { _ == 500 }
  }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

// addAll
banner("WorkArrayBuffer#addAll")
total = 0L
i = 0
while (i < REPS) {
  val m = mkWorkArrayBuffer(1000)
  val m2 = mkWorkArrayBuffer(1000)
  total += time { m.addAll(m2) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#addAll")
total = 0L
i = 0
while (i < REPS) {
  val m = mkList(1000)
  val m2 = mkList(1000)
  total += time { m.addAll(m2) }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

// removeAll
banner("WorkArrayBuffer#removeAll")
total = 0L
i = 0
while (i < REPS) {
  val m = mkWorkArrayBuffer(1000)
  total += time { m.removeAll() }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))

banner("WorkList#removeAll")
total = 0L
i = 0
while (i < REPS) {
  val m = mkList(1000)
  total += time { m.removeAll() }._1
  i += 1
}
println("%dns for %d reps (%gns/rep)".format(total, REPS, total.toDouble/REPS))