<div dir="ltr">Hi there,<div><br></div><div>GHC can often do a pretty good job at optimising generics. I wrote a paper that looks at that in detail:</div><div><br></div><div>José Pedro Magalhães. Optimisation of Generic Programs through Inlining. In 24th Symposium on Implementation and Application of Functional Languages (IFL'12), 2013.<br></div><div><a href="http://dreixel.net/research/pdf/ogpi.pdf">http://dreixel.net/research/pdf/ogpi.pdf</a><br></div><div><br></div><div><br></div><div>Cheers,</div><div>Pedro</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Aug 22, 2015 at 11:26 PM, Ömer Sinan Ağacan <span dir="ltr"><<a href="mailto:omeragacan@gmail.com" target="_blank">omeragacan@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
I'm very confused by an optimization GHC is doing. I have this code:<br>
<br>
<br>
    data Tree a = Leaf a | Branch (Tree a) (Tree a)<br>
      deriving (Generic, Show, NFData)<br>
<br>
    data Tree1 a = Leaf1 a | Branch1 (Tree1 a) (Tree1 a)<br>
      deriving (Show)<br>
<br>
    instance NFData a => NFData (Tree1 a) where<br>
      rnf (Leaf1 a) = rnf a<br>
      rnf (Branch1 t1 t2) = rnf t1 `seq` rnf t2<br>
<br>
<br>
When I benchmarked rnf calls I realized that they're too close, and I looked at<br>
simplifier outputs. I believe these are relevant parts:<br>
<br>
    Rec {<br>
    Main.$fNFDataTree_$crnf [Occ=LoopBreaker]<br>
      :: forall a_ab5v. NFData a_ab5v => Tree a_ab5v -> ()<br>
    Main.$fNFDataTree_$crnf =<br>
      \ (@ a17_ab5v)<br>
        ($dNFData_ab5w :: NFData a17_ab5v)<br>
        (eta_B1 :: Tree a17_ab5v) -><br>
        case eta_B1 of _ [Occ=Dead] {<br>
          Leaf g1_aaHO -><br>
            ($dNFData_ab5w<br>
             `cast` (Control.DeepSeq.NTCo:NFData[0] <a17_ab5v>_N<br>
                     :: NFData a17_ab5v ~R# (a17_ab5v -> ())))<br>
              g1_aaHO;<br>
          Branch g1_aaHP g2_aaHQ -><br>
            case Main.$fNFDataTree_$crnf @ a17_ab5v $dNFData_ab5w g1_aaHP<br>
            of _ [Occ=Dead] { () -><br>
            Main.$fNFDataTree_$crnf @ a17_ab5v $dNFData_ab5w g2_aaHQ<br>
            }<br>
        }<br>
    end Rec }<br>
<br>
    Rec {<br>
    Main.$fNFDataTree1_$crnf [Occ=LoopBreaker]<br>
      :: forall a_abd4. NFData a_abd4 => Tree1 a_abd4 -> ()<br>
    Main.$fNFDataTree1_$crnf =<br>
      \ (@ a17_abd4)<br>
        ($dNFData_abd5 :: NFData a17_abd4)<br>
        (eta_B1 :: Tree1 a17_abd4) -><br>
        case eta_B1 of _ [Occ=Dead] {<br>
          Leaf1 a18_a4tg -><br>
            ($dNFData_abd5<br>
             `cast` (Control.DeepSeq.NTCo:NFData[0] <a17_abd4>_N<br>
                     :: NFData a17_abd4 ~R# (a17_abd4 -> ())))<br>
              a18_a4tg;<br>
          Branch1 t1_a4th t2_a4ti -><br>
            case Main.$fNFDataTree1_$crnf @ a17_abd4 $dNFData_abd5 t1_a4th<br>
            of _ [Occ=Dead] { () -><br>
            Main.$fNFDataTree1_$crnf @ a17_abd4 $dNFData_abd5 t2_a4ti<br>
            }<br>
        }<br>
    end Rec }<br>
<br>
First one is generated by GHC and second one is hand-written. If you compare,<br>
you'll see that they're identical. This looks like some serious magic, because<br>
first one is generated from a default method that uses Generic methods and<br>
types. Does anyone know how is that possible? Which optimization passes are<br>
involved in this?<br>
<br>
Thanks.<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div><br></div>