Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Semantics and implementation of move for SoA vectors

Abierto
  • ¿Algo no está bien?
#472 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Error
Claridad
Necesita aclaración
Estado de actividad
Estancado
Stack tecnológico
haskell
Área
data

Línea de trabajo

Comienza ejecutando la reproducción en Haskell del issue, comparando moveSpec con MVU.move sobre vectores SoA agrupados. Sigue la implementación que hay detrás de MVU.move y determina cómo se gestiona el aliasing entre los arrays subyacentes; se considera terminado cuando los movimientos solapados producen el mismo resultado que la implementación de referencia con un vector temporal.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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:

{-# 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

Lenguaje dominante
Haskell
Estrellas
403
Forks
146
Merge medio
1 d 22 h
PR fusionados (30 d)
3

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de haskell/vector

Todos los issues de haskell/vector

Issues similares

Más issues de Haskell

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.