Semantics and implementation of move for SoA vectors
- Dominant language
- Haskell
- Stars
- 400
- Forks
- 145
- PR merge metrics
- No merged PRs in 30d
Description
It turn out `move` is not implemented correctly for unboxed vector which use structure of arrays (SoA) representation. Here is `move`'s specification:
> If the vectors do not overlap, then this is equivalent to copy. Otherwise, the copying is performed as if the source vector were copied to a temporary vector and then the temporary vector was copied to the target vector.
For tuples move is implemented as pairwise move each underlying array. However it's possible for arrays corresponding to different to alias thus breaking `move` implementation. As an example:
```haskell
{-# LANGUAGE ImportQualifiedPost #-}
{-# LANGUAGE TypeFamilies #-}
module MV where
import Control.Monad.Primitive
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as MVU
import Data.Vector.Generic.Mutable qualified as MVG
-- Reference implementation for move:
moveSpec :: (MVG.MVector v a, PrimMonad m, PrimState m ~ s) => v s a -> v s a -> m ()
moveSpec tgt src = do
tmp <- MVG.clone src
MVG.copy tgt tmp
problemSoA :: IO ()
problemSoA = do
putStrLn "Reference impl"
testMove moveSpec
putStrLn "\nmove"
testMove MVU.move
where
testMove fun = do
va <- MVU.generate 4 id
vb <- MVU.generate 4 (+100)
let src = MVU.zip va vb
dst = MVU.zip vb va
print . ("src = "++) . show =<< VU.freeze src
print . ("dst = "++) . show =<< VU.freeze dst
fun dst src
print . ("dst = "++) . show =<< VU.freeze dst
```
produces
```
Reference impl
"src = [(0,100),(1,101),(2,102),(3,103)]"
"dst = [(100,0),(101,1),(102,2),(103,3)]"
"dst = [(0,100),(1,101),(2,102),(3,103)]"
move
"src = [(0,100),(1,101),(2,102),(3,103)]"
"dst = [(100,0),(101,1),(102,2),(103,3)]"
"dst = [(0,0),(1,1),(2,2),(3,3)]"
```
Which is obviously breaks specification. However I don't see any easy fix. We'll need to check all underlying arrays for overlap and we don't have machinery for that
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.