Repository navigation
More accurate Set and Map size warnings #1010
Description
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.
Activity
treeowl commentedon Jun 8, 2024
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 commentedon Jun 9, 2024
Well we could replace
a * 3 > bwitha > b `quot` 3. This would likely be a slowdown, benchmarks can tell.treeowl commentedon Jun 9, 2024
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.