nimで競プロをするときに、HashSetがTLEする・遅い理由(のひとつ)

追記

1.6.14では修正されている。(いつ修正されたのかは要調査)

バージョン

nim: 1.0.6

要約

よくわからないけど、intのhashが悪いので以下を書いてintのhashプロシージャを上書きしておく。
参考元: https://github.com/nim-lang/Nim/issues/11764#issuecomment-611186437

proc hiXorLo(a, b: uint64): uint64 {.inline.} =
  {.emit: "__uint128_t r=a; r*=b; `result` = (r>>64)^r;".}
proc hashWangYi1*(x: int64|uint64|Hash): Hash {.inline.} =
  const P0 = 0xa0761d6478bd642f'u64
  const P1 = 0xe7037ed1a0b428db'u64
  const P5x8 = 0xeb44accab455d165'u64 xor 8'u64
  Hash(hiXorLo(hiXorLo(P0, uint64(x) xor P1), P5x8))
proc hash(x: int): Hash =
  x.hashWangYi1()

経緯

AtCoderで不可解なTLE(計算量(オーダー)的にはTLEしなさそう)が起きたので、Dropboxに上がっているテストケースを見ながら試行錯誤したところ、HashSetの初期化が悪さをしていそうだった

abc290 c - Max MEX: https://atcoder.jp/contests/abc290/tasks/abc290_c
TLEした提出: https://atcoder.jp/contests/abc290/submissions/40700254

説明(できない)

よくわかっていない。故、詳しい事情がわかる人は教えて欲しい。
それらしいissueは見つけたので、がっつり解明してやるという気概がある人は是非。
issue: https://github.com/nim-lang/Nim/issues/11764

ちなみに

理由がわからないけど解決策がわかったという記事は書いていいのだろうか。

参考

この記事と同じ?内容のissue: https://github.com/nim-lang/Nim/issues/11764#issuecomment-611186437