tables misc

[timotheecour]

links

• [TODO] pseudorandom probing for hash collision by timotheecour · Pull Request #13418 · nim-lang/Nim
• hashing collision: improve performance using linear/pseudorandom probing mix by timotheecour · Pull Request #13440 · nim-lang/Nim
• Unwind just the "pseudorandom probing" part of recent sets,tables changes by c-blake · Pull Request #13816 · nim-lang/Nim
• [minor] was https://github.com/nim-lang/Nim/pull/13803/commits/13b5eb50c032628244d77caeb058a461f241eab2 ok to remove?

[timotheecour]

D20200428T185548 the PR (Unwind just the "pseudorandom probing" part of recent sets,tables changes by c-blake · Pull Request #13816 · nim-lang/Nim) that reverted my tables pseudorandom work causes a number of speed regressions eg:

• [x] regression caused by D20200428T185548

  when defined case1: # D20200507T201947 gitissue
  # with nim js
  import hashes
  static:
  doAssert hash(123) != 0 # fails

  Edited: It works now.

[timotheecour]

• [ ] regression D20200507T203625 caused by D20200428T185548

5X slower

(using -d:danger for timing)

import tables
import times
proc main=
  var
    map = initTable[int, int]()

  for i in 0..<10_000_000:
    map[i] = i
  for i in 0..<3:
    for j in 0..<10_000_000:
      map[j] = map[j] + 1
let t = cpuTime()
main()
let t2 = cpuTime() - t
echo t2
doAssert t2 < 1.0

[timotheecour]

• [ ] too many custom table implementations, in particular for compiler code https://github.com/nim-lang/RFCs/issues/238#issuecomment-646863416

[timotheecour]

• see OrderedTable del and pop are slow · Issue #14971 · nim-lang/Nim

[timotheecour]

performance impact of auto-initializing?

refs: https://github.com/nim-lang/Nim/pull/11094#issuecomment-773859654 https://github.com/nim-lang/RFCs/issues/101#issuecomment-418044191

For 64-element tables, the change seems to make the whole benchmark about 4% slower.