benchshift.nim

import times

proc possiblyleakingshift[T](a: var openarray[T]; d: int) =
  if d == 0: discard # do nothing
  elif abs(d) >= a.len: # reset all
    zeroMem(addr a[0], a.len*sizeof(T))
  elif d > 0: # right shift
    moveMem(addr a[d], addr a[0], (a.len - d)*sizeof(T))
    zeroMem(addr a[0], d*sizeof(T))
  elif d < 0: # left shift
    moveMem(addr a[0], addr a[-d], (a.len + d)*sizeof(T))
    zeroMem(addr a[^(-d)], -d*sizeof(T))

proc firststisashift[T](a: var openarray[T]; d: int) =
  if d == 0: discard # do nothing
  elif abs(d) >= a.len: # reset all
    for el in a.mitems: el.reset
  elif d > 0: # right shift
    for i in countdown(a.len-1,d):
      a[i]=a[i-d]    
    for j in 0..<d: a[j].reset
  elif d < 0: # left shift    
    for i in -d..<a.len:
      a[i+d]=a[i]    
    for j in countdown(-d,1): a[^j].reset

proc laststisashift[T](a: var openarray[T]; d: int) =
  if d == 0: discard # do nothing
  elif abs(d) >= a.len: # reset all
    for el in a.mitems: el.reset
  elif d > 0: # right shift
    for j in 0..<d: a[j].reset # Reset only items that will be overwritten
    moveMem(addr a[d], addr a[0], (a.len - d)*sizeof(T))
  elif d < 0: # left shift    
    for j in countdown(-d,1): a[^j].reset # Reset only items that will be overwritten
    moveMem(addr a[0], addr a[-d], (a.len + d)*sizeof(T))

proc origshift[T](a: var openarray[T]; d: int) =
  ## Shift a right by d places for positive d or
  ## left for negative d.
  ## Shifted in elements are filled with default value.
  var
    h: T
    j: int

  if d == 0: return     # Those weren't in the original,
  elif abs(d) >= a.len: # added them to make this fairer
    for el in a.mitems: 
      el = h
      return

  if d > 0: # right shift
    j = a.high
    while j >= d:
      a[j] = a[j - d]
      dec(j)
    j = min(d, a.len)
    for i in 0 ..< j:
      a[i] = h
  elif d < 0: # left shift
    j = -d
    while j < a.len:
      a[j + d] = a[j]
      inc(j)
    j = max(a.len + d, 0)
    for i in j .. a.high:
      a[i] = h


template time(title:string,body:untyped):untyped=
  GC_fullCollect() # attempt to get consistent result
  var t0 = cpuTime()
  var m0 = getOccupiedMem()
  body
  GC_fullCollect() # attempt to get consistent result
  echo "CPU time: ",title," ", cpuTime() - t0, "s"
  echo "Delta occupied mem: ",title," ", getOccupiedMem() - m0


var s : seq[string] = @[]

for i in 0..10000:
  s.add("string"& $i)

let fa = s # save the seq so we can reset it

time "original":
  for i in 0..10000:
    s.origshift(i)

s = fa
time "first stisa":
  for i in 0..10000:
    s.firststisashift(i)

s = fa
time "possibly leaking":
  for i in 0..10000:
    s.possiblyleakingshift(i)

s = fa # reset the seq

time "last stisa":
  for i in 0..10000:
    s.laststisashift(i)