Opened 4 years ago

Last modified 3 years ago

#11271 new bug

Costly let binding gets duplicated in IO action value

Reported by: dramforever Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.2
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


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.

Change History (2)

comment:1 Changed 4 years ago by nomeata

With 7.8, this is reproducable, but there, -fno-state-hack _does_ amend the problem.

I think the reason is that since 7.10, interface files leak information about one-shot lambdas. This is intentional, but it means that the effect of -fstate-hack is less local. In particular, in this case, we have this in the interface of System.IO:

  print :: Show a => a -> IO ()
  {- Arity: 3, Strictness: <L,1*U(A,1*C1(U),A)><L,U><L,U>,
     Unfolding: InlineRule (0, True, True)
                (forall a. <Show a>_R ->_R <a>_R ->_R Sym (NTCo:IO[0] <()>_R)) -}
  print1 ::
    Show a => a -> State# RealWorld -> (# State# RealWorld, () #)
  {- Arity: 3, Strictness: <L,1*U(A,1*C1(U),A)><L,U><L,U>,
     Unfolding: InlineRule (3, True, False)
                (\ @ a $dShow :: Show a x :: a eta :: State# RealWorld[OneShot] ->
                 hPutStr2 stdout (show @ a $dShow x) True eta) -}

where the real-world argument is marked as OneShot. Without digging deeper, I could imagine that this flag will make GHC believe that the whole argument to replicateM_ is one shot and hence inline ls into it.

The ideas in #9388 should amend this problem, but I was stalled there by performance regressions. But maybe we should just take the plunge, get rid of the state hack in its current form, get a more correct compiler, live with the performance regressions due to that and try to make up for it in other ways. Not sure though.

comment:2 Changed 3 years ago by simonpj

See #1168 which is the master ticket for this problem

Note: See TracTickets for help on using tickets.