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

Push Ifs Up and Fors Down: イディオム、その代数、そして限界 はじめに TigerBeetleの「Tiger Style」ドキュメントからの推奨事項の1つは、「制御フローを集中化する」ことです。大きな関数を分割する際は、すべてのswitch/if文を「親」関数に保持し、分岐しないロジックの断片をヘルパー関数に移動させます。責任を分割します。すべての制御フローは1つの関数で処理され、残りは制御フローを全く気にしないようにします。言い換えれば、「ifsを上に、forsを下に」です。 プログラミングのヒューリスティックである「push-ifs-up-fors-down」は、条件ロジック（if文）を上に（呼び出し元やパイプラインの早い段階に）移動させ、反復ループ（for操作）を下に（バッチ処理やタイトな分岐のないループの遅い段階に）プッシュすることを示唆しています。これにより、分岐を集中化し、バルク操作を活用することで、明瞭さとパフォーマンスが向上します。 matkladもこの原則についてブログを書いており、このプログラミングイディオムに従うことの多くの利点を議論しています。その投稿で、matkladはコードを最適化する方法を説明しています。 条件（「ifs」）を上にプッシュする：関数が入力に基づいて分岐する場合、その分岐を呼び出し元に移動することを検討してください。投稿からの例を考えてみてください。frobnicate(walrus: Option<Walrus>)が内部でオプションをアンパックする代わりに、呼び出し元がNoneケースを処理し、関数はプレーンなWalrusを受け取ります。関数の型は現在、その前提条件を示しており、入力状態空間が狭まり、フィルタリングの一形態として機能します。しかし、重要なのは決定がどこに存在するかであり、データがどれだけ下流に流れるかではありません。 ループ（「fors」）を下にプッシュする：フィルタリングまたはデータセットの削減後にループを延期することで、不要な計算を最小限に抑えます。ループ内でfrobnicate(walrus)を呼び出すのではなく、frobnicate_batch(walruses)を提供し、ループをその内部に配置します。これにより、ホットループは分岐なしで実行され、ベクトル化の候補となります。 この2つの移動は組み合わされます。Option<Walrus>値のコレクションが与えられた場合、呼び出し元はNoneを破棄し、残りをVec<Walrus>にアンラップしてからfrobnicate_batchに渡します。frobnicate_batchはNoneケースを全く考慮する必要がありません。 少し考えると、push-ifs-up-fors-downの原則ははるかに広範な応用があります。この投稿では、リレーショナルデータベースクエリの最適化、関数型プログラミング、圏論に関するこの原則のより広範な視点をいくつか探求します。 データベースクエリのアナロジー：プロジェクションを早く、結合を遅く 同じ原則がデータベースクエリの最適化にも現れます。SQLクエリプランニングでは、プロジェクションと選択をできるだけ早く実行し、結合や展開の多い操作は後回しにすることがよく知られています。しかし、語彙は逆さまです。クエリプランはツリーであり、リーフはテーブルスキャンで、ルートが結果を生成します。データはリーフから上に流れるため、「ツリーを下る」とは「実行が早い」ことを意味します。オプティマイザが述語を下にプッシュすると言うとき、それはできるだけ早く評価することを意味し、これはこの投稿の他の部分が「上」または「早い」と呼ぶもののデータベースでの対応物です。 早期のプロジェクションと選択（下にプッシュ）：データベースの用語では、プロジェクション（例：特定の列を指定したSELECT）は、クエリ実行の早い段階で必要な列のみを選択することで、データセットの幅を削減します。選択（WHERE句）はフィルターとして機能します。どちらもプランツリーの一部として下にプッシュされ、早期に実行されて無関係なデータをフィルタリングし、後続の操作に渡されるデータ量を削減します。 結合の延期（上に結合をプッシュ）：複数のテーブルからのデータを結合する結合は、計算コストが高いです。オプティマイザは、結合の下に選択とプロジェクションを移動させるため、結合はより小さな入力に対して実行されます。その効果は、コストの高い結合演算子がクエリセマンティクスで許可される最小の入力に対して実行されることです。 ベクトル化実行（「for」）：forを下にプッシュすることの別のデータベースアナロジーは、実行セマンティクスの変化です。Volcanoスタイルの実行は行ごとに処理され、各演算子は仮想的なnext()を介してタプルごとに1回呼び出されます。代替案はベクトル化またはバッチ実行であり、各演算子は1000タプル程度のバッチごとに1回呼び出され、内部でタイトなループを実行します。これは、クエリエンジンのレベルでのfrobnicate対frobnicate_batchであり、呼び出しごとのオーバーヘッドと呼び出しごとの決定はバッチごとに1回支払われ、内部ループは分岐が少なくキャッシュフレンドリーです。 関数型プログラミングと圏論のアナロジー 同じ原則を関数型プログラミングと圏論のレンズを通して見てみましょう。 サブオブジェクトへの制限としてのIfsのプッシュアップ 圏論では、集合の圏（または緩やかに言えば、プログラミングにおける型）について話すとき、述語p: A -> Boolを持つことができます。要素は述語を満たすか満たさないかのどちらかです。次に、{a ∈ A | p a}によって与えられる述語を満たす要素のサブセットを考えます。そして、包含を定義する射{a | p a} ↪ Aを追加します。サブセットとその射は、圏論におけるサブオブジェクトを定義します。射のフックされた矢印に注意してください。これは意図的であり、特定の種類の射、つまり単射関数（数学者は矢印の型を定義するのが大好きです :-)) を表していることを示しています。Setでは、単射関数は単射関数です。包含は各要素をそれ自体に送るため、異なる入力は異なる出力を与えます。 これで、matkladへのリンクができました。以前：呼び出し先は任意のAを受け取り、内部でp(a)を実行します。後：呼び出し元はテストを実行し、呼び出し先の入力型はサブセットになります。呼び出し先の入力はすべて既に通過しているため、呼び出し先はifを必要としなくなります。コードでは、サブセットは型（Option<Walrus>の代わりにWalrus）で表されます。圏論的に言えば、Option<Walrus>はコ積1 + Walrusであり、それはNothingまたはWalrusのいずれかです。Option<Walrus>を受け取り、内部で分岐する関数は、実際にはコ積からの関数であり、コ積の普遍性により、そのような関数は正確に2つの関数のペアであり、1つは各項 summand 用です。ifを上にプッシュすることは、そのペアを分離します。呼び出し元は1 summandを処理し、コア関数はWalrusコンポーネントのみになります。 Filter、Map、およびそれらを関連付ける法則 異なる現れ方での同じ原則、つまりコンビネータの代数です。「マップする前にフィルターする」というアドバイスをよく耳にします。しかし、これはいつ正当な書き換えなのでしょうか？なぜなら、次の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) これはパラメトリック性から導かれ、フィルターを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に単純化される場合に効果があります。