search

haskell-unordered-containers / unordered-containers

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

Try removing the `Full` constructor #399

Open sjakobi opened 2 years ago

sjakobi commented 2 years ago

In my mind Full nodes should be pretty rare in the real world. The root node might be one, but at deeper levels I wouldn't expect to encounter any Full nodes.

Therefore it's unclear what benefit we get from all the dedicated code operating on this type of node.

From an earlier experiment to remove Full we have a report of perf regressions, but it's not clear which code regressed and why.

I would expect that the current Int benchmarks show regressions due to their unusually contiguous hash distribution, which I think is rather unrealistic.

treeowl commented 2 years ago

Yeah, my experiments were never very complete. Would surely be worth trying again. As I recall, I didn't really go all the way changing all the code. I think I tried making Full a pattern synonym and just worked through actually blasting it in a few places. That could have been part of the problem, or not. Changing all the code is a lot of work, but I agree with you that it doesn't seem likely to occur anywhere other than the root for non-Int-like instances.