Re: [GHC] #10711: Defining mapM_ in terms of traverse_ causes substantial blow-up in ByteCodeAsm

30 Jul 2015

      #10711: Defining mapM_ in terms of traverse_ causes substantial blow-up in
ByteCodeAsm
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                   Owner:  bgamari
            Type:  bug               |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler          |                 Version:
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |               Test Case:  ghcirun004
      Blocked By:                    |                Blocking:
 Related Tickets:                    |  Differential Revisions:
-------------------------------------+-------------------------------------

Comment (by bgamari):

 [https://gist.github.com/bgamari/9623997162a3399859a9 Here] is a minimal
 testcase demonstrating the difference.

 The efficient definition of `mapM_` (using `(>>)`) produces this Core,
 {{{#!hs
 mapA_3 :: Assembler ()
 mapA_3 = Main.Pure ()

 doTestM_go :: [Assembler Integer] -> Assembler ()
 doTestM_go =
   \ ds_a1XT ->
     case ds_a1XT of _ {
       [] -> mapA_3;
       : y_a1XY ys_a1XZ ->
         let {
           k_a1VW
           k_a1VW = doTestM_go ys_a1XZ } in
         $c>>= y_a1XY (\ _ -> k_a1VW)
     }

 doTestM :: Assembler ()
 doTestM = doTestM_go test
 }}}

 Whereas the slower `Applicative`-based definition produces,

 {{{#!hs
 mapA_3 :: Assembler ()
 mapA_3 = Main.Pure ()

 mapA_2 :: Assembler (() -> ())
 mapA_2 = Main.Pure id

 lvl4_r3JE :: Integer -> Assembler (() -> ())
 lvl4_r3JE = \ _ -> Main.mapA_2

 doTestA_go :: [Assembler Integer] -> Assembler ()
 doTestA_go =
   \ ds_a1XT ->
     case ds_a1XT of _ {
       [] -> mapA_3;
       : y_a1XY ys_a1XZ ->
         let {
           m2_a1W7
           m2_a1W7 = doTestA_go ys_a1XZ } in
         $c>>=
           ($c>>= y_a1XY lvl4_r3JE)
           (\ x1_a1W8 -> $c>>= m2_a1W7 (\ x2_a1W9 -> Pure (x1_a1W8
 x2_a1W9)))
     }

 doTestA :: Assembler ()
 doTestA = doTestA_go test
 }}}

 Note the three `(>>=)` uses in the applicative version, compared to the
 single invocation in the monadic version.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10711#comment:1
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler