PR

遅延された処理を評価するcompute*関数

 遅延された処理の評価を促し,処理の結果である新しい配列を返すには,別途用意されているcompute*関数を利用する必要があります。compute*関数にはcomputeP関数やcomputeS関数があります。

 computePは並列に処理を行う関数,computeSは逐次的に処理を行う関数です。repaでは,並列処理を行う関数として接尾辞P,逐次処理を行う関数として接尾辞S,の2種類の関数が提供されています。

-- | Parallel computation of array elements.
--
--   * The source array must have a delayed representation like `D`, `C` or `P`, 
--     and the result a manifest representation like `U` or `F`.
--
--   * If you want to copy data between manifest representations then use
--    `copyP` instead.
--
--   * If you want to convert a manifest array back to a delayed representation
--     then use `delay` instead.
--
computeP 
        :: (Shape sh, Fill r1 r2 sh e, Repr r2 e, Monad m)
        => Array r1 sh e -> m (Array r2 sh e)
computeP arr = now $ suspendedComputeP arr
{-# INLINE [4] computeP #-}


-- | Sequential computation of array elements.
computeS 
        :: Fill r1 r2 sh e
        => Array r1 sh e -> Array r2 sh e
computeS arr1
 = arr1 `deepSeqArray` 
   unsafePerformIO
 $ do   marr2    <- newMArr (size $ extent arr1) 
        fillS arr1 marr2
        unsafeFreezeMArr (extent arr1) marr2
{-# INLINE [4] computeS #-}

 なぜ,並列処理版の関数だけでなく,逐次処理版の関数も用意されているのでしょうか。

 処理を並列化する場合には,相応の負荷が必ず発生します。配列の大きさによっては,この負荷が問題になるのです。配列が小さい場合,「並列化のための負荷」が「並列化することによる性能の向上」を上回るようになります。つまり,並列化処理のほうが逐次処理よりも性能が下がってしまうのです。第48回でも説明しましたが,並列化はあくまで処理を高速化する手段の一つに過ぎません。並列化によってかえって性能が下がってしまう場合には,逐次処理を行うべきです。

 このような理由から,実際の性能を考えて並列処理と逐次処理を適切に使い分ける必要があります。そこでrepaでは並列処理版と逐次処理版の2種類の関数が提供されているのです。

 接尾辞Pの関数と接尾辞Sの関数の違いは,並列処理するか逐次処理をするかだけではありません。接尾辞Sの関数は値をそのまま返すのに対し,接尾辞Pの関数は値をモナドに包んで返すという違いがあります。

computeP 
        :: (Shape sh, Fill r1 r2 sh e, Repr r2 e, Monad m)
        => Array r1 sh e -> m (Array r2 sh e)
~ 略 ~

-- | Sequential computation of array elements.
computeS 
        :: Fill r1 r2 sh e
        => Array r1 sh e -> Array r2 sh e
~ 略 ~

 また,computeP関数の型にはShapeクラスやReprクラスが文脈として付いているという違いもあります。もっとも,この部分は特に気する必要はありません。行列の形状を表現するsh型はShapeクラスのインスタンス,配列の内部表現を表すr2型のタグはReprクラスのインスタンスでなければならない,という当然の制約を示しているだけです。computeP関数に特有の新しい制約を与えているわけではありません。computeP関数とcomputeS関数の本質的な違いは,値をモナドに包んで返すかどうかだけです。

 接尾辞Pの関数が値をモナドに包んで返すのは,第50回で説明した「遅延評価では評価順序が曖昧なため,プログラムの並列化のために処理の順序を制御するのが難しい」という問題を回避するためです。repaでは,delay関数を使って他の配列から変換したり,map関数やzipWith関数を使ったりすることで,遅延評価されるD型の配列が作成されます。並列処理の制御のためには,遅延評価によって曖昧になった処理の順序を制御する何らかの仕組みが必要です。

 第50回では,並列処理の順序を制御するために,EvalモナドやParモナドといったモナドを利用する方法を説明しました。repaでも同様に,並列処理の順序を制御するためにモナドを利用しています(参考リンク)。ただし,並列処理の順序の制御のために特別なモナドを用意しているわけではありません。repaが提供する接尾辞Pの関数は,値を単純にモナドに包んで返すことで,IOモナドやSTモナドなどの既存のモナドで並列処理の順序を制御できるようにしています。

import Prelude hiding (map)
import Data.Array.Repa

main = do
    let xs' = fromListUnboxed (ix3 2 3 4) [1..24]
    xs  <- computeP $ map (subtract 1) xs'
    ys  <- computeP $ map (subtract 1) (xs :: Array U DIM3 Double)
    zs  <- computeP $ map (/2) xs'
    print $ toList (ys :: Array U DIM3 Double)
    print $ toList (zs :: Array U DIM3 Double)

$ ./Test +RTS -N
[-1.0,0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0,11.0,12.0,13.0,14.0,15.0,16.0
,17.0,18.0,19.0,20.0,21.0,22.0]
[0.5,1.0,1.5,2.0,2.5,3.0,3.5,4.0,4.5,5.0,5.5,6.0,6.5,7.0,7.5,8.0,8.5,9.0,9.5,10.
0,10.5,11.0,11.5,12.0]

 computeP関数の定義に使われているsuspendedComputeP関数とnow関数の具体的な定義を見てみましょう。suspendedComputeP関数は,computeS関数の定義に使われているfillS関数をfillP関数に置き換えただけのものです。

-- | Suspended parallel computation of array elements.
--
--   This version creates a thunk that will evaluate the array on demand.
--   If you force it when another parallel computation is already running
--   then you  will get a runtime warning and evaluation will be sequential. 
--   Use `deepSeqArray` and `now` to ensure that each array is evaluated
--   before proceeding to the next one. 
--  
--   If unsure then just use the monadic version `computeP`. This one ensures
--   that each array is fully evaluated before continuing.
--
suspendedComputeP 
        :: Fill r1 r2 sh e
        => Array r1 sh e -> Array r2 sh e
suspendedComputeP arr1
 = arr1 `deepSeqArray` 
   unsafePerformIO
 $ do   marr2    <- newMArr (size $ extent arr1) 
        fillP arr1 marr2
        unsafeFreezeMArr (extent arr1) marr2
{-# INLINE [4] suspendedComputeP #-}

-- | Sequential computation of array elements.
computeS 
        :: Fill r1 r2 sh e
        => Array r1 sh e -> Array r2 sh e
computeS arr1
 = arr1 `deepSeqArray` 
   unsafePerformIO
 $ do   marr2    <- newMArr (size $ extent arr1) 
        fillS arr1 marr2
        unsafeFreezeMArr (extent arr1) marr2
{-# INLINE [4] computeS #-}

 fillS関数をfillP関数に置き換えるというだけでは何を並列化しているのかがわかりにくいと思います。そこで,unsafePerformIO関数を利用して行っている処理について簡単に説明しましょう。

 newMArrは,指定した大きさのMArr型の可変配列を作成する関数です。unsafeFreezeMArrは,可変配列をArray型の不変配列として返す関数です。newMArrとunsafeFreezeMArrは,Fillableクラスのメソッドとして定義されています。newMArrとunsafeFreezeMArrで扱うMArr型も,Fillableクラスに属する型族として定義されています。

-- Fillable -------------------------------------------------------------------
-- | Class of manifest array representations that can be filled in parallel 
--   and then frozen into immutable Repa arrays.
class Fillable r e where

 -- | Mutable version of the representation.
 data MArr r e

 -- | Allocate a new mutable array of the given size.
 newMArr          :: Int -> IO (MArr r e)

 -- | Write an element into the mutable array.
 unsafeWriteMArr  :: MArr r e -> Int -> e -> IO ()

 -- | Freeze the mutable array into an immutable Repa array.
 unsafeFreezeMArr :: sh  -> MArr r e -> IO (Array r sh e)

 -- | Ensure the strucure of a mutable array is fully evaluated.
 deepSeqMArr      :: MArr r e -> a -> a

 -- | Ensure the array is still live at this point.
 --   Needed when the mutable array is a ForeignPtr with a finalizer.
 touchMArr        :: MArr r e -> IO ()

 型クラスに属する関連型の記法を使っているため少し表現が異なっていますが,MArr型はArray型と同じ型族です。MArr型族では,「Array型族で定義した内部表現」に対応する「可変配列としての内部表現」を定義します。

 Fillableクラスでは,MArr型の可変配列に要素を書き込むunsafeFreezeMArrメソッドなども提供されています。このようにFillableクラスでは,処理結果を新しい配列として返すのに必要な「新しく可変配列を作成し,可変配列に要素を書き込み,不変配列として返す処理」が抽象化されています。

 Fiallableクラスのインスタンスの例を見てみましょう。

-- Fill -----------------------------------------------------------------------
-- | Filling of unboxed vector arrays.
instance U.Unbox e => Fillable U e where
 data MArr U e 
  = UMArr (UM.IOVector e)

 newMArr n
  = liftM UMArr (UM.new n)
 {-# INLINE newMArr #-}

 unsafeWriteMArr (UMArr v) ix
  = UM.unsafeWrite v ix
 {-# INLINE unsafeWriteMArr #-}

 unsafeFreezeMArr sh (UMArr mvec)     
  = do  vec     <- U.unsafeFreeze mvec
        return  $  AUnboxed sh vec
 {-# INLINE unsafeFreezeMArr #-}

 deepSeqMArr (UMArr vec) x
  = vec `seq` x
 {-# INLINE deepSeqMArr #-}

 touchMArr _ 
  = return ()
 {-# INLINE touchMArr #-}

 FillableクラスのU型に対するインスタンスでは,MArr型にU型のタグを渡した場合の可変配列の内部表現として,非ボックス化MVectorの一種である非ボックス化IOVector型を使っています。したがって,「非ボックス化Vectorを内部表現として使うU型の配列」を処理結果として返す場合には,「新しく可変配列を作成し,可変配列に要素を書き込み,不変配列として返す処理」には非ボックス化IOVectorが使われることになります。

 Fillableクラスの各メソッドは,U型の配列を可変配列として扱う場合(MArr U型)の内部表現である非ボックス化IOVectorと,不変配列として扱う場合(Array U型)の内部表現である非ボックス化Vectorの両方に合わせた形で定義されています。新しく可変配列を作成するnewMArrメソッドの処理では,new関数を使って作成した非ボックス化IOVectorをMArr U型のUMArrデータ構成子に包んで返しています。unsafeFreezeMArrメソッドの可変配列を不変配列にして返す処理では,非ボックス化IOVectorを非ボックス化Vectorに変換し,その結果をArray U型のAUnboxedデータ構成子に包んで返します。

 newMArrの定義に使われているnew関数は,並列化を意識した定義になっていないため並列化できません。また,unsafeFreezeMArrは本質的に並列化できません。このため,suspendedComputeP関数でもcomputeS関数と同様に,並列化を意識した特別な関数ではなく逐次処理を行うnewMArrとunsafeFreezeMArrをそのまま使っています。

 一方,可変配列に対する書き込み処理には並列化の余地があります。これがcomputeS関数の定義で使われているfillSとsuspendedComputeP関数の定義で使われているfillPの違いになっています。

 では,fillSとfillPの定義を見てみましょう。fillSとfillPはFillクラスのメソッドです。

-- Fill -----------------------------------------------------------------------
-- | Compute all elements defined by an array and write them to a fillable
--   representation.
--  
--   Note that instances require that the source array to have a delayed
--   representation such as `D` or `C`. If you want to use a pre-existing
--   manifest array as the source then `delay` it first.
class (Shape sh, Repr r1 e, Fillable r2 e) => Fill r1 r2 sh e where
 -- | Fill an entire array sequentially.
 fillS          :: Array r1 sh e -> MArr r2 e -> IO ()

 -- | Fill an entire array in parallel.
 fillP          :: Array r1 sh e -> MArr r2 e -> IO ()

 FillクラスのD型に対するインスタンスでは「D型の配列の各要素を評価した結果を,unsafeWriteMArrメソッドを使ってMArr型に対して書き込む」という形で,fillSとfillPが定義されています。unsafeWriteMArrメソッドはFillableクラスのメソッドです。

-- Fill -----------------------------------------------------------------------
-- | Compute all elements in an array.
instance (Fillable r2 e, Shape sh) => Fill D r2 sh e where
 fillP (ADelayed sh getElem) marr
  = marr `deepSeqMArr` 
    do  traceEventIO "Repa.fillP[Delayed]: start"
        fillChunkedP (size sh) (unsafeWriteMArr marr) (getElem . fromIndex sh) 
        touchMArr marr
        traceEventIO "Repa.fillP[Delayed]: end"
 {-# INLINE [4] fillP #-}

 fillS (ADelayed sh getElem) marr
  = marr `deepSeqMArr` 
    do  traceEventIO "Repa.fillS[Delayed]: start"
        fillChunkedS (size sh) (unsafeWriteMArr marr) (getElem . fromIndex sh)
        touchMArr marr
        traceEventIO "Repa.fillS[Delayed]: end"

 {-# INLINE [4] fillS #-}

 新しく作成する配列の要素を満たす処理を行うのがFillクラスのメソッド,Fillクラスのメソッドによって要素を満たすことのできる配列を定義するのがFillableクラスという関係になっています。具体的には,Fillableクラスのインスタンスとして定義された型に対して,配列を満たす処理を逐次的に実行するのがfillSメソッド,配列を満たす処理を並列に実行するのがfillPメソッドです。

 fillP関数では,配列を満たす処理の並列化のために,「配列に格納するべき値を評価し,評価された結果として得られた値で配列を満たす処理」を適当なチャンク(ブロック)単位に分けて並列に実行しています。map関数やzipWith関数では,配列内の要素間の依存関係や配列内の要素を使った処理の順番に対する依存関係は存在しないので,このようなやり方で問題なく並列化できます。

 次にnow関数の定義を見てみましょう。

-- | Monadic version of `deepSeqArray`. 
-- 
--   Forces an suspended array computation to be completed at this point
--   in a monadic computation.
--
-- @ do  let arr2 = suspendedComputeP arr1
--     ...
--     arr3 <- now $ arr2
--     ...
-- @
--
now     :: (Shape sh, Repr r e, Monad m)
        => Array r sh e -> m (Array r sh e)
now arr
 = do   arr `deepSeqArray` return ()
        return arr
{-# INLINE [4] now #-}

 now関数の定義に使われているdeepSeqArray関数は,いわばrepaのArray型に対するdeepseq関数のようなもので,配列の中身を完全に評価します。

Prelude Data.Array.Repa> :t deepSeqArray
deepSeqArray :: (Shape sh, Repr r e) => Array r sh e -> b -> b

 now関数では,deepSeqArray関数の第2引数として「return ()」を渡すことで,配列を評価する処理をモナド化しています。「arr `deepSeqArray` return arr」ではなく,「return ()」を使ってモナド化し,その後「return arr」で評価したArray型を返す形にしている点に注意してください。このような回りくどいやり方が必要なのは,seq関数と同様に,deepseqArray関数には「第2引数を必要とする時には,第1引数の配列も評価する」という意味しか与えらず,「第1引数を評価し,それから第2引数を返す」という挙動は保証されないためです(参考リンク1参考リンク2参考リンク3)。

 このようにnow関数は,配列の評価を行う処理がモナドを使ってきちんと順序付けられるよう注意深く定義されています。now関数を使うことで,computeP関数ではモナドを使って並列処理の実行を順序付けることができるのです。

 なお,computeP関数とcomputeS関数には,返す配列をU型の配列に限定したcomputeUnboxedP関数やcomputeUnboxedS関数などの変種も用意されています。

-- Conversions ----------------------------------------------------------------
-- | Sequential computation of array elements..
--
--   * This is an alias for `computeS` with a more specific type.
--
computeUnboxedS
        :: Fill r1 U sh e
        => Array r1 sh e -> Array U sh e
computeUnboxedS = computeS
{-# INLINE computeUnboxedS #-}


-- | Parallel computation of array elements.
--
--   * This is an alias for `computeP` with a more specific type.
--
computeUnboxedP
        :: (Fill r1 U sh e, Monad m, U.Unbox e)
        => Array r1 sh e -> m (Array U sh e)
computeUnboxedP = computeP
{-# INLINE computeUnboxedP #-}