Skip to content

Instantly share code, notes, and snippets.

@Ichoran

Ichoran/BenchHashVsAnyRef.scala

Created September 2, 2024 22:58
Show Gist options
  • Save Ichoran/e3303e16d08f6f31705ce483e1f74c73 to your computer and use it in GitHub Desktop.
Save Ichoran/e3303e16d08f6f31705ce483e1f74c73 to your computer and use it in GitHub Desktop.
Download ZIP
Benchmarking of Scala collections' mutable.HashMap vs mutable.AnyRefMap
Raw
BenchHashVsAnyRef.scala
//> using scala 3.5.0
// Run with scala-cli --power --jmh --jvm=21 BenchHashVsAnyRef.scala
// If you change the classes that have to be benchmarked, you may have to rm -r .scala_build
package bhvar
import org.openjdk.jmh.annotations._
import org.openjdk.jmh.infra.Blackhole
import java.util.concurrent.TimeUnit
@State(Scope.Thread)
@BenchmarkMode(Array(Mode.Throughput))
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 4, time = 2000, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 5000, timeUnit = TimeUnit.MILLISECONDS)
@Fork(1)
@Threads(1)
class Bm:
@Param(Array("5000000", "10000", "20"))
var totalSize = -1
@Param(Array("none", "key", "hash", "both"))
var collision = ""
var keys: Array[String] = Array.empty[String]
var sequential: Int = 0
var keyRange: Int = 0
var hashMask: Int = 0xFFFFFFFF
var hm: collection.mutable.HashMap[String, Object] = null
var ar: collection.mutable.AnyRefMap[String, Object] = null
@Setup(Level.Trial)
def setup(): Unit =
val r = new scala.util.Random(398572975175L)
keys = new Array[String](totalSize)
sequential = math.rint(math.sqrt(totalSize/5)).toInt
keyRange = collision match
case "key" => sequential + 10
case "both" => sequential + 10
case _ => totalSize * 2
val twiddle = (collision == "hash" || collision == "both")
var i = 0
while i < sequential do
val key =
if twiddle then
val j = ((i >> 4) << 2) | (i & 3)
val k = (i & 0xC) >> 2
(j+k).toString + "~_@!".charAt(k)
else i.toString
keys(i) = key
i += 1
while i < keys.length do
val h = r.nextInt(keyRange)
val key =
if twiddle then
val j = ((h >> 4) << 2) | (h & 3)
val k = (h & 0xC) >> 2
(j+k).toString + "~_@!".charAt(k)
else
h.toString
keys(i) = key
i += 1
hm = collection.mutable.HashMap.empty[String, Object]
ar = collection.mutable.AnyRefMap.empty[String, Object]
var j = 0
while j < keys.length do
val key = keys(j)
val o = new Object()
hm(key) = o
ar(key) = o
j += 1
@Benchmark
def orElseHash(bh: Blackhole): Unit =
val m = collection.mutable.HashMap.empty[String, Object]
var i = 0
while i < keys.length do
val key = keys(i)
bh.consume(m.getOrElseUpdate(key, new Object()))
i += 1
@Benchmark
def orElseAnyRef(bh: Blackhole): Unit =
val m = collection.mutable.AnyRefMap.empty[String, Object]
var i = 0
while i < keys.length do
val key = keys(i)
bh.consume(m.getOrElseUpdate(key, new Object()))
i += 1
@Benchmark
def buildHash(bh: Blackhole): Unit =
val m = collection.mutable.HashMap.empty[String, Object]
var i = 0
while i < keys.length do
val key = keys(i)
m(key) = new Object()
i += 1
bh.consume(m)
@Benchmark
def buildAnyRef(bh: Blackhole): Unit =
val m = collection.mutable.AnyRefMap.empty[String, Object]
var i = 0
while i < keys.length do
val key = keys(i)
m(key) = new Object()
i += 1
bh.consume(m)
@Benchmark
def getHash(bh: Blackhole): Unit =
var i = 0
while i < keys.length do
hm.get(keys(i)) match
case Some(v) => bh.consume(v)
case _ =>
i += 1
@Benchmark
def getAnyRef(bh: Blackhole): Unit =
var i = 0
while i < keys.length do
ar.get(keys(i)) match
case Some(v) => bh.consume(v)
case _ =>
i += 1
@Benchmark
def containsHash(bh: Blackhole): Unit =
var i = 0
var n = 0
while i < keys.length do
if hm contains keys(i) then n += 1
i += 1
bh.consume(n)
@Benchmark
def containsAnyRef(bh: Blackhole): Unit =
var i = 0
var n = 0
while i < keys.length do
if ar contains keys(i) then n += 1
i += 1
bh.consume(n)
@Benchmark
def mapHash(bh: Blackhole): Unit =
bh.consume(hm.map{ case (k, v) => k -> k })
@Benchmark
def mapAnyRef(bh: Blackhole): Unit =
bh.consume(ar.map{ case (k, v) => k -> k })
@Benchmark
def mkrmHash(bh: Blackhole): Unit =
val m = collection.mutable.HashMap.empty[String, Object]
var i = 0
while i < keys.length do
val key = keys(i)
m(key) = new Object()
if (i & 1) == 1 then
m.remove(keys(i >> 1))
i += 1
bh.consume(m)
@Benchmark
def mkrmAnyRef(bh: Blackhole): Unit =
val m = collection.mutable.AnyRefMap.empty[String, Object]
var i = 0
while i < keys.length do
val key = keys(i)
m(key) = new Object()
if (i & 2) == 3 then
m.remove(keys(i >> 2))
m.remove(keys(1 + (i >> 2)))
i += 1
bh.consume(m)
Raw
results.txt
Collision type "none" means keys are distinct and have distinct hash codes.
"key" means that keys repeat (roughly only sqrt(totalSize) keys are distinct).
"hash" means that hash codes collide about 4x per key
"both" means both effects occur simultaneously
If one map beats another to greater than 10% and error, it is marked on the
right with <A< or <H< for AnyRefMap or HashMap.
######################## Build Map From Array Of Keys ########################
Benchmark (coll) (totalSize) Score Error Units Win
Bm.buildAnyRef none 5000000 2.290 ± 0.122 ops/s <A<
Bm.buildHash none 5000000 1.590 ± 0.067 ops/s
Bm.buildAnyRef key 5000000 15.757 ± 1.471 ops/s
Bm.buildHash key 5000000 16.049 ± 0.917 ops/s
Bm.buildAnyRef hash 5000000 1.525 ± 0.043 ops/s <A<
Bm.buildHash hash 5000000 1.113 ± 0.057 ops/s
Bm.buildAnyRef both 5000000 6.290 ± 0.418 ops/s
Bm.buildHash both 5000000 9.410 ± 0.481 ops/s <H<
Bm.buildAnyRef none 10000 4246.530 ± 268.267 ops/s <A<
Bm.buildHash none 10000 3177.151 ± 226.744 ops/s
Bm.buildAnyRef key 10000 11132.537 ± 699.772 ops/s
Bm.buildHash key 10000 13313.448 ± 834.690 ops/s <H<
Bm.buildAnyRef hash 10000 2949.731 ± 218.632 ops/s
Bm.buildHash hash 10000 2747.090 ± 153.178 ops/s
Bm.buildAnyRef both 10000 4205.982 ± 331.981 ops/s
Bm.buildHash both 10000 5652.636 ± 283.047 ops/s <H<
Bm.buildAnyRef none 20 4357081.072 ± 219178.617 ops/s
Bm.buildHash none 20 4933332.995 ± 285032.269 ops/s <H<
Bm.buildAnyRef key 20 6210685.418 ± 491063.122 ops/s
Bm.buildHash key 20 9496602.364 ± 481041.300 ops/s <H<
Bm.buildAnyRef hash 20 3948376.440 ± 144390.696 ops/s
Bm.buildHash hash 20 7078475.729 ± 283577.815 ops/s <H<
Bm.buildAnyRef both 20 4989133.263 ± 337197.318 ops/s
Bm.buildHash both 20 7580748.244 ± 376980.536 ops/s <H<
###################### Check Map For Every Key In Array ######################
Benchmark (coll) (totalSize) Score Error Units Win
Bm.containsAnyRef none 5000000 5.175 ± 0.044 ops/s <A<
Bm.containsHash none 5000000 4.703 ± 0.023 ops/s
Bm.containsAnyRef key 5000000 20.712 ± 0.592 ops/s
Bm.containsHash key 5000000 22.034 ± 0.563 ops/s <H<
Bm.containsAnyRef hash 5000000 2.116 ± 0.021 ops/s <A<
Bm.containsHash hash 5000000 1.959 ± 0.019 ops/s
Bm.containsAnyRef both 5000000 7.371 ± 0.372 ops/s
Bm.containsHash both 5000000 9.698 ± 0.583 ops/s <H<
Bm.containsAnyRef none 10000 14662.162 ± 2000.257 ops/s
Bm.containsHash none 10000 17797.621 ± 602.498 ops/s <H<
Bm.containsAnyRef key 10000 14922.663 ± 1178.911 ops/s
Bm.containsHash key 10000 23088.100 ± 1276.509 ops/s <H<
Bm.containsAnyRef hash 10000 6961.091 ± 265.698 ops/s
Bm.containsHash hash 10000 8169.106 ± 689.189 ops/s <H<
Bm.containsAnyRef both 10000 4724.558 ± 299.045 ops/s
Bm.containsHash both 10000 6897.558 ± 328.642 ops/s <H<
Bm.containsAnyRef none 20 17699744.797 ± 1114624.295 ops/s
Bm.containsHash none 20 24258707.516 ± 1427458.754 ops/s <H<
Bm.containsAnyRef key 20 14478119.335 ± 803969.151 ops/s
Bm.containsHash key 20 20839452.159 ± 939901.995 ops/s <H<
Bm.containsAnyRef hash 20 13728668.279 ± 676108.566 ops/s
Bm.containsHash hash 20 20063933.897 ± 1037026.044 ops/s <H<
Bm.containsAnyRef both 20 9732464.010 ± 651090.578 ops/s
Bm.containsHash both 20 15139517.626 ± 738325.140 ops/s <H<
################# Get Value For Every Key In Array From Map ##################
Benchmark (coll) (totalSize) Score Error Units Win
Bm.getAnyRef none 5000000 4.057 ± 0.011 ops/s
Bm.getHash none 5000000 4.106 ± 0.026 ops/s
Bm.getAnyRef key 5000000 18.719 ± 0.647 ops/s
Bm.getHash key 5000000 19.373 ± 0.784 ops/s
Bm.getAnyRef hash 5000000 1.846 ± 0.015 ops/s
Bm.getHash hash 5000000 1.902 ± 0.012 ops/s
Bm.getAnyRef both 5000000 6.770 ± 0.252 ops/s
Bm.getHash both 5000000 9.526 ± 0.293 ops/s <H<
Bm.getAnyRef none 10000 9657.405 ± 588.627 ops/s
Bm.getHash none 10000 10567.007 ± 533.540 ops/s
Bm.getAnyRef key 10000 13508.957 ± 911.350 ops/s
Bm.getHash key 10000 18536.514 ± 1074.660 ops/s <H<
Bm.getAnyRef hash 10000 5850.956 ± 340.219 ops/s
Bm.getHash hash 10000 6924.194 ± 674.232 ops/s
Bm.getAnyRef both 10000 4312.183 ± 190.835 ops/s
Bm.getHash both 10000 6230.995 ± 401.229 ops/s <H<
Bm.getAnyRef none 20 14104473.111 ± 876609.838 ops/s
Bm.getHash none 20 16569669.545 ± 1017985.628 ops/s <H<
Bm.getAnyRef key 20 11842887.753 ± 712434.488 ops/s
Bm.getHash key 20 15079640.094 ± 765081.639 ops/s <H<
Bm.getAnyRef hash 20 10652059.448 ± 703751.202 ops/s
Bm.getHash hash 20 14615065.266 ± 1028622.151 ops/s <H<
Bm.getAnyRef both 20 8362727.255 ± 548871.205 ops/s
Bm.getHash both 20 11273652.206 ± 768502.097 ops/s <H<
############## Create New Map Using Map, Same Keys, Value = Key ##############
Benchmark (coll) (totalSize) Score Error Units Win
Bm.mapAnyRef none 5000000 3.350 ± 0.079 ops/s <A<
Bm.mapHash none 5000000 2.615 ± 0.130 ops/s
Bm.mapAnyRef key 5000000 118862.958 ± 7213.926 ops/s <A<
Bm.mapHash key 5000000 80060.024 ± 2788.346 ops/s
Bm.mapAnyRef hash 5000000 2.787 ± 0.062 ops/s
Bm.mapHash hash 5000000 2.677 ± 0.119 ops/s
Bm.mapAnyRef both 5000000 78888.368 ± 4127.532 ops/s
Bm.mapHash both 5000000 74852.147 ± 4486.172 ops/s
Bm.mapAnyRef none 10000 7970.904 ± 435.063 ops/s <A<
Bm.mapHash none 10000 4415.652 ± 258.546 ops/s
Bm.mapAnyRef key 10000 2052477.258 ± 146857.757 ops/s <A<
Bm.mapHash key 10000 1465286.274 ± 55752.282 ops/s
Bm.mapAnyRef hash 10000 6502.688 ± 386.339 ops/s <A<
Bm.mapHash hash 10000 4089.710 ± 357.350 ops/s
Bm.mapAnyRef both 10000 1463875.633 ± 104736.035 ops/s
Bm.mapHash both 10000 1636648.560 ± 100148.354 ops/s <H<
Bm.mapAnyRef none 20 7047510.842 ± 240829.234 ops/s
Bm.mapHash none 20 8526453.479 ± 542813.798 ops/s <H<
Bm.mapAnyRef key 20 10783772.892 ± 704263.807 ops/s
Bm.mapHash key 20 20754548.493 ± 997876.040 ops/s <H<
Bm.mapAnyRef hash 20 5648390.848 ± 309023.875 ops/s
Bm.mapHash hash 20 6986702.589 ± 586545.964 ops/s <H<
Bm.mapAnyRef both 20 8660194.081 ± 534980.403 ops/s
Bm.mapHash both 20 17208604.645 ± 703997.054 ops/s <H<
##### Build Map From Array Of Keys But Remove Half Of Keys While Building ####
Benchmark (coll) (totalSize) Score Error Units Win
Bm.mkrmAnyRef none 5000000 2.308 ± 0.112 ops/s
Bm.mkrmHash none 5000000 2.182 ± 0.125 ops/s
Bm.mkrmAnyRef key 5000000 16.500 ± 1.010 ops/s <A<
Bm.mkrmHash key 5000000 7.279 ± 0.451 ops/s
Bm.mkrmAnyRef hash 5000000 1.532 ± 0.047 ops/s
Bm.mkrmHash hash 5000000 1.644 ± 0.062 ops/s
Bm.mkrmAnyRef both 5000000 6.574 ± 0.347 ops/s <A<
Bm.mkrmHash both 5000000 4.811 ± 0.241 ops/s
Bm.mkrmAnyRef none 10000 4217.788 ± 167.457 ops/s <A<
Bm.mkrmHash none 10000 3848.319 ± 186.244 ops/s
Bm.mkrmAnyRef key 10000 11670.489 ± 862.427 ops/s <A<
Bm.mkrmHash key 10000 6260.474 ± 304.598 ops/s
Bm.mkrmAnyRef hash 10000 3089.235 ± 245.493 ops/s
Bm.mkrmHash hash 10000 3286.643 ± 190.934 ops/s
Bm.mkrmAnyRef both 10000 4347.265 ± 188.515 ops/s <A<
Bm.mkrmHash both 10000 3675.459 ± 253.476 ops/s
Bm.mkrmAnyRef none 20 4455767.267 ± 232247.170 ops/s
Bm.mkrmHash none 20 8500429.176 ± 378954.131 ops/s <H<
Bm.mkrmAnyRef key 20 6413439.232 ± 157216.000 ops/s
Bm.mkrmHash key 20 9181952.083 ± 379491.674 ops/s <H<
Bm.mkrmAnyRef hash 20 3981490.930 ± 233014.742 ops/s
Bm.mkrmHash hash 20 7212037.429 ± 340022.060 ops/s <H<
Bm.mkrmAnyRef both 20 5076030.649 ± 352886.995 ops/s
Bm.mkrmHash both 20 7237211.858 ± 245949.288 ops/s <H<
############## Build Map From Array Of Keys With getOrElseUpdate #############
Benchmark (coll) (totalSize) Score Error Units Win
Bm.orElseAnyRef none 5000000 2.221 ± 0.133 ops/s <A<
Bm.orElseHash none 5000000 1.443 ± 0.071 ops/s
Bm.orElseAnyRef key 5000000 17.752 ± 0.944 ops/s
Bm.orElseHash key 5000000 19.157 ± 1.123 ops/s
Bm.orElseAnyRef hash 5000000 1.397 ± 0.090 ops/s <A<
Bm.orElseHash hash 5000000 0.873 ± 0.068 ops/s
Bm.orElseAnyRef both 5000000 6.317 ± 0.238 ops/s
Bm.orElseHash both 5000000 8.914 ± 0.473 ops/s <H<
Bm.orElseAnyRef none 10000 3867.018 ± 289.465 ops/s <A<
Bm.orElseHash none 10000 3009.419 ± 120.978 ops/s
Bm.orElseAnyRef key 10000 12974.502 ± 937.570 ops/s
Bm.orElseHash key 10000 18954.203 ± 960.270 ops/s
Bm.orElseAnyRef hash 10000 2985.369 ± 151.877 ops/s <A<
Bm.orElseHash hash 10000 2547.268 ± 99.022 ops/s
Bm.orElseAnyRef both 10000 4249.916 ± 167.961 ops/s
Bm.orElseHash both 10000 6110.827 ± 352.120 ops/s <H<
Bm.orElseAnyRef none 20 3989494.668 ± 153846.259 ops/s
Bm.orElseHash none 20 6286770.174 ± 357543.385 ops/s <H<
Bm.orElseAnyRef key 20 6169134.126 ± 385454.228 ops/s
Bm.orElseHash key 20 9628768.550 ± 332462.628 ops/s <H<
Bm.orElseAnyRef hash 20 3830783.563 ± 94044.612 ops/s
Bm.orElseHash hash 20 5661151.435 ± 238486.023 ops/s <H<
Bm.orElseAnyRef both 20 4765009.348 ± 258567.024 ops/s
Bm.orElseHash both 20 7026615.644 ± 372981.115 ops/s <H<
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment