Why doesn't tail recursion results in better performance in this code?

Question

I was creating a faster string splitter method. First, I wrote a non-tail recursive version returning List. Next, a tail recursive one using ListBuffer and then calling toList (+= and toList are O(1)). I fully expected the tail recursive version to be faster, but that is not the case.

Can anyone explain why?

Original version:

def split(s: String, c: Char, i: Int = 0): List[String] = if (i < 0) Nil else {
  val p = s indexOf (c, i)
  if (p < 0) s.substring(i) :: Nil else s.substring(i, p) :: split(s, c, p + 1)
}

Tail recursive one:

import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer
def split(s: String, c: Char): Seq[String] = {
  val buffer = ListBuffer.empty[String]
  @tailrec def recurse(i: Int): Seq[String] =  {
    val p = s indexOf (c, i)
    if (p < 0) {
      buffer += s.substring(i)
      buffer.toList
    } else {
      buffer += s.substring(i, p)
      recurse(p + 1)
    }
  }
  recurse(0)
}

This was benchmarked with code here, with results here, by #scala's jyxent.

Answer 1

You're simply doing more work in the second case. In the first case, you might overflow your stack, but every operation is really simple, and :: is as small of a wrapper as you can get (all you have to do is create the wrapper and point it to the head of the other list). In the second case, not only do you create an extra collection initially and have to form a closure around s and buffer for the nested method to use, but you also use the heavierweight ListBuffer which has to check for each += whether it's already been copied out to a list, and uses different code paths depending on whether it's empty or not (in order to get the O(1) append to work).

Answer 2

You expect the tail recursive version to be faster due to the tail call optimization and I think this is right, if you compare apples to apples:

def split3(s: String, c: Char): Seq[String] = {
  @tailrec def recurse(i: Int, acc: List[String] = Nil): Seq[String] =  {
    val p = s indexOf (c, i)
    if (p < 0) {
      s.substring(i) :: acc
    } else {
      recurse(p + 1, s.substring(i, p) :: acc)
    }
  }
  recurse(0) // would need to reverse
}

I timed this split3 to be faster, except of course to get the same result it would need to reverse the result.

It does seem ListBuffer introduces inefficiencies that the tail recursion optimization cannot make up for.

Edit: thinking about avoiding the reverse...

def split3(s: String, c: Char): Seq[String] = {
  @tailrec def recurse(i: Int, acc: List[String] = Nil): Seq[String] =  {
    val p = s lastIndexOf (c, i)
    if (p < 0) {
      s.substring(0, i + 1) :: acc
    } else {
      recurse(p - 1, s.substring(p + 1, i + 1) :: acc)
    }
  }
  recurse(s.length - 1)
}

This has the tail call optimization and avoids ListBuffer.