Ein 3 Jahre altes Performance-Problem in Gleam mit Rust-Arenas lösen

• Im rekursiven Document-Aufbau des Gleam-Formatierers wurden die wiederholten einzelnen Heap-Allokationen durch arena-basierte Referenzen ersetzt, wodurch ein seit 3 Jahren offenes Performance-Problem behoben wurde
• Box<Self> wurde durch in einer Arena gespeicherte &Self ersetzt, und Rusts Lebensdauerprüfung stellt sicher, dass nach dem Freigeben der Arena keine internen Daten mehr referenziert werden
• Hunderte wiederkehrende Document-Objekte wie Sprach-Keywords und Kommas werden nur einmal allokiert und wiederverwendet, wodurch sich die Laufzeit des Pretty-Printers von 13 ms auf 9,8 ms verringerte und er 24 % schneller wurde
• Auch die gesamte Laufzeit von gleam format, einschließlich Einlesen des Quellcodes und Parsing, wurde um 13 % verkürzt, während der maximale Speicherverbrauch von 8,4 MB auf 7,6 MB und damit um etwa 10 % sank
• Obwohl für die Weitergabe der Arena umfangreiche Änderungen an Funktionen und Aufrufstellen nötig waren und manuelle Arbeit im Umfang von +2963/-1032 erforderlich war, konnten mit der Reduzierung wiederholter Einzelallokationen sowohl Geschwindigkeit als auch Speicherverbrauch verbessert werden

---

Allokationskosten in einer rekursiven Document-Struktur

• Der Pretty-Printer von Gleam verwendet eine rekursive Document-Datenstruktur, die beschreibt, wie Code ausgegeben wird und an welchen Stellen bei Überschreiten der Zeilenbegrenzung umgebrochen werden soll
• Zu den wichtigsten Varianten gehören String für auszugebende Zeichenketten, Break zur Definition von Zeichenketten vor und nach einem Zeilenumbruch, Group zum Bündeln mehrerer Dokumente und Nest zum Erhöhen der Einrückung bei einem Umbruch
• Auch die Liste [1, 2] wird durch eine Kombination aus String, Break, Nest und Group dargestellt
  • Passt sie in die aktuelle Zeile, wird sie in einer Zeile als [1, 2] ausgegeben
  • Überschreitet sie die Zeilenbegrenzung, wird sie entsprechend dem angegebenen Break auf mehrere Zeilen verteilt, eingerückt und mit dem abschließenden Komma ausgegeben
• Varianten wie Nest, die ein anderes Document enthalten, verwendeten bisher Box<Self>, weshalb für jedes verschachtelte Dokument eine einzelne Heap-Allokation nötig war, was einen erheblichen Teil der Laufzeit ausmachen konnte
• Der zugrunde liegende Algorithmus des Gleam-Pretty-Printers wird im Paper Strictly Pretty beschrieben

Box durch Arena-Referenzen ersetzen

