diff options
Diffstat (limited to 'lib/pure/collections/tableimpl.nim')
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 135 |
1 files changed, 102 insertions, 33 deletions
diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index 85bffd60f..3542741fa 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -7,10 +7,13 @@ # distribution, for details about the copyright. # -# An ``include`` file for the different table implementations. +# An `include` file for the different table implementations. include hashcommon +const + defaultInitialSize* = 32 + template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add genHashImpl(key, hc) var h: Hash = hc and maxHash(t) @@ -23,29 +26,28 @@ template rawInsertImpl() {.dirty.} = data[h].val = val data[h].hcode = hc -proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline.} = +proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline, outParamsAt: [3].} = rawGetDeepImpl() proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B], - key: A, val: B, hc: Hash, h: Hash) = + key: A, val: sink B, hc: Hash, h: Hash) = rawInsertImpl() template checkIfInitialized() = - when compiles(defaultInitialSize): - if t.dataLen == 0: - initImpl(t, defaultInitialSize) + if t.dataLen == 0: + initImpl(t, defaultInitialSize) template addImpl(enlarge) {.dirty.} = checkIfInitialized() - if mustRehash(t.dataLen, t.counter): enlarge(t) + if mustRehash(t): enlarge(t) var hc: Hash var j = rawGetDeep(t, key, hc) rawInsert(t, t.data, key, val, hc, j) inc(t.counter) -template maybeRehashPutImpl(enlarge) {.dirty.} = +template maybeRehashPutImpl(enlarge, val) {.dirty.} = checkIfInitialized() - if mustRehash(t.dataLen, t.counter): + if mustRehash(t): enlarge(t) index = rawGetKnownHC(t, key, hc) index = -1 - index # important to transform for mgetOrPutImpl @@ -54,46 +56,91 @@ template maybeRehashPutImpl(enlarge) {.dirty.} = template putImpl(enlarge) {.dirty.} = checkIfInitialized() - var hc: Hash + var hc: Hash = default(Hash) var index = rawGet(t, key, hc) if index >= 0: t.data[index].val = val - else: maybeRehashPutImpl(enlarge) + else: maybeRehashPutImpl(enlarge, val) template mgetOrPutImpl(enlarge) {.dirty.} = checkIfInitialized() - var hc: Hash + var hc: Hash = default(Hash) var index = rawGet(t, key, hc) if index < 0: # not present: insert (flipping index) - maybeRehashPutImpl(enlarge) + when declared(val): + maybeRehashPutImpl(enlarge, val) + else: + maybeRehashPutImpl(enlarge, default(B)) # either way return modifiable val result = t.data[index].val +# template mgetOrPutDefaultImpl(enlarge) {.dirty.} = +# checkIfInitialized() +# var hc: Hash = default(Hash) +# var index = rawGet(t, key, hc) +# if index < 0: +# # not present: insert (flipping index) +# maybeRehashPutImpl(enlarge, default(B)) +# # either way return modifiable val +# result = t.data[index].val + template hasKeyOrPutImpl(enlarge) {.dirty.} = checkIfInitialized() - var hc: Hash + var hc: Hash = default(Hash) var index = rawGet(t, key, hc) if index < 0: result = false - maybeRehashPutImpl(enlarge) + maybeRehashPutImpl(enlarge, val) else: result = true -template delImplIdx(t, i) = +# delImplIdx is KnuthV3 Algo6.4R adapted to i=i+1 (from i=i-1) which has come to +# be called "back shift delete". It shifts elements in the collision cluster of +# a victim backward to make things as-if the victim were never inserted in the +# first place. This is desirable to keep things "ageless" after many deletes. +# It is trickier than you might guess since initial probe (aka "home") locations +# of keys in a cluster may collide and since table addresses wrap around. +# +# A before-after diagram might look like ('.' means empty): +# slot: 0 1 2 3 4 5 6 7 +# before(1) +# hash1: 6 7 . 3 . 5 5 6 ; Really hash() and msk +# data1: E F . A . B C D ; About to delete C @index 6 +# after(2) +# hash2: 7 . . 3 . 5 6 6 ; Really hash() and msk +# data2: F . . A . B D E ; After deletion of C +# +# This lowers total search depth over the whole table from 1+1+2+2+2+2=10 to 7. +# Had the victim been B@5, C would need back shifting to slot 5. Total depth is +# always lowered by at least 1, e.g. victim A@3. This is all quite fast when +# empty slots are frequent (also needed to keep insert/miss searches fast) and +# hash() is either fast or avoided (via `.hcode`). It need not compare keys. +# +# delImplIdx realizes the above transformation, but only works for dense Linear +# Probing, nextTry(h)=h+1. This is not an important limitation since that's the +# fastest sequence on any CPU made since the 1980s. { Performance analysis often +# overweights "key cmp" neglecting cache behavior, giving bad ideas how big/slow +# tables behave (when perf matters most!). Comparing hcode first means usually +# only 1 key cmp is needed for *any* seq. Timing only predictable activity, +# small tables, and/or integer keys often perpetuates such bad ideas. } + +template delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) = let msk = maxHash(t) if i >= 0: dec(t.counter) block outer: while true: # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1 - var j = i # The correctness of this depends on (h+1) in nextTry, + var j = i # The correctness of this depends on (h+1) in nextTry var r = j # though may be adaptable to other simple sequences. - t.data[i].hcode = 0 # mark current EMPTY - t.data[i].key = default(type(t.data[i].key)) - t.data[i].val = default(type(t.data[i].val)) + makeEmpty(i) # mark current EMPTY + {.push warning[UnsafeDefault]:off.} + reset(t.data[i].key) + reset(t.data[i].val) + {.pop.} while true: i = (i + 1) and msk # increment mod table size - if isEmpty(t.data[i].hcode): # end of collision cluster; So all done + if cellEmpty(i): # end of collision cluster; So all done break outer - r = t.data[i].hcode and msk # "home" location of key@i + r = cellHash(i) and msk # initial probe index for key@slot i if not ((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): break when defined(js): @@ -101,30 +148,50 @@ template delImplIdx(t, i) = else: t.data[j] = move(t.data[i]) # data[j] will be marked EMPTY next loop -template delImpl() {.dirty.} = +template delImpl(makeEmpty, cellEmpty, cellHash) {.dirty.} = var hc: Hash var i = rawGet(t, key, hc) - delImplIdx(t, i) + delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) + +template delImplNoHCode(makeEmpty, cellEmpty, cellHash) {.dirty.} = + if t.dataLen > 0: + var i: Hash = hash(key) and maxHash(t) + while not cellEmpty(i): + if t.data[i].key == key: + delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) + break + i = nextTry(i, maxHash(t)) template clearImpl() {.dirty.} = for i in 0 ..< t.dataLen: when compiles(t.data[i].hcode): # CountTable records don't contain a hcode t.data[i].hcode = 0 - t.data[i].key = default(type(t.data[i].key)) - t.data[i].val = default(type(t.data[i].val)) + {.push warning[UnsafeDefault]:off.} + reset(t.data[i].key) + reset(t.data[i].val) + {.pop.} t.counter = 0 +template ctAnd(a, b): bool = + when a: + when b: true + else: false + else: false + template initImpl(result: typed, size: int) = - assert isPowerOfTwo(size) - result.counter = 0 - newSeq(result.data, size) - when compiles(result.first): - result.first = -1 - result.last = -1 + let correctSize = slotsNeeded(size) + when ctAnd(declared(SharedTable), typeof(result) is SharedTable): + init(result, correctSize) + else: + result.counter = 0 + newSeq(result.data, correctSize) + when compiles(result.first): + result.first = -1 + result.last = -1 template insertImpl() = # for CountTable if t.dataLen == 0: initImpl(t, defaultInitialSize) - if mustRehash(len(t.data), t.counter): enlarge(t) + if mustRehash(t): enlarge(t) ctRawInsert(t, t.data, key, val) inc(t.counter) @@ -160,3 +227,5 @@ template equalsImpl(s, t: typed) = if not t.hasKey(key): return false if t.getOrDefault(key) != val: return false return true + else: + return false |