HN 日本語サマリー

← 一覧へ戻る
プログラミング

Push Ifs Up and Fors Down: イディオム、その代数、そして限界

Push Ifs Up and Fors Down: The Idiom, Its Algebra, and Its Limits (debasishg.github.io)

169 pointsby speckx78 コメント

要約

「Push Ifs Up and Fors Down」は、条件分岐(if文)を呼び出し元や処理の早い段階に移動させ、ループ処理(for文)を処理の遅い段階やバッチ処理に移動させるというプログラミングのヒューリスティックです。これにより、コードの可読性とパフォーマンスが向上します。この原則は、データベースクエリ最適化や関数型プログラミング、圏論にも応用できます。

全文翻訳

If文を上に、For文を下に押し上げる:イディオム、その代数、そして限界

はじめに

TigerBeetle の Tiger Style ドキュメント からの推奨事項の1つです。

コントロールフローを集中化する。大きな関数を分割する際は、すべての switch/if 文を「親」関数に保持し、分岐しないロジックの断片をヘルパー関数に移動させるように努める。責任を分割する。すべてのコントロールフローは1つの関数で処理され、残りはコントロールフローを一切気にする必要がないようにする。言い換えれば、「If文を上に、For文を下に押し上げる」ということだ。

プログラミングのヒューリスティックである「If文を上に、For文を下に押し上げる」とは、条件ロジック(if文)を上位(呼び出し元やパイプラインの早い段階)に移動させ、反復ループ(for操作)を下位(バッチ処理やタイトな分岐なしループの遅い段階)に押し下げることを示唆しています。これにより、分岐を集中化し、バルク操作を活用することで、明瞭さとパフォーマンスが向上します。

matklad もこの原則についてブログ記事を執筆しており、このプログラミングイディオムに従うことの多くの利点について議論しています。

その記事で、matklad はコードを最適化する方法を次のように説明しています。

条件分岐(「if」)を上に押し上げる: 関数が入力に基づいて分岐する場合、その分岐を呼び出し元に移動させることを検討してください。記事の例を考えてみましょう。frobnicate(walrus: Option<Walrus>) が内部でオプションをアンパックする代わりに、呼び出し元が None ケースを処理し、関数はプレーンな Walrus を受け取ります。関数の型は前述の前提条件を示すようになり、入力の状態空間が狭まり、フィルタリングの一形態として機能します。しかし、重要なのは決定がどこに存在するかであり、データがどれだけ下流に流れるかではありません。

ループ(「for」)を下に押し下げる: フィルタリングやデータセットの削減が終わるまでループを延期することで、不要な計算を最小限に抑えます。ループ内で frobnicate(walrus) を呼び出す代わりに、frobnicate_batch(walruses) を提供し、ループをその内部に配置します。これにより、ホットなループは分岐なしで実行され、ベクトル化の候補となります。

この2つの操作は組み合わされます。Option<Walrus> 値のコレクションが与えられた場合、呼び出し元は None を破棄し、残りをアンラップして Vec<Walrus> にし、それを frobnicate_batch に渡します。frobnicate_batch は None ケースを一切考慮する必要がありません。

let maybe_walruses: Vec<Option<Walrus>> = ...;
let walruses: Vec<Walrus> = maybe_walruses.into_iter().filter_map(|w| w).collect();
frobnicate_batch(&walruses); // None を見ることはない

少し考えると、この「If文を上に、For文を下に押し上げる」原則は、はるかに広範な応用があることがわかります。この記事では、リレーショナルデータベースのクエリ最適化、関数型プログラミング、圏論との関連で、この原則のより広範な視点をいくつか探求します。

データベースクエリにおける類推:射影を先に、結合を後に

データベースクエリの最適化でも同じ原則が見られます。SQLクエリプランニングでは、射影(projection)と選択(selection)を可能な限り早く実行し、結合(join)やコストの高い操作を後に延期することがよく知られています。しかし、語彙は逆転しています。クエリプランはツリーであり、リーフはテーブルスキャンで、ルートが結果を生成します。データはリーフから上に流れるため、「ツリーを下る」とは「実行の早い段階」を意味します。オプティマイザが述語を下にプッシュすると言うとき、それは実行の早い段階で評価することを意味し、これはこの記事の他の部分で「上」または「早い」と呼んでいるもののデータベースでの対応物です。

早期の射影と選択(下にプッシュ): データベースの用語では、射影(例:特定の列を指定した SELECT)は、クエリ実行の早い段階で必要な列のみを選択することで、データセットの幅を削減します。選択(WHERE句)はフィルタリングとして機能します。どちらもプランツリーの一部として下にプッシュされるため、早期に実行されて無関係なデータをフィルタリングし、後続の操作に渡されるデータ量を削減します。

結合の延期(結合を上にプッシュ): 複数のテーブルからのデータを結合する結合は、計算コストが高いです。オプティマイザは、選択と射影を結合の下に移動させるため、結合はより小さな入力に対して実行されます。その効果は、コストの高い結合演算子が、クエリセマンティクスで許容される最小の入力に対して実行されることです。

ベクトル化実行(「for」): 「for」を下にプッシュする別のデータベースの類推は、実行セマンティクスの変化です。Volcano スタイルの実行は行ごとに処理し、各オペレータは仮想 next() を介してタプルごとに1回呼び出されます。代替案はベクトル化またはバッチ実行であり、各オペレータは1000タプル程度のバッチごとに1回呼び出され、内部でタイトなループを実行します。これは、クエリエンジンのレベルでの frobnicate 対 frobnicate_batch です。呼び出しごとのオーバーヘッドと呼び出しごとの決定はバッチごとに1回支払われ、内部ループは分岐が少なくキャッシュフレンドリーです。

