ekmett / ekmett/linear

A Faster Linear.V.V

Open
#152 1 comment 0 reactions 0 assignees View on GitHub
api-change feature request
Dominant language
Haskell
Stars
220
Forks
55
PR merge metrics
No merged PRs in 30d

Description

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:

```Haskell
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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.