ekmett / linear

Low-dimensional linear algebra primitives for Haskell.
http://hackage.haskell.org/package/linear
Other
201 stars 50 forks source link

A Faster Linear.V.V #152

Open TravisWhitaker opened 5 years ago

TravisWhitaker commented 5 years ago

This package is great for small to medium-sized matrices. However, having terms of type V n (V m a) represented by a Vector (Vector a) hurts once the matrices become larger.

I think it should be possible to speed up the Linear.V.V type with a definition like this:

import Data.Proxy

import qualified Data.Vector as V

import GHC.TypeLits

data V (n :: Nat) a = V {
    vGet :: Int -> a
  , vPut :: Int -> a -> V n a
  }

unsafeV :: KnownNat n => V.Vector a -> V n a
unsafeV v = V (v V.!) (\i x -> unsafeV (v V.// [(i, x)]))

unsafeVofV :: forall n m a.
              (KnownNat n, KnownNat m)
           => V.Vector a
           -> V n (V m a)
unsafeVofV v =
    let ml      = fromIntegral (natVal (Proxy :: Proxy m))
        get i   = unsafeV (V.slice (i * ml) ml v)
        put i x = let xv = V.generate ml (vGet x)
                      u  = V.update v (V.zip (V.enumFromN (i * ml) ml) xv)
                  in unsafeVofV u
    in V get put

unsafeVofVofV = ...
unsafeVofVofVofV = ...

The idea is to be able to use one flat Vector for a V n a, V n (V m a), and so on (although nesting more than two is of questionable utility). This should be sufficient to implement the instances available for the existing V type, although adding map, foldl, traverse, and maybe others to the record to short-circuit vGet and vPut in such loops might be better for performance. This should play nicely with the stream fusion machinery in the vector package. Although, I could easily see a world in which allocating closures in this way is actually slower than a Vector (Vector a); I haven't benchmarked yet.

I'm curious if anyone else is using this library this way? And I'm especially curious if @ekmett is aware of any caveats I'm missing. If this isn't obviously bad I'd be happy to bang this out and do some benchmarking.

ekmett commented 5 years ago

I'd be somewhat worried about accumulating several layers of indirection if anything ever modified vGet and vPut. That said, having some control over the backing store like this could be pretty powerful.