ドキュメントによると、
GHCのパイプラインで、INLINEプラグマがオンになっているタイミングを正確に制御したい場合があります。
なぜ私はこれが欲しいのですか？（RULESプラグマも使用する場合を除いて、この場合、関連するルールを実行できるようにするために、関数のインライン化を延期したい場合があります。）単純化プロセスの特定の段階でのみインライン化する方がよい関数はどれですか。
質問する
680 次
2 に答える
15
他の人が述べたように、あなたは本質的にあなた自身の質問に答えました。RULESしかし、 /と組み合わせて位相制御を使用INLINEすることが有益である場合の、より削減された具体的な例が必要になるかもしれません。
これは、再帰スキームを使用して最近実装した例です。カタモルフィズムの概念を使用してこれを説明します。それらが「fold」演算子を特徴付けるだけで、それらが詳細に何であるかを知る必要はありません。（実際、ここでは抽象的な概念にあまり焦点を当てないでください。これは、私が持っている最も単純な例であり、素晴らしいスピードアップが可能です。）
カタモルフィズムの簡単な紹介
まずMu、フィックスポイントタイプであり、その定義は、の値を「分解」して。を返すAlgebra関数の単なる同義語です。f aa
newtype Mu f = Mu { muF :: f (Mu f) }
type Algebra f a = f a -> a
ffoldここで、2つの演算子とを定義できます。これらは、リストの従来の演算子と演算子fbuildの非常に一般的なバージョンです。foldrbuild
ffold :: Functor f => Algebra f a -> Mu f -> a
ffold h = go h
where go g = g . fmap (go g) . muF
{-# INLINE ffold #-}
fbuild :: Functor f => (forall b. Algebra f b -> b) -> Mu f
fbuild g = g Mu
{-# INLINE fbuild #-}
大まかに言えば、によって定義された構造ffold を破棄Algebra f aし、を生成しaます。fbuild代わりに、によって定義された構造を作成Algebra f aし、値を生成しMuます。そのMu値は、話している再帰データ型に対応します。foldr通常の場合と同様buildに、短所を使用してリストを分解し、短所を使用してリストを作成します。アイデアは、これらの古典的な演算子を一般化したばかりなので、任意の再帰データ型（リストやツリーなど）を処理できるということです。
最後に、これら2つの演算子に付随する法律があり、これが私たちの全体的な指針となりますRULE。
forall f g. ffold f (build g) = g f
このルールは基本的に、森林破壊/融合の最適化、つまり中間構造の除去を一般化します。（私は、上記の法則の正しさの証明は読者の練習問題として残されていると思います。等式の推論によってかなり簡単なはずです。）
これらの2つのコンビネータを、とともに使用してMu、リストのような再帰データ型を表すことができます。そして、そのリストに操作を書き込むことができます。
data ListF a f = Nil | Cons a f
deriving (Eq, Show, Functor)
type List a = Mu (ListF a)
instance Eq a => Eq (List a) where
(Mu f) == (Mu g) = f == g
lengthL :: List a -> Int
lengthL = ffold g
where g Nil = 0
g (Cons _ f) = 1 + f
{-# INLINE lengthL #-}
mapまた、関数を定義することもできます。
mapL :: (a -> b) -> List a -> List b
mapL f = ffold g
where g Nil = Mu Nil
g (Cons a x) = Mu (Cons (f a) x)
{-# INLINE mapL #-}
FTWのインライン化
これで、定義したこれらの再帰型に対して用語を記述する手段ができました。しかし、私たちが次のような用語を書くとしたら
lengthL . mapL (+1) $ xs
次に、定義を展開すると、基本的に2つのffold演算子の構成が得られます。
ffold g1 . ffold g2 $ ...
つまり、実際に構造を破壊してから、再構築して再び破壊しているということです。それは本当に無駄です。mapLまた、の観点から再定義できるfbuildので、他の機能と融合することを願っています。
まあ、私たちはすでに私たちの法律を持っているので、それRULEは正しいです。それを成文化しましょう：
{-# RULES
-- Builder rule for catamorphisms
"ffold/fbuild" forall f (g :: forall b. Algebra f b -> b).
ffold f (fbuild g) = g f
-}
次に、融合の目的で再定義mapLします。fbuild
mapL2 :: (a -> b) -> List a -> List b
mapL2 f xs = fbuild (\h -> ffold (h . g) xs)
where g Nil = Nil
g (Cons a x) = Cons (f a) x
{-# INLINE mapL2 #-}
ああ、終わったよね？間違い！
楽しさと利益のためのフェーズ
問題は、インライン化が発生するタイミングに制約がないことです。これにより、これが完全に台無しになります。最適化したかった以前のケースを考えてみましょう。
lengthL . mapL2 (+1) $ xs
ルールが体全体に後書きを発することができるように、lengthLとの定義をmapL2インライン化する必要があります。ffold/fbuildだから私たちは行きたいです：
ffold f1 . fbuild g1 ...
インライン化を介して、その後に移動します：
g1 f1
私たちを介してRULE。
まあ、それは保証されていません。基本的に、単純化の1つのフェーズでは、GHCはとの定義をインライン化するだけでなく、それらの使用サイトの定義lengthLとをmapLインライン化することもできます。これは、フェーズが関連するすべての識別子を「飲み込んで」、それらを何にもインライン化しないため、ルールが発動する機会が決してないことを意味します。ffoldfbuild
観察結果は、インラインffoldでfbuild できるだけ遅くしたいということです。したがって、私たちは、ルールが発動するために可能な限り多くの機会を公開しようとします。そうでない場合は、体がインライン化され、GHCは引き続き最善を尽くします。しかし、最終的には、遅くインライン化する必要があります。これにより、RULEどの賢いコンパイラ最適化よりも効率が向上します。
したがって、ここでの修正は、フェーズ1でのみ起動するように注釈を付けて指定することですffold。fbuild
ffold g = ...
{-# INLINE[1] ffold #-}
fbuild g = ...
{-# INLINE[1] fbuild #-}
これでmapL、友達は非常に早くインライン化されますが、これらは非常に遅くなります。GHCはあるフェーズ番号Nから始まり、フェーズ番号はゼロに減少します。フェーズ1は最後のフェーズです。フェーズ1よりも早くインライン化することも可能fbuild/ffoldですが、これは基本的に、フェーズ数を増やしてそれを補うか、ルールが常にいくつかの早い段階で実行されるようにする必要があることを意味します。
結論
私の要点**で、これらすべてとそれ以上を見つけることができます。ここでは、言及されているすべての定義と例を示します。また、この例の基準ベンチマークも付属しています。フェーズアノテーションを使用すると、GHCは、火災が発生したときlengthL . mapL2と比較して、実行時間を半分に短縮できます。lengthL . mapL1RULE
これを自分で確認したい場合は、を使用してコードをコンパイルし、コンパイルパイプライン中にルールが実行された-ddump-simpl-statsことを確認できます。ffold/fbuild
最後に、同じ原則のほとんどは、ベクトルやバイト文字列などのライブラリに適用されます。秘訣は、ここに複数のレベルのインライン化と、さらに多くのルールがある場合があることです。これは、ストリームと配列の融合などの手法では、ループを効果的に融合して配列を再利用する傾向があるためです。これは、中間のデータ構造を削除することで、従来の森林伐採を行うだけの場合とは対照的です。生成されたコードの従来の「パターン」によっては（たとえば、ベクトル化された並列リスト内包表記のため）、明らかな欠陥を早期に排除する方法で、インターリーブまたは具体的にフェーズ最適化を行う価値があります。RULEまたは、との組み合わせでより多くのINLINE結果が得られる場合に最適化するRULEs（したがって、時々見られる千鳥状のフェーズ-これは基本的にインライン化のフェーズをインターリーブします。）これらの理由から、RULE火災が発生するフェーズを制御することもできます。
したがって、RULEフェーズを含むsは実行時間を大幅に節約できますが、正しく実行するには多くの時間がかかる可能性があります。これが、最も「高性能」で高度に最適化されたライブラリでのみ表示されることが多い理由です。
ノート
*あなたの最初の質問は、「どの種類の関数が位相制御から利益を得るか」でした。これは、「どの関数が一定の部分式除去から利益を得るか」という質問のように聞こえます。可能であれば、これに正確に答える方法がわかりません！これは、関数やプログラムがどのように動作するかについての理論的な結果よりも、コンパイラの領域に近いものです。数学的な法則があっても、すべての「最適化」が期待する結果をもたらすわけではありません。結果として、答えは事実上「あなたがそれを書いてベンチマークするときあなたはおそらく知っているでしょう」です。
**ファイル内の他の多くのものを安全に無視できます。それは主に遊び場でしたが、あなたにとっても興味深いかもしれません。そこには自然や二分木のような他の例があります-それらを使用して、他のさまざまな融合の機会を利用してみる価値があるかもしれません。
于 2013-02-05T21:08:44.600 に答える
1
まず、GHCのデフォルトの動作は、ほとんどの状況でほとんど最適になるように設計されていることに注意してください。問題がない限り、毎日Haskellについて考える非常に賢い人々をほぼ正しくするのがおそらく最善です（PS私はそれらの人々の1人ではありません）が、あなたは尋ねました...
これを使用する理由は2つあります。
プログラムをより速く最良の形に収束させる：
Haskellは、もう一方の端が最初から出てきたものよりも厳密に優れている限り、各ルールパスを繰り返し試行します。それは常に収束しますが、宇宙の熱的死の前に収束するということは何もありません。一般的なケースでは、パスでいっぱいの手が必要ですが、病理学的に悪化する可能性のあるいくつかのコーナーケースがあります。これにより、これらのエッジケースが発生した場合に手動で回避できます。
極小値に収束することは避けてください
Aルールを適用すると、より適切なルールの適用が妨げられる場合がありますB。B次に、前に来ることが重要ですA。デフォルトの最適化ルールは、この問題を回避するために巧妙に作成されていますが、ドキュメントに記載されているように、非常に保守的でもあります。さらにルールを追加すると、必然的に他の可能な最適化を破り始めます。次に、これが発生しないルールチェーン内の場所を見つける必要があります。私の知る限り、それを伝える唯一の方法は試行錯誤です。
于 2013-02-05T06:37:29.533 に答える