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 nim-lang@13b5eb5 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:

• 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
  An associative containers in which both types can be used as key. nim-lang/RFCs#238 (comment)

[timotheecour]

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

[timotheecour]

performance impact of auto-initializing?

refs: nim-lang#11094 (comment)
nim-lang/RFCs#101 (comment)

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