Opened 9 years ago

Closed 9 years ago

#4874 closed bug (fixed)

Unnecessary reboxing when using INLINABLE

Reported by: tibbe Owned by: igloo
Priority: normal Milestone: 7.2.1
Component: Compiler Version: 7.0.1
Keywords: Cc: johan.tibell@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The intent of the attached library and test harness is to use INLINABLE to generate a specialized lookup function at always passes the key as an unboxed Int#. However, when compiled with

ghc -O2 -fregs-graph -ddump-simpl Test.hs

we can see that there's reboxing (look for allocation of an I# constructor) going on. I wonder if this is related to the new INLINABLE specialization. If all INLINABLE in Data.FullList are replaced by INLINE, no reboxing occurs.

Below is a cleaned up version of the Core for the Test module. The reboxing occurs in $wpoly_go1_rIB, in the call to $slookup_$slookupL.

test1 :: Int
test1 = I# 1

$wpoly_go_rIx :: forall v. Int# -> FL.List Int v -> Maybe v
$wpoly_go_rIx =
  \ (@ v)
    (ww_sHY :: Int#)
    (w_sI0 :: FL.List Int v) ->
    case w_sI0 of _ {
      FL.Nil -> Nothing @ v;
      FL.Cons ipv_iGX ipv1_iGY ipv2_iGZ ->
        case ipv_iGX of _ { I# y_iHB ->
        case ==# ww_sHY y_iHB of _ {
          False -> $wpoly_go_rIx @ v ww_sHY ipv2_iGZ;
          True -> Just @ v ipv1_iGY
        }
        }
    }

poly_go_rIz :: forall v. Int -> FL.List Int v -> Maybe v
poly_go_rIz =
  \ (@ v)
    (w_sHW :: Int)
    (w1_sI0 :: FL.List Int v) ->
    case w_sHW of _ { I# ww_sHY ->
    $wpoly_go_rIx @ v ww_sHY w1_sI0
    }

$slookup_$slookupL :: forall v. Int -> FL.List Int v -> Maybe v
$slookup_$slookupL = poly_go_rIz

