Het artikel bespreekt de programmeerheuristiek "push-ifs-up-fors-down", een principe dat pleit voor het centraliseren van de control flow.
De kernprincipes zijn:
- Push Ifs Up: Conditionele logica (
if-statements) wordt verplaatst naar de aanroeper. Hierdoor worden helperfuncties eenvoudiger, wordt de input-ruimte kleiner en kunnen precondities direct in het type worden vastgelegd.
- Fors Down: Iteratieve lussen (
for) worden uitgesteld tot na het filteren of verplaatst naar batchverwerking. Dit minimaliseert onnodige berekeningen en maakt de code geschikter voor vectorisatie en cache-optimalisatie.
Het artikel trekt parallellen met andere domeinen:
- Database-queries: In SQL-optimalisatie is dit vergelijkbaar met het zo vroeg mogelijk uitvoeren van projecties en selecties (predicate push-down) en het uitstellen van kostbare joins.
- Functioneel Programmeren & Categorietheorie: Het concept wordt gelinkt aan subobjects en monomorfismen. Er wordt een wiskundige bewijsvoering geleverd voor de wet die
filter en map verbindt, waarbij wordt aangetoond dat filteren vóór mappen efficiënter is wanneer het predicaat kan worden vereenvoudigd tot de input.
Conclusie: Deze algebraïsche herschrijvingen verbeteren de structuur en prestaties van een codebase, mits voldaan wordt aan specifieke randvoorwaarden, zoals luss-invariantie van condities.
Push Ifs Up and Fors Down: Het Idioom, de Algebra en de Limieten
Introductie
Centraliseer de control flow. Wanneer je een grote functie opsplitst, probeer dan alle switch/if-statements in de "ouderfunctie" te houden en verplaats niet-vertakkende logicafragmenten naar helperfuncties. Verdeel de verantwoordelijkheid. Alle control flow zou door één functie moeten worden afgehandeld; de rest zou zich helemaal niets aan moeten trekken van de control flow. Met andere woorden: "push ifs up and fors down".
De programmeerheuristiek push-ifs-up-fors-down suggereert dat conditionele logica (if-statements) naar boven moet worden verplaatst (naar de aanroeper of eerder in een pipeline), terwijl iteratieve lussen (for-operaties) naar beneden moeten worden geduwd (naar batchverwerking of later in een compacte, vertakking-vrije lus). Dit verbetert de duidelijkheid en prestaties door vertakkingen te centraliseren en gebruik te maken van bulkoperaties.
Matklad heeft ook over dit principe geblogd en de vele voordelen van dit programmeeridioom besproken. In zijn bericht beschrijft hij het optimaliseren van code door:
- Conditionals ("ifs") omhoog duwen: Als een functie vertakt op basis van zijn input, overweeg dan om die vertakking naar de aanroeper te verplaatsen. Neem bijvoorbeeld het voorbeeld uit het bericht: in plaats van dat
frobnicate(walrus: Option<Walrus>) de option intern uitpakt, handelt de aanroeper de None-geval af en ontvangt de functie een gewone Walrus. Het type van de functie geeft nu zijn preconditie aan, de input-toestandsruimte wordt smaller en fungeert als een vorm van filtering. Het cruciale punt is waar de beslissing wordt genomen, niet hoeveel data er downstream stroomt.
- Lussen ("fors") omlaag duwen: Het uitstellen van lussen tot na het filteren of reduceren van de dataset minimaliseert onnodige berekeningen. In plaats van
frobnicate(walrus) in een lus aan te roepen, kun je frobnicate_batch(walruses) aanbieden en de lus daarbinnen laten leven. Hierdoor draait de "hot loop" zonder vertakkingen en is deze een kandidaat voor vectorisatie.
Deze twee acties vullen elkaar aan. Gegeven een verzameling Option<Walrus>-waarden, verwijdert de aanroeper de Nones en pakt de rest uit tot een Vec<Walrus>, om deze vervolgens aan frobnicate_batch over te dragen, die nooit rekening hoeft te houden met het None-geval.
let maybe_walruses: Vec<Option<Walrus>> = ...;
let walruses: Vec<Walrus> = maybe_walruses.into_iter().filter_map(|w| w).collect();
frobnicate_batch(&walruses); // ziet nooit een None
Het principe push-ifs-up-fors-down heeft veel bredere toepassingen. Dit artikel verkent deze perspectieven met betrekking tot optimalisaties van relationele database-queries en functioneel programmeren en categorietheorie.
Analogie in Database-queries: Projecties vroeg, Joins laat
Hetzelfde principe komt voor bij de optimalisatie van database-queries. In SQL-queryplanning is het bekend dat projecties en selecties zo vroeg mogelijk moeten worden uitgevoerd en dat joins of expansieve operaties moeten worden uitgesteld. De terminologie is hier echter omgekeerd. Een queryplan is een boom waarvan de bladeren tabelscans zijn en de wortel het resultaat produceert. Data stroomt omhoog vanuit de bladeren, dus "onderaan de boom" betekent "eerder in de uitvoering". Wanneer een optimizer spreekt over het "naar beneden duwen" (pushing down) van een predicaat, betekent dit dat het zo vroeg mogelijk wordt geëvalueerd, wat het database-equivalent is van wat in dit artikel "omhoog" of "vroeg" wordt genoemd.
Vroege projecties en selecties (Push down)
In database-termen vermindert een projectie (bijv. SELECT met specifieke kolommen) de breedte van de dataset door vroeg in de query-uitvoering alleen de noodzakelijke kolommen te selecteren. Selecties (WHERE-clausule) fungeren als filter. Beiden worden naar beneden geduwd in de planningsboom, zodat ze vroeg worden uitgevoerd en irrelevante data filteren, waardoor de hoeveelheid data die naar latere operaties wordt doorgegeven, afneemt.
Joins uitstellen (Push joins up)
Joins, die data van meerdere tabellen combineren, zijn rekenintensief. De optimizer verplaatst selecties en projecties onder de joins, zodat joins op kleinere inputs draaien. Het effect is dat de dure combinerende operatoren draaien over de kleinste inputs die de query-semantiek toelaat.
Gevectoriseerde uitvoering (de "for")
Een andere database-analogie voor het omlaag duwen van fors is de verandering in uitvoersemantiek. Volcano-style uitvoering verwerkt één rij per keer, waarbij elke operator één keer per tuple wordt aangeroepen via een virtuele next(). Het alternatief is gevectoriseerde of batch-uitvoering, waarbij elke operator één keer per batch van bijvoorbeeld duizend tuples wordt aangeroepen en intern een compacte lus draait. Dit is frobnicate versus frobnicate_batch op het niveau van een query-engine: de overhead per aanroep en de beslissingen per aanroep worden één keer per batch betaald, en de innerlijke lus is vertakkingsarm en cache-vriendelijk.
Analogie in Functioneel Programmeren en Categorietheorie
Laten we naar dezelfde principes kijken door de lens van functioneel programmeren en categorietheorie.
Pushing-Ifs-Up als een restrictie naar een subobject
In de categorietheorie, wanneer we spreken over de categorie van verzamelingen (of, losjes genomen, typen in programmeren), kunnen we een predicaat $p : A \to \text{Bool}$ hebben. Elementen kunnen het predicaat wel of niet vervullen. Beschouw nu de deelverzameling van elementen die het predicaat vervullen, gegeven door $\{a \in A \mid p a\}$. Voeg hieraan het morfisme $\{a \mid p a\} \hookrightarrow A$ toe dat de inclusie definieert. De deelverzameling samen met het morfisme definieert een subobject in de categorietheorie.
Let op de gekromde pijl in het morfisme. Deze is bewust gekozen en geeft aan dat het een specifiek type morfisme vertegenwoordigt: een monomorfisme. In $\text{Set}$ is een monomorfisme een injectieve functie: de inclusie stuurt elk element naar zichzelf, dus verschillende inputs geven verschillende outputs.
Hier is de link terug naar matklad:
- Voorheen: de aangeroepene accepteert elke $A$ en voert intern
if p(a) uit.
- Nu: de aanroeper voert de test uit, en het input-type van de aangeroepene is de deelverzameling.
De aangeroepene heeft de if niet meer nodig, omdat elke input die hij ontvangt, al is goedgekeurd. In code representeer je de deelverzameling met een type: Walrus in plaats van Option<Walrus>.
Categorisch gezien is Option<Walrus> het coproduct $1 + \text{Walrus}$, wat ofwel niets of een walrus is. Een functie die een Option<Walrus> neemt en intern vertakt, is in feite een functie vanuit een coproduct. Door de universele eigenschap van coproducten is zo'n functie exact een paar functies, één voor elke summand. Het omhoog duwen van de if splitst dat paar: de aanroeper handelt de $1$-summand af, en de kernfunctie is enkel het Walrus-component.
Filter, Map en de wet die hen verbindt
Hetzelfde principe in een andere manifestatie: de algebra van combinators. Je hoort vaak het advies "filter voordat je mapt". Maar wanneer is dit precies een legitieme herschrijving? Immers, de volgende twee expressies zijn niet equivalent:
filter p (map f xs) — $p$ inspecteert de output van $f$ map f (filter p xs) — $p$ inspecteert de input van $f$
In de eerste regel heeft $p$ het type $B \to \text{Bool}$; in de tweede heeft het het type $A \to \text{Bool}$. De wet die hen daadwerkelijk verbindt is:
$\text{filter } p \circ \text{map } f = \text{map } f \circ \text{filter } (p \circ f)$
Dit volgt uit parametriciteit, en is het makkelijkst in te zien door filter te factoriseren via Maybe:
keep :: (a -> Bool) -> a -> Maybe a
keep p x = if p x then Just x else Nothing
filter p = catMaybes . map (keep p)
Hier is filter p zelf geen natuurlijke transformatie — dat kan niet, aangezien $p$ het element-type vastlegt — maar catMaybes :: [Maybe a] -> [a] is dat wel, en dat is waar de naturaliteit leeft:
$\text{map } g \circ \text{catMaybes} = \text{catMaybes} \circ \text{map } (\text{fmap } g)$
Hiermee is de wet een korte berekening. Aangezien $\text{keep } p \circ f = \text{fmap } f \circ \text{keep } (p \circ f)$:
$\text{filter } p \circ \text{map } f$ $= \text{catMaybes} \circ \text{map } (\text{keep } p) \circ \text{map } f$ $= \text{catMaybes} \circ \text{map } (\text{keep } p \circ f)$ $= \text{catMaybes} \circ \text{map } (\text{fmap } f \circ \text{keep } (p \circ f))$ $= \text{catMaybes} \circ \text{map } (\text{fmap } f) \circ \text{map } (\text{keep } (p \circ f))$ $= \text{map } f \circ \text{catMaybes} \circ \text{map } (\text{keep } (p \circ f))$ — naturaliteit van catMaybes $= \text{map } f \circ \text{filter } (p \circ f)$
Merk op dat de rechterkant niet automatisch goedkoper is: filter (p . f) berekent nog steeds $f$ voor elk element om het te kunnen testen. De herschrijving loont wanneer $p \circ f$ vereenvoudigt tot een goedkoop predicaat $q$ op de input — gewoonlijk omdat $p$ een deel van de waarde inspecteert dat $f$ ongemoeid laat. Dan geldt $\text{filter } p \circ \text{map } f = \text{map } f \circ \text{filter } q$, en $f$ wordt alleen uitgevoerd op de overlevers. Beide zijden zijn nog steeds een enkele $O(n)$ pass; wat je bespaart, zijn de aanroepen naar $f$ voor elementen die toch weggegooid zouden worden.
En zo loont push-if-up-fors-down!
Samenvatting
De belangrijkste conclusie van deze bespreking is dat we algemene principes kunnen hebben die ons leiden naar een betere algebra van de codebase of zelfs het hele systeem. Maar al deze principes werken mits aan bepaalde randvoorwaarden wordt voldaan over de componenten heen.
- Een
if uit een lus halen is geldig wanneer de conditie luss-invariant is. Een conditie per element kan de lus niet verlaten; deze kan alleen naar de grens verplaatst worden en vastgelegd worden in een type, zoals Walrus in plaats van Option<Walrus>.
- Een selectie onder een join duwen is geldig wanneer het predicaat alleen refereert aan kolommen van één zijde van de join.
- Filteren vóór mappen is geldig omdat $\text{filter } p \circ \text{map } f = \text{map } f \circ \text{filter } (p \circ f)$, en het bespaart werk alleen wanneer $p \circ f$ reduceert tot een goedkoop predicaat op de input, meestal omdat $p$ een deel van de waarde inspecteert dat $f$ ongemoeid laat.
Kortom, de algebra vertelt je welke herschrijvingen legaal zijn. In het bovenstaande filter/map-geval is het de naturaliteit van catMaybes die de legaliteit bepaalt en je helpt redeneren over de algehele structuur van de code.
Voor het "fors-down" gedeelte gaat het meer over de kosten dan over de equivalentie. Je verandert de vorm van de pijl van $A \to B$ naar $[A] \to [B]$, zodat je de opstartkosten slechts één keer per batch betaalt.
Push Ifs Up and Fors Down: Het Idioom, de Algebra en de Limieten
Introductie
Centraliseer de control flow. Wanneer je een grote functie opsplitst, probeer dan alle switch/if-statements in de "ouderfunctie" te houden en verplaats niet-vertakkende logicafragmenten naar helperfuncties. Verdeel de verantwoordelijkheid. Alle control flow zou door één functie moeten worden afgehandeld; de rest zou zich helemaal niets aan moeten trekken van de control flow. Met andere woorden: "push ifs up and fors down".
De programmeerheuristiek push-ifs-up-fors-down suggereert dat conditionele logica (if-statements) naar boven moet worden verplaatst (naar de aanroeper of eerder in een pipeline), terwijl iteratieve lussen (for-operaties) naar beneden moeten worden geduwd (naar batchverwerking of later in een compacte, vertakking-vrije lus). Dit verbetert de duidelijkheid en prestaties door vertakkingen te centraliseren en gebruik te maken van bulkoperaties.
Matklad heeft ook over dit principe geblogd en de vele voordelen van dit programmeeridioom besproken. In zijn bericht beschrijft hij het optimaliseren van code door:
- Conditionals ("ifs") omhoog duwen: Als een functie vertakt op basis van zijn input, overweeg dan om die vertakking naar de aanroeper te verplaatsen. Neem bijvoorbeeld het voorbeeld uit het bericht: in plaats van dat
frobnicate(walrus: Option<Walrus>) de option intern uitpakt, handelt de aanroeper de None-geval af en ontvangt de functie een gewone Walrus. Het type van de functie geeft nu zijn preconditie aan, de input-toestandsruimte wordt smaller en fungeert als een vorm van filtering. Het cruciale punt is waar de beslissing wordt genomen, niet hoeveel data er downstream stroomt.
- Lussen ("fors") omlaag duwen: Het uitstellen van lussen tot na het filteren of reduceren van de dataset minimaliseert onnodige berekeningen. In plaats van
frobnicate(walrus) in een lus aan te roepen, kun je frobnicate_batch(walruses) aanbieden en de lus daarbinnen laten leven. Hierdoor draait de "hot loop" zonder vertakkingen en is deze een kandidaat voor vectorisatie.
Deze twee acties vullen elkaar aan. Gegeven een verzameling Option<Walrus>-waarden, verwijdert de aanroeper de Nones en pakt de rest uit tot een Vec<Walrus>, om deze vervolgens aan frobnicate_batch over te dragen, die nooit rekening hoeft te houden met het None-geval.
let maybe_walruses: Vec<Option<Walrus>> = ...;
let walruses: Vec<Walrus> = maybe_walruses.into_iter().filter_map(|w| w).collect();
frobnicate_batch(&walruses); // ziet nooit een None
Het principe push-ifs-up-fors-down heeft veel bredere toepassingen. Dit artikel verkent deze perspectieven met betrekking tot optimalisaties van relationele database-queries en functioneel programmeren en categorietheorie.
Analogie in Database-queries: Projecties vroeg, Joins laat
Hetzelfde principe komt voor bij de optimalisatie van database-queries. In SQL-queryplanning is het bekend dat projecties en selecties zo vroeg mogelijk moeten worden uitgevoerd en dat joins of expansieve operaties moeten worden uitgesteld. De terminologie is hier echter omgekeerd. Een queryplan is een boom waarvan de bladeren tabelscans zijn en de wortel het resultaat produceert. Data stroomt omhoog vanuit de bladeren, dus "onderaan de boom" betekent "eerder in de uitvoering". Wanneer een optimizer spreekt over het "naar beneden duwen" (pushing down) van een predicaat, betekent dit dat het zo vroeg mogelijk wordt geëvalueerd, wat het database-equivalent is van wat in dit artikel "omhoog" of "vroeg" wordt genoemd.
Vroege projecties en selecties (Push down)
In database-termen vermindert een projectie (bijv. SELECT met specifieke kolommen) de breedte van de dataset door vroeg in de query-uitvoering alleen de noodzakelijke kolommen te selecteren. Selecties (WHERE-clausule) fungeren als filter. Beiden worden naar beneden geduwd in de planningsboom, zodat ze vroeg worden uitgevoerd en irrelevante data filteren, waardoor de hoeveelheid data die naar latere operaties wordt doorgegeven, afneemt.
Joins uitstellen (Push joins up)
Joins, die data van meerdere tabellen combineren, zijn rekenintensief. De optimizer verplaatst selecties en projecties onder de joins, zodat joins op kleinere inputs draaien. Het effect is dat de dure combinerende operatoren draaien over de kleinste inputs die de query-semantiek toelaat.
Gevectoriseerde uitvoering (de "for")
Een andere database-analogie voor het omlaag duwen van fors is de verandering in uitvoersemantiek. Volcano-style uitvoering verwerkt één rij per keer, waarbij elke operator één keer per tuple wordt aangeroepen via een virtuele next(). Het alternatief is gevectoriseerde of batch-uitvoering, waarbij elke operator één keer per batch van bijvoorbeeld duizend tuples wordt aangeroepen en intern een compacte lus draait. Dit is frobnicate versus frobnicate_batch op het niveau van een query-engine: de overhead per aanroep en de beslissingen per aanroep worden één keer per batch betaald, en de innerlijke lus is vertakkingsarm en cache-vriendelijk.
Analogie in Functioneel Programmeren en Categorietheorie
Laten we naar dezelfde principes kijken door de lens van functioneel programmeren en categorietheorie.
Pushing-Ifs-Up als een restrictie naar een subobject
In de categorietheorie, wanneer we spreken over de categorie van verzamelingen (of, losjes genomen, typen in programmeren), kunnen we een predicaat $p : A \to \text{Bool}$ hebben. Elementen kunnen het predicaat wel of niet vervullen. Beschouw nu de deelverzameling van elementen die het predicaat vervullen, gegeven door $\{a \in A \mid p a\}$. Voeg hieraan het morfisme $\{a \mid p a\} \hookrightarrow A$ toe dat de inclusie definieert. De deelverzameling samen met het morfisme definieert een subobject in de categorietheorie.
Let op de gekromde pijl in het morfisme. Deze is bewust gekozen en geeft aan dat het een specifiek type morfisme vertegenwoordigt: een monomorfisme. In $\text{Set}$ is een monomorfisme een injectieve functie: de inclusie stuurt elk element naar zichzelf, dus verschillende inputs geven verschillende outputs.
Hier is de link terug naar matklad:
- Voorheen: de aangeroepene accepteert elke $A$ en voert intern
if p(a) uit.
- Nu: de aanroeper voert de test uit, en het input-type van de aangeroepene is de deelverzameling.
De aangeroepene heeft de if niet meer nodig, omdat elke input die hij ontvangt, al is goedgekeurd. In code representeer je de deelverzameling met een type: Walrus in plaats van Option<Walrus>.
Categorisch gezien is Option<Walrus> het coproduct $1 + \text{Walrus}$, wat ofwel niets of een walrus is. Een functie die een Option<Walrus> neemt en intern vertakt, is in feite een functie vanuit een coproduct. Door de universele eigenschap van coproducten is zo'n functie exact een paar functies, één voor elke summand. Het omhoog duwen van de if splitst dat paar: de aanroeper handelt de $1$-summand af, en de kernfunctie is enkel het Walrus-component.
Filter, Map en de wet die hen verbindt
Hetzelfde principe in een andere manifestatie: de algebra van combinators. Je hoort vaak het advies "filter voordat je mapt". Maar wanneer is dit precies een legitieme herschrijving? Immers, de volgende twee expressies zijn niet equivalent:
filter p (map f xs) — $p$ inspecteert de output van $f$ map f (filter p xs) — $p$ inspecteert de input van $f$
In de eerste regel heeft $p$ het type $B \to \text{Bool}$; in de tweede heeft het het type $A \to \text{Bool}$. De wet die hen daadwerkelijk verbindt is:
$\text{filter } p \circ \text{map } f = \text{map } f \circ \text{filter } (p \circ f)$
Dit volgt uit parametriciteit, en is het makkelijkst in te zien door filter te factoriseren via Maybe:
keep :: (a -> Bool) -> a -> Maybe a
keep p x = if p x then Just x else Nothing
filter p = catMaybes . map (keep p)
Hier is filter p zelf geen natuurlijke transformatie — dat kan niet, aangezien $p$ het element-type vastlegt — maar catMaybes :: [Maybe a] -> [a] is dat wel, en dat is waar de naturaliteit leeft:
$\text{map } g \circ \text{catMaybes} = \text{catMaybes} \circ \text{map } (\text{fmap } g)$
Hiermee is de wet een korte berekening. Aangezien $\text{keep } p \circ f = \text{fmap } f \circ \text{keep } (p \circ f)$:
$\text{filter } p \circ \text{map } f$ $= \text{catMaybes} \circ \text{map } (\text{keep } p) \circ \text{map } f$ $= \text{catMaybes} \circ \text{map } (\text{keep } p \circ f)$ $= \text{catMaybes} \circ \text{map } (\text{fmap } f \circ \text{keep } (p \circ f))$ $= \text{catMaybes} \circ \text{map } (\text{fmap } f) \circ \text{map } (\text{keep } (p \circ f))$ $= \text{map } f \circ \text{catMaybes} \circ \text{map } (\text{keep } (p \circ f))$ — naturaliteit van catMaybes $= \text{map } f \circ \text{filter } (p \circ f)$
Merk op dat de rechterkant niet automatisch goedkoper is: filter (p . f) berekent nog steeds $f$ voor elk element om het te kunnen testen. De herschrijving loont wanneer $p \circ f$ vereenvoudigt tot een goedkoop predicaat $q$ op de input — gewoonlijk omdat $p$ een deel van de waarde inspecteert dat $f$ ongemoeid laat. Dan geldt $\text{filter } p \circ \text{map } f = \text{map } f \circ \text{filter } q$, en $f$ wordt alleen uitgevoerd op de overlevers. Beide zijden zijn nog steeds een enkele $O(n)$ pass; wat je bespaart, zijn de aanroepen naar $f$ voor elementen die toch weggegooid zouden worden.
En zo loont push-if-up-fors-down!
Samenvatting
De belangrijkste conclusie van deze bespreking is dat we algemene principes kunnen hebben die ons leiden naar een betere algebra van de codebase of zelfs het hele systeem. Maar al deze principes werken mits aan bepaalde randvoorwaarden wordt voldaan over de componenten heen.
- Een
if uit een lus halen is geldig wanneer de conditie luss-invariant is. Een conditie per element kan de lus niet verlaten; deze kan alleen naar de grens verplaatst worden en vastgelegd worden in een type, zoals Walrus in plaats van Option<Walrus>.
- Een selectie onder een join duwen is geldig wanneer het predicaat alleen refereert aan kolommen van één zijde van de join.
- Filteren vóór mappen is geldig omdat $\text{filter } p \circ \text{map } f = \text{map } f \circ \text{filter } (p \circ f)$, en het bespaart werk alleen wanneer $p \circ f$ reduceert tot een goedkoop predicaat op de input, meestal omdat $p$ een deel van de waarde inspecteert dat $f$ ongemoeid laat.
Kortom, de algebra vertelt je welke herschrijvingen legaal zijn. In het bovenstaande filter/map-geval is het de naturaliteit van catMaybes die de legaliteit bepaalt en je helpt redeneren over de algehele structuur van de code.
Voor het "fors-down" gedeelte gaat het meer over de kosten dan over de equivalentie. Je verandert de vorm van de pijl van $A \to B$ naar $[A] \to [B]$, zodat je de opstartkosten slechts één keer per batch betaalt.
Groetjes,