haskell / haskell/vector

Semantics and implementation of move for SoA vectors

Open
#472 0 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.