Rob Pikes Programmierregeln (1989)
(users.ece.utexas.edu)- Ein Artikel über Rob Pikes fünf Programmierregeln aus dem Jahr 1989
- Regel 1: Gehe nicht davon aus, wo ein Programm die meiste Zeit verbringen wird; Engpässe können unerwartet auftreten. Vermeide Speed-Hacks, bis ein Engpass nachgewiesen ist.
- Regel 2: Miss immer zuerst, bevor du auf Geschwindigkeit hin optimierst. Optimiere nur, wenn ein Teil des Codes einen erheblichen Einfluss auf den Rest hat.
- Regel 3: Komplexe Algorithmen sind langsam, wenn n klein ist. Das ist in den meisten Fällen so. Verwende komplexe Algorithmen nur, wenn n häufig groß ist, und wende auch dann zuerst Regel 2 an.
- Regel 4: Einfache Algorithmen und Datenstrukturen sind wünschenswert. Sie sind weniger fehleranfällig als komplexe und leichter zu implementieren.
- Regel 5: Die richtige Datenstruktur ist entscheidend für das Programmieren. Wenn die Daten gut strukturiert sind, wird der Algorithmus offensichtlich.
- Pikes Regeln 1 und 2 spiegeln Tony Hoares Diktum wider: "Vorzeitige Optimierung ist die Wurzel allen Übels."
- Ken Thompson formulierte Pikes Regeln 3 und 4 neu als: "Im Zweifel setze rohe Gewalt ein."
- Regeln 3 und 4 setzen die KISS-Designphilosophie (Keep It Simple, Stupid) um.
- Regel 5 stimmt mit einer Aussage aus Fred Brooks' The Mythical Man-Month überein, die oft verkürzt wird zu: "Schreibe dummen Code, der intelligente Objekte verwendet."
1 Kommentare
Hacker-News-Kommentare
Ich stimme der Aussage "Daten bestimmen alles" voll zu.
Deshalb kamen mir LeetCode-Interviews immer seltsam vor. Meist liegt der Fokus auf Algorithmen, aber in der Praxis sollte man oft gerade nicht von Anfang an so herangehen, und Datenstrukturen sollten stärker im Mittelpunkt stehen.
Natürlich kann man, wenn man gar nichts über Algorithmen weiß, leicht übersehen, wann man wegen Sonderfällen oder aus bestimmten Gründen auf einen bestimmten Algorithmus setzen muss. Trotzdem lassen sich Algorithmen vergleichsweise kurz vermitteln, während es vielen deutlich schwerer fällt, ein Gefühl dafür zu entwickeln, welche Datenstruktur man verwenden sollte.
In dem Moment kippt die Atmosphäre zu "Ah, jetzt ist wirklich ein Senior Engineer im Raum", technische Probleme werden viel offener diskutiert, und der Drang, einen erst einmal beweisen zu lassen, dass man "überhaupt programmieren kann", nimmt ab.
Umgekehrt waren die Teams, mit denen ich am meisten Schwierigkeiten hatte, wenn es darum ging, gute Veränderungen umzusetzen, Meilensteine zu erreichen und zusammenzuarbeiten, genau die, in denen niemand Datenstrukturen und Code-Architektur richtig im Griff hatte. Viele scheinen sich daran gewöhnt zu haben, dass Frameworks alles erledigen und, wenn das nicht reicht, ein Plugin oder Middleware von jemand Klügerem das Problem schon lösen wird.
Ein Engineer, der Datenstrukturen aus dem Weg geht, schadet sich letztlich selbst, verzichtet auf eines der nützlichsten Werkzeuge überhaupt und stößt im Alltag entsprechend schnell an Grenzen.
Zum Beispiel lässt sich Code häufig einsetzen, um den längsten Pfad in einem gewichteten gerichteten azyklischen Graphen (DAG) zu finden, aber der eigentliche Kern war zu erkennen, dass sich das Problem als gewichteter DAG darstellen lässt. Wenn man das nicht sieht, kann man es zwar immer noch lösen, aber mit einer viel langsameren und komplizierteren Lösung.
Der Interviewer sagt einem nicht vorab, dass man hier eine Prioritätswarteschlange, eine Adjazenzmatrix oder einen Trie verwenden sollte. Wenn man feststeckt, kann es Hinweise geben, aber zu viel Lenkung wirkt kaum wie ein starkes Einstellungssignal.
Zur Aussage "Ein raffinierter Algorithmus ist langsam, wenn n klein ist, und n ist meistens klein" habe ich in einem aktuellen Projekt eher erlebt, dass großes n viel größer sein kann, als man denkt.
Man denkt schnell: "Dafür braucht man 100.000 Operationen, das muss unbedingt optimiert werden", aber Computer sind schnell, und 100.000 Multiplikationen sind meist so schnell, dass man darüber gar nicht tief nachdenken muss.
Das heißt nicht, dass man gar nicht nachdenken sollte, aber es ist immer wieder erstaunlich, wie absurd schnell moderne Hardware ist.
Ich habe Produktionsausfälle wegen versehentlich quadratischer Laufzeit gesehen, und selbst wenn 99 % der Nutzer immer nur kleine n haben, stoßen einige Nutzer regelmäßig auf große n und erleben dann eine extrem langsame App.
In den meisten Fällen würde ich lieber einen Algorithmus wählen, der besser als quadratisch ist, auch wenn er im Normalfall etwas langsamer und in der Implementierung etwas komplexer ist. Häufige langsame Pfade werden optimiert, aber seltene langsame Pfade übersieht man leicht, weil Entwickler selbst nicht darüber stolpern, oder sie explodieren erst in der Produktion.
Natürlich würde ich bei einem zu komplexen Algorithmus vielleicht trotzdem die einfache quadratische Implementierung wählen, aber als Standard versuche ich, wenn möglich unter quadratisch zu bleiben. Dazu gibt es auch einen Text von mir: https://kevincox.ca/2023/05/09/less-than-quadratic/
Deshalb traf das vielleicht vor 40 Jahren besser zu, als CPUs im Verhältnis zum Speicher nicht so schnell waren und man sich auf Consumer-Hardware noch weit weniger um Fehlvorhersagen bei Sprüngen kümmerte.
In Interviews passiert dann oft, dass der Hiring Manager es gerne so hätte, aber ein LeetCode-Anfänger, der die Narben aus dem Betrieb noch nicht erlebt hat, diese Entscheidung ablehnt.
https://www.frankmcsherry.org/assets/COST.pdf
Wenn man die Leistungssteigerungen der letzten 20 Jahre bedenkt, scheint es ziemlich passend, diesen Schwellenwert auf 100.000 anzuheben.
Das berühmte Bonmot „Vorzeitige Optimierung ist die Wurzel allen Übels“ stammt nicht von Tony Hoare, sondern tatsächlich von Donald Knuth, und wird oft ohne Kontext so verwendet, als richte es sich gegen Optimierung im Allgemeinen
Der vollständige Satz lautet: „Wir sollten kleine Effizienzgewinne, sagen wir in 97 % der Fälle, vergessen. Vorzeitige Optimierung ist die Wurzel allen Übels. Aber wir sollten Gelegenheiten in den entscheidenden 3 % nicht verpassen.“
Der Kern ist, Zeit für Optimierung dort einzusetzen, wo sie tatsächlich Wirkung hat
Vielleicht hat Tony es zuerst gesagt und Knuth hat es ausgearbeitet und veröffentlicht. Es ist immer gut, das längere Zitat mitzuliefern, das den nötigen Kontext gibt
Programmierung sah damals ganz anders aus als heute. „Vorzeitige Optimierung“ bedeutete damals eher nicht „Lass uns einfach die skalierbare populäre Bibliothek verwenden“, sondern eher „Lass uns einen unverständlichen Bit-Manipulationsalgorithmus verwenden, der nur auf dieser Hardware läuft“
Das steckt bereits in der Aussage „Vorzeitige Optimierung ist die Wurzel allen Übels“, und das Bonmot sagt nicht „Optimierung ist die Wurzel allen Übels“
Ich habe in Vorstellungsgesprächen zu Datenstrukturen und Algorithmen im Unternehmen unzählige Frontend-Entwickler erlebt, die sagten, Bubble Sort sei das Beste. Man muss es nicht aus dem Stand herleiten können; es reicht, ein paar Verfahren zu kennen und für das Problem eine gute Wahl zu nennen
Wenn man „Optimiere nicht zu früh“ so extrem lebt, dass man nicht einmal effiziente Verfahren kennt, wie will man dann wissen, was wichtig ist
Die Aussage „Datenstrukturen sind entscheidend“ gilt bei Datenbanken doppelt
Menschen, die eine DB wie einen dummen Bit-Speicher oder nur als 1:1-Abbild ihrer Objektdefinitionen verwenden, sind oft überrascht, wenn die DB das persönlich nimmt und die Performance ruiniert
Wenn ich noch einmal ein von einem ORM erzeugtes DB-Schema sehen muss, wäre das eine viel zu frühe Wiederbegegnung
Das Problem ist, dass manche oder viele Entwickler kein SQL beherrschen und auch nicht das DB-Wissen haben, das man selbst für die Nutzung eines ORM braucht
Ein ORM ist eine ziemlich undichte Abstraktion, bei der man wissen muss, was darunter liegt. Wenn man das versteht, kann man mit den meisten ORMs ein brauchbares Schema erzeugen
Um Datenstrukturen gut zu organisieren und das auch bei Designänderungen beizubehalten, muss man Daten und Code auf Organisationsebene trennen
DB-Schema-Design, Use Cases und das Mapping dazwischen sollten von der restlichen Implementierung getrennt sein, und diese Gruppe sollte auch Dinge wie Integritätsprüfungen schreiben. Wenn die Organisationsstruktur Daten und Code nicht trennt, ist es schwer, Code und Daten zu trennen
Meine zusätzliche Regel ist, dass sich kleine Performance-Verschwendungen aufsummieren und ein Programm am Ende verlangsamen, auch wenn jede für sich unbedeutend ist
Wenn es keine Auswirkungen auf Komplexität, Lesbarkeit, Wartbarkeit oder Implementierungskosten hat, sollte man Performance nicht einfach liegen lassen. Wenn die übrigen Bedingungen weitgehend gleich sind, ist es nicht sinnvoll, von zwei Optionen die langsamere zu wählen
Und wenn man annimmt, dass n klein ist, funktioniert fast alles. Aber wenn man Code wie etwa O(n²) schreibt, der bei n unter 100 gut läuft und bei über 10000 zusammenbricht, dann sollte man einfach eine Grenze einziehen. Wenn die Annahme eines kleinen n bricht, ist ein deutlicher Fehler besser als eine explodierende AWS-Rechnung oder ein hängendes Programm
Viele dieser Richtlinien laufen letztlich auf Strategien hinaus, Overengineering zu verhindern
Meiner Erfahrung nach ist vorzeitige Optimierung eine der teuersten Fallen überhaupt. Wenn man potenzielle Probleme zu früh umgeht, werden diese Annahmen nicht validiert, und das nächste Team muss eine teure Lösung bauen, um unnötige Komplexität zu beseitigen
Der Ansatz, den ich gelernt habe, ist folgender: Optimierung beruht auf Schätzungen, und frühe Schätzungen sind oft falsch
Außerdem habe ich gelernt, dass ziemlich viel Ego-Management und psychologisches Verständnis nötig ist, wenn man verhindern will, dass Leute unnötig komplizierten Code schreiben
Überproduktion gilt meist als die schlimmste Form von Verschwendung, weil man nicht nur etwas Unnötiges baut, sondern auch Aufwand verbraucht, der für das tatsächlich Benötigte hätte eingesetzt werden können. Bei Overengineering ist es ähnlich
Zum Beispiel startet man mit einer Microservices-Architektur, obwohl man nur 100 Nutzer hat, weil es irgendwann bei 1 Million Nutzern schwer sein könnte, einen Monolithen neu zu gestalten
Deshalb muss man im Lauf der Zeit zuerst angehen, warum der Code immer weniger formbar wird
Insgesamt gute Regeln, aber in der Praxis gilt Regel 1 nicht unverändert.
Zu Beginn braucht man eine Hypothese, was zum Bottleneck werden könnte. Es ist nicht immer möglich, einfach XYZ zu implementieren und danach zu messen, was langsam ist, und es dann zu beheben. X, Y und Z können so zusammenhängen, dass man X und Z auf eine bestimmte Weise bauen muss, um Y schnell zu machen, und manchmal weiß man bereits, dass Y der Bottleneck sein wird.
Selbst wenn man später misst und herausfindet, was langsam ist, muss man auf einen Ansatz setzen, der schneller werden kann. Je fundierter diese Wette ist, desto besser.
Gute Programmierer messen, aber sie können auch vorhersagen, was langsam sein wird, wo viele Bugs auftreten und was viel Speicher verbraucht, sodass sie weniger Iterationen brauchen. Wenn man als Regel formuliert, dass man das Laufzeitverhalten nicht vorhersagen könne, ignoriert man die Erfahrung und das Können guter Programmierer.
Denn gerade das Befolgen von Regel 1 ist der beste Weg, die Erfahrung und den empirischen Hintergrund zu gewinnen, die man für eine gute Intuition zur Vorhersage von Bottlenecks braucht.
Wenn die Geschwindigkeitsprognose falsch ist, trägt man unter Umständen die gesamte Lebensdauer des Projekts unnötig komplexen Code mit sich herum.
Menschen liegen bei der Geschwindigkeit von Algorithmen oft falsch. Wenn der Computer 99 % seiner Zeit damit verbringt,
nvom DB-Server zu holen, sehen O(n) und O(n²) in der realen Laufzeit oft gleich aus.Manchmal ist ein in C geschriebener Algorithmus sogar langsamer als gleichwertiger Python-Code, weil der Bytecode-Compiler etwas Cleveres gemacht hat.
Ich habe viel daran gearbeitet, Legacy-Code schneller zu machen, und meist ist das viel einfacher als gedacht, und der Code ist aus Gründen langsam, die dem ursprünglichen Autor nicht klar waren. In der Praxis ist er oft langsam, weil die Codebasis so komplex geworden ist, dass der ursprüngliche Autor nicht mehr sinnvoll darüber nachdenken konnte. Für mich ist das ein konkretes Beispiel von „zu langsam“, weil ich es ausführen und beim Beobachten der langsamen Stellen leicht debuggen kann.
Wenn man ein Videospiel mit vielen physikalischen Objekten baut und aus Erfahrung sicher weiß, dass die Kollisionserkennung ein großes Problem sein wird, dann ist es kein Speed-Hack, das Spiel und das System darum herum zu entwerfen.
Bei Arbeiten, bei denen man weiß, dass Performance ein großes Thema wird, sollte man natürlich messen. Man versucht nicht herauszufinden, ob es überhaupt ein Thema ist, sondern wie gut man damit umgeht.
Wenn man wegen neuer Anforderungen ein neues System baut, kann man oft einfach erst einmal anfangen. Man baut es, testet und misst, verwirft oder refaktoriert und wiederholt das Ganze.
Rust zum Beispiel begann mit einer Entwurfssprache und einem in OCaml geschriebenen Compiler und wurde dann iterativ weiterentwickelt. Selbst wenn man wusste, dass man irgendwann von OCaml auf Self-Hosting umsteigen könnte, bin ich nicht sicher, ob das einen großen Unterschied gemacht hat.
Wenn es keine Nutzer gibt, ist selbst eine Funktion, die Stunden braucht, immer noch schnell genug im Vergleich zu einer Funktion, die nach einer Optimierung Millisekunden braucht. Ich bin nicht sicher, ob es überhaupt jemanden gibt, der bewiesen hat, dass solche Vorhersagen zuverlässig möglich sind.
Als Gegenargument zu Regel 5: Komplexe Algorithmen auf einfachen Daten können große Performancegewinne bringen, Hindernisse beseitigen und dadurch sogar vereinfachen.
Zum Beispiel kann man statt eines BinaryTree-Objekts eine binäre Suche auf einem sortierten Array verwenden; Merges werden dann zu concat plus Sortierung, es gibt keine Pointer, die Serialisierung wird einfacher, und in manchen Fällen braucht man überhaupt keine Serialisierung mehr. Arrays können auf der Platte, im Speicher oder per
mmapin beidem liegen, man kann Daten verarbeiten, die größer als der RAM sind, und sogar Cold Starts haben, bei denen man nur auf Dateien oder Mappings zeigt und sofort loslegt. Außerdem gibt es cache-oblivious Eigenschaften.Huffman-Codierung ist ein weiteres Beispiel. An der Universität habe ich sie üblicherweise als baumbasierten Algorithmus mit O(n log n)-Komplexität gelernt, wusste aber nicht, dass es auch eine Möglichkeit gibt, einen Huffman-Baum in linearer Zeit in-place auf Array-Basis zu konstruieren.
Natürlich verbringt man 99 % der Zeit damit, Backend-Microservices zu bauen und Standard-Collections zu verwenden. Aber wenn ich im Job Big-Data-Arbeit machen würde, würde ich die Verarbeitung auf einer einzelnen Maschine mit großen lokalen Festplatten meist deutlich bevorzugen, statt irgendein gerade angesagtes MapReduce-artiges System einzuführen.
Rob Pike hätte vermutlich gesagt, man solle den Code zuerst profilen und dann prüfen, ob der clevere Code oder die alternative Datenstruktur tatsächlich schneller ist.
Ich habe diesen Text vor mehr als zehn Jahren zum ersten Mal auf cat-v gelesen, und er hat unauslöschlich beeinflusst, wie ich an Design und Komplexität herangehe und darüber nachdenke.
http://doc.cat-v.org/bell_labs/pikestyle
Ich verstehe nicht, wie man von der ursprünglichen Regel „Datenstrukturen sind zentral“ zu „Schreibe dummen Code mit smarten Objekten“ kommt.
Die Formulierung „smart objects“ war ziemlich schlecht, und die ursprüngliche Regel war trotz ihrer Länge viel besser.