Costly let binding gets duplicated in IO action value
The following code is much slower when optimized.
module Main where
import Control.Monad
import Data.Char
import System.IO
-- getInt: read a integer from stdin, skipping spaces
{-# NOINLINE getInt #-} -- to simplify generated core
getInt :: IO Int
getInt = skipSpaces >> go 0
where skipSpaces = do next <- hLookAhead stdin
if isSpace next
then getChar >> skipSpaces
else return ()
go n = do next <- hLookAhead stdin
if isNumber next
then getChar >> go (10 * n + digitToInt next)
else return n
{-# NOINLINE generateSlowList #-}
generateSlowList :: Int -> [Int]
generateSlowList 0 = [1]
generateSlowList n = scanl (+) 1 (generateSlowList (n-1))
main = do
n <- getInt
let ls = generateSlowList n --- !!!
replicateM_ n $ do
i <- getInt
print (ls !! i)
How to run:
(echo 10000; yes 5000) | time ./slow > /dev/null
After a rough look through the generated core, it seems that the ls
was moved into the argument to replicateM_
, which is a lambda taking a State# RealWorld
. It means that a list is rebuilt every time it's indexed, even though a let binding could have caused sharing. By the way it seems that -fno-state-hack
, which seems related, doesn't seem to help.
Interesting to note that using a bang pattern (let !ls = ...
) would make the problem go away.
Trac metadata
Trac field | Value |
---|---|
Version | 7.10.2 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |