I wonder if it will be useful to add another constructor to IntSet: Full Prefix. This indicates that this is a full tree with a shared prefix.
I expect this to show good improvements for use cases where contiguous runs of Ints are likely. It will also reduce space usage in such cases. For instance, to store [0..n] we will need only $O(\log n)$ memory instead of $O(n)$.
But this would add small overheads in various places, so it will likely not be a clear win in all use cases.
Also, to be clear, this would be small added costs and not a change in the worst case bounds.
For sure we would want to test something like this out on some real world use cases (like GHC, maybe others?) to see how it affects things. Just documenting this idea for now.
I wonder if it will be useful to add another constructor to
IntSet:Full Prefix. This indicates that this is a full tree with a shared prefix.I expect this to show good improvements for use cases where contiguous runs of$O(\log n)$ memory instead of $O(n)$ .
Ints are likely. It will also reduce space usage in such cases. For instance, to store[0..n]we will need onlyBut this would add small overheads in various places, so it will likely not be a clear win in all use cases.
Also, to be clear, this would be small added costs and not a change in the worst case bounds.
For sure we would want to test something like this out on some real world use cases (like GHC, maybe others?) to see how it affects things. Just documenting this idea for now.