• Das bisherige Nest(Box<Self>) wurde zu Nest(&'doc Self) geändert, sodass die Struktur nun ein anderes in der Arena gespeichertes Document referenziert
• Um Referenzen aufnehmen zu können, wurde Document zusätzlich zur String-Lebensdauer 'string um die Lebensdauer 'doc für die Dokumentdaten erweitert
• Für die Implementierung wurde das Crate typed_arena verwendet
  • Mit alloc wird ein Wert in der Arena gespeichert und eine Referenz auf diesen Wert zurückgegeben
  • Allokierte Daten können verwendet werden, solange die Arena lebt
  • Verlässt die Arena den Gültigkeitsbereich, werden auch die darin enthaltenen Daten entfernt
• Die von alloc(&self, value: T) -> &mut T zurückgegebene Referenz kann nicht länger leben als die Arena, und Rusts Borrow Checker blockiert ungültige Referenzen nach dem Freigeben der Arena

Wiederkehrende Dokumente einmal allokieren und wiederverwenden

• Die Arena dient nicht nur dazu, andere Dokumente zu referenzieren, sondern wird im gesamten Code auch zum Cachen wiederkehrender Document-Objekte genutzt
• Dokumente wie String("fn"), String("pub") und String("type"), die Sprach-Keywords darstellen, müssen nicht mehr jedes Mal neu erzeugt werden
• Auch Dokumente wie Break { unbroken: ", ", broken: "," }, die zwischen Listenelementen verwendet werden, werden einmal allokiert und anschließend wiederverwendet
• Hunderte kleine Dokumente, die zuvor fortlaufend in Box verpackt werden mussten, können nun jeweils nur einmal allokiert werden

Eine einfache API, aber weitreichende Änderungen an den Aufrufstellen

• Die Arena-API selbst ist einfach, doch die Umstellung großer Teile des bestehenden Codes erforderte wiederholte Anpassungen
• Funktionen, die zuvor nur Box::new aufriefen, müssen nun zusätzlich ein Arena-Argument entgegennehmen, um Daten darin zu allokieren
• Funktionen wie format_list geben dieselbe Arena nun auch an Unterfunktionen zur Formatierung von Listenelementen weiter und erzeugen verschachtelte Dokumente mit arena.alloc statt mit Box::new
• Nach tagelangem vorsichtigen Suchen und Ersetzen wurde die Arbeit in einem Pull Request im Umfang von +2963/-1032 abgeschlossen
• Die Arbeit war repetitiv und manuell; ein LLM wurde dabei nicht verwendet

Verbesserungen bei Geschwindigkeit und maximalem Speicherverbrauch

• Beim Formatieren des realen Gleam-Projekts squirrel sank die Laufzeit des Pretty-Printers von 13 ms auf 9,8 ms
  • Betrachtet man nur den Pretty-Printer, entspricht das einer Leistungssteigerung von 24 %
• Da gleam format neben dem Formatieren auch den Quellcode des Projekts einliest und parst, macht der Pretty-Printer nur einen Teil der gesamten Arbeit aus, dennoch verkürzte sich auch die Gesamtlaufzeit um 13 %
• Der maximale Speicherverbrauch sank von 8,4 MB auf 7,6 MB und damit um etwa 10 %
• Durch die Reduzierung einzelner Heap-Allokationen mit Arenas wurde der Formatierer schneller und benötigte zugleich weniger Speicher

[GN⁺]

Lobste.rs-Meinungen

• Wenn man die maximale Speichernutzung noch um 10 % senken möchte, lohnt es sich, eine andere Arena in Betracht zu ziehen, die statt Referenzen opake Handles zurückgibt. Wenn sich die Handles statt als 64 Bit als 16 oder 32 Bit darstellen lassen, bringt das viel bei vielen kleinen Allokationen
  Laut https://donsz.nl/blog/arenas/ unterstützt das allerdings nur das Crate compact_arena; wenn es nicht zu den Anforderungen passt, ist eine eigene Implementierung aber auch nicht besonders schwer

  • Mit opaken Handles lassen sich Daten auch dichter speichern. Das persönliche Projekt columnar speichert eine Liste von Option<T> aufgeteilt in ungefähr 1 Bit Präsenzinformation pro Eintrag und die T der tatsächlich vorhandenen Einträge
    Statt einer Referenzform &Option<T> gibt es dann Option<&T> zurück; allgemeiner gesagt folgt man bei struktureller Rekursion eher den Referenzen, statt Referenzen innerhalb der strukturellen Rekursion zu haben
  • Der Beitrag basierte auf einer Untersuchung von vor 2 Jahren und deckte nicht alle Crates vollständig ab; wenn jemand Fehler oder neue fehlende Bibliotheken findet, sind PRs willkommen
    Arenen verdienen eine breitere Nutzung, und wenn statt Handles oder Smart Pointern Referenzen zurückgegeben werden, wird Pattern Matching auf rekursiven Enums in Rust sehr bequem. Normalerweise möchte man etwas wie if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {} schreiben, was wegen Boxen oder Zeigern dazwischen nicht möglich ist, aber mit Referenzen funktioniert transparentes Pattern Matching ohne Nightly-Features. Wenn alle Referenzen auf dieselbe Arena zeigen, bleibt auch die Lifetime, die den gesamten Baum verbindet, konsistent
  • Die Ergebnisse sind gut genug, dass überlegt wird, auch andere Teile des Compilers auf ein Arena-Modell umzustellen; dieser Ansatz soll weiter untersucht werden

• Dieser Ansatz ist auch ziemlich ähnlich zu dem, was eine andere Pretty-Printing-Bibliothek im Wadler-Stil, pretty, unterstützt. Da sie allerdings mehrere Strategien der Speicherallokation unterstützt, kann die API etwas schwergewichtig wirken

• Überraschend, dass der Autor des im Beitrag zitierten Papers bei einer gewöhnlichen IT-Firma in Braunschweig arbeitet

  • Das ist der Reiz von Open Source. Fachliche Expertise und Broterwerb haben oft nicht viel miteinander zu tun