benchmark for two fold implementation of scala IndexedSeq 'bench/jmh:run -i 10 .*IndexedSeqFoldImplBenchmark.*'

IndexedSeq.scala

/*
 * Scala (https://www.scala-lang.org)
 *
 * Copyright EPFL and Lightbend, Inc.
 *
 * Licensed under Apache License 2.0
 * (http://www.apache.org/licenses/LICENSE-2.0).
 *
 * See the NOTICE file distributed with this work for
 * additional information regarding copyright ownership.
 */

package scala
package collection

import scala.annotation.tailrec
import scala.collection.Searching.{Found, InsertionPoint, SearchResult}
import scala.collection.Stepper.EfficientSplit
import scala.math.Ordering

/** Base trait for indexed sequences that have efficient `apply` and `length` */
trait IndexedSeq[+A] extends Seq[A]
  with IndexedSeqOps[A, IndexedSeq, IndexedSeq[A]]
  with IterableFactoryDefaults[A, IndexedSeq] {
  override protected[this] def stringPrefix: String = "IndexedSeq"

  override def iterableFactory: SeqFactory[IndexedSeq] = IndexedSeq

  override def foldLeft[B](z: B)(f: (B, A) => B): B = {
    var b = z
    var i = 0
    while (i < length) {
      val a = apply(i)
      i += 1
      b = f(b, a)
    }
    b
  }

  override def foldRight[B](z: B)(f: (A, B) => B): B = {
    var b = z
    var i = length
    while (i > 0) {
      i -= 1
      val a = apply(i)
      b = f(a, b)
    }
    b
  }

  def foldLeft2[B](z: B)(f: (B, A) => B): B = {
    val LEN = length
    @inline @tailrec def loop(acc: B, n: Int): B = n match {
      case LEN => acc
      case _ => loop(f(acc, apply(n)), n+1)
    }
    loop(z, 0)
  }

  def foldRight2[B](z: B)(f: (A, B) => B): B = {
    @inline @tailrec def loop(acc: B, n: Int): B = n match {
      case 0 => acc
      case _ => loop(f(apply(n), acc), n-1)
    }
    loop(z, 0)
  }
}

@SerialVersionUID(3L)
object IndexedSeq extends SeqFactory.Delegate[IndexedSeq](immutable.IndexedSeq)

/** Base trait for indexed Seq operations */
trait IndexedSeqOps[+A, +CC[_], +C] extends Any with SeqOps[A, CC, C] { self =>

  def iterator: Iterator[A] = view.iterator

  override def stepper[S <: Stepper[_]](implicit shape: StepperShape[A, S]): S with EfficientSplit = {
    import convert.impl._
    val s = shape.shape match {
      case StepperShape.IntShape    => new IntIndexedSeqStepper   (this.asInstanceOf[IndexedSeqOps[Int, AnyConstr, _]],    0, length)
      case StepperShape.LongShape   => new LongIndexedSeqStepper  (this.asInstanceOf[IndexedSeqOps[Long, AnyConstr, _]],   0, length)
      case StepperShape.DoubleShape => new DoubleIndexedSeqStepper(this.asInstanceOf[IndexedSeqOps[Double, AnyConstr, _]], 0, length)
      case _                        => shape.parUnbox(new AnyIndexedSeqStepper[A](this, 0, length))
    }
    s.asInstanceOf[S with EfficientSplit]
  }

  override def reverseIterator: Iterator[A] = new AbstractIterator[A] {
    private[this] var i = self.length
    def hasNext: Boolean = 0 < i
    def next(): A =
      if (0 < i) {
        i -= 1
        self(i)
      } else Iterator.empty.next()
  }

  override def view: IndexedSeqView[A] = new IndexedSeqView.Id[A](this)

  @deprecated("Use .view.slice(from, until) instead of .view(from, until)", "2.13.0")
  override def view(from: Int, until: Int): IndexedSeqView[A] = view.slice(from, until)

  override protected def reversed: Iterable[A] = new IndexedSeqView.Reverse(this)

