Haskellでのキャッシュと明示的な並列処理

Question

現在、私のソリューションをProjet Eulerのproblem 14に最適化しようとしています。 私は本当にHaskellのを楽しみにして私はそれが問題のこれらの種類のために非常に良いフィットだと思う、ここで私が試した三つの異なるソリューションがあります：あなたは、実際の問題を見れば

import Data.List (unfoldr, maximumBy) 
import Data.Maybe (fromJust, isNothing) 
import Data.Ord (comparing) 
import Control.Parallel 

next :: Integer -> Maybe (Integer) 
next 1 = Nothing 
next n 
    | even n = Just (div n 2) 
    | odd n = Just (3 * n + 1) 

get_sequence :: Integer -> [Integer] 
get_sequence n = n : unfoldr (pack . next) n 
    where pack n = if isNothing n then Nothing else Just (fromJust n, fromJust n) 

get_sequence_length :: Integer -> Integer 
get_sequence_length n 
    | isNothing (next n) = 1 
    | otherwise = 1 + (get_sequence_length $ fromJust (next n)) 

-- 8 seconds 
main1 = print $ maximumBy (comparing length) $ map get_sequence [1..1000000] 

-- 5 seconds 
main2 = print $ maximum $ map (\n -> (get_sequence_length n, n)) [1..1000000] 

-- Never finishes 
main3 = print solution 
    where 
    s1 = maximumBy (comparing length) $ map get_sequence [1..500000] 
    s2 = maximumBy (comparing length) $ map get_sequence [500001..10000000] 
    solution = (s1 `par` s2) `pseq` max s1 s2 

は今、多くの可能性がキャッシュにありますほとんどの新しいシーケンスには既に計算されているサブシーケンスが含まれるためです。比較のために

は、私もCでバージョンを書いた：
は、キャッシングと実行時間：0.03秒
キャッシングせずに実行時間：0.3秒だけ非常識だ

！確かに、キャッシングは時間を10分の1に短縮しましたが、キャッシングを行わなくても私のHaskellコードよりも少なくとも17倍は速いです。

私のコードで何が問題になっていますか？ なぜHaskellは私のために関数呼び出しをキャッシュしませんか？関数は純粋なキャッシングであるため、キャッシュは些細なものではなく、使用可能なメモリの問題だけで済むはずです。

私の3番目の並列バージョンの問題点は何ですか？なぜ終わらないの？

言語としてのHaskellに関して、コンパイラは自動的にいくつかのコード（折りたたみ、マップなど）を並列化するか、Control.Parallelを使用して明示的に行う必要がありますか？

編集：私はthisに遭遇しました。彼らは、彼の機能が末尾再帰的ではないと述べた。私のget_sequence_lengthテールは再帰的ですか？どうすればいい？

EDIT2：ダニエル・へ
：返信用
どうもありがとう、本当にすごいです。 私はあなたの改善を試してきました。私は本当に悪いことをいくつか見つけました。

私はWindws 7（64ビット）、8GバイトのRAMを搭載した3.3 GHZクアッドコアについてテストを行っています。
Integerをintに置き換えて言うと、まず、メモリが足りなくなったときに、+ RTS kSize -RTSを指定してもメモリが不足していても、奇妙な結果が出ました。

は最終的に私はすごい...

、Windows上のすべてのHaskellプログラムは、32ビットとして実行されているので、int型は無限再帰を引き起こしあふれたことを意味し、（stackoverflowのは素晴らしいです...）thisを見つけました代わりにLinux仮想マシン（64ビットghc）でテストを実行し、同様の結果が得られました。

Answer 1

さて、上から始めましょう。まず重要なことは、コンパイルと実行に使用している正確なコマンドラインを与えることです。私の答えのために、私はすべてのプログラムのタイミングのために、このラインを使用します：

ghc -O2 -threaded -rtsopts test && time ./test +RTS -N 

次のアップ：タイミングがマシンからマシンに大きく異なるため、私たちは、私のマシンとあなたのプログラムのためのいくつかの基準タイミングを与えるでしょう。ここに私のコンピュータのuname -aの出力があります：

Linux sorghum 3.4.4-2-ARCH #1 SMP PREEMPT Sun Jun 24 18:59:47 CEST 2012 x86_64 Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz GenuineIntel GNU/Linux 

のハイライトは以下のとおりです。クアッドコア、2.4GHz帯、64ビット。

はmain1使用：30.42s user 2.61s system 149% cpu 22.025 total
main2使用：21.42s user 1.18s system 129% cpu 17.416 total
main3使用：、s2における範囲の端からゼロのいずれかを除去することにより、第一：22.71s user 2.02s system 220% cpu 11.237 total

実際に、私は2つの方法でmain3修飾しました第2に、max s1 s2をmaximumBy (comparing length) [s1, s2]に変更すると、誤って正しい答えが計算されるだけです。 =）

