Abstracting over things that can be unpacked

[Johan Tibell]

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

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 e.g.
pairs. Example:

    data T = C {-# UNWRAP #-} (a, b)

If you squint a bit this pragma does the same as [: (a, b) :], except no
vectors are involved. The final representation would be the
unpacked representation of a and b, concatenated together (e.g. (Int, Int)
would result in the field above being 128-bit wide on a 64-bit machine.

The meta-idea tying these two ideas together is to allow for some
abstraction over representation transforming pragmas, such as UNPACK.

P.S. Before someone suggest using type families. Please read my email
titled "Avoiding O(n^2) instances when using associated data types to
unpack values into constructors."

Cheers,
  Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20120302/30d1a476/attachment.htm>