Re: [GHC] #9339: last is not a good consumer

21 Jul 2014

      #9339: last is not a good consumer
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |             Owner:
                  Type:  bug         |            Status:  new
              Priority:  normal      |         Milestone:
             Component:              |           Version:  7.8.3
  libraries/base                     |          Keywords:
            Resolution:              |  Operating System:  Unknown/Multiple
Differential Revisions:              |   Type of failure:  Runtime
          Architecture:              |  performance bug
  Unknown/Multiple                   |         Test Case:
            Difficulty:  Unknown     |          Blocking:
            Blocked By:              |
       Related Tickets:              |
-------------------------------------+-------------------------------------

Comment (by nomeata):

 Ok, let’s do this systematically.

 My benchmarks: One possibly fusing invocation of `last`:
 {{{
 main = print $ Last.last $ filter odd $ [1::Int ..100000000]
 }}}
 and one non-fusing
 {{{
 f = id
 {-# NOINLINE f #-}
 main = print $ Last.last $ f $ filter odd $ [1::Int ..100000000]
 }}}

 I am comparing the existing implementation of `last`, which is
 {{{
 last []                 =  errorEmptyList "last"
 last (x:xs)             =  last' x xs
   where last' y []     = y
         last' _ (y:ys) = last' y ys
 }}}
 with the simpler
 {{{
 last = foldl (\_ x -> x) (errorEmptyList "last")
 }}}

 Just for fun (and because GHC HEAD still compiles), here the numbers with
 GHC-7.6:

 {{{
 LastTestFusing.hs
 <>
 LastTestNonFusing.hs
 <>
 NewLastTestFusing.hs
 <>
 NewLastTestNonFusing.hs
 <>
 }}}
 No significant difference in either of these.

 Now the interesting numbers are those with ghc HEAD, and for that I have
 to wait for the compilation to finish...

 So here they are:
 {{{
 LastTestFusing.hs
 <>
 LastTestNonFusing.hs
 <>
 NewLastTestFusing.hs
 <>
 NewLastTestNonFusing.hs
 <>
 }}}

 We see that the new implementation performs the same in the non-fusing
 case, but much better in the fusing case.

 Why does it even allocate in the fusing case? Because it needs to box them
 for the recursive call:
 {{{
 Rec {
 main_go :: Int# -> Int -> Int
 main_go =
   \ (x :: Int#) (eta :: Int) ->
     case remInt# x 2 of _ {
       __DEFAULT ->
         case x of wild {
           __DEFAULT -> main_go (+# wild 1) (I# wild);
           100000000 -> lvl
         };
       0 ->
         case x of wild {
           __DEFAULT -> main_go (+# wild 1) eta;
           100000000 -> eta
         }
     }
 end Rec }
 }}}

 Guess that’s unavoidable here.

 Also, to make sure that some integer unboxing doesn’t skew the comparison,
 here the numbers with `Integer`:

 {{{
 <>
 LastTestNonFusing.hs
 <>
 NewLastTestFusing.hs
 <>
 NewLastTestNonFusing.hs
 <>
 }}}

 This only confirms the previous findings.

 TL;DR: Implementing `last` with `foldl` has no negative consequences, but
 works nicely when fused. I don’t expect that to happen often, but it’s
 still nice to have, and actually simplifies the existing library
 implementation. If noone complains, I’ll push this soon.

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