performance - なぜ `(map digitToInt) 。show`はとても速いですか？

Question

非負Integerを数字のリストに変換することは、一般的に次のように行われます。

import Data.Char

digits :: Integer -> [Int]
digits = (map digitToInt) . show

文字列変換を行わずにタスクを実行するためのより直接的な方法を見つけようとしていましたが、より高速なものを思いつくことができません。

私がこれまで試してきたこと：

ベースライン:

digits :: Int -> [Int]
digits = (map digitToInt) . show

StackOverflow に関する別の質問からこれを取得しました。

digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)

自分で巻こうとしている：

digits3 :: Int -> [Int]
digits3 = reverse . revDigits3

revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
               (0, digit) -> [digit]
               (rest, digit) -> digit:(revDigits3 rest)

これはに触発されshowIntましたNumeric:

digits4 n0 = go n0 [] where
    go n cs
        | n < 10    =  n:cs
        | otherwise =  go q (r:cs)
        where
        (q,r) = n `quotRem` 10

さてベンチマーク。注: を使用して評価を強制していfilterます。

λ>:set +s
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000]
2400000
(1.58 secs, 771212628 bytes)

これが参考です。今ではdigits2：

λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000]
2400000
(5.47 secs, 1256170448 bytes)

それは3.46倍長いです。

λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)

digits34.89倍遅いです。楽しみのために、 revDigits3 のみを使用して、reverse.

λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000]
2400000
(8.28 secs, 1277538760 bytes)

奇妙なことに、これはさらに遅く、5.24倍遅いです。

そして最後のもの：

λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000]
2400000
(16.48 secs, 1779445968 bytes)

これは10.43倍遅いです。

算術演算とコンスのみを使用すると、文字列変換を伴うものよりも優れているという印象を受けました。どうやら、私には理解できない何かがあるようです。

それで、どんなトリックですか？なぜdigitsそんなに速いのですか？

GHC 6.12.3 を使用しています。

score 30 · Accepted Answer

まだコメントを追加できないので、もう少し作業を行ってすべてを分析します。分析を一番上に置いています。ただし、関連データは以下のとおりです。(注: これはすべて 6.12.3 でも行われます - GHC 7 の魔法はまだありません。)

分析：

バージョン 1: show は int、特に私たちが持っているような短いものにはかなり適しています。文字列の作成は、実際には GHC でまともな傾向があります。ただし、文字列への読み取りとファイルへの大きな文字列の書き込み (または、そうしたくない場合でも stdout) は、コードが完全にクロールできる場所です。これが非常に高速である理由の背後にある詳細の多くは、Int の show 内の巧妙な最適化によるものであると思われます。

バージョン 2:これは、コンパイル時に最も低速でした。いくつかの問題: reverse は引数が厳密です。これが意味することは、次の要素を計算している間、リストの最初の部分で計算を実行できるという利点がないということです。それらをすべて計算し、それらを反転してから、リストの要素に対して計算 (つまり (`mod` 10) ) を実行する必要があります。これは小さいように見えるかもしれませんが、メモリ使用量が増え (ここでも 5 GB のヒープメモリが割り当てられていることに注意してください)、計算が遅くなる可能性があります。(簡単に言えば、リバースは使用しないでください。)

バージョン 3:リバースを使用しないと言ったことを覚えていますか? これを取り除くと、合計実行時間は 1.79 秒になり、ベースラインよりもわずかに遅くなります。ここでの唯一の問題は、数値を深く掘り下げると、リストの背骨を間違った方向に構築していることです (基本的に、「上に」コンシングするのではなく、再帰を使用してリストにコンシングします)。リスト）。

バージョン 4:これは非常に巧妙な実装です。いくつかの利点があります。1 つは、quotRem はユークリッドアルゴリズムを使用する必要があることです。このアルゴリズムは、より大きな引数で対数的です。(おそらく、Euclid よりも速いかもしれませんが、Euclid よりも定数倍以上速いものはないと思います。) さらに、前回説明したように、リストにコンスを適用するので、リストサンクを解決する必要はありません。 go - リストを解析するために戻ってきたときに、リストはすでに完全に構築されています。ご覧のとおり、これによりパフォーマンスが向上します。

このコードは、GHC で -O3 フラグを使用して実行される多くの最適化がリストの高速化を処理するのに対し、GHCi ではそれを行わないため、おそらく GHCi で最も低速でした。

教訓:正しい方法でコンスをリストに追加し、計算速度を低下させる可能性のある中間の厳密性に注意し、コードのパフォーマンスの詳細な統計を調べる際にいくつかの調査を行います。また、-O3 フラグを付けてコンパイルしてください: そうしないと、GHC を超高速にするために多くの時間を費やしたすべての人が、あなたに大きな古い子犬の目を向けます。

データ：

4 つの関数すべてを 1 つの .hs ファイルにまとめ、使用中の関数を反映するために必要に応じて変更しました。また、制限を 5e6 に引き上げました。これは、コンパイルされたコードが 1e6 で 0.5 秒未満で実行される場合があり、これにより、実行中の測定で粒度の問題が発生し始める可能性があるためです。

