Abstracting over things that can be unpacked

[Twan van Laarhoven]

On 03/03/12 01:40, Johan Tibell wrote:
> Hi all,
>
> These ideas are still in very early stages. I present them here in hope
> of starting a discussion. (We discussed this quite a bit at last year's
> ICFP, I hope this slightly different take on the problem might lead to
> new ideas.)
>
> I think the next big step in Haskell performance is going to come from
> using better data representation in common types such as list, sets, and
> maps. Today these polymorphic data structures use both more memory and
> have more indirections than necessary, due to boxing of values. This
> boxing is due to the values being stored in fields of polymorphic type.
>
> First idea: instead of rejecting unpack pragmas on polymorphic fields,
> have them require a class constraint on the field types. Example:
>
>      data UnboxPair a b = (Unbox a, Unbox b) => UP {-# UNPACK #-} !a {-#
> UNPACK #-} !b

I expect that this will not be easy to implement, because it requires 
interaction with things like the garbage collector. For example, 
UnboxPair will need a different info table for different a and b.

It might be possible to essentially specialize UnboxPair for each 
different a and b for which it is used, but that gets tricky with 
generic code.

> The Unbox type class would be similar in spirit to the class with the
> same name in the vector package, but be implemented internally by GHC.
> To a first approximation instances would only exist for fields that
> unpack to non-pointer types (e.g. Int.)
>
> Second idea: Introduce a new pragma, that has similar effect on
> representations as DPH's [::] vector type. This new pragma does deep
> unpacking, allowing for more types to be instances of the Unbox type.

Could this be handled by just having/deriving an Unbox instance for 
(a,b)? I imagine the Unbox type class would have to contain essentially 
the same things as Storable, maybe something like

     type UnboxedRepr :: Int -> #
     class Unbox a where
         type Repr a :: # -- gives size and alignment
         unbox :: a -> Repr a
         box   :: Repr a -> a

A problem with an instance (Unboxed a, Unboxed b) => Unboxed (a,b) is 
that it allows arbitrarily large unboxed values to be created at 
runtime. That doesn't work when you use specialization to create the 
needed info tables.


Twan