Opened 7 years ago

Closed 7 years ago

#5981 closed bug (fixed)

quadratic slowdown with very long module names

Reported by: guest Owned by: simonmar
Priority: normal Milestone: 7.6.1
Component: Compiler Version: 7.4.1
Keywords: Cc: claudiusmaximus@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Posting this for completeness, in case it exposes something more generally suboptimal: I'm not suggesting that such very long module names are likely ever to occur in the real world (and indeed Hugs has a 4k identifier length limit).

In short: parsing "module Module where ..." takes O(length(Module)²) time.

test program (NB: overwrites "./test.hs" without hesitation):

module Main (main) where

import Control.Monad (forM_)
import Data.List (genericReplicate)
import Data.Time.Clock (getCurrentTime, diffUTCTime)
import System.Environment (getArgs)
import System.IO (stdout, hSetBuffering, BufferMode(NoBuffering))
import System.Process (system)

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

test :: Integer -> String
test n = "module M" ++ genericReplicate n 'm' ++ " (main) where main :: IO () ; main = return ()\n"

main :: IO ()
main = do
  [count] <- getArgs
  hSetBuffering stdout NoBuffering
  forM_ (take (read count) fibs) $ \n -> do
    writeFile "test.hs" (test n)
    t0 <- getCurrentTime
    _ <- system "ghci </dev/null >/dev/null test.hs"
    t1 <- getCurrentTime
    putStrLn $ unwords [show n, show (diffUTCTime t1 t0)]

output:

0 0.287553s
1 0.28064s
1 0.294821s
2 0.262876s
3 0.27628s
5 0.27605s
8 0.279612s
13 0.276299s
21 0.267666s
34 0.26738s
55 0.295614s
89 0.270626s
144 0.264852s
233 0.297883s
377 0.295505s
610 0.259852s
987 0.260083s
1597 0.294578s
2584 0.297104s
4181 0.312192s
6765 0.305412s
10946 0.364343s
17711 0.415955s
28657 0.562181s
46368 0.708429s
75025 1.093678s
121393 1.975239s
196418 3.702828s
317811 8.17462s
514229 19.291228s
832040 45.603124s
1346269 116.74497s
2178309 308.660996s

Change History (3)

comment:1 Changed 7 years ago by simonmar

Component: Compiler (Parser)Compiler
difficulty: Unknown
Milestone: 7.6.1
Owner: set to simonmar

I see what's causing this, patch on its way.

comment:2 Changed 7 years ago by marlowsd@…

commit 6f1a4327263385d8056d7cf754ee357d2b14c24b

Author: Simon Marlow <marlowsd@gmail.com>
Date:   Tue Apr 10 16:31:13 2012 +0100

    fix quadratic performance issue with long module names (#5981)

 compiler/main/HeaderInfo.hs |   26 +++++++++++++++-----------
 1 files changed, 15 insertions(+), 11 deletions(-)

comment:3 Changed 7 years ago by simonmar

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.