How is this Generic-based instance implementation optimized by GHC?

22 Aug 2015

      Hi all,

I'm very confused by an optimization GHC is doing. I have this code:

    data Tree a = Leaf a | Branch (Tree a) (Tree a)
      deriving (Generic, Show, NFData)

    data Tree1 a = Leaf1 a | Branch1 (Tree1 a) (Tree1 a)
      deriving (Show)

    instance NFData a => NFData (Tree1 a) where
      rnf (Leaf1 a) = rnf a
      rnf (Branch1 t1 t2) = rnf t1 `seq` rnf t2

When I benchmarked rnf calls I realized that they're too close, and I looked at
simplifier outputs. I believe these are relevant parts:

    Rec {
    Main.$fNFDataTree_$crnf [Occ=LoopBreaker]
      :: forall a_ab5v. NFData a_ab5v => Tree a_ab5v -> ()
    Main.$fNFDataTree_$crnf =
      \ (@ a17_ab5v)
        ($dNFData_ab5w :: NFData a17_ab5v)
        (eta_B1 :: Tree a17_ab5v) ->
        case eta_B1 of _ [Occ=Dead] {
          Leaf g1_aaHO ->
            ($dNFData_ab5w
             `cast` (Control.DeepSeq.NTCo:NFData[0] _N
                     :: NFData a17_ab5v ~R# (a17_ab5v -> ())))
              g1_aaHO;
          Branch g1_aaHP g2_aaHQ ->
            case Main.$fNFDataTree_$crnf @ a17_ab5v $dNFData_ab5w g1_aaHP
            of _ [Occ=Dead] { () ->
            Main.$fNFDataTree_$crnf @ a17_ab5v $dNFData_ab5w g2_aaHQ
            }
        }
    end Rec }

    Rec {
    Main.$fNFDataTree1_$crnf [Occ=LoopBreaker]
      :: forall a_abd4. NFData a_abd4 => Tree1 a_abd4 -> ()
    Main.$fNFDataTree1_$crnf =
      \ (@ a17_abd4)
        ($dNFData_abd5 :: NFData a17_abd4)
        (eta_B1 :: Tree1 a17_abd4) ->
        case eta_B1 of _ [Occ=Dead] {
          Leaf1 a18_a4tg ->
            ($dNFData_abd5
             `cast` (Control.DeepSeq.NTCo:NFData[0] _N
                     :: NFData a17_abd4 ~R# (a17_abd4 -> ())))
              a18_a4tg;
          Branch1 t1_a4th t2_a4ti ->
            case Main.$fNFDataTree1_$crnf @ a17_abd4 $dNFData_abd5 t1_a4th
            of _ [Occ=Dead] { () ->
            Main.$fNFDataTree1_$crnf @ a17_abd4 $dNFData_abd5 t2_a4ti
            }
        }
    end Rec }

First one is generated by GHC and second one is hand-written. If you compare,
you'll see that they're identical. This looks like some serious magic, because
first one is generated from a default method that uses Generic methods and
types. Does anyone know how is that possible? Which optimization passes are
involved in this?

Thanks.

Ömer Sinan Ağacan

José Pedro Magalhães

Ömer Sinan Ağacan

tags

participants (2)