更新処理を三つに分けて配列のRecyclingを実現

 //演算子の定義に戻りましょう。Data.Vectorモジュールでの//演算子の定義は,以下の通りです。

import qualified Data.Vector.Generic as G
~ 略 ~
(//) :: Vector a   -- ^ initial vector (of length @m@)
                -> [(Int, a)] -- ^ list of index/value pairs (of length @n@) 
                -> Vector a
{-# INLINE (//) #-}
(//) = (G.//)

 Data.Vectorモジュールの//演算子は,Data.Vector.Genericモジュールの//演算子を呼び出しているだけです。vectorパッケージでは,Data.Vector.Genericモジュールやその配下のモジュールに存在する同名の関数への処理の委譲がよく利用されます。ただし,こうした定型化された処理の委譲は,今回説明する内容とは関係ありません。以降の説明では,処理の委譲を行っている部分は適宜省略します。

 Data.Vector.Genericモジュールの//演算子の定義は,以下の通りです。

import           Data.Vector.Generic.Mutable ( MVector )
import qualified Data.Vector.Generic.Mutable as M

import qualified Data.Vector.Generic.New as New
import           Data.Vector.Generic.New ( New )

import qualified Data.Vector.Fusion.Stream as Stream
import           Data.Vector.Fusion.Stream ( Stream, MStream, inplace )

~ 略 ~

(//) :: Vector v a => v a        -- ^ initial vector (of length @m@)
                   -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
                   -> v a
{-# INLINE (//) #-}
v // us = update_stream v (Stream.fromList us)

~ 略 ~

update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
{-# INLINE update_stream #-}
update_stream = modifyWithStream M.update

~ 略 ~

-- We have to make sure that this is strict in the stream but we can't seq on
-- it while fusion is happening. Hence this ugliness.
modifyWithStream :: Vector v a
                 => (forall s. Mutable v s a -> Stream b -> ST s ())
                 -> v a -> Stream b -> v a
{-# INLINE modifyWithStream #-}
modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)

 //演算子はupdate_stream関数を呼んでおり,update_stream関数はmodifyWithStream関数を呼んでいます。modifyWithStream関数では,update_stream関数が呼んでいるM.update関数を使って実際の処理を行います。このままでは,処理が複数の関数呼び出しにまたがっていて見通しが悪いので,GHCがコンパイル時に行うのと同じようにインライン化を行ってみましょう。「v // xs」という式を順を追ってインライン化してみます。

    v // xs
==> { //演算子のインライン化 }
    update_stream v (Stream.fromList xs)
==> { update_stream関数のインライン化 }
    modifyWithStream M.update v (Stream.fromList xs)
==> { modifyWithStream関数のインライン化 }
    new (New.modifyWithStream M.update
        (clone v) (Stream.fromList xs))

 インライン化した「new (New.modifyWithStream M.update (clone v) (Stream.fromList xs))」という式のそれぞれの処理を説明していきましょう。fromListは,リストからStream型への変換を行う関数です。

-- | Create a 'Stream' from a list
fromList :: [a] -> Stream a
{-# INLINE fromList #-}
fromList = M.fromList

 modifyWithStreamは,fromListで作成されたStream型を使って処理を行います。cloneは,配列の複製としてNew型の配列を作成する関数です。これらの定義は以下の通りです。

-- | Convert a vector to an initialiser which, when run, produces a copy of
-- the vector.
clone :: Vector v a => v a -> New v a
{-# INLINE_STREAM clone #-}
clone v = v `seq` New.create (
  do
    mv <- M.new (length v)
    unsafeCopy mv v
    return mv)

data New v a = New (forall s. ST s (Mutable v s a))

create :: (forall s. ST s (Mutable v s a)) -> New v a
{-# INLINE create #-}
create p = New p

 New型の定義でSTモナドが使われていることからわかるように,clone関数の結果として返されるNew型には可変配列が格納されています。

 clone関数で使用されているINLINE_STREAMは,GHCが提供する指示文ではなく,C言語のプリプロセサを使って定義されたマクロです。

#define PHASE_STREAM [1]
#define PHASE_INNER  [0]

#define INLINE_STREAM INLINE PHASE_STREAM
#define INLINE_INNER  INLINE PHASE_INNER

 このようにvectorパッケージでは,Cプリプロセサを利用して第38回のコラムで説明した「段階制御の一括管理」を行っています(参考リンク)。

 次に「New.modifyWithStream M.update」を説明しましょう。この部分で,clone関数で作成したNew型の可変配列の要素を更新しています。

 modifyWithStreamはNew型の可変配列に関数を適用する関数であり,updateは指定した配列の要素を書き換える関数です。これら二つの関数を組み合わせることで,New型の配列内要素を更新しています。modifyWithStreamとupdateの定義は以下の通りです。

modifyWithStream :: (forall s. Mutable v s a -> Stream b -> ST s ())
                 -> New v a -> Stream b -> New v a
{-# INLINE_STREAM modifyWithStream #-}
modifyWithStream f (New p) s = s `seq` New (do { v <- p; f v s; return v })

update :: (PrimMonad m, MVector v a)
                        => v (PrimState m) a -> Stream (Int, a) -> m ()
{-# INLINE update #-}
update !v s = Stream.mapM_ upd s
  where
    {-# INLINE_INNER upd #-}
    upd (i,b) = BOUNDS_CHECK(checkIndex) "update" i n
              $ unsafeWrite v i b

    !n = length v

 最後に,new関数によって,New型の可変配列をVector型の不変配列として凍結しています。new関数は,New型から可変配列を取り出し,VectorクラスのunsafeFreezeメソッドを使って可変配列を不変配列に凍結します。

-- Recycling support
-- -----------------

-- | Construct a vector from a monadic initialiser.
new :: Vector v a => New v a -> v a
{-# INLINE_STREAM new #-}
new m = m `seq` runST (unsafeFreeze =<< New.run m)

run :: New v a -> ST s (Mutable v s a)
{-# INLINE run #-}
run (New p) = p

 このように,vectorパッケージでは,Recyclingを可能にするための下準備として,//演算子による更新処理を「複製」「更新」「可変配列の不変配列化」という三つの部分に分けて定義しています。

 //演算子の内部で行われている複製と更新の処理が,参照透明性を崩すような大域的な副作用を発生させることはありません。第20回第21回で説明したように,STモナドでは,可変配列のような更新可能なデータ型をそのままSTモナドの外に持ち出すことを,型によって防いでいます。その結果,更新処理の結果として得られるVector型が不変配列になることが常に保証されます。

 それでは,Recyclingを行うための"clone/new [Vector]"規則を解説しましょう。

{-# RULES
~ 略 ~

"clone/new [Vector]" forall p.
  clone (new p) = p

~ 略 ~
 #-}

 "clone/new [Vector]"規則は,「new関数で配列を不変配列として凍結した直後に,その配列をclone関数で複製する」という処理を除去します。この処理は,//演算子を複数回適用する場合に発生します。newで不変配列として凍結しないのであれば,cloneで配列を複製する必要はないので,//演算子を複数回適用することで発生する「clone (new p)」という処理は無駄です。そこで"clone/new [Vector]"規則を使って「連続した//演算子の適用の間で起こる不変配列化と配列の複製」を除去し,配列の複製が1回で済むように書き換えているのです。

 例を見てみましょう。

    v // xs // ys
==> { //演算子のインライン化 }
    new (New.modifyWithStream M.update
        (clone v) (Stream.fromList xs))
        // ys
==> { //演算子のインライン化 }
    new (New.modifyWithStream M.update
        (clone (new (New.modifyWithStream M.update
        (clone v)
          (Stream.fromList xs))))
          (Stream.fromList ys))
==> { "clone/new [Vector]"規則の適用 }
    new (New.modifyWithStream M.update
        (New.modifyWithStream M.update
        (clone v)
          (Stream.fromList xs))
          (Stream.fromList ys))

 "clone/new [Vector]"規則によって中間での配列の複製が除去され,最初に複製された配列を再利用する形になっているのがわかります。このようにRecyclingでは,配列の更新処理を「複製」「更新」「可変配列の不変配列化」という三つの処理に分解し,書き換え規則を使って中間的な配列の複製を除去します。これにより,配列の複製が1回しか行われなくなり,配列の更新コストを減らせるのです。