  // Override transformation operations to use more efficient views than the default ones
  override def prepended[B >: A](elem: B): CC[B] = iterableFactory.from(new IndexedSeqView.Prepended(elem, this))

  override def take(n: Int): C = fromSpecific(new IndexedSeqView.Take(this, n))

  override def takeRight(n: Int): C = fromSpecific(new IndexedSeqView.TakeRight(this, n))

  override def drop(n: Int): C = fromSpecific(new IndexedSeqView.Drop(this, n))

  override def dropRight(n: Int): C = fromSpecific(new IndexedSeqView.DropRight(this, n))

  override def map[B](f: A => B): CC[B] = iterableFactory.from(new IndexedSeqView.Map(this, f))

  override def reverse: C = fromSpecific(new IndexedSeqView.Reverse(this))

  override def slice(from: Int, until: Int): C = fromSpecific(new IndexedSeqView.Slice(this, from, until))

  override def head: A = apply(0)

  override def headOption: Option[A] = if (isEmpty) None else Some(head)

  override def last: A = apply(length - 1)

  // We already inherit an efficient `lastOption = if (isEmpty) None else Some(last)`

  override final def lengthCompare(len: Int): Int = Integer.compare(length, len)

  override def knownSize: Int = length

  override final def lengthCompare(that: Iterable[_]): Int = {
    val res = that.sizeCompare(length)
    // can't just invert the result, because `-Int.MinValue == Int.MinValue`
    if (res == Int.MinValue) 1 else -res
  }

  override def search[B >: A](elem: B)(implicit ord: Ordering[B]): SearchResult =
    binarySearch(elem, 0, length)(ord)

  override def search[B >: A](elem: B, from: Int, to: Int)(implicit ord: Ordering[B]): SearchResult =
    binarySearch(elem, from, to)(ord)

  @tailrec
  private[this] def binarySearch[B >: A](elem: B, from: Int, to: Int)
                                        (implicit ord: Ordering[B]): SearchResult = {
    if (from < 0) binarySearch(elem, 0, to)
    else if (to > length) binarySearch(elem, from, length)
    else if (to <= from) InsertionPoint(from)
    else {
      val idx = from + (to - from - 1) / 2
      math.signum(ord.compare(elem, apply(idx))) match {
        case -1 => binarySearch(elem, from, idx)(ord)
        case  1 => binarySearch(elem, idx + 1, to)(ord)
        case  _ => Found(idx)
      }
    }
  }
}

IndexedSeqFoldImplBenchmark.scala

package scala.collection.immutable

import java.util.concurrent.TimeUnit

import org.openjdk.jmh.annotations._
import org.openjdk.jmh.infra._

@BenchmarkMode(Array(Mode.AverageTime))
@Fork(2)
@Threads(1)
@Warmup(iterations = 10)
@Measurement(iterations = 10000)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
class IndexedSeqFoldImplBenchmark {
  var list: IndexedSeq[Int] = _

  @Setup(Level.Trial) def doSetup(): Unit = {
    list = (1 to 10000).to(Vector)
  }

  @Benchmark def test(bh: Blackhole): Unit = {
    bh.consume(list.foldLeft(0)(_ + _))
  }

  @Benchmark def test2(bh: Blackhole): Unit = {
    bh.consume(list.foldLeft2(0)(_ + _))
  }
}

sbt

