ApplicativeBenchmark.scala

import cats.{ Applicative, Traverse }
import cats.std.list._
import java.util.concurrent.TimeUnit
import org.openjdk.jmh.annotations._

trait DefaultApApplicative[F[_]] extends Applicative[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] = map(product(ff, fa)) {
    case (f, a) => f(a)
  }
}

trait DefaultMapApplicative[F[_]] extends Applicative[F] {
  def map[A, B](fa: F[A])(f: A => B): F[B] = ap(pure(f))(fa)
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] = ap(map(fa)(a => (b: B) => (a, b)))(fb)
}

@State(Scope.Thread)
@BenchmarkMode(Array(Mode.Throughput))
@OutputTimeUnit(TimeUnit.SECONDS)
class ApplicativeBenchmark {
  val instance1: Applicative[Option] = new DefaultMapApplicative[Option] {
    def pure[A](a: A): Option[A] = Some(a)
    def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] = (ff, fa) match {
      case (Some(f), Some(a)) => Some(f(a))
      case _ => None
    }
  }

  val instance2: Applicative[Option] = new DefaultMapApplicative[Option] {
    def pure[A](a: A): Option[A] = Some(a)
    def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] = (ff, fa) match {
      case (Some(f), Some(a)) => Some(f(a))
      case _ => None
    }

    override def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
    override def product[A, B](fa: Option[A], fb: Option[B]): Option[(A, B)] = (fa, fb) match {
      case (Some(a), Some(b)) => Some((a, b))
      case _ => None
    }
  }

  val instance3: Applicative[Option] = new DefaultApApplicative[Option] {
    def pure[A](a: A): Option[A] = Some(a)
    def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
    def product[A, B](fa: Option[A], fb: Option[B]): Option[(A, B)] = (fa, fb) match {
      case (Some(a), Some(b)) => Some((a, b))
      case _ => None
    }
  }

  val data: List[Option[Int]] = (0 to 10000).map(Option(_)).toList

  @Benchmark
  def traverse1: Option[List[Int]] = Traverse[List].sequence(data)(instance1)

  @Benchmark
  def traverse2: Option[List[Int]] = Traverse[List].sequence(data)(instance2)

  @Benchmark
  def traverse3: Option[List[Int]] = Traverse[List].sequence(data)(instance3)
}

Throughput:

[info] Benchmark                        Mode  Cnt      Score     Error  Units
[info] ApplicativeBenchmark.traverse1  thrpt   40  13317.254 ±  44.992  ops/s
[info] ApplicativeBenchmark.traverse2  thrpt   40  21190.597 ± 165.308  ops/s
[info] ApplicativeBenchmark.traverse3  thrpt   40  21327.822 ±  69.654  ops/s

Allocation rate:

[info] Benchmark                                           Mode  Cnt       Score       Error   Units
[info] ApplicativeBenchmark.traverse1:gc.alloc.rate.norm  thrpt   20  420835.736 ±    10.453    B/op
[info] ApplicativeBenchmark.traverse2:gc.alloc.rate.norm  thrpt   20  311151.151 ± 10149.335    B/op
[info] ApplicativeBenchmark.traverse3:gc.alloc.rate.norm  thrpt   20  310959.283 ± 10421.961    B/op