Compares the speed of cycle detection using Brent's algorithm vs IntSet in Nim stdlib

testbrent.nim

import std/[tables, monotimes, times, strformat]
import "$nim"/compiler/[astdef, ast, idents, types]

var idgen = IdGenerator(module: 0, symId: 0, typeId: 0, disambTable: initCountTable[PIdent]())

type
  CycleDetector = object
    lam, power: int
    tortoise: ItemId
    when defined(statistic):
      numIter: int

proc detect(c: var CycleDetector; itemId: ItemId): bool =
  result = false

  if itemId == c.tortoise:
    when defined(statistic):
      echo fmt"found circle: lam: {c.lam}, power: {c.power}, iteration: {c.numIter}"
    return true

  if c.power == c.lam:
    c.tortoise = itemId
    c.power *= 2
    c.lam = 0

  inc c.lam

  when defined(statistic):
    inc c.numIter

proc isRecursiveStructuralType(t: PType, cycleDetector: var CycleDetector): bool =
  # Copied from compiler/types.nim
  if t == nil:
    return false
  if cycleDetector.detect(t.itemId):
    return true
  case t.kind
  of tyTuple:
    result = false
    var cycleDetectorCopy: CycleDetector
    for a in t.kids:
      cycleDetectorCopy = cycleDetector
      if isRecursiveStructuralType(a, cycleDetectorCopy):
        return true
  of tyProc:
    result = false
    var cycleDetectorCopy: CycleDetector
    if t.returnType != nil:
      cycleDetectorCopy = cycleDetector
      if isRecursiveStructuralType(t.returnType, cycleDetectorCopy):
        return true
    for _, a in t.paramTypes:
      cycleDetectorCopy = cycleDetector
      if isRecursiveStructuralType(a, cycleDetectorCopy):
        return true
  of tyRef, tyPtr, tyVar, tyLent, tySink,
      tyArray, tyUncheckedArray, tySequence, tyDistinct:
    return isRecursiveStructuralType(t.elementType, cycleDetector)
  of tyAlias, tyGenericInst:
    return isRecursiveStructuralType(t.skipModifier, cycleDetector)
  else:
    return false

proc isRecursiveStructuralTypeBrent(t: PType): bool =
  var cycleDetector = CycleDetector(lam: 1, power: 1)
  isRecursiveStructuralType(t, cycleDetector)

proc newType(kind: TTypeKind; son: sink PType = nil): PType =
  # IntSet runs slower if higher bits of input values are different after adding more than 34 ints.
  #for i in 0..16:
  #  discard (nextTypeId idgen)
  #if (idgen.typeId and 3) == 0:
  #  inc idgen.module
  result = newType(kind, idgen, nil, son)

proc genNoRecursPType(len: int): PType =
  assert len > 1
  let intTyp = newType(tyInt)
  result = newType(tyRef, intTyp)
  for i in 0..<(len - 2):
    result = newType(tyRef, result)

proc genRecursPType(beforeCycleLen, cycleLen: int): PType =
  assert beforeCycleLen >= 0
  assert cycleLen > 0
  var tail = newType(tyRef)
  result = tail
  for i in 0..<(cycleLen - 1):
    result = newType(tyRef, result)
  tail.add result
  for i in 0..<beforeCycleLen:
    result = newType(tyRef, result)

proc test =
  var noRecursPType = genNoRecursPType(4)
  assert not isRecursiveStructuralType(noRecursPType)
  assert not isRecursiveStructuralTypeBrent(noRecursPType)

  let recursPType = genRecursPType(0, 2)
  assert isRecursiveStructuralType(recursPType)
  assert isRecursiveStructuralTypeBrent(recursPType)

  let recursPType2 = genRecursPType(1, 2)
  assert isRecursiveStructuralType(recursPType2)
  assert isRecursiveStructuralTypeBrent(recursPType2)

test()

template measure(label: string; body: untyped): untyped =
  when defined(statistic):
    block:
      var r {.inject.} = false
      body
  else:
    let
      loop = 100
      sampling = 64
    block:
      var r {.inject.} = false
      var minT = initDuration(hours = 1)
      for i in 0 ..< sampling:
        let start = getMonoTime()
        for j in 0 ..< loop:
          body
        let finish = getMonoTime()
        minT = min(finish - start, minT)
      echo ($r)[0], ' ', label, minT div loop

proc benchNoRecurs(len: int) =
  echo fmt"No recursive: length: {len}"
  var noRecursPType = genNoRecursPType(len)
  measure("IntSet: "):
    r = isRecursiveStructuralType(noRecursPType)
  measure("brent: "):
    r = isRecursiveStructuralTypeBrent(noRecursPType)

proc benchRecurs(beforeCycleLen, cycleLen: int) =
  echo fmt"Recursive: beforeCycleLen: {beforeCycleLen}, cycleLen: {cycleLen}"
  var recursPType = genRecursPType(beforeCycleLen, cycleLen)
  measure("IntSet: "):
    r = isRecursiveStructuralType(recursPType)
  measure("brent: "):
    r = isRecursiveStructuralTypeBrent(recursPType)

proc bench =
  benchNoRecurs(16)
  benchNoRecurs(64)
  benchNoRecurs(256)
  benchNoRecurs(1500)
  benchRecurs(0, 16)
  benchRecurs(0, 64)
  benchRecurs(0, 256)
  benchRecurs(0, 900)
  benchRecurs(14, 4)
  benchRecurs(15, 4)
  benchRecurs(16, 4)
  benchRecurs(510, 10)
  benchRecurs(511, 10)
  benchRecurs(512, 10)
  benchRecurs(1000, 50)

bench()