## Use new compare -> {LT,EQ,GT} in Data.Map and Data.Set

Maps and sets are heavily used in iTasks, but the `<`

operators sometimes do quite a bit of work. A branch step in a map/set takes on average 1.5 `<`

computations. With a `compare`

function that yields LT, EQ, or GT, only one `compare`

computation is needed, and the work needed for `compare`

is usually at most marginally more than for `<`

. So I propose to replace the `<`

contexts in Data.Map and Data.Set with a new `compare`

class (as in Haskell).

My proposal is to add Data.Ordering:

```
from StdOverloaded import class <(<), class ==(==)
:: Ordering :== Int
LT :== -1
EQ :== 0
GT :== 1
class compare a :: !a !a -> Ordering
compare_with_lt x y :== if (x<y) LT (if (y<x) GT EQ)
compare_with_lt_and_eq x y :== if (x<y) LT (if (x==y) EQ GT)
compare_with_eq_and_lt x y :== if (x==y) EQ (if (x<y) LT GT)
lt_with_compare x y :== compare x y == LT
```

## Expand to see typical instances

```
instance compare Bool where compare x y = if x (if y EQ GT) (if y LT EQ)
instance compare Int where compare x y = compare_with_lt x y
instance compare Char where compare x y = compare_with_lt x y
instance compare Real where compare x y = compare_with_lt x y
instance compare String
where
compare a b
# cmp = cmpAC a b
| cmp < 0 = LT
| cmp > 0 = GT
| otherwise = EQ
where
cmpAC :: !String !String -> Int
cmpAC _ _ = code {
.d 2 0
jsr cmpAC
.o 0 1 i
}
instance compare [a] | compare a
where
compare xs ys = case xs of
[] -> case ys of
[] -> EQ
_ -> LT
[x:xs] -> case ys of
[] -> LT
[y:ys] -> case compare x y of
EQ -> compare xs ys
c -> c
instance compare (Maybe a) | compare a
where
compare a b = case a of
Nothing = case b of
Nothing = EQ
Just _ = LT
Just a = case b of
Nothing = GT
Just b = compare a b
instance compare (a,b) | compare a & compare b
where
compare :: !(!a,b) !(!a,b) -> Ordering | compare a & compare b
compare (xa,xb) (ya,yb) = case compare xa ya of
EQ -> compare xb yb
c -> c
instance compare (a,b,c) | compare a & compare b & compare c
where
compare :: !(!a,b,c) !(!a,b,c) -> Ordering | compare a & compare b & compare c
compare (xa,xb,xc) (ya,yb,yc) = case compare xa ya of
EQ -> case compare xb yb of
EQ -> compare xc yc
c -> c
c -> c
```

Notes:

- Data.GenLexOrd would use this
`:: Ordering`

as well (`:: LexOrd`

will be removed). -
`:: Ordering`

is a synonym for`Int`

for efficiency, but should always be accessed using the macros`EQ`

,`LT`

, and`GT`

. - The
`compare_with_*`

macros allow you to easily define a`compare`

instance given a`<`

(and sometimes`==`

) instance, to ease the transition. - The
`lt_with_compare`

macro allows you to easily define a`<`

instance given a`compare`

instance, to remove duplicate code. - It may prove useful to add
`eq_with_compare`

as well.

I have a proof of concept with this to replace `put`

, `get`

, and `insert`

, and this speeds up iTasks quite a bit. Together with some other optimisations, the cumulative time cost of `checkRegistrations`

(iTasks.Internal.SDS) goes fom 290M cycles to 170M in my benchmark, and the changes to Data.Set are the primary factor there.

So the question is: do we want this? Changing all functions in Data.Map/Set and updating all our code will be quite a bit of work, so I'm not going to do this unless we are sure that we want this.