在 REPA 数组中绘制矩形的最快方法是什么？

Question

通常，在位图中绘制矩形的好方法是遍历 2 个边界维度并设置单个像素。例如，伪代码：

drawRect(array, color, x, X, y, Y):
    for x from x til X:
        for y from y til Y:
            array[x,y] = color

Haskell 的 REPA 的等效项是什么？

Answer 1

在用于制作新数组的普通 REPA 机制中，当将数组复制到外部内存时，制作新的延迟数组是最快的。使用 REPA 的实际性能将取决于您对阵列的处理方式。

让我们定义一个计算类型，它仅取决于数组中的位置和该位置的当前值。

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Array.Repa hiding ((++))
import Data.Array.Repa.Repr.ForeignPtr

import Data.Word
import Control.Monad
import Data.Time.Clock
import System.Mem

type Ghost sh a b = sh -> a -> b

我们可以定义任何形状的填充。

fill :: Shape sh => sh -> sh -> a -> Ghost sh a a
fill from to color = go
    where
        {-# INLINE go #-}
        go sh a =
            if inShapeRange from to sh
            then color
            else a

我们将通过三种不同的方式使用它来定义新数组——延迟数组、结构化遍历和非结构化遍历。

最简单的延迟是fromFunction。

ghostD :: (Shape sh, Source r a) => Ghost sh a b -> Array r sh a -> Array D sh b
ghostD g a = fromFunction (extent a) go
    where
        {-# INLINE go #-}
        go sh = g sh (a ! sh)

结构化遍历可以利用了解底层数组表示的结构。不幸的是，我们在结构化遍历中获取有关位置信息的唯一方法是使用 szipWith 和一个已经包含位置信息的数组进行压缩。

ghostS :: (Shape sh, Structured r1 a b, Source r1 a) => Ghost sh a b -> Array r1 sh a -> Array (TR r1) sh b
ghostS g a = szipWith ($) ghost a
    where
        ghost = fromFunction (extent a) g

非结构化遍历与fromFunction构建的延迟数组非常相似；它还 returns 一个 Array D.

ghostT :: (Shape sh, Source r a) => Ghost sh a b -> Array r sh a -> Array D sh b
ghostT g a = traverse a id go
    where
        {-# INLINE go #-}
        go lookup sh = g sh (lookup sh)

通过一些非常简单的基准测试，我们可以运行看看它们有多快。我们在测量时间之前执行垃圾收集，以尝试获得可靠的计时结果。我们将有两个基准。对于每个机制，。我们将运行一步将结果写入内存 10 次。然后我们将组成101个相同的步骤一次将结果写入内存。

bench :: Int -> String -> IO a -> IO ()
bench n name action = do
    performGC
    start <- getCurrentTime
    replicateM_ n action    
    performGC
    end <- getCurrentTime
    putStrLn $ name ++ " " ++ (show (diffUTCTime end start / fromIntegral n))

iterN :: Int -> (a -> a) -> (a -> a)
iterN 0 f = id
iterN n f = f . iterN (n-1) f

main = do
    (img :: Array F DIM2 Word32) <- computeP (fromFunction (Z :. 1024 :. 1024 ) (const minBound))
    let (Z :. x :. y ) = extent img
        drawBox = fill (Z :. 20 :. 20 ) (Z :. x - 20 :. y - 20 ) maxBound

    bench 10 "Delayed      10x1" ((computeP $ ghostD drawBox img) :: IO (Array F DIM2 Word32))
    bench 10 "Unstructured 10x1" ((computeP $ ghostT drawBox img) :: IO (Array F DIM2 Word32))
    bench 10 "Structured   10x1" ((computeP $ ghostS drawBox img) :: IO (Array F DIM2 Word32))

    bench 1 "Delayed      1x101" ((computeP $ (iterN 100 (ghostD drawBox)) . ghostD drawBox $ img) :: IO (Array F DIM2 Word32))
    bench 1 "Unstructured 1x101" ((computeP $ (iterN 100 (ghostT drawBox)) . ghostT drawBox $ img) :: IO (Array F DIM2 Word32))
    bench 1 "Structured   1x101" ((computeP $ (iterN 100 (ghostS drawBox)) . ghostS drawBox $ img) :: IO (Array F DIM2 Word32))

结果时间是数组被写入外部内存的次数的平均值。这些结果是我机器上多个运行的典型结果。

Delayed      10x1 0.0234s
Unstructured 10x1 0.02652s
Structured   10x1 0.02652s
Delayed      1x101 0.078s
Unstructured 1x101 0.0936s
Structured   1x101 0.2652s

结果似乎并不取决于基准运行中的顺序。

Structured   10x1 0.03276s
Unstructured 10x1 0.02652s
Delayed      10x1 0.01716s
Structured   1x101 0.2184s
Unstructured 1x101 0.1092s
Delayed      1x101 0.0624s

这些结果表明您可以进行一些全数组计算，并且仍然可以通过内存访问来控制性能以写入结果。

通过在场景上绘制来渲染场景的库通常与 REPA 具有非常不同的结构，REPA 主要用于并行处理所有数据的数据处理任务。绘图和渲染库通常使用称为 scene graph 的场景元素图或树，允许它们快速剔除不会在图像或图像的一部分中绘制的元素。如果您可以快速剔除不影响特定像素的所有内容，则无需改变结果即可获得良好的性能。

在 REPA 数组中绘制矩形的最快方法是什么？

What is the fastest way to draw a rectangle in a REPA array?

haskell

repa