Skip to content

`Ord Literal` instance generates code in quadratic size

This is cmpLit:

cmpLit :: Literal -> Literal -> Ordering
cmpLit (LitChar      a)     (LitChar       b)     = a `compare` b
cmpLit (LitString    a)     (LitString     b)     = a `compare` b
cmpLit (LitNullAddr)        (LitNullAddr)         = EQ
cmpLit (LitFloat     a)     (LitFloat      b)     = a `compare` b
cmpLit (LitDouble    a)     (LitDouble     b)     = a `compare` b
cmpLit (LitLabel     a _ _) (LitLabel      b _ _) = a `uniqCompareFS` b -- non-det, tracked in #19438
cmpLit (LitNumber nt1 a)    (LitNumber nt2  b)
  | nt1 == nt2 = a   `compare` b
  | otherwise  = nt1 `compare` nt2
cmpLit (LitRubbish b1)      (LitRubbish b2)       = b1 `compare` b2
cmpLit lit1 lit2
  | litTag lit1 < litTag lit2 = LT
  | otherwise                 = GT

litTag :: Literal -> Int
litTag (LitChar      _)   = 1
litTag (LitString    _)   = 2
litTag (LitNullAddr)      = 3
litTag (LitFloat     _)   = 4
litTag (LitDouble    _)   = 5
litTag (LitLabel _ _ _)   = 6
litTag (LitNumber  {})    = 7
litTag (LitRubbish {})    = 8

A couple of issues concerning code size:

  • The LitNumber case uses both (==) and compare. In the most fortunate case, both functions will inline and we'll end up with the optimal code after simplification (I verified that indeed we do), but I don't see why we shouldn't use the Semigroup Ordering instance here: compare nt1 nt2 <> compare a b. Much simpler and less code bloat.
  • The use of litTag means quadratic code size blow-up in the number of literals: It is inlined and we get a couple of nested cases. A derived instance would use dataToTag#, and that is indeed what I propose we should do.
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information