UNPACK support for sums
Needs RevisionPublic

Authored by osa1 on Jul 22 2016, 11:08 AM.

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Branch
unpack_sums
Lint
Lint SkippedExcuse: later
Unit
No Unit Test Coverage
Build Status
Buildable 11923
Build 15171: [GHC] Linux/amd64: Patch building
Build 15170: arc lint + arc unit
osa1 updated this revision to Diff 8318.Jul 22 2016, 11:08 AM
osa1 retitled this revision from to UNPACK support for sums.
osa1 updated this object.
osa1 edited the test plan for this revision. (Show Details)
osa1 added a reviewer: simonpj.
osa1 planned changes to this revision.Jul 22 2016, 11:09 AM
osa1 updated this revision to Diff 8319.Jul 22 2016, 11:48 AM
osa1 edited edge metadata.
  • fix automatic UNPACK logic. some tests.
bgamari added inline comments.Aug 2 2016, 4:26 AM
compiler/basicTypes/MkId.hs
651

Have you considered being a bit more generous in unboxing here (particularly when -funbox-strict-fields is used)? If you have already considered this it would be nice to have a comment describing why unboxing narrow single-constructor types is desirable while unboxing narrow sums is not. This isn't clear to me at first glance.

osa1 added a comment.Aug 7 2016, 10:05 AM

This breaks tc226, apparently I accidentally relaxed isUnpackableType check a bit too much..

osa1 updated this revision to Diff 8396.Aug 8 2016, 4:01 AM
osa1 edited edge metadata.
This comment was removed by osa1.
osa1 added a comment.Aug 8 2016, 4:03 AM
This comment was removed by osa1.
osa1 updated this revision to Diff 8397.Aug 8 2016, 4:05 AM
osa1 edited edge metadata.
  • fix automatic UNPACK logic. some tests.
  • minor. remove trace calls.
  • fix tc226
osa1 added inline comments.Aug 8 2016, 4:08 AM
compiler/basicTypes/MkId.hs
651

We run some tests months ago and most of the time automatically unpacking sums increased allocations, because of packing them again when passing to functions etc. I think we need worker/wrapper on sums before doing that. I'll document the code.

bgamari requested changes to this revision.Aug 31 2016, 12:35 PM
bgamari edited edge metadata.

Am I correct in assuming that we shouldn't land this until we have worker/wrapper? If so, what is the status of worker/wrapper?

This revision now requires changes to proceed.Aug 31 2016, 12:35 PM
simonpj edited edge metadata.Aug 31 2016, 2:28 PM

Am I correct in assuming that we shouldn't land this until we have worker/wrapper? If so, what is the status of worker/wrapper?

No, it's orthogonal to w/w. It's in my review queue, burt I'd be thrilled if someone else could look at it too.

simonpj requested changes to this revision.Sep 18 2016, 5:12 PM
simonpj edited edge metadata.

Some parts of this are mysterious -- see comments above. Not necessarily worng, but mysterious.

Do you have a test where performance improves? I think you shoudl be able to construct one without difficulty. We need to be certain that it is SOMETIMES good, and give guidance to users about when that is.

You are right that without the ability to pass unboxed sums through to called functions, a lot more reboxing will take place. And the reboxing is notably more expensive because insstead of

let x = (a,b)

which we get for products, we'll have

