0

通常，在位图中绘制矩形的一种好方法是循环遍历 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 等价物是什么？

4

1 回答 1

2

在生成新数组的普通 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非结构化遍历与由;构建的延迟数组非常相似。它还返回一个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 主要用于并行处理所有数据的数据处理任务。绘图和渲染库通常使用称为场景图的场景元素图或树，它允许它们快速剔除不会在图像或图像的一部分中绘制的元素。如果您可以快速剔除不影响特定像素的所有内容，则不需要改变结果以获得良好的性能。

于 2015-01-18T02:27:23.447 回答