[info] Loading global plugins from /home/e/.sbt/1.0/plugins
[info] Loading settings for project scala-build-build from plugins.sbt ...
[info] Loading project definition from /home/e/Local/scala/project/project
[info] Loading settings for project scala-build from metals.sbt,plugins.sbt ...
[info] Loading project definition from /home/e/Local/scala/project
[info] Loading settings for project root from build.sbt ...
[info] Resolving key references (18307 settings) ...
[info] *** Welcome to the sbt build definition for Scala! ***
[info] Check README.md for more information.
[warn] Multiple main classes detected.  Run 'show discoveredMainClasses' to see the list
Processing 819 classes from /home/e/Local/scala/test/benchmarks/target/scala-2.13/classes with "reflection" generator
Writing out Java source to /home/e/Local/scala/test/benchmarks/target/scala-2.13/src_managed/jmh and resources to /home/e/Local/scala/test/benchmarks/target/scala-2.13/resource_managed/jmh
[warn] Multiple main classes detected.  Run 'show discoveredMainClasses' to see the list
[info] running (fork) org.openjdk.jmh.Main -i 10 .*IndexedSeqFoldImplBenchmark.*
[info] # JMH version: 1.20
[info] # VM version: JDK 1.8.0_242, VM 25.242-b08
[info] # VM invoker: /nix/store/i93m7bna9jmn4xrqjaiwvdzimwkzwnzi-openjdk-8u242-b08-jre/lib/openjdk/jre/bin/java
[info] # VM options: <none>
[info] # Warmup: 10 iterations, 1 s each
[info] # Measurement: 10 iterations, 1 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Average time, time/op
[info] # Benchmark: scala.collection.immutable.IndexedSeqFoldImplBenchmark.test
[info] # Run progress: 0,00% complete, ETA 00:01:20
[info] # Fork: 1 of 2
[info] # Warmup Iteration   1: 60835,552 ns/op
[info] # Warmup Iteration   2: 63267,601 ns/op
[info] # Warmup Iteration   3: 62824,705 ns/op
[info] # Warmup Iteration   4: 52293,731 ns/op
[info] # Warmup Iteration   5: 60084,962 ns/op
[info] # Warmup Iteration   6: 47864,571 ns/op
[info] # Warmup Iteration   7: 57659,649 ns/op
[info] # Warmup Iteration   8: 48046,066 ns/op
[info] # Warmup Iteration   9: 51100,564 ns/op
[info] # Warmup Iteration  10: 58277,736 ns/op
[info] Iteration   1: 50145,280 ns/op
[info] Iteration   2: 53019,314 ns/op
[info] Iteration   3: 49218,567 ns/op
[info] Iteration   4: 53545,482 ns/op
[info] Iteration   5: 54380,844 ns/op
[info] Iteration   6: 47097,488 ns/op
[info] Iteration   7: 49795,376 ns/op
[info] Iteration   8: 48702,644 ns/op
[info] Iteration   9: 50434,200 ns/op
[info] Iteration  10: 48237,018 ns/op
[info] # Run progress: 25,00% complete, ETA 00:01:01
[info] # Fork: 2 of 2
[info] # Warmup Iteration   1: 61878,895 ns/op
[info] # Warmup Iteration   2: 59536,361 ns/op
[info] # Warmup Iteration   3: 46351,032 ns/op
[info] # Warmup Iteration   4: 63271,371 ns/op
[info] # Warmup Iteration   5: 41564,749 ns/op
[info] # Warmup Iteration   6: 52198,027 ns/op
[info] # Warmup Iteration   7: 51336,922 ns/op
[info] # Warmup Iteration   8: 43442,228 ns/op
[info] # Warmup Iteration   9: 45175,709 ns/op
[info] # Warmup Iteration  10: 49300,540 ns/op
[info] Iteration   1: 47022,835 ns/op
[info] Iteration   2: 44175,939 ns/op
[info] Iteration   3: 47193,120 ns/op
[info] Iteration   4: 52730,330 ns/op
[info] Iteration   5: 53337,362 ns/op
[info] Iteration   6: 53497,664 ns/op
[info] Iteration   7: 49655,085 ns/op
[info] Iteration   8: 46022,686 ns/op
[info] Iteration   9: 45611,325 ns/op
[info] Iteration  10: 45076,759 ns/op
[info] Result "scala.collection.immutable.IndexedSeqFoldImplBenchmark.test":
[info]   49444,966 ±(99.9%) 2743,959 ns/op [Average]
[info]   (min, avg, max) = (44175,939, 49444,966, 54380,844), stdev = 3159,947
[info]   CI (99.9%): [46701,007, 52188,925] (assumes normal distribution)
[info] # JMH version: 1.20
[info] # VM version: JDK 1.8.0_242, VM 25.242-b08
[info] # VM invoker: /nix/store/i93m7bna9jmn4xrqjaiwvdzimwkzwnzi-openjdk-8u242-b08-jre/lib/openjdk/jre/bin/java
[info] # VM options: <none>
[info] # Warmup: 10 iterations, 1 s each
[info] # Measurement: 10 iterations, 1 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Average time, time/op
[info] # Benchmark: scala.collection.immutable.IndexedSeqFoldImplBenchmark.test2
[info] # Run progress: 50,00% complete, ETA 00:00:41
[info] # Fork: 1 of 2
[info] # Warmup Iteration   1: 64619,343 ns/op
[info] # Warmup Iteration   2: 60362,016 ns/op
[info] # Warmup Iteration   3: 51951,637 ns/op
[info] # Warmup Iteration   4: 47310,428 ns/op
[info] # Warmup Iteration   5: 44775,094 ns/op
[info] # Warmup Iteration   6: 46998,381 ns/op
[info] # Warmup Iteration   7: 43988,169 ns/op
[info] # Warmup Iteration   8: 42843,338 ns/op
[info] # Warmup Iteration   9: 45968,779 ns/op
[info] # Warmup Iteration  10: 49604,955 ns/op
[info] Iteration   1: 46086,430 ns/op
[info] Iteration   2: 46961,587 ns/op
[info] Iteration   3: 46703,236 ns/op
[info] Iteration   4: 45892,153 ns/op
[info] Iteration   5: 43053,004 ns/op
[info] Iteration   6: 47712,348 ns/op
[info] Iteration   7: 44510,007 ns/op
[info] Iteration   8: 44526,658 ns/op
[info] Iteration   9: 45909,705 ns/op
[info] Iteration  10: 44281,988 ns/op
[info] # Run progress: 75,00% complete, ETA 00:00:20
[info] # Fork: 2 of 2
[info] # Warmup Iteration   1: 62086,413 ns/op
[info] # Warmup Iteration   2: 60101,221 ns/op
[info] # Warmup Iteration   3: 49718,001 ns/op
[info] # Warmup Iteration   4: 42735,245 ns/op
[info] # Warmup Iteration   5: 47416,990 ns/op
[info] # Warmup Iteration   6: 43890,133 ns/op
[info] # Warmup Iteration   7: 43240,723 ns/op
[info] # Warmup Iteration   8: 42820,888 ns/op
[info] # Warmup Iteration   9: 45401,032 ns/op
[info] # Warmup Iteration  10: 45821,185 ns/op
[info] Iteration   1: 50755,297 ns/op
[info] Iteration   2: 46464,212 ns/op
[info] Iteration   3: 46068,125 ns/op
[info] Iteration   4: 43807,530 ns/op
[info] Iteration   5: 44705,509 ns/op
[info] Iteration   6: 46954,600 ns/op
[info] Iteration   7: 47188,899 ns/op
[info] Iteration   8: 45079,241 ns/op
[info] Iteration   9: 45724,459 ns/op
[info] Iteration  10: 51739,229 ns/op
[info] Result "scala.collection.immutable.IndexedSeqFoldImplBenchmark.test2":
[info]   46206,211 ±(99.9%) 1837,295 ns/op [Average]
[info]   (min, avg, max) = (43053,004, 46206,211, 51739,229), stdev = 2115,831
[info]   CI (99.9%): [44368,916, 48043,506] (assumes normal distribution)
[info] # Run complete. Total time: 00:01:22
[info] Benchmark                          Mode  Cnt      Score      Error  Units
[info] IndexedSeqFoldImplBenchmark.test   avgt   20  49444,966 ± 2743,959  ns/op
[info] IndexedSeqFoldImplBenchmark.test2  avgt   20  46206,211 ± 1837,295  ns/op
[success] Total time: 89 s (01:29), completed 24.04.2020 19:39:22