[GHC] #7977: Optimization: Shift dropped list heads by coeffecient to prevent thunk generation

[GHC]

#7977: Optimization: Shift dropped list heads by coeffecient to prevent thunk
generation
-----------------------------+----------------------------------------------
Reporter:  schyler           |          Owner:                  
    Type:  feature request   |         Status:  new             
Priority:  normal            |      Component:  Compiler        
 Version:  7.4.2             |       Keywords:                  
      Os:  Unknown/Multiple  |   Architecture:  Unknown/Multiple
 Failure:  None/Unknown      |      Blockedby:                  
Blocking:                    |        Related:                  
-----------------------------+----------------------------------------------
 Consider the following snippet(s) equivalent to ([a..b] !! n), the source
 of (!!) and the source of drop:

 {{{
 normal_list :: Int -> Int
 normal_list n = head $ drop n [a..b]

 shifted_list :: Int -> Int
 shifted_list n = head $ drop (n-n) [(a+n)..b]
 }}}

 {{{
 xs     !! n | n < 0 = undefined
 []     !! _         = undefined
 (x:_)  !! 0         = x
 (_:xs) !! n         = xs !! (n-1)
 }}}

 {{{
 drop n xs     | n <= 0 =  xs
 drop _ []              =  []
 drop n (_:xs)          =  drop (n-1) xs
 }}}

 Notice the (_:xs) matching in these functions as a result of WHNF.

 In the first case, normal_list, thunks are generated for x in ({-x-}_:xs)
 of the target list and overhead is seen in the pattern matching/guard of n
 in drop.

 In the second case, shifted_list, this overhead can be completely removed
 by adding a coefficient such that the list starts at the programmatically
 defined lower bound, a, plus the known fact that the head is dropped n
 times.

 Hence, given the example above, consider:

 {{{
 [x * x + 3 | x <- [1..]] !! n
 -- versus
 [x * x + 3 | x <- [(1+n)..]] !! (n-n)
 -- which is optimized into
 [x * x + 3 | x <- [(n+1)..]] !! 0
 -- which is effectively
 head [x * x + 3 | x <- [(n+1)..]]
 }}}

 The operation is turned from O(n) into O(1).

 Consider benchmark proving GHC 7.4.2 does not make this optimization under
 -O2:

 {{{
 import Criterion.Main

 normal_list :: Int -> Int
 normal_list n = head $ drop n [1..]

 shifted_list :: Int -> Int
 shifted_list n = head $ drop (n-n) [(1+n)..]

 main = defaultMain
     [ bench "normal_list 1000" $ whnf normal_list 1000
     , bench "shifted_list 1000" $ whnf shifted_list 1000
     ]
 }}}

 {{{
 C:\Users\Kyle\Desktop>ghc -O2 listco.hs
 [1 of 1] Compiling Main             ( listco.hs, listco.o )
 Linking listco.exe ...

 C:\Users\Kyle\Desktop>listco.exe
 warming up
 estimating clock resolution...
 mean is 4.644044 us (160001 iterations)
 found 319255 outliers among 159999 samples (199.5%)
   159256 (99.5%) low severe
   159999 (100.0%) high severe
 estimating cost of a clock call...
 mean is 310.3118 ns (34 iterations)

 benchmarking normal_list 1000
 Warning: Couldn't open /dev/urandom
 Warning: using system clock for seed instead (quality will be lower)
 mean: 7.352463 us, lb 7.058339 us, ub 7.646574 us, ci 0.950
 std dev: 1.478087 us, lb 1.478066 us, ub 1.478200 us, ci 0.950
 variance introduced by outliers: 94.651%
 variance is severely inflated by outliers

 benchmarking shifted_list 1000
 mean: 46.42819 ns, lb 45.44244 ns, ub 47.21689 ns, ci 0.950
 std dev: 4.495757 ns, lb 4.035428 ns, ub 4.832396 ns, ci 0.950
 variance introduced by outliers: 77.960%
 variance is severely inflated by outliers
 }}}

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