[Haskell-cafe] vector-simd: some code available, and some questions

[Gábor Lehel]

On Sat, Jul 7, 2012 at 9:13 PM, Nicolas Trangez <nicolas at incubaid.com> wrote:
> - Currently Alignment phantom types (e.g. A8 and A16) are not related to
> each other: a function (like Data.Vector.SIMD.Algorithms.unsafeXorSSE42)
> can have this signature:
>
> unsafeXorSSE42 :: Storable a => SV.Vector SV.A16 a -> SV.Vector SV.A16 a
> -> SV.Vector SV.A16 a
>
> Yet, imaging I'd have an "SV.Vector SV.A32 Word8" vector at hand, the
> function should accept it as well (a 32-byte aligned vector is also
> 16-byte aligned). Is there any way to encode this at the type level?

If the set of alignments you care about is finite, you could do:

class AlignedToAtLeast n a
instance AlignedToAtLeast A1 A1
instance AlignedToAtLeast A4 A1
instance AlignedToAtLeast A4 A4
instance AlignedToAtLeast A8 A1
instance AlignedToAtLeast A8 A4
instance AlignedToAtLeast A8 A8
instance AlignedToAtLeast A16 A1
instance AlignedToAtLeast A16 A4
instance AlignedToAtLeast A16 A8
instance AlignedToAtLeast A16 A16
instance AlignedToAtLeast A32 A1
instance AlignedToAtLeast A32 A4
instance AlignedToAtLeast A32 A8
instance AlignedToAtLeast A32 A16
instance AlignedToAtLeast A32 A32

in which as you can see the numbers of instances grows super-linearly
with the number of alignments, but if there's only a handful it's not
that bad. Then:

unsafeXorSSE42 :: (Storable a, AlignedToAtLeast A16 align) =>
SV.Vector align a -> SV.Vector align a -> SV.Vector align a

A problem with the above is that third parties can add more instances,
breaking the safety. If this is a concern you could do:

class AlignedToAtLeastImpl n a -- do not export this class!
...same instances as above...
class AlignedToAtLeastImpl n a => AlignedToAtLeast n a -- export this class
instance AlignedToAtLeastImpl n a => AlignedToAtLeast n a

The drawback is that it requires UndecidableInstances, and (what
bothers me more) the list of instances won't be present in the
haddocks. So instead of the single instance above you could write all
of them again manually for the exported class, which has the drawback
that you have to write all of them again manually, but not the other
two.

An alternative solution is to encode all of the alignments in unary,
which is more general; if they're all going to be a power of two you
can "store" just the logarithm:

data One
data Twice n -- not practical to call it Double :)

class AlignedToAtLeast n a
instance AlignedToAtLeast One One
instance AlignedToAtLeast One (Twice a)
instance AlignedToAtLeast n a => AlignedToAtLeast (Twice n) (Twice a)

type A1 = One
type A4 = Twice (Twice A1)
type A8 = Twice A4
type A16 = Twice A8
type A32 = Twice A16

and you can apply the same private class thing from above if you want.

-- 
Your ship was caught in a monadic eruption.