ベクトル ライブラリとステート モナドを使用して Haskell で最長共通サブシーケンス アルゴリズムを作成しています(Miller O(NP) アルゴリズムの非常に命令的で変更可能な性質をカプセル化するため)。私はすでにそれを必要とするいくつかのプロジェクトのために C でそれを書いており、C に匹敵する優れたパフォーマンスを備えた命令型グリッドウォーク アルゴリズムを記述する方法を探求する方法として、Haskell でそれを書いています。同じ入力に対してCバージョンよりも約4倍遅いです（そして、適切な最適化フラグでコンパイルされました-システムクロック時間とCriterionHaskell と C のバージョン間の相対時間測定値、および同じデータ型 (大きい入力と小さい入力の両方) を検証するメソッド)。パフォーマンスの問題がどこにあるのかを突き止めようとしており、フィードバックをいただければ幸いです。特に、ここで頻繁に使用しているベクター ライブラリで、よく知られたパフォーマンスの問題が発生している可能性があります。
私のコードには、最も頻繁に呼び出され、ほとんどの作業を行う gridWalk という関数が 1 つあります。パフォーマンスの低下が見られる可能性がありますが、それが何であるかはわかりません。完全な Haskell コードはこちらです。以下のコードのスニペット:
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 (when)
import Data.STRef (newSTRef, modifySTRef, readSTRef)
import Data.Int
type MVI1 s = MVector (PrimState (ST s)) Int
cmp :: U.Vector Int32 -> U.Vector Int32 -> Int -> Int -> Int
cmp a b i j = go 0 i j
where
n = U.length a
m = U.length b
go !len !i !j| (i<n) && (j<m) && ((unsafeIndex a i) == (unsafeIndex b j)) = go (len+1) (i+1) (j+1)
| otherwise = len
-- function to find previous y on diagonal k for furthest point
findYP :: MVI1 s -> Int -> Int -> ST s (Int,Int)
findYP fp k offset = do
let k0 = k+offset-1
k1 = k+offset+1
y0 <- MU.unsafeRead fp k0 >>= \x -> return $ 1+x
y1 <- MU.unsafeRead fp k1
if y0 > y1 then return (k0,y0)
else return (k1,y1)
{-#INLINE findYP #-}
gridWalk :: Vector Int32 -> Vector Int32 -> MVI1 s -> Int -> (Vector Int32 -> Vector Int32 -> Int -> Int -> Int) -> ST s ()
gridWalk a b fp !k cmp = {-#SCC gridWalk #-} do
let !offset = 1+U.length a
(!kp,!yp) <- {-#SCC findYP #-} findYP fp k offset
let xp = yp-k
len = {-#SCC cmp #-} cmp a b xp yp
x = xp+len
y = yp+len
{-#SCC "updateFP" #-} MU.unsafeWrite fp (k+offset) y
return ()
{-#INLINE gridWalk #-}
-- The function below executes ct times, and updates furthest point as they are found during furthest point search
findSnakes :: Vector Int32 -> Vector Int32 -> MVI1 s -> Int -> Int -> (Vector Int32 -> Vector Int32 -> Int -> Int -> Int) -> (Int -> Int -> Int) -> ST s ()
findSnakes a b fp !k !ct cmp op = {-#SCC findSnakes #-} U.forM_ (U.fromList [0..ct-1]) (\x -> gridWalk a b fp (op k x) cmp)
{-#INLINE findSnakes #-}
コスト センターの注釈をいくつか追加し、テスト用に特定の LCS 入力でプロファイリングを実行しました。ここに私が得るものがあります：
total time = 2.39 secs (2394 ticks @ 1000 us, 1 processor)
total alloc = 4,612,756,880 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
gridWalk Main 67.5 52.7
findSnakes Main 23.2 27.8
cmp Main 4.2 0.0
findYP Main 3.5 19.4
updateFP Main 1.6 0.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 64 0 0.0 0.0 100.0 100.0
main Main 129 0 0.0 0.0 0.0 0.0
CAF Main 127 0 0.0 0.0 100.0 100.0
findSnakes Main 141 0 0.0 0.0 0.0 0.0
main Main 128 1 0.0 0.0 100.0 100.0
findSnakes Main 138 0 0.0 0.0 0.0 0.0
gridWalk Main 139 0 0.0 0.0 0.0 0.0
cmp Main 140 0 0.0 0.0 0.0 0.0
while Main 132 4001 0.1 0.0 100.0 100.0
findSnakes Main 133 12000 23.2 27.8 99.9 99.9
gridWalk Main 134 16004000 67.5 52.7 76.7 72.2
cmp Main 137 16004000 4.2 0.0 4.2 0.0
updateFP Main 136 16004000 1.6 0.0 1.6 0.0
findYP Main 135 16004000 3.5 19.4 3.5 19.4
newVI1 Main 130 1 0.0 0.0 0.0 0.0
newVI1.\ Main 131 8004 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal 112 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding 104 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 102 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD 95 0 0.0 0.0 0.0 0.0
プロファイリング出力を正しく解釈している場合 (そして、プロファイリングによる歪みがあまりないと仮定すると)、gridWalkほとんどの時間がかかりますが、主な機能cmpとfindYPで重労働を行うものはgridWalk、プロファイリング レポートにほとんど時間がかからないようです。したがって、おそらくボトルネックは、関数が呼び出しに使用するforM_ラッパーにありますか? ヒープ プロファイルも非常にきれいに見えます。findSnakesgridWalk
核心を読んで、何も飛び出さない。内部ループのいくつかの値がボックス化されている可能性があると思いましたが、コアでそれらを見つけられません。パフォーマンスの問題が、私が見逃した単純なものによるものであることを願っています。
アップデート
@DanielFischer の提案に従って、C バージョンの 4 倍から 2.5 倍のパフォーマンスを向上させるin関数forM_にData.Vector.Unboxedを置き換えました。Haskell と C のバージョンは、試してみたい場合にここに投稿されています。Control.MonadfindSnakes
私はまだコアを掘り下げて、ボトルネックがどこにあるかを確認しています。gridWalk最も頻繁に呼び出される関数であり、それが適切に機能するためには、ループを条件チェックとインライン化されたコードの適切な反復内部ループにlcsh減らす必要があります。アセンブリでは、これはループには当てはまらないと思いますが、コアの変換とアセンブリで名前がマングルされた GHC 関数の場所を特定することについてあまり知識がないので、問題が発生するまで辛抱強くプラグインするだけの問題だと思います。私はそれを理解します。その間、パフォーマンスの修正に関する指針があれば、それらは高く評価されます。whileM_findSnakeswhileM_
私が考えることができる別の可能性は、関数呼び出し中のヒープ チェックのオーバーヘッドです。プロファイリング レポートに見られるように、gridWalk16004000 回呼び出されます。ヒープ チェックに 6 サイクルを想定すると (それよりも少ないと推測されますが、それでも想定しておきましょう)、3.33 GHz ボックスでは 96024000 サイクルで約 0.02 秒です。
また、いくつかのパフォーマンス数値:
Haskell code (GHC 7.6.1 x86_64): 修正前は ~0.25 秒でしforM_た。
time ./T
1
real 0m0.150s
user 0m0.145s
sys 0m0.003s
C code (gcc 4.7.2 x86_64):
time ./test
1
real 0m0.065s
user 0m0.063s
sys 0m0.000s
更新 2:
更新されたコードはこちらです。を使用STUArrayしても数値は変わりません。パフォーマンスは で約 1.5 倍でMac OS X (x86_64,ghc7.6.1)あり、@DanielFischer が Linux で報告したものとかなり似ています。
Haskell コード:
$ time ./Diff
1
real 0m0.087s
user 0m0.084s
sys 0m0.003s
C コード:
$ time ./test
1
real 0m0.056s
user 0m0.053s
sys 0m0.002s
をちらりと見るとcmm、呼び出しは末尾再帰であり、 によってループになっていますllvm。しかし、新しい反復ごとに、ヒープチェックも呼び出す新しい値が割り当てられるように見えるため、パフォーマンスの違いを説明できる可能性があります。ヒープ チェックと割り当てのオーバーヘッドを回避して、反復間で値が割り当てられないように末尾再帰を記述する方法を考える必要があります。