Streamに対する処理をRecycling可能に

 Stream Fusionでは,mapやfoldのような逐次処理から中間の配列を除去していました。同様に,Recyclingではランダム・アクセスで行われる配列の更新から中間の配列の複製を除去することで処理を効率化します。これら二つの融合変換を組み合わせれば,配列に対する処理を効率よく行えると思うかもしれません。

 しかし,実際には,これらを単純に組み合わせるだけでは,効率が高い処理を実現することはできません。Stream FusionとRecyclingは互いの実装を知らないため,「map (+1) v // xs」や「map (+1) (v // xs)」のように「逐次処理と配列の更新を組み合わせた処理」を行う場合には,中間の配列を作成してしまうからです。この問題に対処するため,vectorパッケージでは,「Stream Fusionで利用されるstream関数やunstream関数を使った処理」でRecyclingが行えるような工夫が加えられています。具体的には,unstream関数と"stream/unstream"規則の定義を変更し,新たな書き換え規則を追加しています。これらにより,Stream FusionとRecyclingを組み合わせた場合にも効率化が行われるようになっています。

 vectorパッケージでのstream関数とunstream関数の定義を見てみましょう。

-- Conversions to/from Streams
-- ---------------------------

-- | /O(1)/ Convert a vector to a 'Stream'
stream :: Vector v a => v a -> Stream a
{-# INLINE_STREAM stream #-}
stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
  where
    n = length v

    -- NOTE: the False case comes first in Core so making it the recursive one
    -- makes the code easier to read
    {-# INLINE get #-}
    get i | i >= n    = Nothing
          | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)

-- | /O(n)/ Construct a vector from a 'Stream'
unstream :: Vector v a => Stream a -> v a
{-# INLINE unstream #-}
unstream s = new (New.unstream s)

{-# RULES

"stream/unstream [Vector]" forall s.
  stream (new (New.unstream s)) = s

"New.unstream/stream [Vector]" forall v.
  New.unstream (stream v) = clone v

~ 略 ~
 #-}

 注目すべきは,unstream関数が「new (New.unstream s)」というnew関数を利用した形で定義されていることです。同様に,Stream Fusionのための"stream/unstream [Vector]"規則の定義も「stream (new (New.unstream s)) = s」というnew関数を利用した形になっています。こうした定義の変更により,unstream関数が行う処理をRecyclingの対象にすることが可能になります。

 New.unstream関数では,StreamからNew型の配列を作成します。

unstream :: Vector v a => Stream a -> New v a
{-# INLINE_STREAM unstream #-}
unstream s = s `seq` New (MVector.unstream s)

 したがって「New.unstream (stream v)」という式は,配列の複製としてNew型の配列を作成するclone関数の適用と同じ処理になります。"New.unstream/stream [Vector]"規則ではこの事実を利用し,「New.unstream (stream v)」から「clone v」への書き換えを行います。

 新しいunstream関数の定義によって,「map (+1) v // xs」という式がどう効率化されるかを見ていきましょう。

 vectorパッケージのmap関数は,以下のように定義されています。

-- | /O(n)/ Map a function over a vector
map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
{-# INLINE map #-}
map f = unstream . inplace (MStream.map f) . stream

 このmap関数の定義を用いて,「map (+1) v // xs」をインライン化していきましょう。

    map (+1) v // xs
==> { map関数のインライン化 }
    unstream (inplace (MStream.map (+1)) (stream v)) // xs
==> { unstream関数のインライン化 }
    new (New.unstream (inplace (MStream.map (+1)) (stream v)))
        // xs
==> { //演算子のインライン化 }
    new (New.modifyWithStream M.update
        (clone (new (New.unstream (inplace (MStream.map (+1)) (stream v)))))
          (Stream.fromList xs))
==> { "clone/new [Vector]"規則の適用(Recycling) }
    new (New.modifyWithStream M.update
        (New.unstream (inplace (MStream.map (+1)) (stream v)))
          (Stream.fromList xs))

 map関数の定義に使われているunstream関数をインライン化することで,new関数が現れます。次に//演算子をインライン化することで,clone関数が現れます。これらのnew関数とclone関数を"clone/new [Vector]"規則で書き換えることで,map関数と//演算子の間に現れる配列の作成を除去できます。

 「map (+1) v // xs」を効率化した最後の式では,配列はNew.unstreamで1回だけ作成されています。このように,new関数を使用する新しいunstream関数の定義では,"clone/new [Vector]"規則を適用できるようになっています。これにより,実際にはStream FusionではなくRecyclingを使って処理が効率化されています。

 「(map (*2) (map (+1) v)) // xs」のような式であれば,Recyclingだけでなく,「(map (*2) (map (+1) v)) v」の部分でStream Fusionを使った処理の効率化も行われます。

    (map (*2) (map (+1) v)) // xs
==> { map関数のインライン化 }
    (map (*2) (unstream (inplace (MStream.map (+1)) (stream v)))) // xs
==> { unstream関数のインライン化 }
    (map (*2) (new (New.unstream (inplace (MStream.map (+1)) (stream v)))))
        // xs
==> { map関数のインライン化 }
    (unstream (inplace (MStream.map (*2))
       (stream (new (New.unstream
              (inplace (MStream.map (+1)) (stream v)))))))
       // xs
==> { "stream/unstream [Vector]" 規則の適用(Stream Fusion) }
    (unstream (inplace (MStream.map (*2))
              (inplace (MStream.map (+1)) (stream v))))
        // xs
==> { unstream関数のインライン化 }
    (new (New.unstream
              (inplace (MStream.map (*2))
              (inplace (MStream.map (+1)) (stream v)))))
        // xs
==> { //演算子のインライン化 }
    new (New.modifyWithStream M.update
        (clone (new (New.unstream 
              (inplace (MStream.map (*2))
              (inplace (MStream.map (+1)) (stream v))))))
          (Stream.fromList xs))
==> { "clone/new [Vector]"規則の適用(Recycling) }
    new (New.modifyWithStream M.update
        (New.unstream 
              (inplace (MStream.map (*2))
              (inplace (MStream.map (+1)) (stream v))))
          (Stream.fromList xs))

 このように,unstream関数と"stream/unstream"規則の定義を変更した新しいStream Fusionでは,「Stream Fusionによる中間データ構造の除去」と「Recyclingによる配列の再利用」の両者を生かした効率化を行えます。