strqueue_bench

strqueue_bench.nim

import nimbench

type
  StrQueue = object
    s: string
    pos: int
    filled: int
    b: seq[Slice[int]]
    head: int
    tail: int
    i: int

proc initStrQueue(strsize, qsize: int): StrQueue {.inline.} =
  StrQueue(
    s: newString(strsize),
    pos: 0,
    filled: 0,
    b: newSeq[Slice[int]](qsize),
    head: qsize-1,
    tail: 0,
    i: 0)

proc len(q: StrQueue): int {.inline.} =
  q.i

proc left(q: StrQueue): int {.inline.} =
  ## Return available space
  q.s.len-q.filled

proc pop(q: var StrQueue): Slice[int] {.inline.} =
  assert q.i > 0
  result = q.b[q.tail]
  q.tail = (q.tail+1) mod q.b.len
  dec q.i
  dec(q.filled, result.b-result.a)
  assert q.filled >= 0

proc add(q: var StrQueue, x: string) {.inline.} =
  while q.len > 0 and x.len > q.left:
    discard q.pop()
  if x.len > q.s.len:
    raise newException(ValueError, "string too long")
  q.head = (q.head+1) mod q.b.len
  q.b[q.head] = q.pos .. q.pos+x.len-1
  q.i = min(q.b.len, q.i+1)
  for c in x:
    q.s[q.pos] = c
    q.pos = (q.pos+1) mod q.s.len
  inc(q.filled, x.len)
  assert q.filled <= q.s.len

proc popAnd(q: var StrQueue): Slice[int] {.inline.} =
  assert q.i > 0
  result = q.b[q.tail]
  q.tail = (q.tail+1) and (q.b.len-1)
  dec q.i
  dec(q.filled, result.b-result.a)
  assert q.filled >= 0

proc addAnd(q: var StrQueue, x: string) {.inline.} =
  while q.len > 0 and x.len > q.left:
    discard q.popAnd()
  if x.len > q.s.len:
    raise newException(ValueError, "string too long")
  q.head = (q.head+1) and (q.b.len-1)
  q.b[q.head] = q.pos .. q.pos+x.len-1
  q.i = min(q.b.len, q.i+1)
  for c in x:
    q.s[q.pos] = c
    q.pos = (q.pos+1) and (q.s.len-1)
  inc(q.filled, x.len)
  assert q.filled <= q.s.len

proc addMemCopy(q: var StrQueue, x: var string) {.inline.} =
  while q.len > 0 and x.len > q.left:
    discard q.popAnd()
  if x.len > q.s.len:
    raise newException(ValueError, "string too long")
  q.head = (q.head+1) and (q.b.len-1)
  q.b[q.head] = q.pos .. q.pos+x.len-1
  q.i = min(q.b.len, q.i+1)
  let mLen = min(x.len, q.s.len-q.pos)
  copyMem(addr q.s[q.pos], addr x[0], mLen)
  if x.len < mLen:
    copyMem(addr q.s[0], addr x[mLen], x.len-mLen)
  q.pos = (q.pos+x.len) and (q.s.len-1)
  inc(q.filled, x.len)
  assert q.filled <= q.s.len

iterator items(q: StrQueue): Slice[int] {.inline.} =
  var i = 0
  while i < q.i:
    yield q.b[(q.head-i) mod q.b.len]
    inc i

proc `$`(q: StrQueue): string {.inline.} =
  ## For debugging purposes only
  result = ""
  for b in q:
    let o = result.len
    result.setLen(result.len+b.b-b.a+1)
    for i in b:
      result[o+i-b.a] = q.s[i mod q.s.len]
    result.add('|')

var x = initStrQueue(32, 32)
x.add("helloA")
x.add("helloB")
x.add("helloC")
x.add("helloD")
x.add("helloE")
assert $x == "helloE|helloD|helloC|helloB|helloA|"
x.add("helloF")
assert $x == "helloF|helloE|helloD|helloC|helloB|"
x.add("helloG")
assert $x == "helloG|helloF|helloE|helloD|helloC|"

const iterations = 100
#var qStrSize = 1024
var qStrSize = 65536
#var qSize = 256
var qSize = 1024
var s = newString(1000)
for i in 0 .. s.len-1:
  s[i] = 'a'

bench(addWithModulo, m):
  var x = initStrQueue(qStrSize, qSize)
  for _ in 0 ..< m:
    for _ in 0 .. iterations:
      x.add(s)
    doNotOptimizeAway(x)

benchRelative(addWithAnd, m):
  var x = initStrQueue(qStrSize, qSize)
  for _ in 0 ..< m:
    for _ in 0 .. iterations:
      x.addAnd(s)
  doNotOptimizeAway(x)

benchRelative(addWithMemCopy, m):
  var x = initStrQueue(qStrSize, qSize)
  for _ in 0 ..< m:
    for _ in 0 .. iterations:
      x.addMemCopy(s)
  doNotOptimizeAway(x)

bench(simpleStrCopy, m):
  var s2 = s
  for _ in 0 ..< m:
    for _ in 0 .. iterations:
      for i in 0 .. s.len-1:
        s2[i] = s[i]
  doNotOptimizeAway(s2)

benchRelative(strMemCopy, m):
  var s2 = s
  for i in 0 ..< m:
    for _ in 0 .. iterations:
      copyMem(addr s2[0], addr s[0], s.len)
  doNotOptimizeAway(s2)
  assert s2 == s

bench(noOp, m):
  for i in 0 ..< m:
    memoryClobber()

runBenchmarks()

# Results on my laptop, YMMV

#[
============================================================================
GlobalBenchmark                                 relative  time/iter  iters/s
============================================================================
GlobalBenchmark                                            334.15ps    2.99G
============================================================================
crap.nim                                        relative  time/iter  iters/s
============================================================================
addWithModulo                                                1.38ms   722.64
addWithAnd                                      1652.41%    83.75us   11.94K
addWithMemCopy                                  36495.54%     3.79us  263.73K
simpleStrCopy                                                3.39us  294.82K
strMemCopy                                       270.54%     1.25us  797.60K
noOp                                                         0.00fs      inf
]#

# The smaller the string the less diff there is between memcpy/simpleCpy,
# with a string of length 100 there is little difference.