コンパイラオプション: ghc --make -O3 [ファイル名].hsを使用して、GHC に最適化を行わせます。数字 +RTS -sstderrを使用して統計を標準エラーにダンプします。

-sstderr にダンプすると、digits1 の場合、次のような出力が得られます。

digits1 +RTS -sstderr
12000000
   2,885,827,628 bytes allocated in the heap
         446,080 bytes copied during GC
           3,224 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  5504 collections,     0 parallel,  0.06s,  0.03s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.61s  (  1.66s elapsed)
  GC    time    0.06s  (  0.03s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.67s  (  1.69s elapsed)

  %GC time       3.7%  (1.5% elapsed)

  Alloc rate    1,795,998,050 bytes per MUT second

  Productivity  96.3% of total user, 95.2% of total elapsed

ここには 3 つの重要な統計があります。

使用中の合計メモリ: わずか 1MB ということは、このバージョンはスペース効率が非常に高いことを意味します。
合計時間: 1.61 秒は今のところ何の意味もありませんが、他の実装と比較してどのように見えるかを見ていきます。
生産性: これはガベージコレクションを差し引いた 100% です。96.3% であるため、これは、メモリ内に横たわっている多くのオブジェクトを作成していないことを意味します..

では、バージョン 2 に進みましょう。

digits2 +RTS -sstderr
12000000
   5,512,869,824 bytes allocated in the heap
       1,312,416 bytes copied during GC
           3,336 bytes maximum residency (1 sample(s))
          13,048 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 10515 collections,     0 parallel,  0.06s,  0.04s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    3.20s  (  3.25s elapsed)
  GC    time    0.06s  (  0.04s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    3.26s  (  3.29s elapsed)

  %GC time       1.9%  (1.2% elapsed)

  Alloc rate    1,723,838,984 bytes per MUT second

  Productivity  98.1% of total user, 97.1% of total elapsed

さて、興味深いパターンが見られます。

同じ量のメモリが使用されています。これは、これが非常に優れた実装であることを意味しますが、違いを見つけることができるかどうかを確認するために、より高いサンプル入力でテストする必要があることを意味する可能性があります.
倍の時間がかかります。これがなぜなのかについては、後でいくつかの推測に戻ります。
実際には多少生産性が向上しますが、どちらのプログラムでも GC が大きな部分を占めていないことを考えると、これは何の役にも立ちません。

バージョン 3:

digits3 +RTS -sstderr
12000000
   3,231,154,752 bytes allocated in the heap
         832,724 bytes copied during GC
           3,292 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  6163 collections,     0 parallel,  0.02s,  0.02s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    2.09s  (  2.08s elapsed)
  GC    time    0.02s  (  0.02s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    2.11s  (  2.10s elapsed)

  %GC time       0.7%  (1.0% elapsed)

  Alloc rate    1,545,701,615 bytes per MUT second

  Productivity  99.3% of total user, 99.3% of total elapsed

さて、奇妙なパターンがいくつか見られます。

使用中の合計メモリはまだ 1MB です。したがって、メモリ効率の悪いものにはヒットしていません。これは良いことです。
digits1 には達していませんが、digits2 にはかなり簡単に勝てます。
非常に小さなGC。(95% を超える生産性は非常に優れているため、ここではあまり重要なことを扱っていないことに注意してください。)

そして最後に、バージョン 4:

digits4 +RTS -sstderr
12000000
   1,347,856,636 bytes allocated in the heap
         270,692 bytes copied during GC
           3,180 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  2570 collections,     0 parallel,  0.00s,  0.01s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

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

  %GC time       0.0%  (0.8% elapsed)

  Alloc rate    1,234,293,036 bytes per MUT second

  Productivity 100.0% of total user, 100.5% of total elapsed

うわー！それを分解しましょう：

まだ合計1MBです。5e5 および 5e7 の入力で 1MB のままであるため、これはほぼ確実にこれらの実装の特徴です。もしそうなら、怠惰の証。
元の時間の約 32% を削減しました。これはかなり印象的です。
ここでのパーセンテージは、超光速粒子の計算ではなく、-sstderr の監視の粒度を反映していると思われます。

score 12 · Accepted Answer

「なぜ mod ではなく rem なのか?」という質問に答えるコメントで。正の値を扱う場合rem x y === mod x y、注意すべき唯一の考慮事項はパフォーマンスです。

> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)

それで、パフォーマンスは何ですか？適切なベンチマークツールを使用しない正当な理由がない限り (怠け者であることも、Criterion を知らないことも正当な理由ではありません)、私は Criterion を使用しました。

$ cat useRem.hs 
import Criterion
import Criterion.Main

list :: [Integer]
list = [1..10000]

main = defaultMain
        [ bench "mod" (nf (map (`mod` 7)) list)
        , bench "rem" (nf (map (`rem` 7)) list)
        ]

このショーを実行すると、（でコンパイルされた）remよりもかなり優れています。mod-O2

$ ./useRem 
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950

benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950

performance - なぜ `(map digitToInt) 。show`はとても速いですか？

2 に答える 2

Related

Reference