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

[Ömer Sinan Ağacan]

Awesome, thanks for the pointer, Pedro.

2015-08-22 19:01 GMT-04:00 José Pedro Magalhães <dreixel at gmail.com>:
> Hi there,
>
> GHC can often do a pretty good job at optimising generics. I wrote a paper
> that looks at that in detail:
>
> José Pedro Magalhães. Optimisation of Generic Programs through Inlining. In
> 24th Symposium on Implementation and Application of Functional Languages
> (IFL'12), 2013.
> http://dreixel.net/research/pdf/ogpi.pdf
>
>
> Cheers,
> Pedro
>
> On Sat, Aug 22, 2015 at 11:26 PM, Ömer Sinan Ağacan <omeragacan at gmail.com>
> wrote:
>>
>> 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] <a17_ab5v>_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] <a17_abd4>_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.
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
>