Representation of unlifted wrappers around lifted types
Motivation
Suppose I want a proper strict array. What's that mean?
- Elements are forced when stored in the array.
- Elements read from the array are known to be in WHNF.
Today, there are two ways to do this:
The hard way
We can define
newtype StrictMArray s a = StrictMArray (MutableArray s a)
readM :: StrictMArray s a -> Int -> ST s a
readM (StrictMArray mary) i = do
-- We must force this (already WHNF) value so the compiler knows
-- it's been forced, to avoid creating unneeded thunks in certain cases.
!a <- readArray mary i
pure a
writeM :: StrictMArray s a -> Int -> a -> ST s ()
-- We must remember to force `a` before installing it in the array.
writeM (StrictMArray mary) i !a = writeArray mary i a
This approach is error prone, and it has silly double forces, but it's probably the best we can do right now. The alternative uses unlifted data:
The easy way
This requires an API for arrays of unlifted things that doesn't exist yet, but it will soon. You should be able to get the drift.
data Unlift :: Type -> UnliftedType where
Unlift :: !a -> Unlift a
newtype StrictMArray s a = StrictMArray (MutableUnliftedArray s (Unlift a))
readM :: StrictMArray s a -> Int -> ST s a
readM (StrictMArray mary) i = do
Box (Unlift a) <- readUnliftedArray mary i
pure a
writeM :: StrictMArray s a -> Int -> a -> ST s ()
writeM (StrictMArray mary) i a = writeUnliftedArray mary i (Unlift a)
Wow, that's a lot nicer, isn't it? It's way harder to get things wrong, and there's no more double forcing. Unfortunately ... it's hideously inefficient. The problem is that every element gets its own box for no reason.
Proposal
When an unlifted datatype
- Has exactly one constructor
- which has no class constraints and has exactly one field
- and that field either has kind
UnliftedType
or has kindType
and is strict but not unpacked
then we shouldn't box it. The "not unpacked" condition can be relaxed if the field unpacks to a pointer type.
Some years ago (I can't find the ticket) I (or someone else?) suggested doing something similar for lifted types, but that proved tricky due to the need to force on pattern matching. Here, we can just drop the box on the floor when lowering from Core to STG. Operationally, the constructor "worker" turns into a no-op, as does the associated matcher.
What can go wrong? The main issue is if someone does something sketchy like
getSolo (unsafeCoerce# (Unlift a))
This currently works, though it's explicitly forbidden, and it would stop working with the proposed change. There would also be some profiling changes, which may or may not be okay.