Quadratic amount of code generated
Originally discovered by Twan van Laarhoven, here: http://www.haskell.org/pipermail/cvs-ghc/2008-February/040981.html
On the HEAD, compiling this module:
{-# LANGUAGE MagicHash #-}
module M1 where
import GHC.Exts
type FastInt = Int#
data U = Mk1 { a :: (), b :: FastInt, c :: () }
| Mk2 { a :: (), b :: FastInt, c :: () }
instance Eq U where
x == y = b x ==# b y
with
ghc -c M1.hs -O -ddump-simpl
we see
M1.== :: M1.U -> M1.U -> GHC.Base.Bool
[GlobalId]
[Arity 2
NoCafRefs
Str: DmdType SS]
M1.== =
\ (x_a5J :: M1.U) (y_a5L :: M1.U) ->
case case y_a5L of tpl_B2 {
M1.Mk1 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4;
M1.Mk2 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4
}
of wild_B1 { __DEFAULT ->
case case x_a5J of tpl_B2 {
M1.Mk1 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4;
M1.Mk2 ipv_B3 ipv1_B4 ipv2_B5 -> ipv1_B4
}
of wild1_Xk { __DEFAULT ->
GHC.Prim.==# wild1_Xk wild_B1
}
}
which looks good: Extract the !FastInt from one value, then the other, then compare.
However, if we have this module instead:
module M2 where
import GHC.Exts
newtype FastInt = FastInt Int
deriving Eq
data U = Mk1 { a :: (), b :: {-# UNPACK #-} !FastInt, c :: () }
| Mk2 { a :: (), b :: {-# UNPACK #-} !FastInt, c :: () }
instance Eq U where
x == y = b x == b y
again compiling with
ghc -c M2.hs -O -ddump-simpl
we see
M2.== :: M2.U -> M2.U -> GHC.Base.Bool
[GlobalId]
[Arity 2
NoCafRefs
Str: DmdType SS]
M2.== =
\ (x_a5M :: M2.U) (y_a5O :: M2.U) ->
case x_a5M of tpl_Xj {
M2.Mk1 ipv_Xn rb_B6 ipv1_B5 ->
case y_a5O of tpl1_Xl {
M2.Mk1 ipv2_Xp rb1_Xw ipv3_XX -> GHC.Prim.==# rb_B6 rb1_Xw;
M2.Mk2 ipv2_Xp rb1_Xw ipv3_XX -> GHC.Prim.==# rb_B6 rb1_Xw
};
M2.Mk2 ipv_Xn rb_B6 ipv1_B5 ->
case y_a5O of tpl1_Xl {
M2.Mk1 ipv2_Xp rb1_Xw ipv3_XX -> GHC.Prim.==# rb_B6 rb1_Xw;
M2.Mk2 ipv2_Xp rb1_Xw ipv3_XX -> GHC.Prim.==# rb_B6 rb1_Xw
}
}
where the extraction of the second !FastInt happens inside the branches of the extraction of the first !FastInt, giving a quadratic (in the number of constructors) amount of code. We would expect to get code like that in the first example.
Trac metadata
Trac field | Value |
---|---|
Version | 6.9 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | Unknown |
Architecture | Unknown |