DiffBench.scala

package diff

import org.openjdk.jmh.annotations._

@State(Scope.Thread)
class DiffBench {
  val example1: String = "a" * 1000
  val example2: String = "ab" * 100

  def compare(pair: (Option[Char], Option[Char])) = pair match { 
    case (Some(x), None)    => Some(s"$x is undefined")
    case (None, Some(y))    => Some(s"$y is missing")
    case (Some(x), Some(y)) => if (x != y) Some(s"$x != $y") else None 
    case _ => None
  }

  def diffOrig(s1: String, s2: String): IndexedSeq[String] = {
    val os1 = s1.map(Option.apply)
    val os2 = s2.map(Option.apply)
    os1.zipAll(os2, None, None).flatMap(compare)
  }

  def diffOrigList(s1: String, s2: String): List[String] = {
    val os1 = s1.map(Option.apply)
    val os2 = s2.map(Option.apply)
    os1.zipAll(os2, None, None).flatMap(compare).toList
  }

  def diffRec(a: String, b: String): List[String] = {
    val l = a.toIterator
    val r = b.toIterator

    @annotation.tailrec
    def loop(res: List[String]): List[String] =
      if (l.isEmpty) {
        res.reverse ++ r.map(c => s"$c is missing")
      } else {
        if (r.isEmpty) {
          res.reverse ++ l.map(c => s"$c is undefined")
        } else {
          val lhead = l.next()
          val rhead = r.next()

          if (lhead == rhead) {
            loop(res)
          } else {
            loop(s"$lhead != $rhead" +: res)
          }
        }
      }

    loop(Nil)
  }

  def diffConcise(s1: String, s2: String): List[String] =
    (s1, s2).zipped.collect {
      case (x, y) if x != y => s"$x != $y"
    }.toList ++
      s1.drop(s2.length).map(x => s"$x is undefined") ++
      s2.drop(s1.length).map(y => s"$y is missing")

  def diffFast(s1: String, s2: String): IndexedSeq[String] = {
    val builder = Vector.newBuilder[String]

    def diff(short: String, long: String, status: String) = {
      builder.sizeHint(long.length)
      var i = 0

      while (i < short.length) {
        val x = s1.charAt(i)
        val y = s2.charAt(i)
        if (x != y) builder += s"$x != $y"
        i += 1
      }

      while (i < long.length) {
        val x = long.charAt(i)
        builder += s"$x is $status"
        i += 1
      }
    }

    if (s1.length <= s2.length) diff(s1, s2, "missing")
      else diff(s2, s1, "undefined")

    builder.result
  }

  def diffFastList(s1: String, s2: String): List[String] = {
    val builder = List.newBuilder[String]

    def diff(short: String, long: String, status: String) = {
      builder.sizeHint(long.length)
      var i = 0

      while (i < short.length) {
        val x = s1.charAt(i)
        val y = s2.charAt(i)
        if (x != y) builder += s"$x != $y"
        i += 1
      }

      while (i < long.length) {
        val x = long.charAt(i)
        builder += s"$x is $status"
        i += 1
      }
    }

    if (s1.length <= s2.length) diff(s1, s2, "missing")
      else diff(s2, s1, "undefined")

    builder.result
  }

  @Benchmark
  def checkOrig: IndexedSeq[String] = diffOrig(example1, example2)

  @Benchmark
  def checkOrigList: List[String] = diffOrigList(example1, example2)

  @Benchmark
  def checkRec: List[String] = diffRec(example1, example2)

  @Benchmark
  def checkConcise: List[String] = diffConcise(example1, example2)

  @Benchmark
  def checkFast: IndexedSeq[String] = diffFast(example1, example2)

  @Benchmark
  def checkFastList: List[String] = diffFastList(example1, example2)
}

On 2.12.8:

Benchmark                 Mode  Cnt       Score     Error  Units
DiffBench.checkConcise   thrpt   20   47412.127 ± 550.693  ops/s
DiffBench.checkFast      thrpt   20  108661.093 ± 371.827  ops/s
DiffBench.checkFastList  thrpt   20   91745.269 ± 157.128  ops/s
DiffBench.checkOrig      thrpt   20    8129.848 ±  59.989  ops/s
DiffBench.checkOrigList  thrpt   20    7916.637 ±  15.736  ops/s
DiffBench.checkRec       thrpt   20   62409.682 ± 580.529  ops/s

And allocation rates:

Benchmark                                                  Mode  Cnt       Score       Error   Units
DiffBench.checkConcise:·gc.alloc.rate.norm                thrpt    3   96408.001 ±     0.001    B/op
DiffBench.checkFast:·gc.alloc.rate.norm                   thrpt    3   67624.000 ±     0.001    B/op
DiffBench.checkFastList:·gc.alloc.rate.norm               thrpt    3   84832.000 ±     0.001    B/op
DiffBench.checkOrig:·gc.alloc.rate.norm                   thrpt    3  158056.006 ±     0.004    B/op
DiffBench.checkOrigList:·gc.alloc.rate.norm               thrpt    3  179768.006 ±     0.004    B/op
DiffBench.checkRec:·gc.alloc.rate.norm                    thrpt    3   89784.001 ±     0.001    B/op