Mulitple comparisons on Word types produce redundant comparisons

[dons]

The Ord and Eq instances that are derived for Word types seems to be inefficient (and appeared while writing a ByteString? decoder for UTF8, which does a lot of Word8 matching).

The following code:

bad :: Word -> Bool
bad c | c < 1     = True  
      | c < 2     = True
      | otherwise = False

compiles to the rather horrible:

    case GHC.Prim.eqWord# ww_sXC __word 1 of wild2_aSC {
      GHC.Base.False ->
        case GHC.Prim.ltWord# ww_sXC __word 1 of wild_B1 {
          GHC.Base.False ->
            case GHC.Prim.eqWord# ww_sXC __word 2 of wild21_XUq {
              GHC.Base.False -> GHC.Prim.ltWord# ww_sXC __word 2;
              GHC.Base.True -> GHC.Base.False
            };
          GHC.Base.True -> GHC.Base.True
        };
      GHC.Base.True ->
        case GHC.Prim.eqWord# ww_sXC __word 2 of wild21_XUo {
          GHC.Base.False -> GHC.Prim.ltWord# ww_sXC __word 2;

In particular, notice the (<) on Word becomes a case eqWord# of case ltWord# of ...

While the equivalent at an Int type, using the hand written Ord/Eq instances in GHC.Base, produces:

M.good =
  \ (c_ag0 :: GHC.Base.Int) ->
    case c_ag0 of wild_aRF { GHC.Base.I# x_aRH ->
    case GHC.Prim.<# x_aRH 1 of wild1_B1 {
      GHC.Base.False -> GHC.Prim.<# x_aRH 2; GHC.Base.True -> GHC.Base.True
    }
    }

The poor code only seems to be generated if there's more than 1 comparison against the value.

If I manually wrap Word, and write an instance Eq and Ord for it, based on the ones for Int (attached), we get identical code to the Int case:

M.good =
  \ (c_agn :: M.MyWord) ->
    case c_agn `cast` ((M.:CoMyWord) :: M.MyWord ~ GHC.Word.Word)

    of wild_B1 { GHC.Word.W# x_agV ->
        case GHC.Prim.ltWord# x_agV __word 1 of wild1_X33 {
          GHC.Base.False -> GHC.Prim.ltWord# x_agV __word 2;
          GHC.Base.True -> GHC.Base.True
    }
    }

The Ord and Eq instances for Word seem to be deeply magic:

data Word = W# Word# deriving (Eq, Ord)

Are the instances wired in?

The solution to this might be to have similar instances of Eq and Ord for Word, as for Int, or to change the built-in deriving.

[dons]

Test case

[dons]

The extra comparisons bubble through to the final assembly, as you see here:

good :: Int -> Bool
good c | c < 22    = True
       | c < 42     = True
       | otherwise = False

The good Int yields:

good_info:
  cmpq $22,7(%rbx)
  jl .LcgH
  movl $base_GHCziBase_Bool_closure_tbl,%eax
  cmpq $42,7(%rbx)
  setl %cl
  movzbl %cl,%ecx
  movq (%rax,%rcx,8),%rbx
  addq $8,%rbp
  jmp *(%rbp)
.LcgH:
  movl $base_GHCziBase_True_closure+2,%ebx
  addq $8,%rbp
  jmp *(%rbp)

While our funky Ords for Word:

bad :: Word -> Bool
bad c | c < 22    = True
      | c < 42     = True
      | otherwise = False

yields:

M_zdwbad_info:
  cmpq $22,%rsi
  je .Lcm7
  cmpq $22,%rsi
  jb .Lcmb
  cmpq $42,%rsi
  je .Lcmd
  movl $base_GHCziBase_Bool_closure_tbl,%eax
  cmpq $42,%rsi
  setb %cl
  movzbl %cl,%ecx
  movq (%rax,%rcx,8),%rbx
  jmp *(%rbp)
.Lcm7:
  cmpq $42,%rsi
  je .Lcm9
  movl $base_GHCziBase_Bool_closure_tbl,%eax
  cmpq $42,%rsi
  setb %cl
  movzbl %cl,%ecx
  movq (%rax,%rcx,8),%rbx
  jmp *(%rbp)

[morrow]

Here is a duplication of the issue, and a writeup which will hopefully aid in comparing the code generated in various instances.

---

GHC was invoked as follows for the below:

$ ghc -O2 -keep-s-files -fglasgow-exts -c XXX.hs

GHC version info:

$ ghc -V
The Glorious Glasgow Haskell Compilation System, version 6.9.20080218

---

The code genereated for this example is basically equivalent to that generated by the Int -> Int example, as is desired.

