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.
Indeed -- putting all that test code in a proc make differences disappear!
I am aware of performance problems of code outside of procs, but I really had not thought that that was the problem in this case. And I had not assumed that it makes 30 ns difference for a proc call.
I think in future I really should avoid global code even for small tests.
Stefan_Salewski: And I had not assumed that it makes 30 ns difference for a proc call.
The reason is that a copy of the string is being made. This requires a memory allocation and copying the string. 30ns are 60-90 clock cycles on a 2-3GHz machine and are pretty easy to hit.