関数型プログラミングと圏論における類推

同じ原則を関数型プログラミングと圏論のレンズを通して見てみましょう。

If文を上に押し上げることは、サブオブジェクトへの制限

圏論では、集合の圏(あるいは、緩く言えば、プログラミングにおける型)について話すとき、述語 p : A -> Bool を持つことができます。要素は述語を満たすか満たさないかのどちらかです。ここで、述語を満たす要素のサブセット {a ∈ A | p a} を考えます。そして、サブセットを定義する射 {a | p a} ↪ A を追加します。サブセットとその射は、圏論におけるサブオブジェクトを定義します。

射のフックされた矢印に注意してください。これは意図的であり、特定の種類の射、つまり単射(数学者は矢印の型を定義するのが大好きです :-))を表しています。集合の圏では、単射は単射関数です。包含関数は各要素をそれ自身に送るため、異なる入力は異なる出力を与えます。

ここで matklad とのつながりができます。

  • 以前:呼び出し先は任意の A を受け取り、内部で if p(a) を実行します。
  • 後:呼び出し元はテストを実行し、呼び出し先の入力型はサブセットになります。

呼び出し先は if を必要としなくなります。なぜなら、受け取ることができるすべての入力はすでに通過しているからです。コードでは、サブセットは型 Walrus(Option<Walrus> の代わりに)で表現されます。

圏論的に言えば、Option<Walrus> は積集合 1 + Walrus であり、これは nothing または walrus のどちらかです。Option<Walrus> を受け取り、内部で分岐する関数は、実際には積集合からの関数であり、積集合の普遍性により、そのような関数は正確に2つの関数のペアであり、それぞれが一方の項に対応します。if を上にプッシュすることは、そのペアを分離します。呼び出し元は 1 の項を扱い、コア関数は Walrus の部分だけになります。

フィルタとマップ、そしてそれらを関連付ける法則

同じ原則が異なる現れ方をする場合、それはコンビネータの代数です。よく「マップする前にフィルタリングする」というアドバイスを聞きます。しかし、これはいつ正当な書き換えなのでしょうか?なぜなら、次の2つの式は同等ではないからです。

filter p (map f xs)   -- p は f の*出力*を検査する
map f (filter p xs)   -- p は f の*入力*を検査する

最初の行では p の型は B -> Bool です。2番目の行では A -> Bool です。それらを実際に結びつける法則は次のとおりです。

filter p . map f  ==  map f . filter (p . f)

これはパラメトリック性から導き出され、filter を Maybe を介して因数分解すると最もよくわかります。

keep :: (a -> Bool) -> a -> Maybe a
keep p x = if p x then Just x else Nothing

filter p = catMaybes . map (keep p)

ここで filter p 自体は自然変換ではありません。そうなることはできません。なぜなら p は要素型を固定し、自然性正方形を描くことができないからです(試してみてください!)。しかし、catMaybes :: [Maybe a] -> [a] は自然変換であり、そこに自然性が宿っています。

map g . catMaybes  ==  catMaybes . map (fmap g)

それにより、法則は短い計算になります。keep p . f == fmap f . keep (p . f) であるため:

filter p . map f
  == catMaybes . map (keep p) . map f
  == catMaybes . map (keep p . f)
  == catMaybes . map (fmap f . keep (p . f))
  == catMaybes . map (fmap f) . map (keep (p . f))
  == map f . catMaybes . map (keep (p . f))       -- catMaybes の自然性
  == map f . filter (p . f)

右辺が自動的に安価になるとは限らないことに注意してください。filter (p . f) は、テストするためにすべての要素に対して f を計算します。この書き換えは、p . f が安価な述語 q に単純化される場合に効果を発揮します。通常は p が f がそのままにしておく値の一部を検査する場合です。その場合、filter p . map f == map f . filter q となり、f は生存者に対してのみ実行されます。両辺は依然として単一の O(n) パスですが、破棄される予定だった要素に対する f の呼び出しが節約されます。

そして、「If文を上に、For文を下に押し上げる」原則が効果を発揮します!

まとめ

上記の議論から得られる主な教訓は、コードベース、あるいはシステム全体のより良い代数へと導く一般的な原則を持つことができるということです。しかし、これらの原則はすべて、コンポーネント全体で有効でなければならないいくつかの制約の下で機能します。

  • ループから if を取り出すことは、条件がループ不変である場合に有効です。要素ごとの条件はループから離れることはできません。それは境界に移動し、Option<Walrus> の代わりに Walrus のように型に記録されるだけです。
  • 結合の下に選択をプッシュすることは、述語が結合の片側のみから列を参照する場合に有効です。
  • マップの前にフィルタリングすることは、filter p . map f == map f . filter (p . f) として有効であり、p . f が入力に対する安価な述語に還元される場合にのみ作業を節約します。通常は p が f がそのままにしておく値の一部を検査する場合です。

したがって、どの書き換えが合法であるかを教えてくれるのは代数です。上記のフィルタ/マップの場合、合法性を駆動し、コードの全体構造を推論するのに役立つのは catMaybes の自然性です。

「for を下に」の部分については、同等性よりもコストに関するものです。A -> B から [A] -> [B] へと矢印の形状を変更するため、セットアップコストをバッチごとに1回支払います。