bench_spaceset_magiccontainer.nim

import std/[algorithm, monotimes, strformat]
import ../magiccontainer/src/magiccontainer
import ../sparseset/sparseset

type Payload = object
  value: int

type PhaseTimes = object
  insertNs: int64
  lookupNs: int64
  iterateNs: int64
  deleteNs: int64
  totalNs: int64
  checksum: int64

type Summary = object
  lib: string
  size: int
  reps: int
  queryCount: int
  insertNs: int64
  lookupNs: int64
  iterateNs: int64
  deleteNs: int64
  totalNs: int64

proc medianNs(values: seq[int64]): int64 =
  var tmp = values
  tmp.sort()
  tmp[tmp.len div 2]

proc randIndices(n: int, count: int, seed: uint64): seq[int] =
  result = newSeq[int](count)
  var x = seed
  for i in 0 ..< count:
    x = x * 6364136223846793005'u64 + 1442695040888963407'u64
    result[i] = int((x shr 32) mod uint64(n))

proc runMagic(size: int, queries: seq[int]): PhaseTimes =
  var c = MagicContainer[Payload]()
  var ids = newSeq[int](size)

  var t0 = getMonoTime()
  for i in 0 ..< size:
    ids[i] = c.add(Payload(value: i))
  var t1 = getMonoTime()

  var checksum = 0'i64
  for q in queries:
    checksum += c[ids[q]].value.int64
  var t2 = getMonoTime()

  for item in c.items:
    checksum += item.value.int64
  var t3 = getMonoTime()

  for i in 0 ..< size:
    if (i and 1) == 0:
      c.del(ids[i])
  var t4 = getMonoTime()

  doAssert c.len == size div 2

  result.insertNs = t1.ticks - t0.ticks
  result.lookupNs = t2.ticks - t1.ticks
  result.iterateNs = t3.ticks - t2.ticks
  result.deleteNs = t4.ticks - t3.ticks
  result.totalNs = t4.ticks - t0.ticks
  result.checksum = checksum

proc runSparse(size: int, queries: seq[int]): PhaseTimes =
  var s = initSparseSet[uint32, Payload](size + 1)

  var t0 = getMonoTime()
  for i in 0 ..< size:
    s[uint32(i)] = Payload(value: i)
  var t1 = getMonoTime()

  var checksum = 0'i64
  for q in queries:
    checksum += s[uint32(q)].value.int64
  var t2 = getMonoTime()

  for item in s.values:
    checksum += item.value.int64
  var t3 = getMonoTime()

  for i in 0 ..< size:
    if (i and 1) == 0:
      s.del(uint32(i))
  var t4 = getMonoTime()

  doAssert s.len == size div 2

  result.insertNs = t1.ticks - t0.ticks
  result.lookupNs = t2.ticks - t1.ticks
  result.iterateNs = t3.ticks - t2.ticks
  result.deleteNs = t4.ticks - t3.ticks
  result.totalNs = t4.ticks - t0.ticks
  result.checksum = checksum

proc benchmarkOne(lib: string, size: int, reps: int, queries: seq[int]): Summary =
  var ins, look, iter, del, tot: seq[int64]
  ins = newSeq[int64](reps)
  look = newSeq[int64](reps)
  iter = newSeq[int64](reps)
  del = newSeq[int64](reps)
  tot = newSeq[int64](reps)

  var checksum = 0'i64

  for r in 0 ..< reps:
    let t =
      if lib == "magiccontainer": runMagic(size, queries)
      else: runSparse(size, queries)
    checksum = checksum xor t.checksum
    ins[r] = t.insertNs
    look[r] = t.lookupNs
    iter[r] = t.iterateNs
    del[r] = t.deleteNs
    tot[r] = t.totalNs

  result.lib = lib
  result.size = size
  result.reps = reps
  result.queryCount = queries.len
  result.insertNs = medianNs(ins)
  result.lookupNs = medianNs(look)
  result.iterateNs = medianNs(iter)
  result.deleteNs = medianNs(del)
  result.totalNs = medianNs(tot)

  if checksum == 0:
    echo "checksum guard: ", checksum

proc nsToMs(ns: int64): float = ns.float / 1_000_000.0

proc printTableRow(s: Summary) =
  echo fmt"| {s.lib:<14} | {s.size:>9} | {s.queryCount:>8} | {nsToMs(s.insertNs):>9.3f} | {nsToMs(s.lookupNs):>9.3f} | {nsToMs(s.iterateNs):>9.3f} | {nsToMs(s.deleteNs):>9.3f} | {nsToMs(s.totalNs):>9.3f} |"

when isMainModule:
  let sizes = @[100, 1_000, 5_000, 10_000, 25_000, 50_000, 100_000, 250_000, 500_000, 1_000_000]

  discard runMagic(1_000, randIndices(1_000, 4_000, 1'u64))
  discard runSparse(1_000, randIndices(1_000, 4_000, 2'u64))

  echo "# Benchmark: sparseset vs magiccontainer"
  echo "# metric: median of repetitions, lower is better"
  echo "| library        |      size |  lookups | insert ms | lookup ms | iterate ms | delete ms | total ms |"
  echo "|----------------|----------:|---------:|----------:|----------:|-----------:|----------:|---------:|"

  var results: seq[Summary] = @[]
  for size in sizes:
    let reps = if size <= 100_000: 7 else: 5
    let qCount = clamp(size * 4, 10_000, 2_000_000)
    let queries = randIndices(size, qCount, uint64(size) xor 0x1234_5678'u64)

    let sparse = benchmarkOne("sparseset", size, reps, queries)
    let magic = benchmarkOne("magiccontainer", size, reps, queries)

    results.add(sparse)
    results.add(magic)
    printTableRow(sparse)
    printTableRow(magic)

  echo ""
  echo "# Relative total speedup (magiccontainer / sparseset)"
  echo "| size | faster lib | speedup x |"
  echo "|-----:|------------|----------:|"

  for size in sizes:
    var s, m: Summary
    for r in results:
      if r.size == size and r.lib == "sparseset":
        s = r
      elif r.size == size and r.lib == "magiccontainer":
        m = r

    let ratio = m.totalNs.float / s.totalNs.float
    if ratio > 1.0:
      echo fmt"| {size:>4} | sparseset | {ratio:>8.2f} |"
    else:
      echo fmt"| {size:>4} | magiccontainer | {1.0 / ratio:>8.2f} |"