ここでは、シリアル速度に焦点を当てます。 （あなたの直接の質問の1つに答えるには、いいえ、GHCはあなたのプログラムを自動的に並列化したりメモしたりしません。どちらも見積もりが難しいオーバーヘッドがあります。この答えのシリアルソリューションでも100％を超えるCPU使用率が得られている理由は考えられませんが、別のスレッドやそのようなものでガベージコレクションが起こっている可能性があります）main2から開始します。 。少しブーストを取得するための最も安価な方法はIntegerからIntに、すべてのタイプの署名を変更することです：Intを使用して

：11.17s user 0.50s system 129% cpu 8.986 total（約2倍速い）

次のブーストは、（内側のループに割り当てを減らすことから来ています中間のMaybeの値を削除します）。これを使用する

import Data.List 
import Data.Ord 

get_sequence_length :: Int -> Int 
get_sequence_length 1 = 1 
get_sequence_length n 
    | even n = 1 + get_sequence_length (n `div` 2) 
    | odd n = 1 + get_sequence_length (3 * n + 1) 

lengths :: [(Int,Int)] 
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000] 

main = print (maximumBy (comparing fst) lengths) 

：4.84s user 0.03s system 101% cpu 4.777 total次のブーストがevenとdivよりも高速演算を使用してから来て

：

import Data.Bits 
import Data.List 
import Data.Ord 

even' n = n .&. 1 == 0 

get_sequence_length :: Int -> Int 
get_sequence_length 1 = 1 
get_sequence_length n = 1 + get_sequence_length next where 
    next = if even' n then n `quot` 2 else 3 * n + 1 

lengths :: [(Int,Int)] 
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000] 

main = print (maximumBy (comparing fst) lengths) 

この使用：自宅で一緒に、次の人のために1.27s user 0.03s system 105% cpu 1.232 total

を、これは私たちが始めたmain2よりも約17倍高速ですD - メモ化のためにC.

に切り替えると競争力の向上は、いくつかの選択肢があります。一番簡単なのは、data-memocombinatorsのような既存のパッケージを使用して、不変の配列を作成し、そこから読み取ることです。タイミングは、この配列の適切なサイズを選択することにかなり敏感です。この問題のために、私は50000がかなり良い上限であることを発見しました。これにより

import Data.Bits 
import Data.MemoCombinators 
import Data.List 
import Data.Ord 

even' n = n .&. 1 == 0 

pre_length :: (Int -> Int) -> (Int -> Int) 
pre_length f 1 = 1 
pre_length f n = 1 + f next where 
    next = if even' n then n `quot` 2 else 3 * n + 1 

get_sequence_length :: Int -> Int 
get_sequence_length = arrayRange (1,50000) (pre_length get_sequence_length) 

lengths :: [(Int,Int)] 
lengths = map (\n -> (get_sequence_length n, n)) [1..1000000] 

main = print (maximumBy (comparing fst) lengths) 

：0.53s user 0.10s system 149% cpu 0.421 total

すべての最速は、メモ化ビットのための可変、箱なしのアレイを使用することです。それははるかに慣用的ではありませんが、素人のスピードです。速度は、この配列のサイズに対しては、配列の大きさがあなたが答えを求めている最大のものと同じくらい大きい限り、それほど敏感ではありません。これにより

import Control.Monad 
import Control.Monad.ST 
import Data.Array.Base 
import Data.Array.ST 
import Data.Bits 
import Data.List 
import Data.Ord 

even' n = n .&. 1 == 0 
next n = if even' n then n `quot` 2 else 3 * n + 1 

get_sequence_length :: STUArray s Int Int -> Int -> ST s Int 
get_sequence_length arr n = do 
    bounds@(lo,hi) <- getBounds arr 
    if not (inRange bounds n) then (+1) `fmap` get_sequence_length arr (next n) else do 
     let ix = n-lo 
     v <- unsafeRead arr ix 
     if v > 0 then return v else do 
      v' <- get_sequence_length arr (next n) 
      unsafeWrite arr ix (v'+1) 
      return (v'+1) 

maxLength :: (Int,Int) 
maxLength = runST $ do 
    arr <- newArray (1,1000000) 0 
    writeArray arr 1 1 
    loop arr 1 1 1000000 
    where 
    loop arr n len 1 = return (n,len) 
    loop arr n len n' = do 
     len' <- get_sequence_length arr n' 
     if len' > len then loop arr n' len' (n'-1) else loop arr n len (n'-1) 

main = print maxLength 

：0.16s user 0.02s system 138% cpu 0.130 total（メモ化Cバージョンと競合する）

Answer 2

GHCは何も自動的に並列化しません。そして、あなたが推測するように、get_sequence_lengthはテール再帰的ではありません。 hereを参照してください。そして、コンパイラが（あなたに最適な最適化をしていない限り）コンパイラがどのようにそれらの再帰的な追加を評価することができないかを考えてみましょう。あなたは通常、良いことではない "サンクを築く"です。

代わりに、再帰ヘルパー関数を呼び出してアキュムレータを渡すか、foldrという用語で定義してみてください。