diff options
Diffstat (limited to 'test/benchmarks/src/main')
7 files changed, 390 insertions, 6 deletions
diff --git a/test/benchmarks/src/main/scala/scala/BitManipulationBenchmark.scala b/test/benchmarks/src/main/scala/scala/BitManipulationBenchmark.scala new file mode 100644 index 0000000000..23e303ede0 --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/BitManipulationBenchmark.scala @@ -0,0 +1,170 @@ +package scala.collection + +import org.openjdk.jmh.annotations._ +import org.openjdk.jmh.infra._ +import org.openjdk.jmh.runner.IterationType +import benchmark._ +import java.util.concurrent.TimeUnit + +@BenchmarkMode(Array(Mode.AverageTime)) +@Fork(2) +@Threads(1) +@Warmup(iterations = 10) +@Measurement(iterations = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class BitManipulationBenchmark { + val powersOfTwo = Array(1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824) + + ////////////////////////////////////////////// + + @Benchmark def withIntegerBitCount(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = withIntegerBitCount(v) + // assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)") + bh.consume(leadingZeros) + } + } + + private def withIntegerBitCount(v: Int) = Integer.SIZE - Integer.bitCount(v - 1) + + ////////////////////////////////////////////// + + @Benchmark def withIntegerNumberOfLeadingZeros(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = withIntegerNumberOfLeadingZeros(v) + // assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)") + bh.consume(leadingZeros) + } + } + + private def withIntegerNumberOfLeadingZeros(v: Int) = Integer.numberOfLeadingZeros(v - 1) + + ////////////////////////////////////////////// + + @Benchmark def withLoop(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = withLoop(v) + bh.consume(leadingZeros) + } + } + + private def withLoop(v: Int): Int = { + var r = Integer.SIZE + var copy = v >> 1 + while (copy != 0) { + r -= 1 + copy = copy >> 1 + } + r + } + + ////////////////////////////////////////////// + + @Benchmark def withMatch(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = withMatch(v) + // assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)") + bh.consume(leadingZeros) + } + } + + private def withMatch(i: Int) = i match { + case 1 => 32 + case 2 => 31 + case 4 => 30 + case 8 => 29 + case 16 => 28 + case 32 => 27 + case 64 => 26 + case 128 => 25 + case 256 => 24 + case 512 => 23 + case 1024 => 22 + case 2048 => 21 + case 4096 => 20 + case 8192 => 19 + case 16384 => 18 + case 32768 => 17 + case 65536 => 16 + case 131072 => 15 + case 262144 => 14 + case 524288 => 13 + case 1048576 => 12 + case 2097152 => 11 + case 4194304 => 10 + case 8388608 => 9 + case 16777216 => 8 + case 33554432 => 7 + case 67108864 => 6 + case 134217728 => 5 + case 268435456 => 4 + case 536870912 => 3 + case 1073741824 => 2 + } + + + ////////////////////////////////////////////// + + @Benchmark def with2DeBruijn(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = with2DeBruijn(v) + // assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)") + bh.consume(leadingZeros) + } + } + + // https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn + private val multiplyDeBruijnBitPosition2 = Array(32, 31, 4, 30, 3, 18, 8, 29, 2, 10, 12, 17, 7, 15, 28, 24, 1, 5, 19, 9, 11, 13, 16, 25, 6, 20, 14, 26, 21, 27, 22, 23) + + private def with2DeBruijn(v: Int) = multiplyDeBruijnBitPosition2((v * 0x077CB531) >>> 27) + + + ////////////////////////////////////////////// + + @Benchmark def withBinSearch(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = withBinSearch(v) + // assert (leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)") + bh.consume(leadingZeros) + } + } + + private def withBinSearch(v: Int) = + if (v < 65536) if (v < 256) if (v < 16) if (v < 4) if (v == 1) 32 else 31 + else if (v == 4) 30 else 29 + else if (v < 64) if (v == 16) 28 else 27 + else if (v == 64) 26 else 25 + else if (v < 4096) if (v < 1024) if (v == 256) 24 else 23 + else if (v == 1024) 22 else 21 + else if (v < 16384) if (v == 4096) 20 else 19 + else if (v == 16384) 18 else 17 + else if (v < 16777216) if (v < 1048576) if (v < 262144) if (v == 65536) 16 else 15 + else if (v == 262144) 14 else 13 + else if (v < 4194304) if (v == 1048576) 12 else 11 + else if (v == 4194304) 10 else 9 + else if (v < 268435456) if (v < 67108864) if (v == 16777216) 8 else 7 + else if (v == 67108864) 6 else 5 + else if (v < 1073741824) if (v == 268435456) 4 else 3 + else if (v == 1073741824) 2 else 1 + + ////////////////////////////////////////////// + + @Benchmark def withSumBinSearch(bh: Blackhole) { + for (v <- powersOfTwo) { + val leadingZeros = withSumBinSearch(v) + // assert(leadingZeros == withLoop(v), s"$leadingZeros != ${withLoop(v)} ($v)") + bh.consume(leadingZeros) + } + } + + private def withSumBinSearch(v: Int): Int = { + var exponent = Integer.SIZE + var remaining = v + if (remaining >= 65536) { remaining >>>= 16; exponent = 16 } + if (remaining >= 256) { remaining >>>= 8; exponent -= 8 } + if (remaining >= 16) { remaining >>>= 4; exponent -= 4 } + if (remaining >= 4) { remaining >>>= 2; exponent -= 2 } + if (remaining >= 2) exponent - 1 else exponent + } +}
\ No newline at end of file diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala new file mode 100644 index 0000000000..134cd6879b --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/collection/immutable/HashMapBenchmark.scala @@ -0,0 +1,56 @@ +package scala.collection.immutable + +import org.openjdk.jmh.annotations._ +import org.openjdk.jmh.infra._ +import org.openjdk.jmh.runner.IterationType +import benchmark._ +import java.util.concurrent.TimeUnit + +@BenchmarkMode(Array(Mode.AverageTime)) +@Fork(2) +@Threads(1) +@Warmup(iterations = 10) +@Measurement(iterations = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class HashMapBenchmark { + @Param(Array("10", "100", "1000")) + var size: Int = _ + + var existingKeys: Array[Any] = _ + var missingKeys: Array[Any] = _ + + @Setup(Level.Trial) def initKeys(): Unit = { + existingKeys = (0 to size).map(i => (i % 4) match { + case 0 => i.toString + case 1 => i.toChar + case 2 => i.toDouble + case 3 => i.toInt + }).toArray + missingKeys = (size to 2 * size).toArray + } + + var map: collection.immutable.HashMap[Any, Any] = null + + @Setup(Level.Trial) def initialize = { + map = collection.immutable.HashMap(existingKeys.map(x => (x, x)) : _*) + } + + @Benchmark def contains(bh: Blackhole): Unit = { + var i = 0; + while (i < size) { + bh.consume(map.contains(existingKeys(i))) + bh.consume(map.contains(missingKeys(i))) + i += 1 + } + } + + @Benchmark def get(bh: Blackhole): Unit = { + var i = 0; + while (i < size) { + bh.consume(map.get(existingKeys(i))) + bh.consume(map.get(missingKeys(i))) + i += 1 + } + } +} diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala index 94844dcae2..36e2518993 100644 --- a/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala +++ b/test/benchmarks/src/main/scala/scala/collection/immutable/ListBenchmark.scala @@ -23,12 +23,14 @@ class ListBenchmark { var values: List[Content] = _ var mid: Content = _ var last: Content = _ + var replacement: Content = _ @Setup(Level.Trial) def initKeys(): Unit = { values = List.tabulate(size)(v => Content(v)) mid = Content(size / 2) last = Content(Math.max(0,size -1)) + replacement = Content(size * 2 + 1) } @Benchmark def filter_includeAll: Any = { @@ -55,18 +57,14 @@ class ListBenchmark { values.filter(v => v.value == last.value) } - @Setup(Level.Trial) def initKeys(): Unit = { - values = List.tabulate(size)(n => if (n == size / 2) "mid" else "") - } - @Benchmark def mapConserve_identity: Any = { values.mapConserve(x => x) } @Benchmark def mapConserve_modifyAll: Any = { - values.mapConserve(x => "replace") + values.mapConserve(x => replacement) } @Benchmark def mapConserve_modifyMid: Any = { - values.mapConserve(x => if (x == "mid") "replace" else x) + values.mapConserve(x => if (x == mid) replacement else x) } } diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/MapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/MapBenchmark.scala new file mode 100644 index 0000000000..a0358d6a1a --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/collection/immutable/MapBenchmark.scala @@ -0,0 +1,29 @@ +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 = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class MapBenchmark { + + var base: Map[String,String] = _ + + + @Setup(Level.Trial) def initKeys(): Unit = { + base = Map("a" -> "a", "b" -> "b", "c" -> "c", "d" -> "d") + } + + // immutable map is implemented as EmptyMap -> Map1 -> Map2 -> Map3 -> Map4 -> Hashmap + // add an extra entry to Map4 causes a lot of work, benchmark the transition + @Benchmark def map4AddElement(bh: Blackhole): Unit = { + bh.consume(base.updated("e", "e")) + } +} diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/SetBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/SetBenchmark.scala new file mode 100644 index 0000000000..9330626691 --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/collection/immutable/SetBenchmark.scala @@ -0,0 +1,29 @@ +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 = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class SetBenchmark { + + var base: Set[String] = _ + + + @Setup(Level.Trial) def initKeys(): Unit = { + base = Set("a", "b", "c", "d") + } + + // immutable map is implemented as EmptySet -> Set1 -> Set2 -> Set3 -> Set4 -> HashSet + // add an extra entry to Set4 causes a lot of work, benchmark the transition + @Benchmark def set4AddElement(bh: Blackhole): Unit = { + bh.consume(base + "e") + } +} diff --git a/test/benchmarks/src/main/scala/scala/collection/immutable/VectorMapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/immutable/VectorMapBenchmark.scala new file mode 100644 index 0000000000..61e621dcdf --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/collection/immutable/VectorMapBenchmark.scala @@ -0,0 +1,32 @@ +package scala.collection.immutable + +import org.openjdk.jmh.annotations._ +import org.openjdk.jmh.infra._ +import org.openjdk.jmh.runner.IterationType +import benchmark._ +import java.util.concurrent.TimeUnit + +@BenchmarkMode(Array(Mode.AverageTime)) +@Fork(2) +@Threads(1) +@Warmup(iterations = 10) +@Measurement(iterations = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class VectorMapBenchmark { + @Param(Array("10", "100", "1000")) + var size: Int = _ + + var values: Vector[Any] = _ + + @Setup(Level.Trial) def initKeys(): Unit = { + values = (0 to size).map(i => (i % 4) match { + case 0 => i.toString + case 1 => i.toChar + case 2 => i.toDouble + case 3 => i.toInt + }).toVector + } + + @Benchmark def groupBy = values.groupBy(_.getClass) +} diff --git a/test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala new file mode 100644 index 0000000000..3f01d154e9 --- /dev/null +++ b/test/benchmarks/src/main/scala/scala/collection/mutable/HashMapBenchmark.scala @@ -0,0 +1,70 @@ +package scala.collection.mutable + +import org.openjdk.jmh.annotations._ +import org.openjdk.jmh.infra._ +import org.openjdk.jmh.runner.IterationType +import benchmark._ +import java.util.concurrent.TimeUnit + +import scala.collection.mutable + +@BenchmarkMode(Array(Mode.AverageTime)) +@Fork(2) +@Threads(1) +@Warmup(iterations = 10) +@Measurement(iterations = 10) +@OutputTimeUnit(TimeUnit.NANOSECONDS) +@State(Scope.Benchmark) +class HashMapBenchmark { + @Param(Array("10", "100", "1000")) + var size: Int = _ + + var existingKeys: Array[Any] = _ + var missingKeys: Array[Any] = _ + + @Setup(Level.Trial) def initKeys(): Unit = { + existingKeys = (0 to size).map(i => (i % 4) match { + case 0 => i.toString + case 1 => i.toChar + case 2 => i.toDouble + case 3 => i.toInt + }).toArray + missingKeys = (size to 2 * size).toArray + } + + var map = new mutable.HashMap[Any, Any] + + @Setup(Level.Invocation) def initializeMutable = existingKeys.foreach(v => map.put(v, v)) + + @TearDown(Level.Invocation) def tearDown = map.clear() + + @Benchmark def getOrElseUpdate(bh: Blackhole): Unit = { + var i = 0; + while (i < size) { + bh.consume(map.getOrElseUpdate(existingKeys(i), -1)) + bh.consume(map.getOrElseUpdate(missingKeys(i), -1)) + i += 1 + } + } + + @Benchmark def get(bh: Blackhole): Unit = { + var i = 0; + while (i < size) { + bh.consume(map.get(existingKeys(i), -1)) + bh.consume(map.get(missingKeys(i), -1)) + i += 1 + } + } + + @Benchmark def put(bh: Blackhole): Any = { + var map = new mutable.HashMap[Any, Any] + + var i = 0; + while (i < size) { + map.put(existingKeys(i), i) + i += 1 + } + + map + } +} |