[GHC] #6040: Adding a type signature changes heap allocation into stack allocation without changing the actual type

[GHC]

#6040: Adding a type signature changes heap allocation into stack allocation
without changing the actual type
---------------------------------+------------------------------------------
    Reporter:  tibbe             |       Owner:  simonpj         
        Type:  bug               |      Status:  new             
    Priority:  normal            |   Milestone:  7.8.1           
   Component:  Compiler          |     Version:  7.4.1           
    Keywords:                    |          Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |     Failure:  None/Unknown    
  Difficulty:  Unknown           |    Testcase:                  
   Blockedby:                    |    Blocking:                  
     Related:                    |  
---------------------------------+------------------------------------------

Comment(by milan):

 I was asked by Johan to demonstrate the issue.

 I would like to note that I am not sure it is even a bug -- I understand
 what is going on and I am not sure what a better behaviour would be -- but
 maybe the transformation Simon suggests is a good idea.

 Consider two methods `delete1` and `delete2` which delete all occurences
 of a given key in the list:

 {{{
 module Test ( delete1, delete2 ) where

 delete1 :: Eq k => k -> [k] -> [k]
 delete1 = go
   where go _ [] = []
         go k (x:xs) | k == x = go k xs
                     | otherwise = x : go k xs

 delete2 :: Eq k => k -> [k] -> [k]
 delete2 = go
   where go :: Eq k => k -> [k] -> [k]
         go _ [] = []
         go k (x:xs) | k == x = go k xs
                     | otherwise = x : go k xs
 }}}

 The difference is that in the first case, `go` is a closure which captures
 the `Eq` dictionary of the outer function. In the second case, `go` is
 being given the `Eq` dictionary as a parameter and therefore floats out of
 `delete2`. STG illustrates this nicely:

 {{{
 ==================== STG syntax: ====================
 Test.delete1 =
     \r [$dEq_sql eta_sqs eta1_sqt]
         let {
           go_sqq =
               sat-only \r [ds_sqm ds1_sqh]
                   case ds1_sqh of wild_sqO {
                     [] -> [] [];
                     : x_sqn xs_sqp ->
                         case GHC.Classes.== $dEq_sql ds_sqm x_sqn of
 wild1_sqP {
                           GHC.Types.False ->
                               let { sat_sqN = \u [] go_sqq ds_sqm xs_sqp;
                               } in  : [x_sqn sat_sqN];
                           GHC.Types.True -> go_sqq ds_sqm xs_sqp;
                         };
                   };
         } in  go_sqq eta_sqs eta1_sqt;
 SRT(Test.delete1): []
 Test.delete2_go =
     \r [$dEq_sqB ds_sqC ds1_sqx]
         case ds1_sqx of wild_sqQ {
           [] -> [] [];
           : x_sqD xs_sqF ->
               case GHC.Classes.== $dEq_sqB ds_sqC x_sqD of wild1_sqS {
                 GHC.Types.False ->
                     let { sat_sqR = \u [] Test.delete2_go $dEq_sqB ds_sqC
 xs_sqF;
                     } in  : [x_sqD sat_sqR];
                 GHC.Types.True -> Test.delete2_go $dEq_sqB ds_sqC xs_sqF;
               };
         };
 SRT(Test.delete2_go): []
 Test.delete2 =
     \r [$dEq_sqK eta_sqL eta1_sqM]
         Test.delete2_go $dEq_sqK eta_sqL eta1_sqM;
 SRT(Test.delete2): []
 }}}

 The result is that `delete1` has to heap-allocate the dictionary while
 `delete2` does not.

 {{{
  Test_delete1_info()
          { update_frame: <none>
            label: Test_delete1_info
            rep:HeapRep static { Fun {arity: 3 fun_type: ArgSpec 20} }
          }
      crz:
          Hp = Hp + 8;
          if (Hp > HpLim) goto crC;
          I32[Hp - 4] = sqq_info;
          I32[Hp + 0] = I32[Sp + 0];
          R1 = Hp - 2;
          Sp = Sp + 4;
          jump sqq_info ();
  ...
 }}}

 The performance difference is very minor -- `delete1` needs one more two-
 word heap allocation. The time difference will not probably be measurable.
 I notised this only because I monitor heap allocations in `containers`
 code as they cause ghc perf tests which monitor heap allocation to fail.

 BTW, we use identical `insert` and `go` functions in containers because
 the outer is marked `INLINE` in pre-7.0 GHC.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/6040#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler