Received: from TK5EX14HUBC105.redmond.corp.microsoft.com (157.54.80.48) by DB3EX14HUBC302.europe.corp.microsoft.com (10.166.18.182) with Microsoft SMTP Server (TLS) id 14.2.283.4; Wed, 22 Feb 2012 14:33:16 +0000 Received: from mail35-va3-R.bigfish.com (157.54.51.114) by mail.microsoft.com (157.54.80.48) with Microsoft SMTP Server (TLS) id 14.2.247.5; Wed, 22 Feb 2012 14:33:03 +0000 Received: from mail35-va3 (localhost [127.0.0.1]) by mail35-va3-R.bigfish.com (Postfix) with ESMTP id 650702200EB for ; Wed, 22 Feb 2012 14:32:57 +0000 (UTC) Received: from mail35-va3 (localhost.localdomain [127.0.0.1]) by mail35-va3 (MessageSwitch) id 1329921174179423_24957; Wed, 22 Feb 2012 14:32:54 +0000 (UTC) Received: from VA3EHSMHS015.bigfish.com (unknown [10.7.14.252]) by mail35-va3.bigfish.com (Postfix) with ESMTP id 2197A4A0054 for ; Wed, 22 Feb 2012 14:32:54 +0000 (UTC) Received: from mail-yw0-f53.google.com (209.85.213.53) by VA3EHSMHS015.bigfish.com (10.7.99.25) with Microsoft SMTP Server (TLS) id 14.1.225.23; Wed, 22 Feb 2012 14:32:53 +0000 Received: by mail-yw0-f53.google.com with SMTP id j72so53766yhj.12 for ; Wed, 22 Feb 2012 06:32:58 -0800 (PST) Received: from mr.google.com ([10.60.20.38]) by 10.60.20.38 with SMTP id k6mr14560727oee.21.1329921178813 (num_hops = 1); Wed, 22 Feb 2012 06:32:58 -0800 (PST) Received: by 10.60.20.38 with SMTP id k6mr12470198oee.21.1329921178554; Wed, 22 Feb 2012 06:32:58 -0800 (PST) Received: by 10.60.37.2 with HTTP; Wed, 22 Feb 2012 06:32:32 -0800 (PST) From: =?iso-8859-1?Q?Jos=E9_Pedro_Magalh=E3es?= To: Generics Mailing List , GHC users , Simon Peyton-Jones Subject: Inlining and generic programming Thread-Topic: Inlining and generic programming Thread-Index: AQHM8W7qZJS6AwocI0eyYKamsfk5mA== Sender: "josepedromagalhaes@gmail.com" Date: Wed, 22 Feb 2012 14:32:32 +0000 Message-ID: Content-Language: en-GB X-MS-Exchange-Organization-AuthAs: Anonymous X-MS-Exchange-Organization-AuthSource: TK5EX14HUBC105.redmond.corp.microsoft.com X-MS-Has-Attach: X-MS-TNEF-Correlator: received-spf: pass (mail35-va3: domain of gmail.com designates 209.85.213.53 as permitted sender) client-ip=209.85.213.53; envelope-from=josepedromagalhaes@gmail.com; helo=mail-yw0-f53.google.com ;3.google.com ; x-google-sender-auth: l2u34oGDfv1AqceOUYYWp8B_Iis dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:sender:from:date:x-google-sender-auth:message-id :subject:to:content-type; bh=c6kFXyzilbkkajjR52OJ3Z7PepKAEwsrkQKzw2/y6Ts=; b=CHMVSi8Mfu2LpeDTuHh+Qi42+9f7n+uA7lxJ4nSzrrNzDqYU+YyyTQVbXti97nvhDB rGqiwA0XeCSVW1TNJE/XFr9akWqYesfZ5SJD/xU5mkg/egvJuiAuVlJAy+y4iyMT6jox iYjLx7lRWkVFtWY0fBTYH5IdecvBqkqxmuwbw= authentication-results: mr.google.com; spf=pass (google.com: domain of josepedromagalhaes@gmail.com designates 10.60.20.38 as permitted sender) smtp.mail=josepedromagalhaes@gmail.com; dkim=pass header.i=josepedromagalhaes@gmail.com x-spamscore: -12 x-bigfish: =?utf-8?q?vps-12=28z1039oz146fK168aJc85dh1432N14ffOzz1202h10c0jz?= =?utf-8?q?z8275ch8275dh5eeeKz2fh5fh2a8h668h839hbd3h=29?= Content-Type: multipart/alternative; boundary="_000_CAZFbn8fq5WnJiLU9S2zYomRu5ji8dKLtdD1Xev97Y34ydQmailgmai_" MIME-Version: 1.0 --_000_CAZFbn8fq5WnJiLU9S2zYomRu5ji8dKLtdD1Xev97Y34ydQmailgmai_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Hello all, First of all, I'm sorry that this email is so absurdly long. But it's not e= asy to explain the problem at hand, so I took a step-by-step approach. The = executive summary is: GHC can do a great job with inlining, but often it do= esn't, and I don't understand why. So I have some questions, which are high= lighted in the text below. In general, any insights regarding inlining or i= mproving the performance of generics are welcome. My final goal is to be ab= le to state that generic functions (in particular using GHC.Generics) will = have no runtime overhead whatsoever when compared to a handwritten type-spe= cific version. The setting Generic programming is based on representing datatypes in a uniform way usi= ng a small set of representation types. Functions defined on those represen= tation types can then be applied to all datatypes, because we can convert b= etween datatypes and their representations. However, generic functions tend to be slower than their specialised counter= parts, because they have to deal with the conversions. But clever inlining = (together with other compiler optimisations) can completely remove this ove= rhead. The problem I'm tackling is how to tell GHC exactly what it should i= n the particular case of optimisation of generic code. Simplified example I'll focus on the problem of optimising a non-trivial function for generic = enumeration of terms. My experience shows that GHC does quite good at optim= ising simple functions, especially consumers (like generic equality). But p= roducers are trickier. First, we'll need some auxiliary functions: -- | Interleave elements from two lists. Similar to (++), but swap left = and -- right arguments on every recursive application. -- -- From Mark Jones' talk at AFP2008 {-# NOINLINE (|||) #-} (|||) :: [a] -> [a] -> [a] [] ||| ys =3D ys (x:xs) ||| ys =3D x : ys ||| xs -- | Diagonalization of nested lists. Ensure that some elements from eve= ry -- sublist will be included. Handles infinite sublists. -- -- From Mark Jones' talk at AFP2008 {-# NOINLINE diag #-} diag :: [[a]] -> [a] diag =3D concat . foldr skew [] . map (map (\x -> [x])) skew :: [[a]] -> [[a]] -> [[a]] skew [] ys =3D ys skew (x:xs) ys =3D x : combine (++) xs ys combine :: (a -> a -> a) -> [a] -> [a] -> [a] combine _ xs [] =3D xs combine _ [] ys =3D ys combine f (x:xs) (y:ys) =3D f x y : combine f xs ys The particular implementation of these functions doesn't really matter. = What's important is that we have a way to interleave lists (|||) and a way = to diagonalise a matrix into a list (diag). We mark these functions as NOIN= LINE because inlining them will only make the core code more complicated (a= nd may prevent rules from firing). Suppose we have a type of Peano natural numbers: data Nat =3D Ze | Su Nat deriving Eq Implementing enumeration on this type is simple: enumNat :: [Nat] enumNat =3D [Ze] ||| map Su enumNat Now, a generic representation of Nat in terms of sums and products could= look something like this: type RepNat =3D Either () Nat That is, either a singleton (for the Ze case) or a Nat (for the Su case)= . Note that I am building a shallow representation, since at the leaves we = have Nat, and not RepNat. This mimics the situation with current generic pr= ogramming libraries (in particular GHC.Generics). We'll need a way to convert between RepNat and Nat: toNat :: RepNat -> Nat toNat (Left ()) =3D Ze toNat (Right n) =3D Su n fromNat :: Nat -> RepNat fromNat Ze =3D Left () fromNat (Su n) =3D Right n (In fact, since we're only dealing with a generic producer we won't need= the fromNat function.) To get an enumeration for RepNat, we first need to know how to enumerate= units and sums: enumU :: [()] enumU =3D [()] enumEither :: [a] -> [b] -> [Either a b] enumEither ea eb =3D map Left ea ||| map Right eb Now we can define an enumeration for RepNat: enumRepNat :: [RepNat] enumRepNat =3D enumEither enumU enumNatFromRep With the conversion function toNat, we can use enumRepNat to get an enum= eration for Nat directly: enumNatFromRep :: [Nat] enumNatFromRep =3D map toNat enumRepNat First, convince yourself that enumNatFromRep and enumNat are equivalent = functions: take 100 enumNat =3D=3D take 100 enumNatFromRep Now, what I want is that enumNatFromRep generates the same core code as = enumNat. That should be possible; here are the necessary steps: map toNat enumRepNat =3D=3D { inline enumRepNat } map toNat (enumEither enumU enumNatFromRep) =3D=3D { inline enumEither } map toNat (map Left enumU ||| map Right enumNatFromRep) =3D=3D { inline enumU } map toNat (map Left [()] ||| map Right enumNatFromRep) =3D=3D { inline map } map toNat ([Left ()] ||| map Right enumNatFromRep) =3D=3D { free theorem (|||): forall f a b. map f (a ||| b) =3D map f a |= || map f b } map toNat [Left ()] ||| map toNat (map Right enumNatFromRep) =3D=3D { inline map } [toNat (Left ())] ||| map toNat (map Right enumNatFromRep) =3D=3D { definition of toNat (or inline toNat + case of constant) } [Ze] ||| map toNat (map Right enumNatFromRep) =3D=3D { functor composition law: forall f g l. map f (map g l) =3D map = (f . g) l } [Ze] ||| map (toNat . Right) enumNatFromRep =3D=3D { definition of toNat (or inline toNat + case of constant) } [Ze] ||| map Su enumNatFromRep Now let's see what the compiler generates. I'm using GHC-7.4.1. Let's co= mpile with -O1 and use -ddump-simpl to see the final simplifier output (cor= e code) for enumNatFromRep: EnumAlone.enumNatFromRep :: [EnumAlone.Nat] [GblId, Str=3DDmdType, Unf=3DUnf{Src=3D, TopLvl=3DTrue, Arity=3D0, Value=3DFalse, ConLike=3DFalse, Cheap=3DFalse, Expandable=3DFalse, Guidance=3DIF_ARGS [] 30 0}] EnumAlone.enumNatFromRep =3D GHC.Base.map @ EnumAlone.RepNat @ EnumAlone.Nat EnumAlone.toNat EnumAlone.enumRepNat EnumAlone.enumRepNat [Occ=3DLoopBreaker] :: [EnumAlone.RepNat] [GblId, Str=3DDmdType] EnumAlone.enumRepNat =3D EnumAlone.||| @ (Data.Either.Either () EnumAlone.Nat) lvl4_rvV lvl5_rvW Ah, it didn't even inline enumRepNat because it made it a loop breaker. = We certainly want to inline it, so let's add a pragma: {-# INLINE enumRepNat #-} Recompiling, we get: EnumAlone.enumRepNat [InlPrag=3DINLINE (sat-args=3D0)] :: [EnumAlone.RepNat] [GblId, Str=3DDmdType, Unf=3DUnf{Src=3DInlineStable, TopLvl=3DTrue, Arity=3D0, Value=3DFalse, ConLike=3DFalse, Cheap=3DFalse, Expandable=3DFalse, Guidance=3DALWAYS_IF(unsat_ok=3DFalse,boring_ok=3DFalse) Tmpl=3D EnumAlone.enumEither @ () @ EnumAlone.Nat EnumAlone.enumU EnumAlone.enumNatF= romRep}] EnumAlone.enumRepNat =3D EnumAlone.||| @ (Data.Either.Either () EnumAlone.Nat) lvl4_rvV lvl5_rvW EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat] [GblId, Str=3DDmdType] EnumAlone.enumNatFromRep =3D GHC.Base.map @ EnumAlone.RepNat @ EnumAlone.Nat EnumAlone.toNat EnumAlone.enumRepNat So no real difference in the generated code, other than the reassignment= of loop breakers. For some reason enumRepNat still doesn't get inlined. Question: why won't GHC inline enumRepNat, even when I tell it to do so = with an INLINE pragma? Well, let's inline it ourselves, then. We redefine enumNatFromRep to: enumNatFromRep =3D map toNat (enumEither enumU enumNatFromRep) This however doesn't help much. We get the following core: lvl6_rw5 :: [Data.Either.Either () EnumAlone.Nat] [GblId] lvl6_rw5 =3D EnumAlone.||| @ (Data.Either.Either () EnumAlone.Nat) lvl4_rw3 lvl5_rw4 EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat] [GblId, Str=3DDmdType] EnumAlone.enumNatFromRep =3D GHC.Base.map @ EnumAlone.RepNat @ EnumAlone.Nat EnumAlone.toNat lvl6_rw5 GHC is really keen on floating that (|||) out. Let's be very explicit ab= out inlining: {-# INLINE toNat #-} {-# INLINE enumU #-} {-# INLINE enumEither #-} Also, maybe it's floating it out because it doesn't have anything else t= o do to it. Let's add the free theorem of (|||) as a rule: {-# RULES "ft |||" forall f a b. map f (a ||| b) =3D map f a ||| map f b= #-} We needed this in our manual derivation, so GHC should need it too. Reco= mpiling, we see we've made some progress: lvl5_ryv :: [Data.Either.Either () EnumAlone.Nat] [GblId] lvl5_ryv =3D GHC.Base.map @ EnumAlone.Nat @ (Data.Either.Either () EnumAlone.Nat) (Data.Either.Right @ () @ EnumAlone.Nat) EnumAlone.enumNatFromRep lvl6_ryw :: [EnumAlone.Nat] [GblId] lvl6_ryw =3D GHC.Base.map @ (Data.Either.Either () EnumAlone.Nat) @ EnumAlone.Nat EnumAlone.toNat lvl5_ryv EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat] [GblId, Str=3DDmdType] EnumAlone.enumNatFromRep =3D EnumAlone.||| @ EnumAlone.Nat lvl4_ryu lvl6_ryw enumNatFromRep finally starts with (|||) directly. But its second argume= nt, lvl6_ryw, is a map of lvl5_ryv, which is itself a map! At this stage I = expected GHC to be aware of the fusion law for map, but it seems that it is= n't. Question: why is map fusion not happening automatically? Let's add it as a rule: {-# RULES "map/map1" forall f g l. map f (map g l) =3D map (f . g) l #-} And now we're in a much better situation: lvl3_ryD :: [Data.Either.Either () EnumAlone.Nat] [GblId, Caf=3DNoCafRefs] lvl3_ryD =3D GHC.Types.: @ (Data.Either.Either () EnumAlone.Nat) EnumAlone.fromNat1 (GHC.Types.[] @ (Data.Either.Either () EnumAlone.Nat)) lvl4_ryE :: [EnumAlone.Nat] [GblId] lvl4_ryE =3D GHC.Base.map @ (Data.Either.Either () EnumAlone.Nat) @ EnumAlone.Nat EnumAlone.toNat lvl3_ryD lvl5_ryF :: [EnumAlone.Nat] [GblId] lvl5_ryF =3D GHC.Base.map @ EnumAlone.Nat @ EnumAlone.Nat EnumAlone.Su EnumAlone.enumNatFromRep EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat] [GblId, Str=3DDmdType] EnumAlone.enumNatFromRep =3D EnumAlone.||| @ EnumAlone.Nat lvl4_ryE lvl5_ryF Note how toNat is entirely gone from the second part of the enumeration = (lvl5_ryF). Strangely enough, the enumerator for Ze (lvl4_ryE) is still ver= y complicated: map toNat ([Left ()]). Why doesn't GHC simplify this to just= [Ze]? Apparently because GHC doesn't simplify map over a single element li= st. Question: why doesn't GHC optimise map f [x] to [f x]? Let's tell it to do so: {-# RULES "map/map2" forall f x. map f (x:[]) =3D (f x):[] #-} Now we're finally where we wanted: lvl_ryA :: [EnumAlone.Nat] [GblId, Caf=3DNoCafRefs] lvl_ryA =3D GHC.Types.: @ EnumAlone.Nat EnumAlone.Ze (GHC.Types.[] @ EnumAlone.Nat) lvl3_ryD :: [EnumAlone.Nat] [GblId] lvl3_ryD =3D GHC.Base.map @ EnumAlone.Nat @ EnumAlone.Nat EnumAlone.Su EnumAlone.enumNatFromRep EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat] [GblId, Str=3DDmdType] EnumAlone.enumNatFromRep =3D EnumAlone.||| @ EnumAlone.Nat lvl_ryA lvl3_ryD This is what I wanted: no more representation types (Either or ()), and = the code looks exactly like what is generated for the handwritten enumNat. More realistic generic programming Now let's see if we can transport this to the setting of a generic progr= amming library. I'll use a bare-bones version of GHC.Generics: infixr 5 :+: infixr 6 :*: data U =3D U deriving (Show, Read) data a :+: b =3D L a | R b deriving (Show, Read) data a :*: b =3D a :*: b deriving (Show, Read) newtype Var a =3D Var a deriving (Show, Read) newtype Rec a =3D Rec a deriving (Show, Read) class Representable a where type Rep a to :: Rep a -> a from :: a -> Rep a Let's represent Nat in this library: instance Representable Nat where type Rep Nat =3D U :+: (Rec Nat) from Ze =3D L U from (Su n) =3D R (Rec n) to (L U) =3D Ze to (R (Rec n)) =3D Su n (Note, in particular, that we do not need INLINE pragmas on the from/to = methods. This might just be because GHC thinks these are small and inlines = them anyway, but in general we want to make sure they are inlined, so we ty= pically use pragmas there.) Now we need to implement enumeration generically. We do this by giving a= n instance for each representation type: class GEnum' a where genum' :: [a] instance GEnum' U where {-# INLINE genum' #-} genum' =3D [U] instance (GEnum a) =3D> GEnum' (Rec a) where {-# INLINE genum' #-} genum' =3D map Rec genum instance (GEnum a) =3D> GEnum' (Var a) where {-# INLINE genum' #-} genum' =3D map Var genum instance (GEnum' f, GEnum' g) =3D> GEnum' (f :+: g) where {-# INLINE genum' #-} genum' =3D map L genum' ||| map R genum' instance (GEnum' f, GEnum' g) =3D> GEnum' (f :*: g) where {-# INLINE genum' #-} --genum' =3D diag [ [ x :*: y | y <- genum' ] | x <- genum' ] genum' =3D diag (map (\x -> map (\y -> x :*: y) genum') genum') We explicitly tell GHC to inline each case, as before. Note that for pro= ducts I'm not using the more natural list comprehension syntax because I do= n't quite understand how that gets translated into core. In the cases for Var and Rec we use genum from the GEnum class: class GEnum a where genum :: [a] {-# INLINE genum #-} default genum :: (Representable a, GEnum' (Rep a)) =3D> [a] genum =3D map to genum' GEnum' is the class used for instantiating the generic representation ty= pes, and GEnum is used for user types. We use a default signature to provid= e a default method that can be used when we have a Representable instance f= or the type in question. This makes instantiating Nat very easy: instance GEnum Nat Unfortunately, the core code generated in this situation (with the same = RULES as before) is not nice at all: Main.$fGEnumNat_$cgenum [Occ=3DLoopBreaker] :: [Base.Nat] [GblId, Str=3DDmdType] Main.$fGEnumNat_$cgenum =3D GHC.Base.map @ (Base.Rep Base.Nat) @ Base.Nat Base.$fRepresentableNat_$cto (lvl37_r79y `cast` (Sym (GEnum.NTCo:GEnum') ; (GEnum.GEnum' (Sym (Base.TFCo:R:R= epNat)) ; GEnum.NTCo:GEnum' ) :: [Base.C Base.Nat_Ze_ Base.U Base.:+: Base.C Base.Nat_Su_ (Base.Rec Base.Nat)] ~# [Base.Rep Base.Nat])) We see a map of the `to` function, which is definitely not what we want.= Oddly enough, if we give an explicit definition of genum for Nat, with the= inlined default... instance GEnum Nat where genum =3D map to genum' ... then we get the optimised code we want: lvl34_r79p :: [Base.Nat] [GblId, Caf=3DNoCafRefs] lvl34_r79p =3D GHC.Types.: @ Base.Nat Base.Ze (GHC.Types.[] @ Base.Nat) lvl35_r79q :: [Base.Nat] [GblId] lvl35_r79q =3D GHC.Base.map @ Base.Nat @ Base.Nat Base.Su Main.$fGEnumNat_$cgenum Main.$fGEnumNat_$cgenum [Occ=3DLoopBreaker] :: [Base.Nat] [GblId, Str=3DDmdType] Main.$fGEnumNat_$cgenum =3D GEnum.||| @ Base.Nat lvl34_r79p lvl35_r79q Again, no representation types, no `to`, just the same code that is gene= rated for enumNat. Perfect. But we had to avoid using the default definitio= n, which is a pity. Question: why won't GHC inline the default method of a class, even when = I have a pragma telling it to do so? Let's look at one more datatype, because Nat does not use products. So l= et's consider trees: data Tree a =3D Leaf | Bin a (Tree a) (Tree a) instance Representable (Tree a) where type Rep (Tree a) =3D U :+: (Var a :*: Rec (Tree a) :*: Rec (Tree a)) from (Bin x l r) =3D R (Var x :*: Rec l :*: Rec r) from Leaf =3D L U to (R (Var x :*: (Rec l) :*: (Rec r))) =3D Bin x l r to (L U) =3D Leaf We give a GEnum instance using the same trick as before: instance GEnum (Tree Int) where genum =3D map to genum' (For simplicity only for trees of integers.) The generated code for tree= s is unfortunately not as nice: a2_r79M :: [Base.Rec (Base.Tree GHC.Types.Int) Base.:*: Base.Rec (Base.Tree GHC.Types.Int)] [GblId, Str=3DDmdType] a2_r79M =3D GEnum.diag @ (Base.Rec (Base.Tree GHC.Types.Int) Base.:*: Base.Rec (Base.Tree GHC.Types.Int)= ) lvl8_r79L lvl9_r79N :: [Base.Tree GHC.Types.Int] [GblId] lvl9_r79N =3D GHC.Base.map @ (Base.Rec (Base.Tree GHC.Types.Int) Base.:*: Base.Rec (Base.Tree GHC.Types.Int)= ) @ (Base.Tree GHC.Types.Int) lvl5_r79H a2_r79M Main.$fGEnumTree_$cgenum [Occ=3DLoopBreaker] :: [Base.Tree GHC.Types.Int] [GblId, Str=3DDmdType] Main.$fGEnumTree_$cgenum =3D GEnum.||| @ (Base.Tree GHC.Types.Int) lvl4_r79G = lvl9_r79N Note how lvl9_r79N is a map over a2_r79M, and a2_r79M is a `diag`. Ok, w= e need the free theorem of `diag` to tell GHC how to commute the `diag` wit= h map: {-# RULES "ft/diag" forall f l. map f (diag l) =3D diag (map (map f) l) = #-} Unfortunately this doesn't change the generated core code. With some mor= e debugging looking at the generated code at each simplifier iteration, I b= elieve that this is because a2_r79M got lifted out too soon, prevent the ru= le from applying. With some imagination I decided to try the -fno-full-lazi= ness flag to prevent let-floating. I'm not sure this is a good idea in gene= ral, but in this particular case it gives much better results: a1_r72i :: [Base.Rec (Base.Tree GHC.Types.Int)] [GblId, Str=3DDmdType] a1_r72i =3D GHC.Base.map @ (Base.Tree GHC.Types.Int) @ (Base.Rec (Base.Tree GHC.Types.Int)) ((\ (tpl_B1 :: Base.Tree GHC.Types.Int) -> tpl= _B1) `cast` (> -> Sym (Base.NTCo:Rec >) :: (Base.Tree GHC.Types.Int -> Base.T= ree GHC.Types.Int) ~# (Base.Tree GHC.Types.Int -> Base.R= ec (Base.Tree GHC.Types.Int)))) Main.$fGEnumTree_$cgenum Main.$fGEnumTree_$cgenum [Occ=3DLoopBreaker] :: [Base.Tree GHC.Types.Int] [GblId, Str=3DDmdType] Main.$fGEnumTree_$cgenum =3D GEnum.||| @ (Base.Tree GHC.Types.Int) (GHC.Types.: @ (Base.Tree GHC.Types.Int) (Base.Leaf @ GHC.Types.Int) (GHC.Types.[] @ (Base.Tree GHC.Types.Int))) (GEnum.diag @ (Base.Tree GHC.Types.Int) (GHC.Base.map @ (Base.Rec (Base.Tree GHC.Types.Int)) @ [Base.Tree GHC.Types.Int] (\ (x_a1yQ :: Base.Rec (Base.Tree GHC.Types.Int)) -> GHC.Base.map @ (Base.Rec (Base.Tree GHC.Types.Int)) @ (Base.Tree GHC.Types.Int) (\ (x1_X1zB :: Base.Rec (Base.Tree GHC.Types.Int)) -> Base.Bin @ GHC.Types.Int a_r72h (x_a1yQ `cast` (Base.NTCo:Rec > :: Base.Rec (Base.Tree GHC.Types.Int) ~# Base.Tree GHC.Types.Int)) (x1_X1zB `cast` (Base.NTCo:Rec > :: Base.Rec (Base.Tree GHC.Types.Int) ~# Base.Tree GHC.Types.Int))) a1_r72i) a1_r72i)) Note how our enum is now of the shape `[Leaf] ||| diag y`, which is good= . The only catch is that there are some `Rec`s still laying around, with th= eir associated newtype coercions, and a function a1_r72i that basically wra= ps the recursive enumeration in a Rec, only to be unwrapped in the body of = `$fGEnumTree_$cgenum`. I don't know how to get GHC to simplify this code an= y further. Question: why do I need -fno-full-laziness for the ft/diag rule to apply= ? Question: why is GHC not getting rid of the Rec newtype in this case? I have also played with -O2, in particular because of the SpecConstr opt= imisation, but found that it does not affect these particular examples (per= haps it only becomes important with larger datatypes). I have also experime= nted with phase control in the rewrite rules and the inline pragmas, but di= dn't find it necessary for this example. In general, anyway, my experience = with the inliner is that it is extremely fragile, especially across differe= nt GHC versions, and it's hard to get any guarantees of optimisation. I hav= e also played with the -funfolding-* options before, with mixed results. [1= ] It's also a pity that certain flags are not explained in detail in the us= er's manual [2,3], like -fliberate-case, and -fspec-constr-count and thresh= old, for instance. Thank you for reading this. Any insights are welcome. In particular, I'm= wondering if I might be missing some details regarding strictness. Cheers, Pedro [1] http://dreixel.net/research/pdf/ogie.pdf [2] http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-referen= ce.html [3] http://www.haskell.org/ghc/docs/latest/html/users_guide/options-opti= mise.html#options-f --_000_CAZFbn8fq5WnJiLU9S2zYomRu5ji8dKLtdD1Xev97Y34ydQmailgmai_ Content-Type: text/html; charset="iso-8859-1" Content-ID: Content-Transfer-Encoding: quoted-printable Hello all,

First of all, I'm sorry that this email is so absurdly long. But it's not e= asy to explain the problem at hand, so I took a step-by-step approach. The = executive summary is: GHC can do a great job with inlining, but often it doesn't, and I don't understan= d why. So I have some questions, which are highlighted in the text below. I= n general, any insights regarding inlining or improving the performance of = generics are welcome. My final goal is to be able to state that generic functions (in particular using GHC.Gen= erics) will have no runtime overhead whatsoever when compared to a handwrit= ten type-specific version.


The setting

Generic programming is based on representing datatypes in a uniform way usi= ng a small set of representation types. Functions defined on those represen= tation types can then be applied to all datatypes, because we can convert b= etween datatypes and their representations.
However, generic functions tend to be slower than their specialised counter= parts, because they have to deal with the conversions. But clever inlining = (together with other compiler optimisations) can completely remove this ove= rhead. The problem I'm tackling is how to tell GHC exactly what it should in the particular case of optimi= sation of generic code.


Simplified example

I'll focus on the problem of optimising a non-trivial function for generic = enumeration of terms. My experience shows that GHC does quite good at optim= ising simple functions, especially consumers (like generic equality). But p= roducers are trickier.

First, we'll need some auxiliary functions:

-- | Interleave elements from two lists. Similar to (++), but swap = left and
-- right arguments on every recursive application.
--
-- From Mark Jones' talk at AFP2008
{-# NOINLINE (|||) #-}
(|||) :: [a] -> [a] -> [a]
[]     ||| ys =3D ys
(x:xs) ||| ys =3D x : ys ||| xs


-- | Diagonalization of nested lists. Ensure that some elements from every<= br> -- sublist will be included. Handles infinite sublists.
--
-- From Mark Jones' talk at AFP2008
{-# NOINLINE diag #-}
diag :: [[a]] -> [a]
diag =3D concat . foldr skew [] . map (map (\x -> [x]))

skew :: [[a]] -> [[a]] -> [[a]]
skew []     ys =3D ys
skew (x:xs) ys =3D x : combine (++) xs ys

combine :: (a -> a -> a) -> [a] -> [a] -> [a]
combine _ xs     []     =3D xs
combine _ []     ys     =3D ys
combine f (x:xs) (y:ys) =3D f x y : combine f xs ys

The particular implementation of these functions doesn't really matter. Wha= t's important is that we have a way to interleave lists (|||) and a way to = diagonalise a matrix into a list (diag). We mark these functions as NOINLIN= E because inlining them will only make the core code more complicated (and may prevent rules from firing).
Suppose we have a type of Peano natural numbers:

data Nat =3D Ze | Su Nat deriving Eq

Implementing enumeration on this type is simple:

enumNat :: [Nat]
enumNat =3D [Ze] ||| map Su enumNat

Now, a generic representation of Nat in terms of sums and products could lo= ok something like this:

type RepNat =3D Either () Nat

That is, either a singleton (for the Ze case) or a Nat (for the Su case). N= ote that I am building a shallow representation, since at the leaves we hav= e Nat, and not RepNat. This mimics the situation with current generic progr= amming libraries (in particular GHC.Generics).

We'll need a way to convert between RepNat and Nat:

toNat :: RepNat -> Nat
toNat (Left ()) =3D Ze
toNat (Right n) =3D Su n

fromNat :: Nat -> RepNat
fromNat Ze =3D Left ()
fromNat (Su n) =3D Right n

(In fact, since we're only dealing with a generic producer we won't need th= e fromNat function.)

To get an enumeration for RepNat, we first need to know how to enumerate un= its and sums:

enumU :: [()]
enumU =3D [()]

enumEither :: [a] -> [b] -> [Either a b]
enumEither ea eb =3D map Left ea ||| map Right eb

Now we can define an enumeration for RepNat:

enumRepNat :: [RepNat]
enumRepNat =3D enumEither enumU enumNatFromRep

With the conversion function toNat, we can use enumRepNat to get an enumera= tion for Nat directly:

enumNatFromRep :: [Nat]
enumNatFromRep =3D map toNat enumRepNat

First, convince yourself that enumNatFromRep and enumNat are equivalent fun= ctions:

take 100 enumNat =3D=3D take 100 enumNatFromRep

Now, what I want is that enumNatFromRep generates the same core code as enu= mNat. That should be possible; here are the necessary steps:

  map toNat enumRepNat

=3D=3D { inline enumRepNat }

  map toNat (enumEither enumU enumNatFromRep)

=3D=3D { inline enumEither }

  map toNat (map Left enumU ||| map Right enumNatFromRep)

=3D=3D { inline enumU }

  map toNat (map Left [()] ||| map Right enumNatFromRep)

=3D=3D { inline map }

  map toNat ([Left ()] ||| map Right enumNatFromRep)

=3D=3D { free theorem (|||): forall f a b. map f (a ||| b) =3D map f a ||| = map f b }

  map toNat [Left ()] ||| map toNat (map Right enumNatFromRep)

=3D=3D { inline map }

  [toNat (Left ())] ||| map toNat (map Right enumNatFromRep)

=3D=3D { definition of toNat (or inline toNat + case of constant) }

  [Ze] ||| map toNat (map Right enumNatFromRep)

=3D=3D { functor composition law: forall f g l. map f (map g l) =3D map (f = . g) l }

  [Ze] ||| map (toNat . Right) enumNatFromRep

=3D=3D { definition of toNat (or inline toNat + case of constant) }

  [Ze] ||| map Su enumNatFromRep

Now let's see what the compiler generates. I'm using GHC-7.4.1. Let's compi= le with -O1 and use -ddump-simpl to see the final simplifier output (core c= ode) for enumNatFromRep:

EnumAlone.enumNatFromRep :: [EnumAlone.Nat]
[GblId,
 Str=3DDmdType,
 Unf=3DUnf{Src=3D<vanilla>, TopLvl=3DTrue, Arity=3D0, Value=3DFa= lse,
         ConLike=3DFalse, Cheap=3DF= alse, Expandable=3DFalse,
         Guidance=3DIF_ARGS [] 30 0= }]
EnumAlone.enumNatFromRep =3D
  GHC.Base.map
    @ EnumAlone.RepNat
    @ EnumAlone.Nat
    EnumAlone.toNat
    EnumAlone.enumRepNat

EnumAlone.enumRepNat [Occ=3DLoopBreaker] :: [EnumAlone.RepNat]
[GblId, Str=3DDmdType]
EnumAlone.enumRepNat =3D
  EnumAlone.|||
    @ (Data.Either.Either () EnumAlone.Nat) lvl4_rvV lvl5_rv= W

Ah, it didn't even inline enumRepNat because it made it a loop breaker. We = certainly want to inline it, so let's add a pragma:

{-# INLINE enumRepNat #-}=

Recompiling, we get:

EnumAlone.enumRepNat [InlPrag=3DINLINE (sat-args=3D0)]
  :: [EnumAlone.RepNat]
[GblId,
 Str=3DDmdType,
 Unf=3DUnf{Src=3DInlineStable, TopLvl=3DTrue, Arity=3D0, Value=3DFalse= ,
         ConLike=3DFalse, Cheap=3DF= alse, Expandable=3DFalse,
         Guidance=3DALWAYS_IF(unsat= _ok=3DFalse,boring_ok=3DFalse)
         Tmpl=3D EnumAlone.enumEith= er
            &nb= sp;    @ () @ EnumAlone.Nat EnumAlone.enumU EnumAlone.enumNa= tFromRep}]
EnumAlone.enumRepNat =3D
  EnumAlone.|||
    @ (Data.Either.Either () EnumAlone.Nat) lvl4_rvV lvl5_rv= W

EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat]
[GblId, Str=3DDmdType]
EnumAlone.enumNatFromRep =3D
  GHC.Base.map
    @ EnumAlone.RepNat
    @ EnumAlone.Nat
    EnumAlone.toNat
    EnumAlone.enumRepNat

So no real difference in the generated code, other than the reassignment of= loop breakers. For some reason enumRepNat still doesn't get inlined.

Question: why won't GHC inline enumRepNat, even when I tell it to do so = with an INLINE pragma?

Well, let's inline it ourselves, then. We redefine enumNatFromRep to:

enumNatFromRep =3D map toNat (enumEither enumU enumNatFromRep)

This however doesn't help much. We get the following core:

lvl6_rw5 :: [Data.Either.Either () EnumAlone.Nat]
[GblId]
lvl6_rw5 =3D
  EnumAlone.|||
    @ (Data.Either.Either () EnumAlone.Nat) lvl4_rw3 lvl5_rw= 4

EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat]
[GblId, Str=3DDmdType]
EnumAlone.enumNatFromRep =3D
  GHC.Base.map
    @ EnumAlone.RepNat @ EnumAlone.Nat EnumAlone.toNat lvl6_= rw5

GHC is really keen on floating that (|||) out. Let's be very explicit about= inlining:

{-# INLINE toNat #-}
{-# INLINE enumU #-}
{-# INLINE enumEither #-}

Also, maybe it's floating it out because it doesn't have anything else to d= o to it. Let's add the free theorem of (|||) as a rule:

{-# RULES "ft |||" forall f a b. map f (a ||| b) =3D map f a ||| = map f b #-}

We needed this in our manual derivation, so GHC should need it too. Recompi= ling, we see we've made some progress:

lvl5_ryv :: [Data.Either.Either () EnumAlone.Nat]
[GblId]
lvl5_ryv =3D
  GHC.Base.map
    @ EnumAlone.Nat
    @ (Data.Either.Either () EnumAlone.Nat)
    (Data.Either.Right @ () @ EnumAlone.Nat)
    EnumAlone.enumNatFromRep

lvl6_ryw :: [EnumAlone.Nat]
[GblId]
lvl6_ryw =3D
  GHC.Base.map
    @ (Data.Either.Either () EnumAlone.Nat)
    @ EnumAlone.Nat
    EnumAlone.toNat
    lvl5_ryv

EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat]
[GblId, Str=3DDmdType]
EnumAlone.enumNatFromRep =3D
  EnumAlone.||| @ EnumAlone.Nat lvl4_ryu lvl6_ryw

enumNatFromRep finally starts with (|||) directly. But its second argument,= lvl6_ryw, is a map of lvl5_ryv, which is itself a map! At this stage I exp= ected GHC to be aware of the fusion law for map, but it seems that it isn't= .

Question: why is map fusion not happening automatically?

Let's add it as a rule:

{-# RULES "map/map1" forall f g l. map f (map g l) =3D map (f . g= ) l #-}

And now we're in a much better situation:

lvl3_ryD :: [Data.Either.Either () EnumAlone.Nat]
[GblId, Caf=3DNoCafRefs]
lvl3_ryD =3D
  GHC.Types.:
    @ (Data.Either.Either () EnumAlone.Nat)
    EnumAlone.fromNat1
    (GHC.Types.[] @ (Data.Either.Either () EnumAlone.Nat))
lvl4_ryE :: [EnumAlone.Nat]
[GblId]
lvl4_ryE =3D
  GHC.Base.map
    @ (Data.Either.Either () EnumAlone.Nat)
    @ EnumAlone.Nat
    EnumAlone.toNat
    lvl3_ryD

lvl5_ryF :: [EnumAlone.Nat]
[GblId]
lvl5_ryF =3D
  GHC.Base.map
    @ EnumAlone.Nat
    @ EnumAlone.Nat
    EnumAlone.Su
    EnumAlone.enumNatFromRep

EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat]
[GblId, Str=3DDmdType]
EnumAlone.enumNatFromRep =3D
  EnumAlone.||| @ EnumAlone.Nat lvl4_ryE lvl5_ryF

Note how toNat is entirely gone from the second part of the enumeration (lv= l5_ryF). Strangely enough, the enumerator for Ze (lvl4_ryE) is still very c= omplicated: map toNat ([Left ()]). Why doesn't GHC simplify this to just [Z= e]? Apparently because GHC doesn't simplify map over a single element list.

Question: why doesn't GHC optimise map f [x] to [f x]?

Let's tell it to do so:

{-# RULES "map/map2" forall f x. map f (x:[]) =3D (f x):[] #-}

Now we're finally where we wanted:

lvl_ryA :: [EnumAlone.Nat]
[GblId, Caf=3DNoCafRefs]
lvl_ryA =3D
  GHC.Types.:
    @ EnumAlone.Nat EnumAlone.Ze (GHC.Types.[] @ EnumAlone.N= at)

lvl3_ryD :: [EnumAlone.Nat]
[GblId]
lvl3_ryD =3D
  GHC.Base.map
    @ EnumAlone.Nat
    @ EnumAlone.Nat
    EnumAlone.Su
    EnumAlone.enumNatFromRep

EnumAlone.enumNatFromRep [Occ=3DLoopBreaker] :: [EnumAlone.Nat]
[GblId, Str=3DDmdType]
EnumAlone.enumNatFromRep =3D
  EnumAlone.||| @ EnumAlone.Nat lvl_ryA lvl3_ryD

This is what I wanted: no more representation types (Either or ()), and the= code looks exactly like what is generated for the handwritten enumNat.


More realistic generic programming

Now let's see if we can transport this to the setting of a generic programm= ing library. I'll use a bare-bones version of GHC.Generics:

infixr 5 :+:
infixr 6 :*:

data U          =3D U &nb= sp;            deriv= ing (Show, Read)
data a :+: b    =3D L a | R b    &nb= sp; deriving (Show, Read)
data a :*: b    =3D a :*: b     &nb= sp;  deriving (Show, Read)
newtype Var a   =3D Var a      &nbs= p;   deriving (Show, Read)
newtype Rec a   =3D Rec a      &nbs= p;   deriving (Show, Read)

class Representable a where
  type Rep a
  to   :: Rep a -> a
  from :: a -> Rep a

Let's represent Nat in this library:

instance Representable Nat where
  type Rep Nat =3D U :+: (Rec Nat)
  from Ze          &= nbsp; =3D L U
  from (Su n)        =3D R (Rec n)<= br>   to (L U)       =3D Ze
  to (R (Rec n)) =3D Su n

(Note, in particular, that we do not need INLINE pragmas on the from/to met= hods. This might just be because GHC thinks these are small and inlines the= m anyway, but in general we want to make sure they are inlined, so we typic= ally use pragmas there.)

Now we need to implement enumeration generically. We do this by giving an i= nstance for each representation type:

class GEnum' a where
  genum' :: [a]

instance GEnum' U where
  {-# INLINE genum' #-}
  genum' =3D [U]

instance (GEnum a) =3D> GEnum' (Rec a) where
  {-# INLINE genum' #-}
  genum' =3D map Rec genum

instance (GEnum a) =3D> GEnum' (Var a) where
  {-# INLINE genum' #-}
  genum' =3D map Var genum

instance (GEnum' f, GEnum' g) =3D> GEnum' (f :+: g) where
  {-# INLINE genum' #-}
  genum' =3D map L genum' ||| map R genum'

instance (GEnum' f, GEnum' g) =3D> GEnum' (f :*: g) where
  {-# INLINE genum' #-}
  --genum' =3D diag [ [ x :*: y | y <- genum' ] | x <- genum' ]<= br>   genum' =3D diag (map (\x -> map (\y -> x :*: y) genum') genum'= )

We explicitly tell GHC to inline each case, as before. Note that for produc= ts I'm not using the more natural list comprehension syntax because I don't= quite understand how that gets translated into core.

In the cases for Var and Rec we use genum from the GEnum class:

class GEnum a where
  genum :: [a]
  {-# INLINE genum #-}
  default genum :: (Representable a, GEnum' (Rep a)) =3D> [a]
  genum =3D map to genum'

GEnum' is the class used for instantiating the generic representation types= , and GEnum is used for user types. We use a default signature to provide a= default method that can be used when we have a Representable instance for = the type in question. This makes instantiating Nat very easy:

instance GEnum Nat

Unfortunately, the core code generated in this situation (with the same RUL= ES as before) is not nice at all:

Main.$fGEnumNat_$cgenum [Occ=3DLoopBreaker] :: [Base.Nat]
[GblId, Str=3DDmdType]
Main.$fGEnumNat_$cgenum =3D
  GHC.Base.map
    @ (Base.Rep Base.Nat)
    @ Base.Nat
    Base.$fRepresentableNat_$cto
    (lvl37_r79y
     `cast` (Sym (GEnum.NTCo:GEnum') <Base.U Base.:&= #43;: (Base.Rec Base.Nat)> ;
            &nb= sp;            =             &nb= sp; (GEnum.GEnum' (Sym (Base.TFCo:R:RepNat)) ;
            &nb= sp;            =             &nb= sp;   GEnum.NTCo:GEnum' <Base.Rep Base.Nat>)
             ::= [Base.C Base.Nat_Ze_ Base.U
            &nb= sp;    Base.:+: Base.C Base.Nat_Su_ (Base.Rec Base.Nat)]=
            &nb= sp;     ~#
            &nb= sp;   [Base.Rep Base.Nat]))

We see a map of the `to` function, which is definitely not what we want. Od= dly enough, if we give an explicit definition of genum for Nat, with the in= lined default...

instance GEnum Nat where genum =3D map to genum'

... then we get the optimised code we want:

lvl34_r79p :: [Base.Nat]
[GblId, Caf=3DNoCafRefs]
lvl34_r79p =3D
  GHC.Types.: @ Base.Nat Base.Ze (GHC.Types.[] @ Base.Nat)

lvl35_r79q :: [Base.Nat]
[GblId]
lvl35_r79q =3D
  GHC.Base.map @ Base.Nat @ Base.Nat Base.Su Main.$fGEnumNat_$cgenum
Main.$fGEnumNat_$cgenum [Occ=3DLoopBreaker] :: [Base.Nat]
[GblId, Str=3DDmdType]
Main.$fGEnumNat_$cgenum =3D
  GEnum.||| @ Base.Nat lvl34_r79p lvl35_r79q

Again, no representation types, no `to`, just the same code that is generat= ed for enumNat. Perfect. But we had to avoid using the default definition, = which is a pity.

Question: why won't GHC inline the default method of a class, even when = I have a pragma telling it to do so?

Let's look at one more datatype, because Nat does not use products. So let'= s consider trees:

data Tree a =3D Leaf | Bin a (Tree a) (Tree a)

instance Representable (Tree a) where
  type Rep (Tree a) =3D U :+: (Var a :*: Rec (Tree a) :*: Rec (Tre= e a))
  from (Bin x l r) =3D R (Var x :*: Rec l :*: Rec r)
  from Leaf        =3D L U
  to (R (Var x :*: (Rec l) :*: (Rec r))) =3D Bin x l r
  to (L U)          =             &nb= sp;        =3D Leaf

We give a GEnum instance using the same trick as before:

instance GEnum (Tree Int) where genum =3D map to genum'

(For simplicity only for trees of integers.) The generated code for trees i= s unfortunately not as nice:

a2_r79M
  :: [Base.Rec (Base.Tree GHC.Types.I= nt)
      Base.:*: Base.Rec (Base.Tree GHC.Types.Int)]
[GblId, Str=3DDmdType]
a2_r79M =3D
  GEnum.diag
    @ (Base.Rec (Base.Tree = GHC.Types.Int)
       Base.:*: Base.Rec (Base.Tree GHC.Types.Int))
    lvl8_r79L

lvl9_r79N :: [Base.Tree GHC.Types.Int]=
[GblId]
lvl9_r79N =3D
  GHC.Base.map
    @ (Base.Rec (Base.Tree = GHC.Types.Int)
       Base.:*: Base.Rec (Base.Tree GHC.Types.Int))
    @ (Base.Tree GHC.Types.= Int)
    lvl5_r79H
    a2_r79M

Main.$fGEnumTree_$cgenum [Occ=3DLoopBreaker]
  :: [Base.Tree GHC.Types.Int] [GblId, Str=3DDmdType]
Main.$fGEnumTree_$cgenum =3D
  GEnum.||| @ (Base.Tree GHC.Types.In= t) lvl4_r79G lvl9_r79N

Note how lvl9_r79N is a map over a2_r79M, and a2_r79M is a `diag`. Ok, we n= eed the free theorem of `diag` to tell GHC how to commute the `diag` with m= ap:

{-# RULES "ft/diag" forall f l. map f (diag l) =3D diag (map (map= f) l) #-}

Unfortunately this doesn't change the generated core code. With some more d= ebugging looking at the generated code at each simplifier iteration, I beli= eve that this is because a2_r79M got lifted out too soon, prevent the rule = from applying. With some imagination I decided to try the -fno-full-laziness flag to prevent let-floating. I'm = not sure this is a good idea in general, but in this particular case it giv= es much better results:

a1_r72i :: [Base.Rec (Base.Tree GHC.Types.= Int)]
[GblId, Str=3DDmdType]
a1_r72i =3D
  GHC.Base.map
    @ (Base.Tree GHC.Types.= Int)
    @ (Base.Rec (Base.Tree = GHC.Types.Int))
    ((\ (tpl_B1 :: Base.Tree GHC.Types.Int) -> tpl_B1)
     `cast` (<Base.Tree GHC.Types.Int>
             -&= gt; Sym (Base.NTCo:Rec <Base.Tree GHC.T= ypes.Int>)
             ::= (Base.Tree GHC.Types.Int -> Base.T= ree GHC.Types.Int)
            &nb= sp;     ~#
            &nb= sp;   (Base.Tree GHC.Types.Int -> Base.Rec (Base.Tree GHC.Types.Int))))
    Main.$fGEnumTree_$cgenum

Main.$fGEnumTree_$cgenum [Occ=3DLoopBreaker]
  :: [Base.Tree GHC.Types.Int] [GblId, Str=3DDmdType]
Main.$fGEnumTree_$cgenum =3D
  GEnum.|||
    @ (Base.Tree GHC.Types.= Int)
    (GHC.Types.:
       @ (Base.Tree GHC.Types.Int)
       (Base.Leaf @ GHC.Types.Int)
       (GHC.Types.[] @ (Base.Tree GHC.Types.Int)))
    (GEnum.diag
       @ (Base.Tree GHC.Types.Int)
       (GHC.Base.map
          @ (Base.Rec (Base.Tr= ee GHC.Types.Int))
          @ [Base.Tree GHC.Types.Int]
          (\ (x_a1yQ :: Base.R= ec (Base.Tree GHC.Types.Int)) ->              GH= C.Base.map
            &nb= sp;  @ (Base.Rec (Base.Tree GHC.Types= .Int))
            &nb= sp;  @ (Base.Tree GHC.Types.Int)<= br>             &nb= sp;  (\ (x1_X1zB :: Base.Rec (Base.Tree GHC.Types.Int)) ->
            &nb= sp;     Base.Bin
            &nb= sp;       @ = GHC.Types.Int
            &nb= sp;       a_r72h
            &nb= sp;       (x_a1yQ
            &nb= sp;        `cast` (Base.NTCo:Rec <Bas= e.Tree GHC.Types.Int>
            &nb= sp;            =     :: Base.Rec (Base.Tree GHC.Types.Int) ~# Base.Tree GHC.Types.= Int))
            &nb= sp;       (x1_X1zB
            &nb= sp;        `cast` (Base.NTCo:Rec <Bas= e.Tree GHC.Types.Int>
            &nb= sp;            =     :: Base.Rec (Base.Tree GHC.Types.Int) ~# Base.Tree GHC.Types.= Int)))
            &nb= sp;  a1_r72i)
          a1_r72i))

Note how our enum is now of the shape `[Leaf] ||| diag y`, which is good. T= he only catch is that there are some `Rec`s still laying around, with their= associated newtype coercions, and a function a1_r72i that basically wraps = the recursive enumeration in a Rec, only to be unwrapped in the body of `$fGEnumTree_$cgenum`. I don't know ho= w to get GHC to simplify this code any further.

Question: why do I need -fno-full-laziness for the ft/diag rule to apply= ?

Question: why is GHC not getting rid of the Rec newtype in this case?

I have also played with -O2, in particular because of the SpecConstr optimi= sation, but found that it does not affect these particular examples (perhap= s it only becomes important with larger datatypes). I have also experimente= d with phase control in the rewrite rules and the inline pragmas, but didn't find it necessary for this exampl= e. In general, anyway, my experience with the inliner is that it is extreme= ly fragile, especially across different GHC versions, and it's hard to get = any guarantees of optimisation. I have also played with the -funfolding-* options before, with mixed resul= ts. [1] It's also a pity that certain flags are not explained in detail in = the user's manual [2,3], like -fliberate-case, and -fspec-constr-count and = threshold, for instance.

Thank you for reading this. Any insights are welcome. In particular, I'm wo= ndering if I might be missing some details regarding strictness.


Cheers,
Pedro

[1] http://dreixel.net= /research/pdf/ogie.pdf
[2] http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html=
[3] http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise.ht= ml#options-f
--_000_CAZFbn8fq5WnJiLU9S2zYomRu5ji8dKLtdD1Xev97Y34ydQmailgmai_--