[vector] #32: Performance of concatMap and O2/Odph

[vector]

#32: Performance of concatMap and O2/Odph
---------------------+------------------------------------------------------
Reporter:  choener   |        Owner:        
    Type:  defect    |       Status:  closed
Priority:  critical  |    Milestone:  0.7.1 
 Version:  0.6       |   Resolution:  fixed 
Keywords:            |  
---------------------+------------------------------------------------------
Changes (by rl):

  * status:  new => closed
  * resolution:  => fixed

Comment:

 Doh, I'm such an idiot. GHC transforms `good` to:

 {{{
 good :: Int -> Int -> VU.Vector (Int,Int)
 good i j
   | 23 <= j-i-13 =
     VU.map (\(k,l) -> (k-l,l)) $
     VU.concatMap (
       \d -> VU.map (\d' -> (d,d'))
             $ VU.enumFromN 3 (d-5))
     $ VU.enumFromN 8 23

   | otherwise =
     VU.map (\(k,l) -> (k-l,l)) $
     VU.concatMap (
       \d -> VU.map (\d' -> (d,d'))
             $ VU.enumFromN 3 (d-5))
     $ VU.enumFromN 8 (j-i-13)
 }}}

 Now, the first alternative doesn't depend on `i` and `j` at all and is
 floated out:

 {{{
 vec :: VU.Vector (Int,Int)
 vec = VU.map (\(k,l) -> (k-l,l)) $
       VU.concatMap (
         \d -> VU.map (\d' -> (d,d'))
               $ VU.enumFromN 3 (d-5))
       $ VU.enumFromN 8 23


 good :: Int -> Int -> VU.Vector (Int,Int)
 good i j
   | 23 <= j-i-13 = vec
   | otherwise = ...
 }}}

 Of course, `j-i-13` is indeed greater than 23 in the example so it's the
 first alternative that get executed. When Criterion runs this multiple
 times, the actual computation only happens once. In all subsequent runs,
 `good` is basically a noop which, of course, explains why it appears to be
 fast.

 FWIW, the implementation of `concatMap` has changed in vector 0.7. The
 result is that `bad` runs twice as fast as with 0.6 and `good` now has the
 same performance as `bad`. I presume this is because GHC fails to float
 out the computation.

 I'm going to close this. It was a good example, helped find quite a few
 bugs in !SpecConstr.

-- 
Ticket URL: <http://trac.haskell.org/vector/ticket/32#comment:13>
vector <http://trac.haskell.org/vector>
Package vector