let x = case x# of
             (# (##) | #) -> Nothing
             (# | x #) -> Just x

which involves both a thunk and a test.

Moreover, if that thunk is later decompsed by a case

...(case x of { Nothing -> e1, Just y -> e2 }...

will we succeed in inlining x and transforming this to a case on x#??

It woudl be good to check this and give a Note to explain.

compiler/basicTypes/MkId.hs
651

Yes, pls do document this decision

817

I'm afraid I don't understand this code at all. An example in a Note would help HUGELY. Admittely the product casse lacks an example; maybe you can fix that at tthe same time?

For example here you seem to be building a case that scrutinises a case. Why? And you seem to bind but a sinngle variable (ubx_sum_bndr) whereas in the product case we bind a variable for each field of the unboxed thing. I'm lost

883

Hmm. What this not-newTyCon stuff? (I know it's like that before this patch.) What about

netype N a = MkN a

data T = MkT {-# UNPACK #-} !(N (Int, Int))

would we not like to unpack this to two Ints? Does that happen now? If so how?

885

Good question, worth a Note.

For non-existentials I think we could unpack fine. E.g.

data T a where
  MkT :: Eq a => a -> a -> T a

data F a where
  MkF :: {-# UNPACK #-} !(T a) -> Int -> F a

I think we could unpack the T argument to three fields of type Eq a, a and a resp.

But types like this are rare. Mostly non-vanilla data cons have existentials. There is no reason in principle not to upnack them too, but doing so would add new existentials to the enclsoing data constructor e.g.

data T where
  MkT :: Eq a => a -> a -> T

data F where
  MkF :: {-# UNPACK #-} !T -> F

We could unpack the T but then MkF woudl get an existential type variable. Nothing wrong with that,, but I think the present code would take a bit of adjusting to allow it.

Could you put this comment into a Note in the code to explain, please?

compiler/coreSyn/MkCore.hs
360

Perhpas give an example to illustrate?

simonpj added inline comments.Sep 18 2016, 5:18 PM
compiler/basicTypes/MkId.hs
817

Oh I think I get it a bit more now. For

data T = MkT {-# UNPACK #-} !(Maybe Int)

we will generate

MkT :: Maybe Int -> T
MkT x = case x of
                  Nothing -> MkT {# (# #) | #)
                  Just y -> MkT (# | y #)

That is, the sum type gets replaced by a single field with an unboxed sum type.

See how helpful the example is!

But it rasies the question: why not do the same thing for products, and generate a single field that is an unboxed tuple?

885

Ah. A good reason for NOT doing this stuff wtih existentials is that it won't work for sums. If each constructor of the sum binds a different collection of existentials we are stuck.

Let's note this too

osa1 added inline comments.Sep 25 2016, 10:14 PM
compiler/basicTypes/MkId.hs
817

But it rasies the question: why not do the same thing for products, and generate a single field that is an unboxed tuple?

Because it doesn't matter in products. In sums we have to do this otherwise code size explodes.

(btw, your example is slightly wrong I think)

Example. If we have this product:

data T = T X Y

and unpack it twice

data U = U {-# UNPACK #-} !T
           {-# UNPACK #-} !T

we generate this "unpacker"

case t1 of
    T x1 y1 ->
        case t2 of
          T x2 y2 -> U x1 y1 x2 y2

Now, suppose T was a sum:

data T = T1 X | T2 Y

If we generate the same unpacker expression, we get this

case t1 of
    T1 x1 ->
        case t2 of
           T1 x2 -> U 1# x1 1# x2
           T2 y2 -> U 1# x1 2# y2
    T2 y1 ->
        case t2 of
            T1 x2 -> Y 2# y1 1# x2
            T2 y2 -> Y 2# y1 2# y2

You can see how this tree grows as number of unpacked and alternatives increase. Currently we do this instead

case
  (case t1 of
     T1 x1 -> (# x1 | #)
     T2 y1 -> (# | y1 #)) of
  ubx1 ->
    case
      (case t2 of
          T1 x2 -> (# x2 | #)
          T2 y2 -> (# | y2 #)) of
        ubx2 -> U x1 x2

Which avoids this exponential growth in code size by not duplicating unpackers in alternatives.

I'll improve the documentation and add some notes.

osa1 added a comment.Sep 25 2016, 10:26 PM

Do you have a test where performance improves? I think you shoudl be able to construct one without difficulty. We need to be certain that it is SOMETIMES good, and give guidance to users about when that is.

I'm afraid we don't have such a case. Two semesters ago I tried _really hard_ to produce such a program, but I failed. I think the problem is that pointer taggins is really good, and wasting a whole word to avoid a pointer is not any better than using just one word (which sometimes doesn't need to be dereferenced becuase of pointer tagging).

(I'm going to start a new unboxed sums discussion to discuss this further)

osa1 updated this revision to Diff 9412.Nov 14 2016, 6:20 PM
osa1 edited edge metadata.
  • fix automatic UNPACK logic. some tests.
  • minor. remove trace calls.
  • fix tc226
  • Try to document confusing sum type unpacker expr
osa1 added inline comments.Nov 14 2016, 6:26 PM
compiler/basicTypes/MkId.hs
883

I just tried this and we unpack this just fine. The reason is because before calling isUnpackableType we normalize types using topNormaliseType. I'm not sure when isNewTyCon tc condition is true here. I tried a nested newtype and even that was unpacked here.

osa1 updated this revision to Diff 9413.Nov 14 2016, 6:48 PM
osa1 edited edge metadata.
  • Update a comment
bgamari requested changes to this revision.Dec 6 2016, 12:03 AM
bgamari edited edge metadata.

@osa1, what is the status of this?

Bumping this out of the review queue for now.

This revision now requires changes to proceed.Dec 6 2016, 12:03 AM
osa1 added a comment.Dec 6 2016, 12:05 AM

@bgamari This is ready for reviews. Ping @simonpj.

compiler/basicTypes/MkId.hs
885

Why do we get stuck when sum constrs bind different existentials?

Is this patch still waiting to be reviewed @osa1 ?

Ahh, sorry I missed this, @osa1! Could you add some description in the Diff summary?

Also, wasn't there also some worker/wrapper work that went along with this?

Also, could you explicitly "request review"?

osa1 added a comment.Apr 4 2017, 8:45 AM

This was ready for reviews when I first submitted this, but now it may need a rebase.. I'll try to do that later today and request reviews if it passes the tests.

@bgamari worker/wrapper stuff is much more complicated and risky (because it sometimes makes programs slower) so it's not included here. This patch is not risky in that sense because UNPACK pragmas are added manually so we don't accidentally make any programs slower.

osa1 added a comment.Apr 4 2017, 8:47 AM

(ps. I had a patch for worker/wrapper stuff too.. I don't remember the state of it though, it may not be ready for reviews)