16

go ワーカーの末尾再帰ループ パターンは、純粋なコードを記述する場合に非常にうまく機能するようです。STモナドに対してそのようなループを書く同等の方法は何でしょうか? より具体的には、ループの繰り返しで新しいヒープが割り当てられるのを避けたいと考えています。私の推測では、ループ全体で変化しているすべての値が各反復で渡されるようにコードを書き直すか、反復全体でそれらの値にレジスタの場所 (またはスピルの場合はスタック) を使用できるようにする必要がありますCPS transformation。fixST以下に簡単な例を示します (実行しようとしないでください。セグメンテーション違反でクラッシュする可能性があります!)。findSnakesこれには、goワーカー パターンを持つ関数が呼び出されますが、変化する状態値はアキュムレータ引数を介して渡されません。

{-# LANGUAGE BangPatterns #-}
module Test where

import Data.Vector.Unboxed.Mutable as MU
import Data.Vector.Unboxed as U hiding (mapM_)
import Control.Monad.ST as ST
import Control.Monad.Primitive (PrimState)
import Control.Monad as CM (when,forM_)
import Data.Int

type MVI1 s  = MVector (PrimState (ST s)) Int

-- function to find previous y
findYP :: MVI1 s -> Int -> Int -> ST s Int
findYP fp k offset = do
              y0 <- MU.unsafeRead fp (k+offset-1) >>= \x -> return $ 1+x
              y1 <- MU.unsafeRead fp (k+offset+1)
              if y0 > y1 then return y0
              else return y1
{-#INLINE findYP #-}

findSnakes :: Vector Int32 -> MVI1 s ->  Int -> Int -> (Int -> Int -> Int) -> ST s ()
findSnakes a fp !k !ct !op = go 0 k
     where
           offset=1+U.length a
           go x k'
            | x < ct = do
                yp <- findYP fp k' offset
                MU.unsafeWrite fp (k'+offset) (yp + k')
                go (x+1) (op k' 1)
            | otherwise = return ()
{-#INLINE findSnakes #-}

cmm出力を見るとghc 7.6.1(私の限られた知識でcmm- 間違っていたら訂正してください)、この種のコール フローがループインs1tb_info(各反復でヒープ割り当てとヒープ チェックが発生します) であることがわかります。

findSnakes_info -> a1_r1qd_info -> $wa_r1qc_info (new stack allocation, SpLim check)
-> s1sy_info -> s1sj_info: if arg > 1 then s1w8_info else R1 (can't figure out 
what that register points to)

-- I am guessing this one below is for go loop
s1w8_info -> s1w7_info (big heap allocation, HpLim check) -> s1tb_info: if arg >= 1
then s1td_info else R1

s1td_info (big heap allocation, HpLim check) -> if arg >= 1 then s1tb_info
(a loop) else s1tb_info (after executing a different block of code)

私の推測ではarg >= 1、cmmコード内のフォームのチェックは、goループが終了したかどうかを判断することです。それが正しければ、goループがループを越えて通過するように書き直されない限りyp、新しい値のためにループを越えてヒープ割り当てが行われるようです (私はypそのヒープ割り当てを引き起こしていると推測しています)。go上記の例でループを記述する効率的な方法は何でしょうか? ypループで引数として渡すか、同等の方法で変換する必要があるとgo思います。上記のループを書き直してヒープ割り当てを削除する良い方法が思いつかないので、助けていただければ幸いです。fixSTCPSgo

4

1 に答える 1