WedX - журнал о программировании и компьютерных науках

Трафаретные хаки Haskell Repa

Проблема

Я пытаюсь понять, как работает Repa, и я начал с "размытого" примера кода из < пакет href="https://hackage.haskell.org/package/repa-examples">Repa Examples. В коде используется stencil2 Quasi Quote:

[stencil2|   2  4  5  4  2
             4  9 12  9  4
             5 12 15 12  5
             4  9 12  9  4
             2  4  5  4  2 |]

Это просто фрагмент TemplateHaskell, который генерирует функцию:

makeStencil2 5 5 coeffs where
     {-# INLINE[~0] coeffs #-}
     coeffs = \ ix -> case ix of
                      Z :. -2 :. -2 -> Just 2
                      Z :. -2 :. -1 -> Just 4
                      Z :. -2 :. 0 -> Just 5
                      Z :. -2 :. 1 -> Just 4
                      Z :. -2 :. 2 -> Just 2
                      [...]
                      _ -> Nothing

Можно использовать TH, но я хотел бы сохранить коэффициенты в массиве Repa, поэтому я изменил код, чтобы вместо этого использовать массив Repa, но мой код работает в 2 раза медленнее по сравнению с исходным.

Некоторые заметки

Я заметил, что авторы Repa используют жестко запрограммированную матрицу значений 7 на 7 для получения коэффициентов: https://hackage.haskell.org/package/repa-3.2.3.3/docs/src/Data-Array-Repa-Stencil-Dim2.html#forStencil2 (см.: template7x7)

Вопросы

  1. Я хочу спросить вас, почему он не оптимизирован как оригинальный и как мы можем это исправить? Я хочу написать функцию «свертки», которая позволит мне выполнять свертку трафарета (массива Repa) над изображением.
  2. Действительно ли нам нужно использовать такие жестко запрограммированные матрицы, чтобы GHC оптимизировал код? Неужели нельзя создать быстрый код на Haskell без использования таких «хаков»?

Кодекс

Оригинальная функция размытия:

blur    :: Monad m => Int -> Array U DIM2 Double -> m (Array U DIM2 Double)
blur !iterations arrInit
 = go iterations arrInit
 where  go !0 !arr = return arr
        go !n !arr  
         = do   arr'    <- computeP
                         $ A.smap (/ 159)
                         $ forStencil2 BoundClamp arr
                           [stencil2|   2  4  5  4  2
                                        4  9 12  9  4
                                        5 12 15 12  5
                                        4  9 12  9  4
                                        2  4  5  4  2 |]
                go (n-1) arr'

моя функция размытия:

blur !iterations arrInit = go iterations arrInit
    where 
          stencilx7 = fromListUnboxed (Z :. 7 :. 7) 
                    [  0,  0,  0,  0,  0,  0, 0
                    ,  0,  2,  4,  5,  4,  2, 0
                    ,  0,  4,  9, 12,  9,  4, 0
                    ,  0,  5, 12, 15, 12,  5, 0
                    ,  0,  4,  9, 12,  9,  4, 0
                    ,  0,  2,  4,  5,  4,  2, 0
                    ,  0,  0,  0,  0,  0,  0, 0
                    ] :: Array U DIM2 Int
          magicf (Z :. x :. y) = Just $ fromIntegral $ unsafeIndex stencilx7 (Z:. (x+3) :. (y+3))
          go !0 !arr = return arr
          go !n !arr  
           = do   
                  arr'    <- computeP
                           $ A.smap (/ 159)
                           $ A.forStencil2 BoundClamp arr 
                            $ makeStencil2 5 5 magicf
                  go (n-1) arr'

Остальная часть кода:

{-# LANGUAGE PackageImports, BangPatterns, TemplateHaskell, QuasiQuotes #-}
{-# OPTIONS -Wall -fno-warn-missing-signatures -fno-warn-incomplete-patterns #-}

import Data.List
import Control.Monad
import System.Environment
import Data.Word
import Data.Array.Repa.IO.BMP
import Data.Array.Repa.IO.Timing
import Data.Array.Repa                          as A
import qualified Data.Array.Repa.Repr.Unboxed   as U
import Data.Array.Repa.Stencil                  as A
import Data.Array.Repa.Stencil.Dim2             as A
import Prelude                                  as P

main 
 = do   args    <- getArgs
        case args of
         [iterations, fileIn, fileOut]  -> run (read iterations) fileIn fileOut
         _                              -> usage

usage   = putStr $ unlines
        [ "repa-blur <iterations::Int> <fileIn.bmp> <fileOut.bmp>" ]


-- | Perform the blur.
run :: Int -> FilePath -> FilePath -> IO ()
run iterations fileIn fileOut
 = do   arrRGB  <- liftM (either (error . show) id) 
                $  readImageFromBMP fileIn

        arrRGB `deepSeqArray` return ()
        let (arrRed, arrGreen, arrBlue) = U.unzip3 arrRGB
        let comps                       = [arrRed, arrGreen, arrBlue]

        (comps', tElapsed)
         <- time $ P.mapM (process iterations) comps

        putStr $ prettyTime tElapsed

        let [arrRed', arrGreen', arrBlue'] = comps'
        writeImageToBMP fileOut
                (U.zip3 arrRed' arrGreen' arrBlue')


process :: Monad m => Int -> Array U DIM2 Word8 -> m (Array U DIM2 Word8)
process iterations 
        = promote >=> blur iterations >=> demote
{-# NOINLINE process #-}


promote :: Monad m => Array U DIM2 Word8 -> m (Array U DIM2 Double)
promote arr
 = computeP $ A.map ffs arr
 where  {-# INLINE ffs #-}
        ffs     :: Word8 -> Double
        ffs x   =  fromIntegral (fromIntegral x :: Int)
{-# NOINLINE promote #-}


demote  :: Monad m => Array U DIM2 Double -> m (Array U DIM2 Word8)
demote arr
 = computeP $ A.map ffs arr

 where  {-# INLINE ffs #-}
        ffs     :: Double -> Word8
        ffs x   =  fromIntegral (truncate x :: Int)

Компилировать с: ghc -O2 -threaded -fllvm -fforce-recomp Main.hs -ddump-splices


Ответы:


1
  1. Чтение коэффициентов свертки из массива теоретически не может быть таким же быстрым, как пайка констант прямо в скомпилированном коде, потому что последний подход ничего не стоит на машинном уровне.

  2. Нет, GHC может сводить статические трафареты произвольного размера. См. мою реализацию. статических сверток с fixed-vector лямбда-выражений:

    [dim2St| 1   2   1
             0   0   0
            -1  -2  -1 |]
    -->
    Dim2Stencil
     n3
     n3
     (VecList
        [VecList
           [\ acc a -> return (acc + a),
            \ acc a -> (return $ (acc + (2 * a))),
            \ acc a -> return (acc + a)],
         VecList
           [\ acc _ -> return acc,
            \ acc _ -> return acc,
            \ acc _ -> return acc],
         VecList
           [\ acc a -> return (acc - a),
            \ acc a -> (return $ (acc + (-2 * a))),
            \ acc a -> return (acc - a)]])
     (\ acc a reduce -> reduce acc a)
     (return 0)
    
03.11.2013
  • 1. Но если такой массив известен во время компиляции (он известен в этом примере) и дополнительно мы встраиваем каждую функцию, которая его использует, GHC сможет оптимизировать его таким же образом, не так ли? 03.11.2013
  • 2. Я знаю это, потому что трафарет создает лямбда-функцию и во время компиляции (см. код, склеенный ddump), но можем ли мы вместо этого использовать простой статический массив, известный во время компиляции? Это дало бы мне возможность создавать более быстрый код, если такой массив определен статически, и более медленный, если он загружается динамически. 03.11.2013
  • Additiona, будьте так любезны, скажите, пожалуйста, что на самом деле происходит под капотом? Теоретически программа должна перебрать каждый пиксель изображения и умножить его на коэффициенты из трафарета. Так что это просто свертка массива массива. Как можно оптимизировать такой статический код, чтобы он работал быстрее, чем такое простое умножение? (Я просто хочу понять оптимизации, которые здесь происходят). 03.11.2013
  • 1. Если вам не нужны преимущества динамичности (например, каким-то образом подключаемый шаблон во время выполнения), почему бы вам просто не использовать квазикавычки? 03.11.2013
  • 2. Гибкость в Haskell может быть легко введена в любой момент, не так ли? Напишите, например, тип класса Convolver 03.11.2013
  • Если вы сворачиваете массив с массивом, в каждом пикселе вам нужно 1) прочитать значение пикселя из изображения и сохранить его в регистре 2) прочитать coeff и сохранить его в регистре 3) умножить их. Со статическим трафаретом: 1) прочитать значение с изображения и сохранить его в регистре; 2) умножить регистр на месте на непосредственную константу. Вычисление свертки как 5x5 требует большого количества регистров, и я подозреваю, что первая версия дополнительно страдает от отсутствия регистров и необходимости сохранять вычисленные значения в стеке или не может использовать все 4 арифметических блока (это всего лишь предположение). 03.11.2013
  • давайте продолжим это обсуждение в чате 03.11.2013
  • Новые материалы

    Как создать диаграмму градиентной кисти с помощью D3.js
    Резюме: Из этого туториала Вы узнаете, как добавить градиентную кисть к диаграмме с областями в D3.js. Мы добавим градиент к значениям SVG и применим градиент в качестве заливки к диаграмме с..

    Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что это выглядит сложно…
    Просто начните и учитесь самостоятельно Я хотел выучить язык программирования MVC4, но не мог выучить его раньше, потому что он кажется мне сложным, и я бросил его. Это в основном инструмент..

    Лицензии с открытым исходным кодом: руководство для разработчиков и создателей
    В динамичном мире разработки программного обеспечения открытый исходный код стал мощной парадигмой, способствующей сотрудничеству, инновациям и прогрессу, движимому сообществом. В основе..

    Объяснение документов 02: BERT
    BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..

    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..

    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..


    Для любых предложений по сайту: [email protected]