IntSet: reverse bitmap for faster comparison? #674
Description
This is just an idea to improve instance Ord IntSet (related to #470 ). It's quite a pervasive change, and it'd help only in a special case - that may occur frequently, though.
When all elements of the IntSet are small, the tree is in fact Tip prefix bitmap. For just that special case, instance Eq IntSet is just two comparisons of machine words,
but instance Ord IntSet (in suggested #670) needs more ops (more than 10, see relateTipTip, relateBM).
It would be much easier if compare (Tip p bm1) (Tip p bm2) = compare bm1 bm2
but since the comparison must have fromAscList semantics, we need
= compare (reverse bm1) (reverse bm2) (the implementation does not actually use revNat)
Instead of doing the reversal here, we could define bitmapOf x not as 2^x but 2^(wordSize - 1 - x)
In the general case (comparing Tips that sit below Bin) we need the Relation result (that encodes 5 possible results) so there's no hope of doing this in one op.
I think that the underlying reason for all this is that some ops on machine words are uniform (direction does not matter, as in .&.), some are symmetric (two directions, but identical cost, e.g., shift-left, shift-right), but some are asymmetric (one direction, the other one is missing: lexicographic comparison, carry propagation in arithmetical operations).
Now everything regarding bitmaps (not prefixes!) in IntSet is uniform or symmetric - except for this comparison?