import GHC.Word (Word(..)) -- for W#
import GHC.Prim (ltWord#,int2Word#)

choose :: Word -> Int
choose (W# c)
    | c `ltWord#` (int2Word# 0x80#)  = 1
    | c `ltWord#` (int2Word# 0xc0#)  = 2
    | otherwise = 3

maps to (obtained with ghc --show-iface):

lvl :: GHC.Base.Int {- HasNoCafRefs Strictness: m Unfolding: (GHC.Base.I# 1) -}
lvl1 :: GHC.Base.Int {- HasNoCafRefs Strictness: m Unfolding: (GHC.Base.I# 2) -}
lvl2 :: GHC.Base.Int {- HasNoCafRefs Strictness: m Unfolding: (GHC.Base.I# 3) -}
2 choose :: GHC.Word.Word -> GHC.Base.Int
    {- Arity: 1 HasNoCafRefs Strictness: U(L)m
       Unfolding: (\ ds :: GHC.Word.Word ->
                   case @ GHC.Base.Int ds of wild { GHC.Word.W# c ->
                   case @ GHC.Base.Int GHC.Prim.ltWord# c __word 128 of wild1 {
                     GHC.Base.False
                     -> case @ GHC.Base.Int GHC.Prim.ltWord# c __word 192 of wild2 {
                          GHC.Base.False -> M.lvl2 GHC.Base.True -> M.lvl1 }
                     GHC.Base.True -> M.lvl } }) -}

---

The code generated for this example is that to which the other two aspire.

choose :: Int -> Int
choose c
    | c < 0x80  = 1
    | c < 0xc0  = 2
    | otherwise = 3

maps to (obtained with ghc --show-iface):

lvl :: GHC.Base.Int {- HasNoCafRefs Strictness: m Unfolding: (GHC.Base.I# 1) -}
lvl1 :: GHC.Base.Int {- HasNoCafRefs Strictness: m Unfolding: (GHC.Base.I# 2) -}
lvl2 :: GHC.Base.Int {- HasNoCafRefs Strictness: m Unfolding: (GHC.Base.I# 3) -}
choose :: GHC.Base.Int -> GHC.Base.Int
  {- Arity: 1 HasNoCafRefs Strictness: U(L)m
     Unfolding: (\ c :: GHC.Base.Int ->
                 case @ GHC.Base.Int c of wild { GHC.Base.I# x ->
                 case @ GHC.Base.Int GHC.Prim.<# x 128 of wild1 {
                   GHC.Base.False
                   -> case @ GHC.Base.Int GHC.Prim.<# x 192 of wild2 {
                        GHC.Base.False -> Int.lvl2 GHC.Base.True -> Int.lvl1 }
                   GHC.Base.True -> Int.lvl } }) -}

---

This is the example of nonoptimal (wrt that of Int -> Int) code generated for the same function but with Word -> Int (and with no explicit unboxing).

import Data.Word (Word)

choose :: Word -> Int
choose c
    | c < 0x80  = 1
    | c < 0xc0  = 2
    | otherwise = 3

maps to (obtained with ghc --show-iface):

$wchoose :: GHC.Prim.Word# -> GHC.Prim.Int#
  {- Arity: 1 HasNoCafRefs Strictness: L
     Unfolding: (\ ww :: GHC.Prim.Word# ->
                 case @ GHC.Prim.Int# GHC.Prim.eqWord# ww __word 128 of wild2 {
                   GHC.Base.False
                   -> case @ GHC.Prim.Int# GHC.Prim.ltWord# ww __word 128 of wild {
                        GHC.Base.False
                        -> case @ GHC.Prim.Int# GHC.Prim.eqWord# ww __word 192 of wild21 {
                             GHC.Base.False
                             -> case @ GHC.Prim.Int# GHC.Prim.ltWord# ww __word 192 of wild1 {
                                  GHC.Base.False -> 3 GHC.Base.True -> 2 }
                             GHC.Base.True -> 3 }
                        GHC.Base.True -> 1 }
                   GHC.Base.True
                   -> case @ GHC.Prim.Int# GHC.Prim.eqWord# ww __word 192 of wild21 {
                        GHC.Base.False
                        -> case @ GHC.Prim.Int# GHC.Prim.ltWord# ww __word 192 of wild {
                             GHC.Base.False -> 3 GHC.Base.True -> 2 }
                        GHC.Base.True -> 3 } }) -}
choose :: GHC.Word.Word -> GHC.Base.Int
  {- Arity: 1 HasNoCafRefs Strictness: U(L)m Worker: M.$wchoose 1 -}

---

[simonpj]

Excellent point, thanks. It's actually not at all easy to optimise the generation of Ord instances perfectly; see Note [Comparision of primitive types] in TcGenDeriv.hs. But I have improved matters a bit, by making a special case for data types that are wrappers for primitive types.

Thu Feb 28 12:11:06 GMT 2008  simonpj@microsoft.com
  * Fix Trac #2130: improve derived Ord for primmitive types

That still leaves room for improvement: I've opened a new ticket for that #2132. But it does completely fix the Word type and its friends.

Simon

[igloo]

Merged