[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
      Resolution:                    |             Keywords:  optimization
                                     |  deoptimization
Operating System:  Linux             |         Architecture:  x86_64
 Type of failure:  Runtime           |  (amd64)
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Description changed by malphunction:

@@ -77,1 +77,1 @@
- #!/usr/bin/env ruyb
+ #!/usr/bin/env ruby

New description:

 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 ruby
 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#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler