Sieben O(N²)-Algorithmen an einem Samstag ersetzt

Ihre KI kann Code schreiben, der funktioniert. Code zu schreiben, der skaliert, ist das, wo eine räumliche Runtime gewonnen oder verloren wird – und genau das ist die Disziplin, um die herum RakuAI gebaut ist.

Die Agenten sind gut darin, Code zu schreiben, der funktioniert. Sie sind manchmal schlecht darin, Code zu schreiben, der skaliert. Das ist ein Muster, das ich mittlerweile erkenne und einplane: Wenn die Issue-Rahmung nach einer Funktion fragt, die X tut, schreibt der Agent eine Funktion, die X bei einer kleinen Eingabe korrekt tut und bei einer real großen zusammenbricht.

Diesen Samstag habe ich gezielt nach diesen Funktionen gesucht. Sieben davon kamen zurück. Bis zum Ende des Samstags liefen alle sieben mit ihren tatsächlichen Produktionsalgorithmen statt den Brute-Force-Platzhaltern, die die Agenten ursprünglich hatten landen lassen.

Das ist der Beitrag darüber, was jeder einzelne war, warum es wichtig war, und was die Agenten bei jedem falsch gemacht haben.

Das Muster

Das Muster zeigt sich so. Ein Issue wird angelegt. „Implementiere Kollisionserkennung zwischen Objekten A und B. Sollte erkennen, wann Objekte sich überlappen. Abnahmekriterium: Bool-Funktion gibt true zurück, wenn sie sich überlappen, sonst false.”

Der Agent schreibt die Funktion. Die Funktion funktioniert. Die Funktion ist O(N²)-Brute-Force. Für zwei Objekte ist das in Ordnung. Für zweihundert Objekte ist das in Ordnung. Für zweitausend Objekte ist die Framerate verschwunden.

Der Prompt des Agenten spezifizierte die asymptotische Komplexität nicht. Der Agent erfüllte den Prompt. Der Prompt erfüllte nicht die Engine.

Das ist ein Disziplinproblem auf meiner Seite, kein Agentenproblem. Der Fix besteht darin, im Prompt spezifisch bei Komplexitätszielen zu sein, die Algorithmenklasse explizit anzugeben, wenn es wichtig ist, und regelmäßig auf diese Art von Brute-Force-Fallback zu auditieren. Dieser Samstag war der Audit-Rhythmus.

Sieben konkrete Ersetzungen

Ich möchte bei jeder konkret sein, weil das Muster identisch ist und die Lektionen sich aufaddieren.

Eins. 2D-Physik-Grobphasen-Kollisionserkennung. Die ursprüngliche Implementierung war eine doppelt verschachtelte Schleife über jedes Objektpaar. O(N²) pro Frame. Ersetzt durch Sweep-and-Prune (Baraff, 1992): Die achsenausgerichteten Bounding-Boxen werden nach ihrer minimalen X-Koordinate sortiert, dann einmal durchgescannt. Paare überlappen sich auf der X-Achse nur, wenn das maximale X einer Box größer ist als das minimale X der anderen. Die Sortierung ist O(N log N); der Scan ist O(N + K), wobei K die Anzahl tatsächlich überlappender Paare ist. Bei typischen Szenen ist K viel kleiner als N², was der ganze Punkt ist.

Zwei. Räumliche Kollisionserkennung für das Agent-Population-Subsystem. Dasselbe Muster, andere Fläche. Die ursprüngliche Implementierung war eine doppelt verschachtelte Schleife, die jeden Agenten gegen jeden anderen Agenten prüfte. Ersetzt durch ein Spatial-Hash-Grid. Jeder Agent wird nach seinen Bounding-Cell-Koordinaten gehasht; Kollisionen werden nur zwischen Agenten in derselben oder benachbarten Zellen geprüft. Die Zellgröße wird auf ungefähr das Zweifache des durchschnittlichen Agentenradius gewählt. Erwartete Komplexität O(N), Worst Case O(N²), wenn alle in derselben Zelle sind, was im normalen Spielbetrieb nicht vorkommt. Die Hash-Funktion ist FNV-artiges 3D-Koordinaten-Hashing. Die Paar-Deduplizierung erfolgt über ein geordnetes uint64_t-Set von (min(a,b), max(a,b))-Paaren.

Drei. Vertex-Cache-Optimierung des Modell-Loaders. Die ursprüngliche Implementierung lud Vertices und Dreiecke in der vom Asset-Autor angegebenen Reihenfolge in den Renderer. Die meisten Autorenwerkzeuge optimieren nicht für den Vertex-Cache der GPU, was bedeutet, dass der Renderer viele Zyklen damit verschwendet, Vertices erneut abzurufen, die er schon hatte. Ersetzt durch Tom Forsyths Vertex-Cache-Optimierung von 2006: ein LRU-Cache-Modell mit einer Größe von 32, das jedes Kandidaten-Dreieck über eine Position-im-Cache-Zerfallsfunktion plus einen Valenz-Bonus bewertet (Dreiecke, die Vertices mit vielen anderen unverarbeiteten Dreiecken teilen, punkten höher). Das Ergebnis ist eine amortisierte Cache-Miss-Rate, die für typische Mesh-Topologien nahezu optimal ist. Die Implementierung läuft in O(T), wobei T die Dreiecksanzahl ist.

Vier. Abgleich von Vision-Feature-Deskriptoren. Die Computer-Vision-Pipeline der Runtime führt bei jedem Frame Feature-Erkennung durch und gleicht Features zwischen aufeinanderfolgenden Frames zum Tracking ab. Die ursprüngliche Implementierung hatte einen Platzhalter, der einen festen Anteil der Eingabe-Deskriptoren als „abgeglichen” zurückgab. Der Platzhalter war nicht einmal Brute-Force. Er war ein bewusster Stub. Der Ersatz ist echter Brute-Force-Deskriptor-Abgleich mit Lowes Ratio-Test (2004). Für ORB-Deskriptoren (binär) ist die Distanzmetrik Hamming via XOR plus eine Kernighan-Bit-Zählung. Für SIFT- und Float-Deskriptoren ist die Distanz L². Der Ratio-Test verwirft mehrdeutige Übereinstimmungen, bei denen der beste und der zweitbeste Kandidat in der Distanz zu nah beieinanderliegen. Der Schwellenwert für den Ratio-Test ist 0,75, der Standardwert in der Literatur. Die Komplexität ist O(N₁ × N₂ × D), wobei D die Deskriptor-Dimension ist, die bei ORB 32 Byte beträgt. Das ist Brute-Force im wörtlichen Sinne, aber bei den Deskriptorlängen und Feature-Anzahlen, mit denen wir arbeiten, ist es schnell genug und das, womit die Literatur vergleicht. Klügere Näherungen (FLANN, hierarchisches k-Means) stehen für ein späteres Wochenende auf der Warteliste.

Fünf. Constraint-Solver für Stoffphysik. Die ursprüngliche Implementierung iterierte Constraints in fester Reihenfolge mit niedriger Iterationszahl, was wackligen Stoff erzeugte, der nicht konvergierte. Ersetzt durch einen Position-Based-Dynamics-Solver mit ordentlichem Constraint-Shuffling zwischen den Iterationen. Das Shuffling ist wichtig, weil Constraint-Solver, die Constraints immer in derselben Reihenfolge verarbeiten, verzerrt werden: Stoff dehnt sich am Ende vorhersehbar in eine Richtung. Shuffling bei jeder Iteration entfernt die Verzerrung. Die Iterationszahl wurde von 4 auf 12 für Produktionsqualität angehoben, mit einem 4-Iterationen-Schnellpfad für Low-End-Geräte.

