Подтвердить что ты не робот

Плохая производительность с транспонированной и суммарной суммой в Repa

Я разработал кумулятивную функцию суммы, как определено ниже в библиотеке Haskell Repa. Тем не менее, я столкнулся с проблемой при объединении этой функции с транспозицией. Все 3 из следующих операций занимают второе место:

cumsum $ cumsum $ cumsum x
transpose $ transpose $ transpose x
transpose $ cumsum x

Однако, если я пишу:

cumsum $ transpose x

производительность ухудшается ужасно. В то время как каждая отдельная операция в изоляции занимает значительно меньше секунды на изображении 1920x1080, при объединении они теперь занимают 30 + секунд...

Любые идеи о том, что может быть причиной этого? Моя кишка говорит мне, что это имеет какое-то отношение к задержанным массивам, а не к форсированию в нужное время и т.д. Но у меня недостаточно опыта, чтобы проследить это еще довольно давно.

{-# LANGUAGE TypeOperators, FlexibleContexts, TypeFamilies #-}

import Data.Array.Repa as Repa

{-# INLINE indexSlice #-}
indexSlice :: (Shape sh, Elt a) => Int -> Array (sh :. Int) a -> (sh :. Int) -> a
indexSlice from arr (z :. ix) = arr `unsafeIndex` (z :. (ix + from))

{-# INLINE sliceRange #-}
sliceRange :: (Slice sh, Shape sh, Elt a) => Int -> Int -> Array (sh :. Int) a -> Array (sh :. Int) a
sliceRange from to arr = fromFunction (z :. (to - from + 1)) $ indexSlice from arr
    where (z :. _) = extent arr

{-# INLINE cumsum' #-}
cumsum' :: (Slice (SliceShape sh), Slice sh, Shape (FullShape sh), Shape (SliceShape sh), Elt a, Num a) =>
     Array (FullShape sh :. Int) a -> t -> (sh :. Int) -> a
cumsum' arr f (sh :. outer) = Repa.sumAll $ sliceRange 0 outer $ Repa.slice arr (sh :. All)

{-# INLINE cumsum #-}
cumsum :: (FullShape sh ~ sh, Slice sh, Slice (SliceShape sh), Shape sh, Shape (SliceShape sh), Elt a, Num a) =>
    Array (sh :. Int) a -> Array (sh :. Int) a
cumsum arr = Repa.force $ unsafeTraverse arr id $ cumsum' arr
4b9b3361

ОТВЕТЫ

Ответ 1

С точки зрения реализатора библиотеки способ отладки заключается в создании оболочки для подозрительной операции, а затем посмотрите на основной код, чтобы увидеть, работает ли слияние.

-- Main.hs ---------------------------------------------------
import Solver
import Data.Array.Repa.IO.BMP

main 
 = do   Right img       <- readImageFromBMP "whatever.bmp"
        print $ cumsumBMP img

-- Solver.hs --------------------------------------------------
{-# LANGUAGE TypeOperators, FlexibleContexts, TypeFamilies #-}
module Solver (cumsumBMP) where
import Data.Array.Repa  as Repa
import Data.Word

{- all your defs -}

{-# NOINLINE cumsumBMP #-}
cumsumBMP :: Array DIM3 Word8 -> Array DIM3 Word8
cumsumBMP img = cumsum $ transpose img

Я поместил код "решателя" в отдельный модуль, поэтому нам нужно только пробираться по основному коду для определений, о которых мы заботимся.

Скомпилируйте как:

touch Solver.hs ; ghc -O2 --make Main.hs \
 -ddump-simpl -dsuppress-module-prefixes -dsuppress-coercions  > dump

Перейдите к определению cumsumBMP и найдите ключевое слово letrec. Поиск letrec - это быстрый способ поиска внутренних циклов.

Не слишком далеко, я вижу это: (слегка переформатированный)

case gen_a1tr
of _ {
  GenManifest vec_a1tv ->
    case sh2_a1tc  `cast` ... of _ { :. sh3_a1iu  sh4_a1iv ->
    case ix'_a1t9  `cast` ... of _ { :. sh1'_a1iz sh2'_a1iA ->
    case sh3_a1iu  `cast` ... of _ { :. sh5_X1n0  sh6_X1n2 ->
    case sh1'_a1iz `cast` ... of _ { :. sh1'1_X1n9 sh2'1_X1nb ->
    case sh5_X1n0             of _ { :. sh7_X1n8   sh8_X1na ->
    ...
    case sh2'1_X1nb           of _ { I# y3_X1nO ->
    case sh4_a1iv             of _ { I# y4_X1nP ->
    case sh2'_a1iA            of _ { I# y5_X1nX ->
    ...
    let { x3_a1x6 :: Int# [LclId]
      x3_a1x6 =
        +#
          (*#
             (+#
                (*#
                   y1_a1iM
                   y2_X1nG)
                y3_X1nO)
             y4_X1nP)
          y5_X1nX } in
    case >=#
           x3_a1x6
           0
    of ...

Disaster! Связывание x3_a1x6 явно выполняет некоторую полезную работу (умножения, дополнения и т.д.), Но завернуто в длинную серию операций unboxing, которые также выполняются для каждой итерации цикла. Хуже всего то, что он распаковывает длину и ширину (форму) массива на каждой итерации, и эта информация всегда будет одинаковой. GHC должен действительно вытеснять эти case-выражения из цикла, но этого пока нет. Это экземпляр Проблема № 4081 на трассе GHC, который, надеюсь, скоро будет исправлен.

Работа вокруг заключается в применении deepSeqArray к входящему массиву. Это накладывает спрос на его значение на верхнем уровне (вне цикла), что позволяет GHC знать, что это нормально, чтобы переместить совпадения дел дальше. Для такой функции, как cumsumBMP, мы также ожидаем, что входящий массив уже будет явным, поэтому мы можем добавить для него явное совпадение:

{-# NOINLINE cumsumBMP #-}
cumsumBMP :: Array DIM3 Word8 -> Array DIM3 Word8
cumsumBMP [email protected](Array _ [Region RangeAll (GenManifest _)])
  = img `deepSeqArray` cumsum $ transpose img

Компиляция снова, внутренний цикл теперь выглядит намного лучше:

letrec {
$s$wfoldlM'_loop_s2mW [...]
  :: Int# -> Word# -> Word# [...]
$s$wfoldlM'_loop_s2mW =
  \ (sc_s2mA :: Int#) (sc1_s2mB :: Word#) ->
    case <=# sc_s2mA a_s2ji of _ {
      False -> sc1_s2mB;
      True ->
        $s$wfoldlM'_loop_s2mW
          (+# sc_s2mA 1)
          (narrow8Word#
             (plusWord#
                sc1_s2mB
                (indexWord8Array#
                   rb3_a2gZ
                   (+#
                      rb1_a2gX
                      (+#
                         (*#
                            (+#
                               (*#
                                  wild19_X1zO
                                  ipv1_X1m5)
                               sc_s2mA)
                            ipv2_X1m0)
                         wild20_X1Ct)))))
    }; } in

Это жесткий, хвостовой рекурсивный цикл, который использует только примитивные операции. Если вы компилируете с помощью -fllvm -optlo-O3, нет никакой причины, которая не будет работать так же быстро, как эквивалентная программа C.

Там есть небольшая икота при запуске:

desire:tmp benl$ ./Main 
Main: Solver.hs:(50,1)-(51,45): Non-exhaustive patterns in function cumsumBMP

Это просто напоминает нам, что нам нужно заставить массив перед вызовом cumsumBMP.

-- Main.hs ---------------------------------------------------
...
import Data.Array.Repa as Repa
main 
 = do   Right img       <- readImageFromBMP "whatever.bmp"
        print $ cumsumBMP $ Repa.force img

Вкратце:

  • Вам нужно добавить несколько deepSeqArray и совпадение шаблонов на ваш верхний уровень функции для борьбы с текущим беспорядком в GHC. Это демонстрируется окончательная версия функции cumsumBMP выше. Если вы хотите, чтобы штаб-квартира GHC исправилась это скоро добавьте себя как cc в Проблема № 4081 на трассе GHC. Программы Repa будут намного красивее, если это будет исправлено.
  • Вам не нужно добавлять goop для каждой функции. В этом примере мне не нужно было прикоснуться к indexSlice и друзьям. Общее правило состоит в том, чтобы добавить goop в функции, которые используют force, fold или sumAll. Эти функции создают экземпляр фактических циклов, которые работают над данными массива, то есть они преобразуют задержанный массив в значение манифеста.
  • Производительность фрагмента кода Repa определяется так же контекстом, в котором он использовался как фактический код. Если вы передадите функции верхнего уровня с задержанными массивами, они будут работать очень медленно. Об этом больше говорится в Учебном пособии по Repa.
  • Файлы BMP, считанные с библиотекой repa-io, не предварительно принудительно, поэтому вам необходимо принудительно их использовать перед использованием. Вероятно, это неправильный вариант, поэтому я изменю его в следующей версии.