Push Ifs Up, Fors Down: Die Algebra hinter der Code-Optimierung
Push Ifs Up and Fors Down: The Idiom, Its Algebra, and Its Limits
Das Programmier-Idiom „Push Ifs Up and Fors Down“ besagt, dass bedingte Logik nach oben (zum Aufrufer) und Schleifen nach unten (in Batch-Operationen) verschoben werden sollten. Der Artikel zeigt, dass dieses Prinzip weit über einfache Refactorings hinausgeht: Es findet sich in relationalen Datenbank-Optimierungen (Projektionen und Selektionen früh, Joins spät) und in der Kategorientheorie wieder. Dort entspricht das Hochziehen von Ifs einer Einschränkung auf ein Subobjekt, und die Regel „Filter vor Map“ folgt aus der Natürlichkeit von catMaybes. Doch jede Rewrite-Regel hat Grenzen – die Algebra sagt, wann sie legal ist.
Es ist die Algebra, die dir sagt, welche Rewrites legal sind.
- socializer
Ich bin immer wieder beeindruckt von der Fähigkeit von LLMs, triviale Ideen in langatmige und schwerfällige Blogbeiträge mit unnötigen Analogien zu verwandeln.
- hatthew
Reden wir darüber aus der Perspektive der Informatik (Algorithmusoptimierung) oder des Software Engineering (Codedesign)?
Aus Sicht des Software Engineering: Schreib eine flatmap-Funktion, die explizit Collection<Optional<Walrus>> behandelt. Die Implementierung spielt keine Rolle. Wenn deine Sprache/dein Framework bereits eine kompatible flatmap-Funktion hat, schreib eine einzelne frobnicate(Optional<Walrus>)-Funktion, die den Wert zurückgibt, der nötig ist, damit flatmap(frobnicate) sie verwerfen kann.
Aus Sicht der Informatik: Ein Filter von Collection<Optional<Walrus>> nach Collection<Walrus> ist wahrscheinlich keine gute Idee. Wenn deine Collection klein ist, spielt nichts eine Rolle. Wenn deine Collection groß ist, willst du wahrscheinlich keine Zeit damit verbringen, eine neue Kopie davon zu erstellen. Wenn dein Filter nur eine View statt einer harten Kopie zurückgibt, dann gibt es keinen Optimierungsvorteil und du solltest einfach das tun, was aus Software-Engineering-Sicht am sinnvollsten ist. Wenn frobnicate billig ist, zahlst du sowieso die Branch-Prediction-Failure-Steuer, egal wann du frobnicatest, und wenn frobnicate teurer ist, solltest du wahrscheinlich parallelisieren und jeden Thread das Auspacken des Optional übernehmen lassen. So oder so willst du wahrscheinlich keine Zeit damit verbringen, eine Kopie zu erstellen.
Das sind alles Verallgemeinerungen auf Basis von Hypothesen und es gibt sicherlich viele Ausnahmen, aber allgemein gesprochen sehe ich hier kein starkes Argument. Wenn Optimierung wichtig ist, dann optimiere basierend auf deinem eigenen Profiling deiner Situation, und wenn Optimierung nicht wichtig ist, dann entwirf deine Funktionen basierend auf dem, was [...]
- rtpg
Ich habe immer das Gegenteil geglaubt: Bringe Bedingungen tief in deinen Code, damit der übergeordnete Kontrollfluss regelmäßig ist.
Aber ich schätze, meine übergeordnete Philosophie für Code, der Fehler vermeidet, ist, dass man ein paar Dinge hat, die man beim Umgang mit Daten tut:
- Verteilen
- Entscheiden
Und man möchte vermeiden, dass Verteilen und Entscheiden an derselben Stelle vermischt werden.
"Verteilen" kann for-Schleifen sein, aber auch das Aufteilen von Daten anhand eines Schlüssels in N verschiedene Buckets.
"Entscheiden" ist, wo man die Daten genauer betrachtet, um eine Entscheidung zu treffen (wie "ist das ein großer Kunde oder ein kleiner Kunde").
Verteilen beinhaltet oft Entscheidungsfindung, aber wenn man alles an einer Stelle vermischt, kann man seine Entscheidungspunkte verschleiern. Wenn man es aufteilt, wird es einfach "offensichtlich" richtig oder "offensichtlich" falsch. Performance-Zeug ist natürlich eine andere Diskussion, aber in der Praxis sind die meisten Dinge nicht in einem Maßstab, wo es eine Rolle spielt.
by_category = defaultdict(list)
for d in data:
by_category[category(d)].append(d)
for category, per_category_data in by_category.items():
do_thing(category, per_category_data)
Ich schätze Codemuster sehr, die Fehler offensichtlich machen oder es zumindest schwerer machen, einen Fehler irgendwo unterzubringen. Manche Muster sind in diesem Modell allerdings schwerer zu beschreiben.
(Ich mag allerdings den Rat, ein konsistentes Vokabular für die Arbeit mit Collections als Prinzip zu haben, aber ich finde, dass die Verwendung von Bedingungen auf oberster Ebene einen schnell in "... warum ist diese Methode n[...]" bringt.)
- ivanjermakov
Sparen Sie sich etwas Zeit und lesen Sie stattdessen den Originalbeitrag: https://matklad.github.io/2023/11/15/push-ifs-up-and-fors-do...
- gorgoiler
Ähm, nein? Du schreibst f(w: Walrus) -> Walrus und lässt dann den Aufrufer Walrus|None und Iterable[Walrus] handhaben, wie er will!
Und wenn jemand entscheidet, dass die Codebasis eine Abstraktion über (und damit spezifische Funktionen für) Iterable[Walrus|None] braucht, dann checkst du das Wetter und schlägst vor, dass er eine Pause macht und einen Spaziergang unternimmt. (Du checkst das Wetter, um zu sehen, ob du ihm deinen Regenschirm leihen solltest.)
Was übersehe ich?