Sechs. KI-Agenten-Pfadplanung für das Crowd-Subsystem. Die ursprüngliche Implementierung war ein Platzhalter, der bei jedem Schritt einen zufälligen gültigen Nachbarn wählte. Agenten wanderten in zufälligen Richtungen und kamen gelegentlich durch Zufall an ihren Zielen an. Ersetzt durch ordentliche A*-Pfadplanung über das Navigationsnetz, mit Euklidischer Distanz als Heuristik und einer Kostenfunktion, gewichtet nach Geländesteigung und Oberflächentyp. Die Implementierung verwendet einen binären Heap für die offene Menge und eine Hash-Menge für die geschlossene Menge, was die Kosten pro Schritt auf O(log N) beim Heap und O(1) bei der Hash-Menge bringt.

Sieben. Animations-Blending über mehrere Clips hinweg. Die ursprüngliche Implementierung war ein Platzhalter, der einfach den zuletzt angeforderten Clip abspielte und die anderen ignorierte. Ersetzt durch einen ordentlichen gewichteten Blend-Baum: Jeder Ausgabe-Frame ist eine gewichtete Summe der Pro-Bone-Transformationen der beitragenden Clips, mit Gewichten, die von einer Blend-Baum-Topologie gesteuert werden, die der Animationsautor angibt. Die Blend-Berechnung respektiert die Bone-Hierarchie-Reihenfolge, sodass Kind-Bones geblendete Eltern-Transformationen korrekt erben.

Was ich gelernt habe

Drei Dinge, von denen im Nachhinein keines überraschend ist.

Den Algorithmus im Issue spezifizieren. Für jede Funktion, die auf einer nicht-trivialen Eingabegröße operiert, muss die Issue-Rahmung die erwartete Komplexität angeben. „Erkenne Kollisionen zwischen N Objekten” reicht nicht. „Erkenne Kollisionen zwischen N Objekten im Worst Case O(N log N) mittels Sweep-and-Prune (Baraff 1992) oder gleichwertig” reicht. Die Zitation ist die Disziplin. Ohne sie schreibt der Agent die einfachste korrekte Sache, und das ist Brute-Force.

Der Audit-Durchgang ist essenziell. Ich hätte diese nicht abgefangen, indem ich PRs beim Landen las. Jeder einzelne PR war eine Funktion, die funktionierte, mit Tests, die bestanden. Der Audit-Durchgang, der fragt „finde jede Funktion in der Runtime, die O(N²) oder schlechter ist, und beurteile, ob sie es sein sollte”, ist das, was sie zutage bringt. Das Audit dem Rhythmus hinzufügen.

Die Literatur ist der Cheat-Code. Jede dieser Ersetzungen ist ein veröffentlichter Algorithmus mit einem jahrzehntealten Paper dahinter. Baraff 1992. Forsyth 2006. Lowe 2004. Position-Based Dynamics. A*. Das sind keine Neuheiten. Die Agenten schreiben die literaturäquivalente Version von jedem davon, wenn man ihnen sagt, welches Paper sie lesen sollen.

Was Partner und Entwickler daraus mitnehmen sollten

Wenn Sie eine Engine für eine Partnerschaft evaluieren und das Team hat kein algorithmisches Audit seiner Codebasis durchgeführt, bitten Sie sie, eines zu machen. Das Audit wird Dinge zutage bringen. Die Reaktion des Teams auf das, was es zutage bringt, ist aussagekräftiger als jede Feature-Liste.

Wenn Sie einen agentengetriebenen Workflow auf einer performance-sensiblen Codebasis betreiben, ist der Audit-Durchgang nicht optional. Die Agenten werden funktionierenden Code landen. Der funktionierende Code wird manchmal die Brute-Force-Version sein. Das Audit ist, wie man herausfindet, welche.

Wenn Sie ein KI-Labor sind, das einen Coding-Agenten für performance-sensible Arbeit baut, ist die Metrik, für die ich optimieren würde: „Fragt der Agent nach asymptotischer Komplexität, wenn er eine Funktion implementiert, deren Name ein Skalierungsanliegen impliziert.” Die meisten Agenten tun das nicht. Diejenigen, die es tun, produzieren besseren Code.

Samstagnachmittag. Sieben Brute-Force-Algorithmen durch ihre echten Produktionsversionen ersetzt. Die Engine wurde schneller. Die Codebasis wurde ehrlicher.

Zurück zum Bauen.