A co-worker of mine had a random thought on IRC:

Is data type “unrolling” a valid performance optimization? Used anywhere?

Something like: data List a = Nil | Cons a {-# Unroll 10 #-} (List a)

I thought, that sounds like the vec package I wrote. One module there uses the GADT definition

data Vec (n :: Nat) a where
    VNil  :: Vec 'Z a
    (:::) :: a -> Vec n a -> Vec ('S n) a

and a clever way to define functions so GHC unrolls them. Another module uses the data family

data family   Vec (n :: Nat) a
data instance Vec 'Z     a = VNil
data instance Vec ('S n) a = a ::: !(Vec n a)

which in some cases optimizes better than the GADT version. However in neither version we can {-# UNPACK #-} the tail. GHC simply says

Ignoring unusable UNPACK pragma on the second argument of ‘:::’

It’s not “obvious” to the compiler that tail is a single constructor data type: technically it’s not even a single constructor in the GADT; and it’s not clear in data family case either, because of the degenerate Vec ('S Any) case. But a single contructor data type is a requirement for UNPACK to work.

There’s however another trick we can use: Backpack.

Backpack is a system for retrofitting Haskell with an applicative, mix-in module system. In short, we are able to write more efficient monomorphic code. For example, the description of unpacked-containers says:

This backpack mixin package supplies unpacked sets and maps exploiting backpack’s ability to unpack through signatures.

Unpacking is exactly what we want to do.

(read more)

Other recent blog posts