- Zur Visualisierung des JavaScript- und WebAssembly-Kompilierungsprozesses der SpiderMonkey-Engine wurde das interne Tooling umfassend überarbeitet und um die Erzeugung interaktiver Graphen erweitert
- Das bisherige Graphviz-basierte iongraph litt unter instabilen Layouts und einer unintuïtiven Struktur, was die Effizienz beim Debugging verringerte; als Ersatz wurde daher ein neuer Layout-Algorithmus eigens entwickelt
- Der neue Algorithmus vereinfacht den Sugiyama-Ansatz, stellt Schleifenstrukturen klar dar und implementiert ein stabiles, schnelles Layout in weniger als 1000 Zeilen JavaScript-Code
- Die Graphen nutzen geradlinige Kanten im Stil von Eisenbahndiagrammen, was die Lesbarkeit erhöht, und erreichen Render-Geschwindigkeiten, die gegenüber Graphviz um ein Vielfaches höher sind
- Das Tool ist in den Firefox-Profiler integriert; zudem sind Erweiterungen wie Suche und Register-Visualisierung geplant
Überarbeitung des Visualisierungstools von SpiderMonkey
- Zur Visualisierung der internen Graphen, die vom Ion-Optimierungscompiler von SpiderMonkey erzeugt werden, wurde das Tool neu aufgebaut
- Nutzer können auf einer Webseite JavaScript-Code eingeben und den Funktionsoptimierungsprozess in Echtzeit als Graph erkunden
- Der Graph lässt sich per Ziehen, Zoom und Slider bedienen, um Änderungen Schritt für Schritt nachzuverfolgen
- Das bisherige Graphviz-basierte iongraph erzeugte PDF-Ausgaben, stimmte jedoch nicht mit der Struktur des Quellcodes überein und litt unter erheblicher Instabilität der Ausgabe
- Schon kleine Codeänderungen konnten die Positionen der Knoten stark verschieben, wodurch Vergleiche zwischen Passes schwierig wurden
- Schleifen- und Bedingungsstrukturen wurden visuell verzerrt, wodurch der Kontrollfluss schwer zu erkennen war
Grenzen von Graphviz und der neue Ansatz
- Der Sugiyama-Algorithmus von Graphviz eignet sich für die Optimierung allgemeiner Graphen, bildet jedoch die Eigenschaften von Kontrollflussgraphen (CFGs) nicht gut ab
- Schleifen in JavaScript und WebAssembly haben nur einen einzigen Einstiegspunkt und besitzen einen reduzierbaren (reducible) Kontrollfluss
- Das SpiderMonkey-Team nutzte diese Einschränkungen, um einen vereinfachten spezialisierten Algorithmus zu entwerfen
- Zyklen entfernen: Loop-Backedges werden ignoriert
- Schichtung (Leveling): Blöcke nach einer Schleife werden weiter unten platziert, um den Codefluss abzubilden
- Kreuzungsminimierung ausgelassen: Zur Priorisierung der Stabilität bleibt die Reihenfolge von True-/False-Verzweigungen fest
- Erhalt der Schleifenbaumstruktur: Verschachtelte Schleifen werden visuell klar dargestellt
- Das Ergebnis ist ein kompaktes, schnelles und stabiles Layout; die erste Implementierung umfasst rund 1000 Zeilen JavaScript
Schritte des iongraph-Layout-Algorithmus
- Schritt 1: Layering
- Blöcke werden nach Ebenen angeordnet, unter Berücksichtigung von Beziehungen innerhalb und außerhalb von Schleifen
- Blöcke nach dem Ende einer Schleife werden um die gesamte Höhe der Schleife weiter unten platziert
- Schritt 2: Erzeugung von Dummy-Knoten
- Für Kanten, die mehrere Ebenen überqueren, werden Dummy-Knoten eingefügt, um visuelle Kollisionen zu vermeiden
- Kanten mit demselben Ziel werden zusammengeführt, um visuelles Rauschen zu reduzieren
- Schritt 3: Kantenausrichtung (Straighten)
- Eltern- und Kindknoten werden ausgerichtet, damit vertikale Linien erhalten bleiben; zudem wird Schleifen-Einrückung angewendet
- Auch Dummy-Knoten nehmen an der Ausrichtung teil, um Überlappungen zu vermeiden und die Struktur zu bewahren
- Schritt 4: Tracking horizontaler Kanten
- Horizontale Kanten werden in Tracks angeordnet, damit sie sich nicht überlagern
- Je nach Kantenrichtung werden sie oben oder unten getrennt; zusammenführbare Kanten werden gebündelt
- Schritt 5: Vertikale Platzierung (Verticalize)
- Jeder Ebene wird eine Y-Koordinate zugewiesen, um eine gleichmäßige Höhenverteilung und bessere Lesbarkeit zu erreichen
- Schritt 6: Rendering (Render)
- Verwendet werden geradlinige Kanten im Stil von Eisenbahndiagrammen
- Kanten kreuzen sich nur vertikal und horizontal, wodurch Richtung und Struktur klar erkennbar sind
Wirkung des einfachen Algorithmus
- Statt komplexer Optimierungen sorgt eine vorhersehbare regelbasierte Anordnung für Lesbarkeit und Stabilität
- Feste Knotenreihenfolge und vereinfachte Kanten sichern Konsistenz zwischen den Passes
- Durch den Verzicht auf einen Constraint Solver entsteht eine für Menschen leichter verständliche Struktur
- So sind bedeutungsorientierte Entscheidungen möglich, etwa die Platzierung innerhalb von Schleifen oder das Absenken nachfolgender Blöcke
- Leistungssteigerung: Einen zlib-Funktionsgraphen, für den Graphviz 10 Minuten brauchte, rendert das Tool in 20 Millisekunden
- Das liefert eine um Größenordnungen höhere Geschwindigkeit und bessere Erkunderbarkeit
Ausblick
- iongraph ist bereits in den Firefox-Profiler integriert, sodass sich Graphen bei der Leistungsanalyse anzeigen lassen
- Derzeit ist es nur in SpiderMonkey-Shell-Builds verfügbar und nicht in Browser-Builds enthalten
- Vorgeschlagene künftige Funktionen
- Erweiterte Navigation, Suche, Visualisierung der Registerzuweisung und mehr
- Eine klare Roadmap gibt es nicht; Open-Source-Beiträge sind willkommen
- Für lokale Experimente kann mit der Einstellung
IONFLAGS=logs zunächst /tmp/ion.json erzeugt und dann
in der eigenständigen Distribution geladen werden
- Der Quellcode ist auf GitHub veröffentlicht; außerdem können Entwickler direkt über einen Matrix-Chatroom Kontakt aufnehmen
1 Kommentare
Hacker-News-Kommentare
Für einen präzisen Vergleich sollte man nicht Graphviz insgesamt, sondern dot(1) vergleichen.
Graphviz ist ein Visualisierungs-Framework, das mehrere Layout-Engines enthält (dot, neato, fdp, sfdp, circo, twopi usw.).
Es wäre wirklich großartig, wenn der neu vorgeschlagene Algorithmus zu Graphviz beitragen würde.
Siehe dazu die Beschreibung der Graphviz-Sprache und die Dokumentation der dot-Layout-Engine.
Für Kontrollflussgraphen (CFG) mit reduzierbarem Kontrollfluss könnte er gut funktionieren, aber es scheint viele komplexe Ausnahmen zu geben.
Außerdem ist iongraph JavaScript-basiert, sodass man es zur Integration in Graphviz wohl mit Tools wie Claude nach C konvertieren müsste.
Die Fähigkeit, sich die Originalimplementierung eines Algorithmus direkt anzusehen, wirkt wie eine echte Superkraft.
Als jemand, der mit Graphviz komplexe Visualisierungen gemacht hat, war ich zunächst überrascht, dass jemand es direkt neu implementiert hat.
Aber nachdem ich die Struktur des Algorithmus gesehen habe, wurde mir klar, dass er vielleicht einfacher ist, als man denkt.
Trotzdem bleibt es dabei, dass man die versteckte Komplexität erst schwer einschätzen kann, bevor die tatsächliche Implementierung fertig ist.
Wenn man einen allgemeinen Algorithmus auf einen bestimmten Problembereich spezialisiert, kann man deutlich bessere Ergebnisse erzielen.
In den meisten Fällen verwenden wir aus Bequemlichkeit aber einfach den universellen Algorithmus.
Ein auf eine bestimmte Anwendung zugeschnittenes Systemdesign bringt große Verbesserungen bei Performance, Skalierbarkeit und Fehlertoleranz.
Aber wenn man auf eine 1000-fache Verbesserung zielt, sind 1–2 Jahre schnell vorbei.
Allgemeine Graph-Layout-Systeme müssen mit viel mehr unterschiedlichen Fällen umgehen und werden dadurch zwangsläufig komplex.
Deshalb halte ich einen Kompromiss für sinnvoll: die Eingabe analysieren, in Spezialfällen einen schnellen Algorithmus verwenden und sonst auf einen garantiert allgemeinen Algorithmus zurückfallen.
Das war ein guter Artikel. Zur Einordnung: dot in Graphviz ist keine reine Implementierung des Sugiyama-Algorithmus.
Die tatsächliche Implementierung wird in den Papieren auf der Website ausführlich beschrieben.
Wenn man Bilder vergleicht, die dot und iongraph auf großen Graphen gegenüberstellen, sieht man, dass dot auf Minimierung der Fläche optimiert ist und iongraph nicht.
Große Graphvisualisierungen sehen zwar beeindruckend aus, sind in der Praxis aber selten wirklich hilfreich.
Visualisierungen funktionieren nur bis zu einigen Dutzend Knoten gut; darüber hinaus wird das Verständnis wegen der Kantenkomplexität schwierig.
Am Ende klappt es nur bei einfachen Beispielen gut und stört in komplexen Umgebungen eher.
Die meisten Probleme lassen sich auf kleinere Einheiten herunterbrechen.
Allerdings ist Graphviz auch bei kleinen Graphen ästhetisch nicht besonders gelungen, während iongraph bei der Lesbarkeit der Linienführung deutlich besser ist.
Langfristig braucht es meiner Meinung nach interaktive Elemente wie Suche sowie Hervorheben-/Ausblenden-Funktionen.
Es ist frustrierend, dass Diagramme weder Links ausgeben noch aufnehmen können.
Auch Mermaid unterstützt zwar Textlinks, aber Diagramm-Links nur eingeschränkt.
Die zugehörige Diskussion auf StackOverflow ist ebenfalls lesenswert.
Man braucht ein Tool, in dem solche Funktionen von Anfang an als erstklassige Features mitgedacht wurden.
Die eigentliche Stärke von Graphviz ist die dot-Sprache.
In dot definierte Graphen bieten eine hervorragende Kompatibilität zwischen verschiedenen Tools, und die Syntax ist einfach und gut lesbar.
Es gibt zwar Alternativen wie Mermaid, aber dot wird wohl noch lange als Standardformat bestehen bleiben.
Wirklich ein großartiger Artikel.
Ich frage mich, ob solche Techniken auch in der TALA-Layout-Engine von D2 verwendet wurden.
TALA-Beispiele ansehen
Wer sich für Graph Drawing interessiert, dem empfehle ich die Vorlesungen von Will Evans (Link).
Ich habe früher einen Bugfix zum Dot-Lexer des Open Graph Drawing Framework (OGDF) beigetragen,
und OGDF implementiert schnellere Algorithmen mit weniger Kreuzungen als Graphviz.
Meiner Erfahrung nach waren die Ergebnisse von OGDF deutlich sauberer.
Die zugehörigen PRs finden sich hier: GitHub-Link
Interessant. Mich würde interessieren, wie man die Beispiele ausführt.
Das Gute an diesem Projekt ist die Unterstützung für interaktive Erkundung mit Fokus auf Web-Clients.
Weil das Layout auf Kontrollflussgraphen (CFG) spezialisiert ist, sind domänenspezifische Visualisierungen möglich.
Graphviz hat ebenfalls Funktionen für Polylinien und Steuerung der Kantenreihenfolge, aber die Dokumentation dazu ist dürftig.
Es wäre gut, den Edge-Routing-Algorithmus von Brandes und Kopf zu integrieren.
Graphviz ist ein fast 40 Jahre altes Projekt und wird derzeit nur noch von ein paar Freiwilligen der zweiten Generation gepflegt.
Tool-Entwicklung ist immer ein schwieriger Markt, und die Nutzer sind zwar klug, arbeiten aber oft in Abteilungen mit kleinem Budget.
Es ist bedauerlich, wie langsam sich deklarative 2D-Diagramm-Tools weiterentwickeln.
Wer in so einem Bereich arbeitet, bekommt von mir immer ein +1 zur Unterstützung.
Ich habe auch mermaid und graphviz benutzt, bin am Ende aber wieder bei FigJam gelandet — wegen der besseren Lesbarkeit und Ästhetik.
graphviz ist ein riesiges Binary, mermaid hängt vom SVG-Rendering im Browser ab, was unpraktisch ist.
Man braucht einfach ein Tool, mit dem sich Diagramme leicht in Textform erstellen lassen.
Der vom Autor vorgeschlagene Ansatz ist meiner Meinung nach ein guter Versuch, diesen Trade-off zu steuern.
Abgesehen davon, dass Schleifen nicht behandelt wurden, war ich zufrieden.
SVG/HTML-Ausgabe ist praktisch für Stiländerungen und zum Kopieren.
Wenn man ein textbasiertes Diagramm-Tool sucht, würde ich TikZ empfehlen.
Siehe auch das TikZ-Wiki.
Allerdings gibt es dort kein unmittelbares visuelles Feedback wie bei FigJam.
Bei mermaid haben mir die zu vielen Abhängigkeiten und die mangelnde Konsistenz des Codes nicht gefallen.
Stattdessen ist nomnoml (Link) sauber implementiert, und es gibt auch graphre (Link), eine nach TypeScript portierte Variante.
Um mermaid mit resvg-js zu verwenden, wäre ein Refactoring rund um die Messung der SVG-Textbreite nötig.