[GHC] #1094: loop optimization by removing constants

[GHC]

#1094: loop optimization by removing constants
--------------------------------+-------------------------------------------
    Reporter:  Azmo             |       Owner:                             
        Type:  feature request  |      Status:  new                        
    Priority:  normal           |   Milestone:  6.8                        
   Component:  Compiler         |     Version:  6.6                        
    Severity:  normal           |    Keywords:  loop constants optimization
  Difficulty:  Unknown          |    Testcase:                             
Architecture:  Multiple         |          Os:  Multiple                   
--------------------------------+-------------------------------------------
the current version of Data.List.foldl' is:

 {{{
 foldl'           :: (a -> b -> a) -> a -> [b] -> a
 foldl' f a []     = a
 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
 }}}

 which for some reason is faster if removing the first parameter, e.g:

 {{{
 foldl2'           :: (a -> b -> a) -> a -> [b] -> a
 foldl2' f = loop
   where loop a []     = a
         loop a (x:xs) = let a' = f a x in a' `seq` loop a' xs

 }}}

 ----

 Testing speed difference:

 {{{

 module Main (main) where

 import System (getArgs)

 sumFoldl' :: Int -> Int
 sumFoldl' n = foldl' (+) 0 [1..n]

 sumFoldl2' :: Int -> Int
 sumFoldl2' n = foldl2' (+) 0 [1..n]

 -- copy of Data.List.foldl'
 foldl'           :: (a -> b -> a) -> a -> [b] -> a
 foldl' f a []     = a
 foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

 -- altered version of foldl'
 foldl2'           :: (a -> b -> a) -> a -> [b] -> a
 foldl2' f = loop
   where loop a []     = a
         loop a (x:xs) = let a' = f a x in a' `seq` loop a' xs

 main = do
   [v,n] <- getArgs
   case v of
     "1" -> print (sumFoldl' (read n))
     "2" -> print (sumFoldl2' (read n))

 }}}

 ----

 I have no idea how the optimization of loops is done, but the request is
 that this kind of loop rewriting should be done by the compiler, not by
 the user (to get a faster loop).
 It seems to just be a matter of finding and removing constants
 (identifiers just passed along).

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