List.foldRight performance evaluation (run against Scala 2.10.0 with OpenJDK 1.7.0).

CaliperBenchmark.scala

case class ListFoldRightBenchmark() extends SimpleScalaBenchmark {
  import scala.collection.mutable.ArrayStack

  @Param(Array("0", "1", "2", "3", "5", "10", "100", "500", "1000", "2000"))
  val length: Int = 0

  var list: List[Int] = _

  override def setUp() {
    // set up all your benchmark data here
    list = (0 to length).toList
  }

  val addValues = (left: Int, right: Int) => left + right

  /*
  def foldRightAlternative1[A,B](list: List[A])(z: B)(op: (A,B) => B): B = {
    val s = new ArrayStack[A]
    list.foreach(a => s += a)
    s.iterator.foldLeft(z)((b,a) => op(a,b))
  }

  def foldRightAlternative2[A,B](list: List[A])(z: B)(op: (A,B) => B): B = {
    import scala.collection.mutable.ArrayStack
    val s = new ArrayStack[A]
    list.foreach(a => s += a)
    var r = z
    while (!s.isEmpty) { r = op(s.pop, r) }
    r
  }
  */

  def foldRightAlternative4[A, B](list: List[A])(z: B)(f: (A, B) => B): B =
    if (list.lengthCompare(10) < 0) // MAX_DEPTH=10
      list.foldRight(z)(f)
    else
      list.reverse.foldLeft(z)(flip(f))

  def flip[A, B](f: (A, B) => B): (B, A) => B = (second: B, first: A) => f(first, second)

  def timecurrentFoldRight(reps: Int) = repeat(reps)(list.foldRight(0)(addValues))

  def timecurrentReverseFoldLeft(reps: Int) = repeat(reps)(list.reverse.foldLeft(0)(flip(addValues)))

  //def timefoldRightAlternative1(reps: Int) = repeat(reps)(foldRightAlternative1(list)(0)(addValues))

  //def timefoldRightAlternative2(reps: Int) = repeat(reps)(foldRightAlternative2(list)(0)(addValues))

  def timefoldRightAlternative4(reps: Int) = repeat(reps)(foldRightAlternative4(list)(0)(addValues))

  //def timecurrentReverseFoldLeftOneHundredThousand(reps: Int) = repeat(reps)((0 to 100000).toList.reverse.foldLeft(0)(flip(addValues)))

  //def timefoldRightAlternative4OneHundredThousand(reps: Int) = repeat(reps)(foldRightAlternative4((0 to 100000).toList)(0)(addValues))
}

object CaliperListFoldRightBenchmarkRunner {
  def main(args: Array[String]) {
    Runner.main(classOf[ListFoldRightBenchmark], args)
  }
}

Output

[info]  0% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=0} 7.86 ns; σ=0.01 ns @ 3 trials
[info]  3% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=0} 10.66 ns; σ=1.88 ns @ 10 trials
[info]  7% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=0} 10.10 ns; σ=0.04 ns @ 3 trials
[info] 10% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=1} 14.09 ns; σ=0.03 ns @ 3 trials
[info] 13% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=1} 17.69 ns; σ=0.14 ns @ 3 trials
[info] 17% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=1} 17.52 ns; σ=0.71 ns @ 10 trials
[info] 20% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=2} 18.12 ns; σ=0.07 ns @ 3 trials
[info] 23% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=2} 25.01 ns; σ=0.19 ns @ 3 trials
[info] 27% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=2} 21.97 ns; σ=0.74 ns @ 10 trials
[info] 30% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=3} 25.60 ns; σ=0.16 ns @ 3 trials
[info] 33% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=3} 32.73 ns; σ=0.27 ns @ 3 trials
[info] 37% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=3} 30.05 ns; σ=0.06 ns @ 3 trials
[info] 40% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=5} 38.64 ns; σ=0.18 ns @ 3 trials
[info] 43% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=5} 52.02 ns; σ=0.24 ns @ 3 trials
[info] 47% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=5} 45.09 ns; σ=2.25 ns @ 10 trials
[info] 50% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=10} 73.29 ns; σ=0.45 ns @ 3 trials
[info] 53% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=10} 97.15 ns; σ=1.43 ns @ 10 trials
[info] 57% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=10} 110.32 ns; σ=0.12 ns @ 3 trials
[info] 60% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=100} 601.09 ns; σ=10.10 ns @ 10 trials
[info] 63% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=100} 874.19 ns; σ=7.16 ns @ 3 trials
[info] 67% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=100} 799.21 ns; σ=7.91 ns @ 6 trials
[info] 70% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=500} 3878.12 ns; σ=50.46 ns @ 10 trials
[info] 73% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=500} 4336.24 ns; σ=43.34 ns @ 4 trials
[info] 77% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=500} 3980.11 ns; σ=68.34 ns @ 10 trials
[info] 80% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=1000} 8007.56 ns; σ=77.13 ns @ 3 trials
[info] 83% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=1000} 8784.73 ns; σ=82.55 ns @ 8 trials
[info] 87% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=1000} 8192.57 ns; σ=107.57 ns @ 10 trials
[info] 90% Scenario{vm=java, trial=0, benchmark=currentFoldRight, length=2000} 18305.89 ns; σ=544.02 ns @ 10 trials
[info] 93% Scenario{vm=java, trial=0, benchmark=currentReverseFoldLeft, length=2000} 17793.30 ns; σ=175.51 ns @ 5 trials
[info] 97% Scenario{vm=java, trial=0, benchmark=foldRightAlternative4, length=2000} 16403.81 ns; σ=117.96 ns @ 3 trials
[info] 
[info] length              benchmark       ns linear runtime
[info]      0       currentFoldRight     7.86 =
[info]      0 currentReverseFoldLeft    10.66 =
[info]      0  foldRightAlternative4    10.10 =
[info]      1       currentFoldRight    14.09 =
[info]      1 currentReverseFoldLeft    17.69 =
[info]      1  foldRightAlternative4    17.52 =
[info]      2       currentFoldRight    18.12 =
[info]      2 currentReverseFoldLeft    25.01 =
[info]      2  foldRightAlternative4    21.97 =
[info]      3       currentFoldRight    25.60 =
[info]      3 currentReverseFoldLeft    32.73 =
[info]      3  foldRightAlternative4    30.05 =
[info]      5       currentFoldRight    38.64 =
[info]      5 currentReverseFoldLeft    52.02 =
[info]      5  foldRightAlternative4    45.09 =
[info]     10       currentFoldRight    73.29 =
[info]     10 currentReverseFoldLeft    97.15 =
[info]     10  foldRightAlternative4   110.32 =
[info]    100       currentFoldRight   601.09 =
[info]    100 currentReverseFoldLeft   874.19 =
[info]    100  foldRightAlternative4   799.21 =
[info]    500       currentFoldRight  3878.12 ======
[info]    500 currentReverseFoldLeft  4336.24 =======
[info]    500  foldRightAlternative4  3980.11 ======
[info]   1000       currentFoldRight  8007.56 =============
[info]   1000 currentReverseFoldLeft  8784.73 ==============
[info]   1000  foldRightAlternative4  8192.57 =============
[info]   2000       currentFoldRight 18305.89 ==============================
[info]   2000 currentReverseFoldLeft 17793.30 =============================
[info]   2000  foldRightAlternative4 16403.81 ==========================
[info] 
[info] vm: java
[info] trial: 0

Note, this is based on the following benchmark template project using Caliper: https://github.com/sirthias/scala-benchmarking-template