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
или эквивалентным способом преобразования fixST
или CPS
. Я не могу придумать хороший способ переписать цикл go
выше, чтобы удалить выделение кучи и позаботится о помощи.