11

関数型言語のコンパイラ/ランタイムは、適用可能な場合、連鎖したすべての反復を1つに減らしますか？プログラマーの観点からは、怠惰やストリームなどの構造を使用して関数型コードを最適化することができますが、話の反対側を知りたいと思っています。私の機能的な例はScalaで書かれていますが、その言語に答えを制限しないでください。

機能的な方法： 

// I assume the following line of code will go
// through the collection 3 times, one for creating it
// one for filtering it and one for summing it 
val sum = (1L to 1000000L).filter(_ % 2 == 0).sum // => 250000500000

コンパイラーに次と同等の命令に最適化してもらいたい： 

/* One iteration only */
long sum, i;
for (i = 1L, sum = 0L; i <= 1000000L; i++) {
  if (i % 2 == 0)
    sum += i;
}
4

3 に答える 3

14

Haskellは定義上非厳密な言語であり、私が知っているすべての実装は、非厳密なセマンティクスを提供するために遅延評価を使用します。

類似のコード（開始と終了の引数があるため、コンパイル時の評価はできません）

val :: Int -> Int -> Int
val low high = sum $ filter even [low .. high]

1回の走査のみで、一定の小さなメモリで合計を計算します。[low .. high]はの構文糖衣でenumFromTo low highあり、の定義enumFromToはInt基本的に

enumFromTo x y
    | y < x     = []
    | otherwise = go x
      where
        go k = k : if k == y then [] else go (k+1)

（実際、GHCの実装ではInt#、ワーカーの効率を理由にボックス化されgoていないを使用しますが、セマンティクスには影響しません。他のIntegralタイプの場合、定義は類似しています）。

の定義filterは

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

およびsum：

sum     l       = sum' l 0
  where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

それを組み立てると、最適化がなくても、評価は続行されます

sum' (filter even (enumFromTo 1 6)) 0
-- Now it must be determined whether the first argument of sum' is [] or not
-- For that, the application of filter must be evaluated
-- For that, enumFromTo must be evaluated
~> sum' (filter even (1 : go 2)) 0
-- Now filter knows which equation to use, unfortunately, `even 1` is False
~> sum' (filter even (go 2)) 0
~> sum' (filter even (2 : go 3)) 0
-- 2 is even, so
~> sum' (2 : filter even (go 3)) 0
~> sum' (filter even (go 3)) (0+2)
-- Once again, sum asks whether filter is done or not, so filter demands another value or []
-- from go
~> sum' (filter even (3 : go 4)) 2
~> sum' (filter even (go 4)) 2
~> sum' (filter even (4 : go 5)) 2
~> sum' (4 : filter even (go 5)) 2
~> sum' (filter even (go 5)) (2+4)
~> sum' (filter even (5 : go 6)) 6
~> sum' (filter even (go 6)) 6
~> sum' (filter even (6 : [])) 6
~> sum' (6 : filter even []) 6
~> sum' (filter even []) (6+6)
~> sum' [] 12
~> 12

もちろん、これはループよりも効率的ではありません。列挙の各要素に対してリストセルを生成する必要があり、次にフィルターを通過する各要素に対してリストセルを生成する必要があり、合計によってすぐに消費されるだけです。 。

メモリ使用量が実際に少ないことを確認しましょう。

module Main (main) where

import System.Environment (getArgs)

main :: IO ()
main = do
    args <- getArgs
    let (low, high) = case args of
                        (a:b:_) -> (read a, read b)
                        _       -> error "Want two args"
    print $ sum $ filter even [low :: Int .. high]

そしてそれを実行し、

