search

haskell-unordered-containers / unordered-containers

Efficient hashing-based container types
BSD 3-Clause "New" or "Revised" License
222 stars 97 forks source link

Tweak `insertKeyExists` and `deleteKeyExists` #458

Closed sjakobi closed 2 years ago

sjakobi commented 2 years ago

(This currently includes #456)

sjakobi commented 2 years ago

These new invariant tests are great! :)

      alterF
        valid:                             FAIL
          *** Failed! Falsified (after 28 tests and 26 shrinks):
          {_->[Nothing]}
          K {hash = 9, _x = A}
          fromList [(K {hash = 0, _x = A},1),(K {hash = 9, _x = B},1),(K {hash = 9, _x = A},1)]
          [Invalid (INV6_misplaced_hash 0) (SubHashPath {partialHash = 9, lengthInBits = 5})] /= [Valid]
          Use --quickcheck-replay=980663 to reproduce.
          Use -p '/Data.HashMap.Strict.alterF.valid/' to rerun this test only.
sjakobi commented 2 years ago

Note for myself:

I somehow couldn't reproduce the bugs above with cabal test -O0. I should look into this!

EDIT: Explained by @treeowl in #459.

treeowl commented 2 years ago

Oh, I'm starting to understand now. You're shifting as you go to avoid an extra argument?

sjakobi commented 2 years ago

Oh, I'm starting to understand now. You're shifting as you go to avoid an extra argument?

Exactly.

sjakobi commented 2 years ago

It seems that right now, there are no benchmarks using this code. All benchmarks for alterF seem to rely on rules that rewrite the code to either insert or delete.

This may change with #404 though.

sjakobi commented 2 years ago

I can't find a significant speedup in the alter benchmarks, but not a slowdown either. The generated Core seems slightly better.