search

haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
315 stars 178 forks source link

More accurate Set and Map size warnings #1010

Open meooow25 opened 3 months ago

meooow25 commented 3 months ago

Set and Map documentation carry warnings that say

The size of the set must not exceed maxBound::Int. Violation of this condition is not detected and if the size limit is exceeded, its behaviour is undefined.

However, we multiple sizes by delta = 3 without caring about overflow when balancing, which means we get violated invariants earlier than that.

I doubt anyone will be running into this in practice, but the limit should be document as maxBound `div` 3 perhaps. Or less, in case there are other potentially troublesome operations I missed.

treeowl commented 3 months ago

Good point. Is it possible to avoid the problem by being careful about how we do the comparisons? It's not an issue for 64 bit, but we still (nominally) support 32 bit, and (theoretically) 29 bit.

meooow25 commented 3 months ago

Is it possible to avoid the problem by being careful about how we do the comparisons?

Well we could replace a * 3 > b with a > b `quot` 3. This would likely be a slowdown, benchmarks can tell.

treeowl commented 3 months ago

Hmph. That does sound like a slowdown. Checking for overflow would probably be a slowdown too (more work for branch prediction), but what do I know? Changing the documentation is at least easy.