Program compiled with 7.4.1 runs many times slower than compiled with 7.2.2

[gchrupala]

The morfette program ( http://hackage.haskell.org/package/morfette), when compiled with 7.4.1 runs extremely slow: approx. 20x times slower than when compiled with 7.2.1.

To reproduce, install morfette using both compilers, and run it on the attached `sample' file.

morfette train sample output --iter-pos=10 --iter-lemma=3

I attach the output of the profiler for both compilers. It would seem the performance bug is related to code from the modules GramLab?.Perceptron.Multiclass and GramLab?.Perceptron.Vector

[simonmar]

Thanks, we'll take a look.

[simonpj]

Simon M is going to identify what the problem is.

[pcapriotti]

The problem seems to have been introduced in the last version of the array library. Here is a minimal test case:

import Control.Monad
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad.ST

type DenseVector i = UArray i Float

main = do
  let lo = (0,0)
      hi = (1000,1000)
      m = test (lo, hi)
  print $ bounds m

test bounds = m
  where m = runSTUArray $ do
              params <- newArray bounds 0
              replicateM_ 10000 $ do
                params' <- {-# SCC "freeze" #-} unsafeFreeze params
                let _ = params' :: DenseVector (Int,Int)
                return ()
              return params

foo :: DenseVector (Int,Int) -> ST s ()
foo _ = return ()

The unsafeFreeze call is significantly slower with array-0.4.0.0 than array-0.3.0.3.

[milan]

Module for array package to test the unsafeFreeze and unsafeThaw rule firings.

[milan]

Hi,

I also came across this bug.

The problem is that with array-0.4.0.0, the RULEs for unsafeFreeze and unsafeThaw do not fire. The problem can be reproduced by copying the attached Test module to either array-0.3.0.3 or array-0.4.0.0 package and adding it to array.cabal. The Test module contains the following method:

test bounds = m
  where m = runSTUArray $ do
              a <- newArray bounds 0

              a' <- unsafeFreeze a
              a'' <- unsafeThaw a'
              let _ = a' :: UArray Int Int
                  _ = a'' `asTypeOf` a

              return a

Here are the results of compilation with GHC-7.4.1:

array-0.3.0.3
Rule fired: Class op newArray
Rule fired: unsafeFreeze/STUArray
Rule fired: unsafeThaw/STUArray
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op rangeSize
Rule fired: Class op rangeSize
Rule fired: unpack-list

array-0.4.0.0
Rule fired: Class op newArray
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: freeze/STUArray
Rule fired: thaw/STUArray
Rule fired: Class op rangeSize
Rule fired: Class op rangeSize
Rule fired: unpack-list

[simonmar]

unsafeFreeze and unsafeThaw need to be imported from Data.Array.Unsafe now, as the deprecation warning states. If you import them from the new location then the RULEs will fire as expected.

The problem boils down to a lack of the feature requested in #4879: deprecating exports, so I've raised the priority of that ticket.

[simonmar]

On second thoughts, we don't understand why the RULE doesn't fire, because the unsafeFreeze proxy in Data.Array.MArray is declared INLINE. Re-opening so we can investigate.

[milan]

I am not a specialist, but considering the code

module Data.Array.MArray
  {-# INLINE unsafeFreeze #-}
  unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
  unsafeFreeze = Data.Array.Base.unsafeFreeze

module Data.Array.Unsafe
  (exports Data.Array.Base.unsafeFreeze)

module Data.Array.Base
  {-# INLINE unsafeFreeze #-}
  unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
  unsafeFreeze = freeze

  {-# RULES
  "unsafeFreeze/STArray"  unsafeFreeze = ArrST.unsafeFreezeSTArray
  "unsafeFreeze/STUArray" unsafeFreeze = unsafeFreezeSTUArray
  #-}  

then when calling Data.Array.Base.unsafeFreeze, RULES have chance to fire before the INLINing happen. But when calling Data.Array.MArray.unsafeFreeze, RULES do not fire (as they fire only on Data.Array.Base.unsafeFreeze) and then both INLINing happen at once, replacing the Data.Array.MArray.unsafeFreeze by Data.Array.Base.freeze.

When the Data.Array.Base module postpones the INLINing of unsafeFreeze to phase 1, as in

module Data.Array.Base
  {-# INLINE[1] unsafeFreeze #-}
  unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
  unsafeFreeze = freeze

everything works as expected.

I am not a RULES expert, so I do not know, what the right behaviour is. In a situation like this:

{-# INLINE f #-}
f = g

{-# INLINE g #-}
g = h
{-# RULES "g/gspec" g = gspec #-}

is f expected to be rewrittenn to h or gspec? In our array situation, GHC follows the f -> g -> h path.

[simonpj]

Aha! It is very very very fragile to expect a RULE to fire if there is a directly ocmpeting INLINE.

{-# RULE "blah"  f (g x) = ... #-}
{-# INLINE f #-}

The INLINE can, and for reliability must, be postponed to allow the RULE to fire.

{-# RULE "blah"  f (g x) = ... #-}
{-# INLINE[1] f #-}

So this is the real solution. Ian or Paolo, can you add phases to the INLINE for unsafeFreeze and unsafeThaw?

We should really check that three is no more of this nonsense. GHC should really warn if we have a RULE on a function that does not have delayed inlining.

[simonpj@…]

commit 79062a8a0e9168b7f925c05699c30333563a9303

Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Mon Jul 23 09:17:09 2012 +0100

    Make the desugarer warn about RULES that may not fire
    
    This warning was suggested by Trac #6082, where we had
    a library RULE that failed to fire because its function
    was inlined too soon.

 compiler/deSugar/Desugar.lhs |   23 +++++++++++++++++++++++
 1 files changed, 23 insertions(+), 0 deletions(-)

[simonpj]

Done! Library still needs changing -- and the libraries where this shows up a potential bug. Paolo will do this.

[pcapriotti]

This is now fixed in HEAD.

[pcapriotti]

Merged as 8dcd15240a9c2ba142fcbd31f597b51cf2f560bf.