2

フィボナッチ数列の特定のインデックスで数値を取得するためのさまざまなアプローチを試していましたが、それらは基本的に 2 つのカテゴリに分類できます。

  • リストの作成とインデックスのクエリ
  • 変数の使用 (リストなしで、個別またはタプルの可能性があります)

私は両方の例を選びました：

fibs1 :: Int -> Integer
fibs1 n = fibs1' !! n
    where fibs1' = 0 : scanl (+) 1 fibs1'

fib2 :: Int -> Integer
fib2 n = fib2' 1 1 n where
    fib2' _ b 2 = b
    fib2' a b n = fib2' b (a + b) (n - 1)

fibs1:

real    0m2.356s
user    0m2.310s
sys     0m0.030s

fibs2:

real    0m0.671s
user    0m0.667s
sys     0m0.000s

どちらも 64 ビット GHC 7.6.1 と-O2 -fllvm. それらのコア ダンプの長さは非常に似ていますが、私が解釈するのがあまり得意ではない部分が異なります。

fibs1n = 350000 ( ) で失敗したことには驚きませんでしたStack space overflow。しかし、私はそれがそれほど多くのメモリを使用したという事実に満足していません.

いくつかのことを明確にしたいと思います：

  1. ほとんどのリストはすぐに役に立たなくなるのに、なぜ GC は計算中にリストの先頭を処理しないのですか?
  2. 一度に2つの要素しか必要とされないのに、なぜGHCはリストバージョンを変数バージョンに最適化しないのですか?

編集：申し訳ありませんが、速度の結果を混ぜて修正しました。ただし、私の疑問のうち 3 つのうち 2 つはまだ有効です ;)。

4

1 に答える 1

4

リストのほとんどがすぐに役に立たなくなるのに、なぜ GC は計算中にリストの先頭を処理しないのですか?

fibs1大量のメモリを使用し、scanl怠惰なため遅いです。リスト要素を評価しないため、

fibs1' = 0 : scanl (+) 1 fibs1'

生産する

0 : scanl (+) 1 (0 : more)
0 : 1 : let f2 = 1+0 in scanl (+) f2 (1 : more')
0 : 1 : let f2 = 1+0 in f2 : let f3 = f2+1 in scanl (+) f3 (f2 : more'')
0 : 1 : let f2 = 1+0 in f2 : let f3 = f2+1 in f3 : let f4 = f3+f2 in scanl (+) f4 (f3 : more''')

など。そのため、入れ子になった巨大なサンクをすぐに取得できます。そのサンクが評価されると、スタックにプッシュされ、250000 から 350000 の間のある時点で、デフォルトのスタックには大きすぎます。

また、各リスト要素は、評価されていない間、前の要素への参照を保持するため、リストの先頭をガベージ コレクションすることはできません。

厳密なスキャンを使用する場合、

fibs1 :: Int -> Integer
fibs1 n = fibs1' !! n
  where
    fibs1' = 0 : scanl' (+) 1 fibs1'
    scanl' f a (x:xs) = let x' = f a x in x' `seq` (a : scanl' f x' xs)
    scanl' _ a [] = [a]

番目のリストセルが生成されるときk、その値はすでに評価されているため、前のセルを参照していません。したがって、リストをトラバースするときに、リストをガベージコレクションすることができます (他に何も参照を保持していないと仮定します)。

その実装では、リストバージョンはほぼ同じくらい高速で無駄fib2がありません（それでもリストセルを割り当てる必要があるため、割り当てが少し多くなり、おそらく少し遅くなりますが、違いはごくわずかです。フィボナッチ数リスト構築のオーバーヘッドが無視できるほど大きくなる)。

の考え方scanlは、その結果が段階的に消費されるため、消費によって要素が強制され、大きなサンクの蓄積が防止されるというものです。

一度に2つの要素しか必要とされないのに、なぜGHCはリストバージョンを変数バージョンに最適化しないのですか?

そのオプティマイザーは、アルゴリズムを見てそれを判断することはできません。scanlコンパイラには不透明で、何をするかわかりませんscanl。

正確なソースコードを取得するとscanl(名前を変更するかscanl、プレリュードから非表示にするか、名前を変更することを選択しました)、

scans                   :: (b -> a -> b) -> b -> [a] -> [b]
scans f q ls            =  q : (case ls of
                                []   -> []
                                x:xs -> scans f (f q x) xs)

モジュールをエクスポートしてコンパイルし (-O2 を使用)、生成されたインターフェイス ファイルを次のコマンドで確認します。

ghc --show-iface Scan.hi

(たとえば、コンパイラのバージョン間の小さな違い)

Magic: Wanted 33214052,
       got    33214052
Version: Wanted [7, 0, 6, 1],
         got    [7, 0, 6, 1]
Way: Wanted [],
     got    []
interface main:Scan 7061
  interface hash: ef57dac14815e2f1f897b42a007c0c81
  ABI hash: 8cfc8dab79de6a51fcad666f1869574f
  export-list hash: 57d6805e5f0b5f76f0dd8dfb228df988
  orphan hash: 693e9af84d3dfcc71e640e005bdc5e2e
  flag hash: 1e8135cb44ef6dd330f1f56943d1f463
  used TH splices: False
  where
exports:
  Scan.scans
module dependencies:
package dependencies: base* ghc-prim integer-gmp
orphans: base:GHC.Base base:GHC.Float base:GHC.Real
family instance modules:
import  -/  base:Prelude 1cb4b618cf45281dc97748b1831bf0cd
d79ca4e223c0de0a770a3b88a5e67687
  scans :: forall b a. (b -> a -> b) -> b -> [a] -> [b]
    {- Arity: 3, HasNoCafRefs, Strictness: LLL -}
vectorised variables:
vectorised tycons:
vectorised reused tycons:
scalar variables:
scalar tycons:
trusted: safe-inferred
require own pkg trusted: False

インターフェイス ファイルが関数の展開を公開せず、その型、アリティ、正格性のみを公開し、CAF を参照していないことを確認します。

モジュールのインポートがコンパイルされると、コンパイラーが通過しなければならないのは、インターフェースファイルによって公開された情報だけです。

ここでは、コンパイラが関数の呼び出しを発行する以外のことを実行できるようにする情報は公開されていません。

展開が公開された場合、コンパイラは展開をインライン化し、型と組み合わせ関数を認識してコードを分析し、サンクを構築しないより熱心なコードを生成する機会がありました。

ただし、のセマンティクスscanlは最大限に遅延しており、入力リストが検査される前に出力の各要素が発行されます。その結果、リストに未定義の値が含まれていると結果が変わるため、GHC は加算を厳密にすることができません。

scanl (+) 1 [undefined] = 1 : scanl (+) (1 + undefined) [] = 1 : (1 + undefined) : []

その間

scanl' (+) 1 [undefined] = let x' = 1 + undefined in x' `seq` 1 : scanl' (+) x' []
                         = *** Exception: Prelude.undefined

バリアントを作成できます

scanl'' f b (x:xs) = b `seq` b : scanl'' f (f b x) xs

上記の入力に対して生成1 : *** Exception: Prelude.undefinedされますが、リストに未定義の値が含まれている場合、厳格さによって結果が実際に変更されるため、コンパイラーが展開を知っていたとしても、未定義の値がないことを証明できない限り、評価を厳密にすることはできませんでした。これは私たちには明らかな事実ですが、コンパイラーにはわかりません [コンパイラーにそれを認識させ、未定義の値がないことを証明できるようにするのは簡単ではないと思います]。

于 2012-12-06T21:25:41.880 に答える