[GHC] #11677: Dramatic de-optimization with "-O", "-O1", "-O2" options

[GHC]

#11677: Dramatic de-optimization with "-O", "-O1", "-O2" options
-------------------------------------+-------------------------------------
           Reporter:  malphunction   |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  7.10.3
           Keywords:  optimization   |  Operating System:  Linux
  deoptimization                     |
       Architecture:  x86_64         |   Type of failure:  Runtime
  (amd64)                            |  performance bug
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Look for this simple program:
 {{{#!hs:
 import Control.Monad
 import Data.Maybe

 -- import qualified Data.HashMap.Strict as M
 -- import qualified Data.Map.Lazy as M
 import qualified Data.Map.Strict as M

 -- import Control.DeepSeq
 -- import Control.Exception


 main :: IO ()
 main = do
     putStrLn "Start"

     n <- read <$> getLine
     q <- read <$> getLine

     dict' <- M.fromList <$> replicateM n ((\(k:v:_) -> (k,v)) <$> words
 <$> getLine)

     -- dict <- evaluate $ force dict'
     let dict = dict'

     count <- length <$> catMaybes <$> replicateM q (flip M.lookup dict <$>
 getLine)
     print count
 }}}

 When compiled __without__ "-O2" it runs about 0.07 sec on my computer.
 But when compiled __with__ "-O2" it runs about 77 sec (1100 times
 slowly!).

 Look: compile and run without "-O2":

 {{{
 % rm -rf ./mime_type mime_type.{o,hi} && ghc mime_type.hs -o mime_type &&
 cat my_data.txt | time ./mime_type
 [1 of 1] Compiling Main             ( mime_type.hs, mime_type.o )
 Linking mime_type ...
 Start
 4738
 ./mime_type  0,06s user 0,01s system 97% cpu 0,069 total
 }}}

 And with "-O2":

 {{{
 % rm -rf ./mime_type mime_type.{o,hi} && ghc -O2 mime_type.hs -o mime_type
 && cat my_data.txt | time ./mime_type
 [1 of 1] Compiling Main             ( mime_type.hs, mime_type.o )
 Linking mime_type ...
 Start
 4738
 ./mime_type  76,73s user 0,10s system 99% cpu 1:17,12 total
 }}}


 But when force `dict` variable (`dict <- evaluate $ force dict'`), it runs
 fast in both cases (with and without "-O2").

 Also this bug is reproductable with "-O", "-O1" options.

 Also this bug is reproductable with GHC 7.10.2 and GHC 8.0.1-rc2 (The
 Glorious Glasgow Haskell Compilation System, version 8.0.0.20160204).

 Data file my_data.txt is attached. It has simple structure:
 * N, number of key-value pairs
 * K, number of keys for searching
 * N key-value pairs
 * K kes

 You can generate it with this Ruby script:
 {{{
 #!/usr/bin/env ruyb
 lst = ('a'..'z').to_a

 N = 10000
 K = 10000

 File.open('my_data.txt', 'w') do |f|
     f.puts(N)
     f.puts(K)
     N.times do
         f.puts("#{lst.sample(3).join} #{lst.sample(5).join}")
         # f.puts("(\"#{lst.sample(3).join}\",\"#{lst.sample(5).join}\")")
     end
     K.times do
         f.puts("#{lst.sample(3).join}")
     end
 end
 }}}

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