Opened 9 years ago

Closed 9 years ago

Last modified 11 months ago

#4306 closed bug (fixed)

UNPACK can lead to unnecessary copying and wasted stack space

Reported by: Olathe Owned by:
Priority: normal Milestone:
Component: Compiler Version: 6.12.3
Keywords: Cc: Olathe
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case: simplCore/should_compile/T4306
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

You can write a pattern-matched function to take only certain components of a data type. If you pattern match on an UNPACKed component and GHC decomposes your function into several simpler functions, those functions will pass every UNPACKed component, used or not, between the simpler functions.

This wastes time copying the unneeded UNPACKed components to the stack and obviously wastes stack space.


For example, the function upd below

data D = D {-# UNPACK #-} !Double {-# UNPACK #-} !Double
data UPD = UPD {-# UNPACK #-} !Double D

upd (UPD _ (D x _)) = sqrt $! (x*x + x*x)

takes only one component of the nested data structure. However, it will be decomposed into Test.upd and Test.$wupd

Test.upd :: Test.UPD -> GHC.Types.Double
GblId
[Arity 1
 Worker Test.$wupd
 NoCafRefs
 Str: DmdType U(AU(LA))m]
Test.upd =
  __inline_me (\ (w_spS :: Test.UPD) ->
                 case w_spS of _ { Test.UPD ww_spU ww1_spV ->
                 case ww1_spV of _ { Test.D ww3_spX ww4_spY ->
                 case Test.$wupd ww_spU ww3_spX ww4_spY of ww5_sq3 { __DEFAULT ->
                 GHC.Types.D# ww5_sq3
                 }
                 }
                 })

Test.$wupd :: GHC.Prim.Double#
              -> GHC.Prim.Double#
              -> GHC.Prim.Double#
              -> GHC.Prim.Double#
GblId
[Arity 3
 NoCafRefs
 Str: DmdType ALA]
Test.$wupd =
  \ _ (ww1_spX :: GHC.Prim.Double#) _ ->
  ...

wherein Test.upd takes the structure and passes all of the UNPACKed components to Test.$wupd, giving it Arity 3, and which immediately drops all the unneeded components via underscores.


The correct behavior can be seen when you don't use UNPACK at all, as with ppb here

data B = B                !Double                !Double
data PPB = PPB                !Double B

ppb (PPB _ (B x _)) = sqrt $! (x*x + x*x)

for which GHC produces a nested function, Test.$wppb, which has Arity 1, as it should.

Test.$wppb :: GHC.Prim.Double# -> GHC.Prim.Double#
GblId
[Arity 1
 NoCafRefs
 Str: DmdType L]
Test.$wppb =
  \ (ww_sr1 :: GHC.Prim.Double#) ->

Attachments (2)

Test.hs (785 bytes) - added by Olathe 9 years ago.
Source file with various UNPACKed combinations.
Test.core (10.4 KB) - added by Olathe 9 years ago.
-ddump-simpl output from that file (compiled with -O2).

Download all attachments as: .zip

Change History (5)

Changed 9 years ago by Olathe

Attachment: Test.hs added

Source file with various UNPACKed combinations.

Changed 9 years ago by Olathe

Attachment: Test.core added

-ddump-simpl output from that file (compiled with -O2).

comment:1 Changed 9 years ago by Olathe

Cc: Olathe added

I don't know much about compilers, so feel free to disregard this completely. I thought of a nice, probably simple, optimization pass.

With each unused argument (the argument can be replaced with an underscore) in an unexported function (it is only visible in the current .hs file),

  • Find out whether it is easy to remove those arguments from each call.
    • If partial application ever stops short of the argument, it's too hard. For example, if the shortest partial application of an arity-26 function is of the form f a b c, the first 3 are considered easy and the last 23 are hard.
  • If it is easy, delete the argument from each call site, and delete the argument from the function definition.

Such an optimization pass would solve this bug (since it is very easy in this case) and optimize other code for free.

comment:2 Changed 9 years ago by simonpj

Resolution: fixed
Status: newclosed
Test Case: simplCore/should_compile/T4306

Although this isn't a release-critical bug I couldn't resist fixing it

Tue Sep 14 12:38:27 BST 2010  simonpj@microsoft.com
  * Make absent-arg wrappers work for unlifted types (fix Trac #4306)
  
  Previously we were simply passing arguments of unlifted
  type to a wrapper, even if they were absent, which was
  stupid.
  
  See Note [Absent error Id] in WwLib.

    M ./compiler/coreSyn/CoreUtils.lhs -1 +5
    M ./compiler/stranal/WwLib.lhs -9 +21

It was just an un-implemented corner of the worker/wrapper construction machinery.

Thanks for pointing it out.

Simon

comment:3 Changed 11 months ago by Krzysztof Gogolewski <krz.gogolewski@…>

In 448b77b9/ghc:

Add RubbishLit for absent bindings of UnliftedRep

Summary:
Trac #9279 reminded us that the worker wrapper transformation copes
really badly with absent unlifted boxed bindings.

As `Note [Absent errors]` in WwLib.hs points out, we can't just use
`absentError` for unlifted bindings because there is no bottom to hide
the error in.
So instead, we synthesise a new `RubbishLit` of type
`forall (a :: TYPE 'UnliftedRep). a`, which code-gen may subsitute for
any boxed value. We choose `()`, so that there is a good chance that
the program crashes instead instead of leading to corrupt data, should
absence analysis have been too optimistic (#11126).

Reviewers: simonpj, hvr, goldfire, bgamari, simonmar

Reviewed By: simonpj

Subscribers: osa1, rwbarton, carter

GHC Trac Issues: #15627, #9279, #4306, #11126

Differential Revision: https://phabricator.haskell.org/D5153
Note: See TracTickets for help on using tickets.