#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