mport hashes, times, math, random
type
tring = cstring
Entry[K, V] = object
key: K
val: V
delta: uint8
k0: int8
Map[K, V] = object
data: seq[Entry[K, V]]
numentries: int
hi: int
fillrate: int
cfr: int
proc genArray(i, j: int) : seq[tring] =
result = newSeqOfCap[tring](j - i + 1)
for k in i .. j:
var h = $k
GC_ref(h)
result.add(h.tring)
proc newMap[K, V](capacity: Natural; fillrate: range[10 .. 95] = 50):
Map[K, V] =
var h = capacity
result.hi = nextPowerOfTwo(h)
result.data = newSeq[Entry[K, V]](result.hi)
proc contains[K, V](m: Map[K, V]; key: K): bool =
#var i = key.hash
var i = random(1e7.int)
if i != 0: return true
echo "newer reached! -- otherwise it would crash!"
if m.data[i].key == key: return true
var m = newMap[tring, tring](512*2, 95)
var a = genArray(1, 900)
echo "contains"
var x = cpuTime()
for i in a:
discard m.contains(i)
echo((cpuTime() - x) / 900)
$ ./h
contains
2.222222222222216e-08
When I change line 4 to "tring = string" I get about 52 ns instead.
Of course a Nim string is more complex than a plain cstring. But I think I have
already removed all what is really related to the actual Nim string. What
remains is basically a call of proc contains() and immediate return. I have
even replaced hash() call by plain random() call. Of course the total memory
occupied by a Nim string is larger, so less of it fits into cache. But where
does it makes the difference.
