Opened 8 years ago

Closed 8 years ago

#5731 closed bug (fixed)

Bad code for Double literals

Reported by: rl Owned by: igloo
Priority: highest Milestone: 7.4.1
Component: Compiler Version: 7.3
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:

Description

Caught by the vector benchmark suite. Small program:

foo :: [Double] -> [Double]
foo = map f
  where
    f x = 1 / x

The current head generates this rather terrible code (with -O2):

foo3 :: GHC.Integer.Type.Integer
foo3 = __integer 1

foo2 :: GHC.Types.Double
foo2 =
  case GHC.Integer.Type.doubleFromInteger foo3
  of wild_afu { __DEFAULT ->
  GHC.Types.D# wild_afu
  }

foo1 :: GHC.Types.Double -> GHC.Types.Double
foo1 =
  \ (eta_B1 :: GHC.Types.Double) ->
    GHC.Float.divideDouble foo2 eta_B1

foo :: [GHC.Types.Double] -> [GHC.Types.Double]
foo = GHC.Base.map @ GHC.Types.Double @ GHC.Types.Double foo1

It does generate perfectly fine code for this, though:

bar :: [Double] -> [Double]
bar = map (\x -> 1/x)

Change History (8)

comment:1 Changed 8 years ago by rl

The culprit seems to be this bit of code in integer-gmp/GHC/Integer/Type.lhs:

-- previous code: doubleFromInteger n = fromInteger n = encodeFloat n 0
-- doesn't work too well, because encodeFloat is defined in
-- terms of ccalls which can never be simplified away.  We
-- want simple literals like (fromInteger 3 :: Float) to turn
-- into (F# 3.0), hence the special case for S# here.

{-# NOINLINE doubleFromInteger #-}
doubleFromInteger :: Integer -> Double#
doubleFromInteger (S# i#) = int2Double# i#
doubleFromInteger (J# s# d#) = encodeDouble# s# d# 0#

Note the NOINLINE pragma which has been added by this patch:

commit 94df30b07c20c0031c1a8cc57ee3479423b963ac
Author:	Ian Lynagh <igloo@earth.li>  Sat Jul 23 17:56:40 2011
Committer:	Ian Lynagh <igloo@earth.li>  Sat Jul 23 17:56:40 2011
Original File:	GHC/Integer.lhs

Don't inline most integer operations

We get lots of code, and the simplifier generally can't do much with
it. We'll instead use builtin rules to do constant folding where
possible.

Unfortunately, it seems that there are no builtin rules for this and similar cases. IMO, we should either revert the patch or add rules for all interesting cases for 7.4.1.

I'm a bit surprised that nofib hasn't caught this, it is a huge performance regression in many situations.

comment:2 Changed 8 years ago by rl

Poking around further, it turns out that inlining doubleFromInteger doesn't help at all here. This is because Integer literals are now represented by LitInteger rather than the S# and J# constructors. The relevant comment in Literal.lhs says:

An Integer literal is represented using, well, an Integer, to make it
easier to write RULEs for them. 

 [...]

 * They only get converted into real Core,
      mkInteger [c1, c2, .., cn]
   during the CorePrep phase.

This means that for literals, we won't see S# until CorePrep when it's too late for anything interesting to happen. So the quickest solution is probably to add built-in rules for all conversion functions in Type.lhs to builtinIntegerRules in PrelRules.lhs. At the moment, there are only rules for integerToWord and integerToInt. It seems a pity to me that these rules can't be implemented in the library, though.

BTW, integer-gmp contains two rules which, I believe, are dead:

{-# RULES "integerToInt" forall i. integerToInt (S# i) = i #-}
{-# RULES "gcdInteger/Int" forall a b.
            gcdInteger (S# a) (S# b) = S# (gcdInt a b)
  #-}

I believe neither of these can ever match because the various NOINLINE pragmas mean that the S# constructor won't be exposed to the simplifier.

comment:3 Changed 8 years ago by simonpj

difficulty: Unknown

You are right that the RULES you mention are redundant; would you like to remove them?

The right fix is to add two more rules (for Float and Double) to builtinIntegerRules in prelude/PrelRules. Follow the pattern for the rules "integerToWord" and "integerToInt". Here's how they work, taking Int as the example:

  • Occurrences of an integer literal start life as (fromInteger 3), where the "3" is an Integer literal. This literal is, as you say, held as a literal right through the compiler to the back end.
  • The Num Int instance in GHC.Num has this definition for fromInteger:
    instance Num Int where
        {-# INLINE fromInteger #-}	 -- Just to be sure!
        fromInteger i = I# (integerToInt i)
    
  • So (fromInteger 3) turns into I# (integerToInt 3). The function integerToInt is defined in package integer-gmp, module GHC.Integer.Type.
  • Now there is a builtin rule in PrelRules, so that integerToInt 3 is rewritten to 3#, a literal of type Int#.

All that is needed is to play the same game for Double and Float, just as is done for Int and Word. Would you feel like doing that?

Two side notes

  • The reason why one program gives good code and the other does not is because the type checker short-circuits the entire fol-de-rol if it see the rigth answer on the spot.
  • I see that GHC.Integer.Type.integerToInt also has a RULE that will never fire, so it too could be removed.

It would be good to transfer this knowledge into a Note [Integer literals] somewhere; but I'm not sure where!

Simon

comment:4 Changed 8 years ago by igloo

Milestone: 7.4.1
Priority: normalhigh

Milestoning as 7.4.1 as this is a regression.

comment:5 Changed 8 years ago by rl

There's also integerToWord64 and integerToInt64. I fear I don't really have a lot of time for this right now so it would be great if someone else could do this.

comment:6 Changed 8 years ago by simonpj

Owner: set to igloo

Ian, perhpas you might handle this? It should be easy enough and you're already familiar with the setup.

Simon

comment:7 Changed 8 years ago by simonpj

Priority: highhighest

comment:8 Changed 8 years ago by igloo

Resolution: fixed
Status: newclosed

HEAD and 7.4 now have rules for all Integer functions except those that don't take Integers as arguments (because we don't have a good way to write those rules yet).

That includes all the functions mentioned in this ticket.

Note: See TracTickets for help on using tickets.