$wpoly_go1_rIB :: forall v. Int# -> Int# -> M.HashMap Int v -> Maybe v
$wpoly_go1_rIB =
  \ (@ v)
    (ww_sI7 :: Int#)
    (ww1_sIb :: Int#)
    (w_sId :: M.HashMap Int v) ->
    case w_sId of _ {
      M.Nil -> Nothing @ v;
      M.Tip rb_iFO rb1_iFP rb2_iFW rb3_iFX ->
        case ==# ww_sI7 rb_iFO of _ {
          False -> Nothing @ v;
          True ->
            case rb1_iFP of _ { I# y_iHB ->
            case ==# ww1_sIb y_iHB of _ {
              False -> $slookup_$slookupL @ v (I# ww1_sIb) rb3_iFX;
              True -> Just @ v rb2_iFW
            }
            }
        };
      M.Bin _ rb1_iGj l_iGk r_iGl ->
        case eqWord#
               (and#
                  (int2Word# ww_sI7) (int2Word# rb1_iGj))
               __word 0
        of _ {
          False -> $wpoly_go1_rIB @ v ww_sI7 ww1_sIb r_iGl;
          True -> $wpoly_go1_rIB @ v ww_sI7 ww1_sIb l_iGk
        }
    }

poly_go1_rID :: forall v. M.Hash -> Int -> M.HashMap Int v -> Maybe v
poly_go1_rID =
  \ (@ v)
    (w_sI5 :: M.Hash)
    (w1_sI9 :: Int)
    (w2_sId :: M.HashMap Int v) ->
    case w_sI5 of _ { I# ww_sI7 ->
    case w1_sI9 of _ { I# ww1_sIb ->
    $wpoly_go1_rIB @ v ww_sI7 ww1_sIb w2_sId
    }
    }

$slookup :: forall v. Int -> M.HashMap Int v -> Maybe v
$slookup =
  \ (@ v)
    (k0_iFA :: Int)
    (t_iFB :: M.HashMap Int v) ->
    poly_go1_rID @ v k0_iFA k0_iFA t_iFB

test :: M.HashMap Int Int -> Maybe Int
test =
  \ (m_aBp :: M.HashMap Int Int) ->
    $slookup @ Int test1 m_aBp


------ Local rules for imported ids --------
"SPEC FL.lookupL [Int]" [ALWAYS]
    forall {@ v_iGO $dEq_sHl :: Eq Int}
      FL.lookupL @ Int @ v_iGO $dEq_sHl
      = $slookup_$slookupL @ v_iGO
"SPEC M.lookup [Int]" [ALWAYS]
    forall {@ v_iFx
            $dEq_sHm :: Eq Int
            $dHashable_sHn :: Data.Hashable.Hashable Int}
      M.lookup @ Int @ v_iFx $dEq_sHm $dHashable_sHn
      = $slookup @ v_iFx

Attachments (5)

Test.hs (123 bytes) - added by tibbe 9 years ago.
FullList.hs (643 bytes) - added by tibbe 9 years ago.
HashMap.hs (1019 bytes) - added by tibbe 9 years ago.
location.tar.gz (1.5 KB) - added by tibbe 9 years ago.
Second test case
Test.hcr (52.1 KB) - added by tibbe 9 years ago.
Core for second test case

Download all attachments as: .zip

Change History (13)

Changed 9 years ago by tibbe

Attachment: Test.hs added

Changed 9 years ago by tibbe

Attachment: FullList.hs added

Changed 9 years ago by tibbe

Attachment: HashMap.hs added

comment:1 Changed 9 years ago by tibbe

To compile, place HashMap.hs and FullList.hs in a newly created Data directory.

comment:2 Changed 9 years ago by igloo

Milestone: 7.0.3

comment:3 Changed 9 years ago by simonmar

Owner: set to simonpj

comment:4 Changed 9 years ago by tibbe

Cc: johan.tibell@… added

Background: While trying to give an efficient implementation of #4887, I've run into what could be the same issue.

This is an entirely new test case, so it might shine more light on the problem. To reproduce (using GHC 7.0.1):

tar zxf location.tar.gz
cd repro
ghc -O2 Test.hs -ddump-simpl

The interesting part is the series of calls to call site specialized functions, starting at Test.test. In the attached Core, note how $wpoly_go_r1FO returns an unboxed tuple, which is scrutinized by Test.$ssearch. Test.$ssearch then converts the unboxed tuple to a boxed tuple and returns it to Test.test, where it's scrutinized again. I would expect Test.$ssearch to be inlined into Test.test (it's body is trivial) and there to be now allocation of (boxed) tuples.

Here's the relevant part of the Core:

Test.$ssearch :: forall a. Int -> M.Map Int a -> (Maybe a, M.Location Int a)
Test.$ssearch =
  \ (@ a)
    (k0 :: Int)
    (m :: M.Map Int a) ->
    case k0 of _ { I# k0# ->
    case $wpoly_go_r1FO @ a k0# (M.Root @ Int @ a) m
    of _ { (# ww2_s1Fy, ww3_s1Fz #) ->
    (ww2_s1Fy, ww3_s1Fz)
    }
    }

Test.test :: M.Map Int Int -> M.Map Int Int
Test.test =
  \ (m :: M.Map Int Int) ->
    case Test.$ssearch @ Int Test.test2 m
    of _ { (ds_d1DR, l) ->
    case ds_d1DR of _ {
      Nothing ->
        M.assign @ Int @ Int Test.test1 l;
      Just v ->
        case v of _ { I# v# ->
        M.assign
          @ Int
          @ Int
          (I# (+# v# 1))
          l
        }
    }
    }

Changed 9 years ago by tibbe

Attachment: location.tar.gz added

Second test case

Changed 9 years ago by tibbe

Attachment: Test.hcr added

Core for second test case

comment:5 Changed 9 years ago by simonpj

I've had a quick look at your new example. What's happening is that

  • $ssearch is marked INLINEABLE, so we capture its RHS (which is big).
  • Because this big thing is the inlining of $ssearch, it isn't inlined (too big)

This happens because a variable (at the moment) only has one inlining.

You marked search as INLINEABLE because you wanted to be able to specialise it. But having specialised it, you really want the resulting thing ($ssearch in this case) to behave as an ordinary function. Curreintly it is "inheriting" the INLINEABLE pragma from its parent search.

Maybe I should just disable that inheritance. I'll try that. But not tonight.

comment:6 Changed 9 years ago by simonpj

Owner: changed from simonpj to igloo

I've fixed this as described above.

Fri Jan 14 16:32:27 GMT 2011  simonpj@microsoft.com
  * Fix Trac #4874: specialisation of INLINABLE things
  
  Johan discovered that when INLINABLE things are specialised
  bad things can happen. This patch implements a hack -- but
  it's a simple hack and it solves the problem.
  
  See Note [Inline specialisations]. 
  
  The hack part is that really INLINABLE should not cause *any* loss
  optimisation, and it does; see Note [Don't w/w INLINABLE things] in
  WorkWrap.

    M ./compiler/specialise/Specialise.lhs -18 +47

(Most of the new lines are comments!)

Ian, if you felt able to turn either of Johan's test cases into a performance test, that'd be great. I don't think it's significant that the test uses mutiple modules; I think they could be combined into one.

Simon

comment:7 Changed 9 years ago by simonpj

PS: for the first test I had to replace import Hashable by

class Hashable a where
  hash :: a -> Int
instance Hashable Int where
  hash x = x

comment:8 Changed 9 years ago by igloo

Resolution: fixed
Status: newclosed

I had a go, but I couldn't get a significant difference in the RTS stats.

Note: See TracTickets for help on using tickets.