Opened 5 years ago

Closed 14 months ago

#9214 closed feature request (fixed)

UNPACK support for sum types

Reported by: mojojojo Owned by: osa1
Priority: normal Milestone:
Component: Compiler Version: 7.8.2
Keywords: Cc: RyanGlScott, michalt
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D1540 Phab:D1559 Phab:D2259
Wiki Page: UnpackedSumTypes

Description

Currently the pragma only supports single-constructor types. So in the following example it will simply be ignored:

data A = 
  A1 Char |
  A2 {-# UNPACK #-} !B

data B = 
  B1 Int |
  B2 Bool

However the problem seems to be easily solvable by denormalizing the type A to something like the following during unpacking:

data A =
  A1 Char |
  A2_1 Int |    -- from B1
  A2_2 Bool     -- from B2

Change History (9)

comment:1 Changed 5 years ago by schyler

Smells fishy. Would create a pwr(N,2) number of denormalizations where N is the number of inner sum types. Sounds like code explosion to me...

Would be better to calculate the largest size of the fully unpacked type like a C compiler would for unions.

o/t The behaviour of the trac for n2 notation is really annoying!

Last edited 5 years ago by schyler (previous) (diff)

comment:2 Changed 5 years ago by tibbe

It's even more complicated than just allocating the max needed by any of the unpacked sum type's constructor. The GC needs to know what the fields are in any given constructor to be able to GC correctly. I don't think this will be hard (that's why we haven't done it already).

comment:3 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:4 Changed 4 years ago by thomie

Differential Rev(s): Phab:D1540 Phab:D1559
Owner: set to osa1
Wiki Page: UnpackedSumTypes
Last edited 4 years ago by thomie (previous) (diff)

comment:5 Changed 3 years ago by dfeuer

I'm just popping in to +1 this. Currently, Data.IntMap defines

data IntMap a = Bin ... !(IntMap a) !(IntMap a) | Tip ... | Nil

Logically, it *should* be

data IntMap a = IM !(IntMap1) | Nil
data IntMap1 a = Bin ... !(IntMap1) !(IntMap1) | Tip ...

which would enforce the invariant that no Nils can occur within a tree. But that has an extra indirection, which seems likely unacceptable. If we could UNPACK the IntMap1 into the IntMap, we'd get the current performance with much nicer type guarantees.

comment:6 Changed 3 years ago by dfeuer

One special case is a GADT with one constructor that takes one argument without any class context. For instance

data Foo a = This a | That a a
data Bar a b where
  Bar :: !(Foo a) -> Bar a a
data Baz where
  Baz :: !(Foo a) -> Baz

It would be great to be able to unpack Foo into Bar and Baz. Matching on the Bar or Baz constructor would force its contents to WHNF and reveal the evidence/open the existential.

comment:7 Changed 3 years ago by RyanGlScott

Cc: RyanGlScott added

comment:8 Changed 3 years ago by michalt

Cc: michalt added
Differential Rev(s): Phab:D1540 Phab:D1559Phab:D1540 Phab:D1559 Phab:D2259

comment:9 Changed 14 months ago by thomie

Resolution: fixed
Status: newclosed

In 714bebff44076061d0a719c4eda2cfd213b7ac3d:

Author: Ömer Sinan Ağacan <omeragacan@gmail.com>
Date:   Thu Jul 21 08:07:41 2016 +0000

    Implement unboxed sum primitive type
Note: See TracTickets for help on using tickets.