$ ./sumEvens +RTS -s -RTS 1 1000000
250000500000
      40,071,856 bytes allocated in the heap
          12,504 bytes copied during GC
          44,416 bytes maximum residency (2 sample(s))
          21,120 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0        75 colls,     0 par    0.00s    0.00s     0.0000s    0.0000s
  Gen  1         2 colls,     0 par    0.00s    0.00s     0.0002s    0.0003s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.01s  (  0.01s elapsed)
  GC      time    0.00s  (  0.00s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.01s  (  0.01s elapsed)

  %GC     time       6.1%  (7.6% elapsed)

  Alloc rate    4,367,976,530 bytes per MUT second

  Productivity  91.8% of total user, 115.8% of total elapsed

50万のリストセル（1）と少しの変更に約40MBを割り当てましたが、最大常駐時間は約44KBでした。上限を1,000万で実行すると、全体の割り当て（および実行時間）は10倍に増加します（一定のものを差し引いたもの）が、最大常駐時間は同じままです。

（1） GHCは列挙とフィルターを融合し、タイプの範囲の偶数のみを生成しますInt。残念ながら、それはsum左の折り目であり、GHCの融合フレームワークは右の折り目を融合するだけなので、融合することはできません。

さて、も融合するにsumは、リライトルールでそれを行うようにGHCに教える多くの作業を行う必要があります。vector幸いなことに、これはパッケージ内の多くのアルゴリズムで実行されており、それを使用すると、

module Main where

import qualified Data.Vector.Unboxed as U
import System.Environment (getArgs)

val :: Int -> Int -> Int
val low high = U.sum . U.filter even $ U.enumFromN low (high - low + 1)

main :: IO ()
main = do
    args <- getArgs
    let (low, high) = case args of
                        (a:b:_) -> (read a, read b)
                        _       -> error "Want two args"
    print $ val low high

リストセルを割り当てない高速なプログラムが得られ、パイプラインは実際にループに書き直されます。

$ ./sumFilter +RTS -s -RTS 1 10000000
25000005000000
          72,640 bytes allocated in the heap
           3,512 bytes copied during GC
          44,416 bytes maximum residency (1 sample(s))
          17,024 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0         0 colls,     0 par    0.00s    0.00s     0.0000s    0.0000s
  Gen  1         1 colls,     0 par    0.00s    0.00s     0.0001s    0.0001s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.01s  (  0.01s elapsed)
  GC      time    0.00s  (  0.00s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.01s  (  0.01s elapsed)

  %GC     time       1.0%  (1.2% elapsed)

  Alloc rate    7,361,805 bytes per MUT second

  Productivity  97.7% of total user, 111.5% of total elapsed

val誰かが興味を持っている場合、GHCが（の労働者）のために作成するコアは次のとおりです。

Rec {
Main.main_$s$wfoldlM'_loop [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=3, Caf=NoCafRefs, Str=DmdType LLL]
Main.main_$s$wfoldlM'_loop =
  \ (sc_s303 :: GHC.Prim.Int#)
    (sc1_s304 :: GHC.Prim.Int#)
    (sc2_s305 :: GHC.Prim.Int#) ->
    case GHC.Prim.># sc1_s304 0 of _ {
      GHC.Types.False -> sc_s303;
      GHC.Types.True ->
        case GHC.Prim.remInt# sc2_s305 2 of _ {
          __DEFAULT ->
            Main.main_$s$wfoldlM'_loop
              sc_s303 (GHC.Prim.-# sc1_s304 1) (GHC.Prim.+# sc2_s305 1);
          0 ->
            Main.main_$s$wfoldlM'_loop
              (GHC.Prim.+# sc_s303 sc2_s305)
              (GHC.Prim.-# sc1_s304 1)
              (GHC.Prim.+# sc2_s305 1)
        }
    }
end Rec }
于 2013-01-07T23:43:18.763 に答える
2

数年前、まさにこのトピックに関する2つのブログ投稿を投稿しました。

http://jnordenberg.blogspot.de/2010/03/scala-stream-fusion-and-specialization.html http://jnordenberg.blogspot.de/2010/05/scala-stream-fusion-and-specialization.html

それ以来、Scalaコンパイラーによって行われる特殊化と最適化はかなり改善されていることに注意してください（おそらくホットスポットでも）。そのため、今日の結果はさらに良くなる可能性があります。

于 2013-01-08T12:50:21.687 に答える
2

理論的には、あるコメント者が書いたように、コンパイラはこれをコンパイル時の結果に減らすことができます。これが一部のマクロで行われることは想像に難くないですが、一般的なケースではほとんどありません。

呼び出しを挿入する.viewと、Scalaで怠惰なセマンティクスが得られるため、命令型コードほど単純ではありませんが、1回の反復のみが実行されます。

val lz = (1L to 1000000L).view.filter(_ % 2 == 0) // SeqView (lazy)!
lz.sum

PSそれ以外の場合は3回の反復があるというあなたの仮定は間違っています。要素に対する反復を含まないを(1L to 1000000L)作成します。NumericRangeしたがって、.view1回の反復を節約できます。

于 2013-01-07T22:43:00.443 に答える