Erster Prototyp für unveränderliches Region Borrowing in Vale

 (verdagon.dev)
2 Punkte von GN⁺ 2023-07-13 | 1 Kommentare | Auf WhatsApp teilen
  • Vales Prototyp für Region Borrowing wurde erstmals erfolgreich kompiliert, sodass sich ein speichersicherer Ansatz, der generationale Referenzen und Regionen kombiniert, in einem realen Programm verifizieren lässt
  • Entwickler können Code auf eine C/C++-nahe Weise schreiben und pure und Region Borrowing nur dort anwenden, wo es nötig ist, um den Overhead der Generationsprüfungen zu verringern
  • Das erste Zero-Check-Vale-Programm war ein Cellular-Automata-Beispiel zur Generierung von Roguelike-Levels, und das resultierende Assembler-Ergebnis entsprach nahezu dem Niveau des Modus unsafe_with_bounds
  • Im Benchmark zeigte safe_fastest gegenüber unsafe_with_bounds keinen beobachtbaren Slowdown, während unsafe_no_bounds 1,18 ± 0,01-mal schneller war als beide anderen Modi
  • Es handelt sich noch nicht um einen direkten Vergleich mit C/Rust; wegen LLVM-Optimierungsrauschen, des Reifegrads des Prototyps und fehlender Unterstützung für Inline-Daten stehen ein Vale-spezifischer Pre-Optimizer und die Bereinigung der Regionsfunktionen noch aus

Kombination aus generationalen Referenzen und Region Borrowing

  • Vales Ansatz für Speichersicherheit zielt darauf ab, Reference Counting, verfolgte Garbage Collection und Borrow Checking nicht zu verwenden
  • Die Grundstruktur ist, dass Entwickler Programme in einer Weise schreiben, die C oder C++ nahekommt, während Vales generational references die Speichersicherheit aufrechterhalten
  • Werden anschließend pure und region borrowing angewendet, lässt sich der Großteil des Overheads von Generationsprüfungen entfernen
  • Mit zusätzlichem linear style geht Vale davon aus, Generationsprüfungen im Vale-Code auf null senken zu können
  • Region Borrowing ist vollständig opt-in, sodass man zunächst bequem schreiben und es erst später nur in den Teilen ergänzen kann, die Optimierung benötigen
  • Das Ziel ist eine Struktur, in der innerhalb desselben Programms einige Teile flexibel wie in Java, andere schnell wie in Rust oder irgendwo dazwischen gewählt werden können

Arbeiten, die für den Prototyp nötig waren

  • In den vergangenen Jahren wurde beim Aufbau der Compiler-Basis daran gearbeitet, ein regionsbasiertes Borrowing-System zusammen mit generational references zu unterstützen
  • Das Borrowing-System selbst ist komplex, und es wurden stärkere full generics als bei bisherigen Templates benötigt
  • Damit Regionen und generationale Referenzen natürlich zusammenarbeiten, war auch eine neue Compiler-Phase nötig
    • Intern werden Regionen auf ganze Zahlen der Form „pure height“ reduziert
    • Ein Region-Generic-Parameter wird als negative Zahl dargestellt, die Standardregion als 0, und jeder pure-Block als ansteigende positive Zahl
  • Vor einigen Monaten wurde der Regions-Prototyp fertiggestellt; er hat noch raue Kanten, aber zum ersten Mal wurde etwas erfolgreich kompiliert
  • Das Ergebnis war das erste Zero-Check-Vale-Programm
    • Mit dem Compiler-Flag --print_mem_overhead true lässt sich die Anzahl der Generationsprüfungen eines Programms zählen

Das erste Zero-Check-Programm und der Vergleich des Assemblers

  • Das erste Programm war ein Cellular-Automata-Beispiel zur Erzeugung von Levels für ein Roguelike-Spiel
  • Schon kleine Fehler im Compiler-Code können zusätzliche Instruktionen in den resultierenden Assembler einfügen und dadurch künstlichen Overhead im Endprogramm erzeugen
  • Um Probleme zurückzuverfolgen, wurde der resultierende Assembler fortlaufend mit Vales Unsafe-Modi verglichen
    • unsafe_no_bounds: Schaltet ähnlich wie in C alle Speicher-Schutzmechanismen aus und verwendet Raw Pointer statt generational references
    • unsafe_with_bounds: Fügt ähnlich wie in Rust Bounds Checking für Array-Zugriffe hinzu
  • Nach mehreren Monaten der Nachverfolgung von Unterschieden war der resultierende Assembler nahezu identisch mit dem Modus unsafe_with_bounds
  • Der einzige erwartete Unterschied war, dass bei jeder Allokation oben eine pseudozufällige Generationsnummer eingefügt wurde; bei tatsächlichen Generationsprüfungen wurde sie jedoch nicht gelesen
    • Intern wird zur Wahrung der Geschwindigkeit ein monoton ansteigendes Register verwendet
    • Wenn isolates oder unique references hinzukommen, könnte auch dieser Unterschied entfallen

Benchmark-Ergebnisse und Messbedingungen

  • Die Benchmark-Zusammenfassung lautet wie folgt
Summary
  './build_unsafe_no_bounds/main' ran
    1.18 ± 0.01 times faster than './build_unsafe_with_bounds/main'
    1.18 ± 0.01 times faster than './build_safe_fastest/main'
  • safe_fastest, Vales normaler Modus, zeigt im Vergleich zu einem Modus mit nur Bounds Checking keinen Slowdown
  • In dieser Messung hat dieser Ansatz keinen beobachtbaren Overhead
  • Wer es selbst ausprobieren möchte, kann den regions branch bauen, die Benchmarking-Skripte ansehen und auf dem Discord-Server Fragen stellen
  • Die Messbedingungen haben klare Einschränkungen
    • Es ist kein Benchmark mit direktem Vergleich zu Sprachen wie C oder Rust
    • Solche Compiler besitzen jahrelange separate Optimierungen, die die Versuchsvariablen verwischen könnten
    • Um die Unterschiede des Speichersicherheitsansatzes zu isolieren, wird mit unsafe_no_bounds und unsafe_with_bounds verglichen
    • Die Messumgebung war ein Razer Blade 15" von 2018 mit 512GB SSD unter Ubuntu 22.04
    • Als Messwerkzeug wurde hyperfine verwendet, ausgeführt innerhalb von cset shield

Optimierungsrauschen in größeren Programmen

  • In größeren Programmen wurde recht deutlich optimizer noise beobachtet
    • Es unterscheidet sich von Benchmark-Rauschen; das Mess-Setup zeigte sehr konsistente Laufzeiten wie ± 0.01
    • Kleine Änderungen in einem Bereich konnten Messwerte in eine Richtung verschieben
  • Beim Ändern der Größe der Generationsnummer gab es sogar einen Fall mit konsistent negativem Overhead von 1.13 ± 0.01
    • Da das Programm nicht viele Generationsnummern enthielt, war dieses Ergebnis merkwürdig
    • Möglicherweise haben Änderungen bei der Registerallokierung Leistungsunterschiede aus semantischen Unterschieden überlagert
  • In einem größeren Programm, einem kleinen Roguelike-Spiel, konnte der Optimizer zwei identische Branches innerhalb einer if-Anweisung nicht zusammenführen und verpasste auch andere offensichtliche Optimierungen
  • Welchen Einfluss die Existenz einer nicht gelesenen Integer-Zahl hat, ist nicht sicher; möglich ist auch ein LLVM-Bug
  • Dieses Ergebnis deutet darauf hin, dass ein Vale-spezifischer Pre-Optimizer ähnlich wie Rusts MIR nötig sein könnte
    • LLVM wurde eher mit Blick auf C entworfen
    • Wenn LLVM generational references als Muster interpretiert, das absichtlich auf freigegebenen Speicher zugreift, könnte es dies als undefined behavior behandeln

Einsatzmöglichkeiten und nächste Schritte

  • Generationale Referenzen und Regionen können in Kombination einen sehr schnellen Ansatz für Speichersicherheit schaffen
  • Software-Domänen, für die dieser Ansatz gut passen könnte, erfüllen folgende Bedingungen
    • Sie wollen besser vorhersehbare Latenzen als bei tracing garbage collection
    • Sie wollen bessere Performance und bessere Cache-Freundlichkeit als bei reference counting
    • Sie wollen Prototyping und Iteration einfacher gestalten als mit Borrow Checking
  • Bevor Vale direkt mit C oder C++ verglichen werden kann, bleibt noch Arbeit übrig
    • Der LLVM-Optimizer hat Probleme, Generation und Immutability herzuleiten; deshalb ist ein Vale-spezifischer Pre-Optimizer nötig
    • Vale muss inline data unterstützen, statt der aktuellen Übergangslösung, bei der alle Structs auf dem Heap liegen
    • Der obige Benchmark verwendete keine Structs, daher beeinflusst die fehlende Unterstützung für Inline-Daten dieses Ergebnis nicht
    • Die Regionsfunktionen befinden sich noch im Prototyp-Stadium und müssen geglättet sowie technische Schulden reduziert werden, bevor sie in den Main Branch gemergt werden
  • Nach dem Merge ist geplant, die Standardbibliothek Regionen verwenden zu lassen, sodass Nutzer Vorteile erhalten, auch wenn ihr main program code Regionen nicht direkt nutzt
  • Die aktuellen Messungen zeigen, dass Zero-Check-Programme möglich sind und die erwartete Geschwindigkeit erreichen können

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-13
Hacker-News-Kommentare

  • Ich habe Vale heruntergeladen und ausprobiert, aber mein erster Eindruck war schlecht, als der valec-Compiler beim ersten Start ohne Argumente sofort "(panic)" ausgab.
    panic ist eine sehr starke Formulierung und sollte in normalen Fehlerbehandlungssituationen meiner Meinung nach vermieden werden. Wenn ein Programm einen Panic auslöst, wirkt das wie eine unkontrollierte Situation und hinterlässt keinen guten Eindruck.
    Danach wollte ich mir die Hilfe zu den Kommandozeilenargumenten ansehen, aber die gab es aktuell praktisch nicht. Ich speicherte dann das Hello-World-Beispiel von der Website als hello.vl und führte valec hello.vl aus, worauf Unknown subcommand erschien.
    Also führte ich valec build hello.vl aus, bekam Unrecognized input: hello.vl und danach wieder (panic). Auch valec help half nicht, also gab ich schließlich auf. Ich habe keine Ahnung, wie man das benutzen soll.

    • Tut mir leid. Es sieht so aus, als würde die Hilfedatei nicht mehr korrekt ausgegeben. Wenn du die in den Downloads enthaltene valec-help-build.txt direkt mit cat ansiehst, sollte dort erklärt sein, was du suchst.
      Der Compiler ist im Moment an vielen Stellen noch ziemlich roh. Von August bis Mai habe ich mich zu 100 % auf das Prototyping von Regions konzentriert, und was du jetzt erlebst, ist technische Schuld, die sich dabei angesammelt hat. Dazu gehört auch, dass es keine Integrationstests für das Hilfesystem gibt.
      In den letzten ein bis zwei Monaten habe ich begonnen, diese Schuld abzubauen, aber wir sind noch nicht wieder auf dem Stand des 0.2-Releases. Wenn du mehr Hilfe brauchst, sag Bescheid oder komm auf den Discord-Server, dort gibt es viele Leute, die helfen können.
    • Ich denke, Vale befindet sich praktisch noch in der Forschungs- und Entwicklungsphase. Eher in dem Sinn, dass man erwarten kann, dass nur bestimmte Commits auf bestimmten Branches funktionieren, nicht in dem Sinn, dass sich jeder einfach den Compiler holen und etwas damit bauen kann.
      Das README macht diesen Punkt allerdings nicht klar sichtbar und sagt eher „Try Vale“, was mehrdeutig ist. Im Moment wirkt es aber eher wie Forschung/Entwicklungsarbeit bzw. ein Proof of Concept.
    • Das ist weniger ein Bug als eher ein Benutzeroberflächenproblem. Wenn etwas experimentell ist, kann man meiner Meinung nach sogar bei echten Bugs etwas großzügiger sein.
      Auch was Benutzeroberfläche oder Bugs angeht, kann die Erfahrung, 40 Jahre altes C++ mit einem 35 Jahre alten gdb zu debuggen, es mit jeder experimentellen Sprache locker aufnehmen. Zum Beispiel ist die Ausgabe von funcname()::staticvarname eine seltsame Oberfläche und scheitert ungefähr zur Hälfte. Von C++-Build-Systemen ganz zu schweigen.
      Bei experimenteller Technologie kann man das Konzept kritisieren, aber eine raue Benutzeroberfläche ist meiner Meinung nach in gewissem Maß hinnehmbar.
    • Im GitHub-README steht, wie man den Compiler benutzt.
      https://github.com/ValeLang/Vale#building-a-vale-program
    • Für Software, die noch im Alpha-Stadium ist, sieht das ungefähr erwartbar aus.

  • Eine geringere Latenz als bei Tracing Garbage Collection, bessere Performance und Cache-Freundlichkeit als Referenzzählung und leichteres Prototyping und Iterieren als mit Borrow Checking — das weckt bei mir mehr als nur Neugier.
    Ich habe sogar angefangen, den RSS-Feed zu abonnieren: https://verdagon.dev/rss.xml

    • Endlich eine neue Idee für AOT-kompilierte Sprachen, die nicht darauf hinausläuft: „Lassen wir einfach gelegentlich Speicherbugs zu.“

  • Vale braucht mehr Sponsoren
    https://github.com/sponsors/ValeLang
    Ich hoffe, während dieser Beitrag auf der Startseite ist, hilft das Projekt dabei, sein Ziel von 3.000 Dollar pro Monat zu erreichen.
    Ich würde Evan gern dabei unterstützen, das in Vollzeit zu machen. Ich bin selbst Sponsor. Eine Sprache, die schnell und sicher ist und zugleich Spaß beim Prototyping macht, ist unterstützenswert.

    • Ich frage mich, wie sich GitHub-Sponsoring und Patreon-Sponsoring bei der Umsatzbeteiligung unterscheiden.

  • Mit „Vale-spezifischer Pre-Optimizer, etwas Ähnliches wie Rusts Cranelift“ ist vermutlich MIR gemeint, also die Mid-level Intermediate Representation. Dazu gibt es einen guten Blogpost: https://blog.rust-lang.org/2016/04/19/MIR.html
    Cranelift ist in erster Linie ein Compiler-Backend mit Fokus auf JIT, könnte theoretisch aber auch LLVM ersetzen. An einem Ersatz-Backend wird gearbeitet, allerdings mit Einschränkungen: https://github.com/bjorn3/rustc_codegen_cranelift

    • Klingt richtig. Cranelift kann man als Rust-Optimizer für WebAssembly ansehen.

  • Ein Ansatz, bei dem man sich im Großteil des Codes nicht um Speicherverwaltung kümmern muss, aber heiße Codepfade bei Bedarf mit Zero-Cost-Abstraktionen optimieren kann, klingt so, als würde er die Vorteile beider Seiten vereinen.
    Vor allem dann, wenn man der Bequemlichkeit zuliebe nicht Sicherheit, sondern nur Performance eintauscht.

    • Ich benutze nur C++, mache mir über Speicherverwaltung aber überhaupt keine Gedanken.
      Gemeinsames Eigentum ist ein schlechtes Konzept, deshalb benutze ich auch keine Smart Pointer.
      Probleme mit Speicherverwaltung sind meistens trivial.

  • Ich frage mich weiterhin, was sicher im Kontext von generational references eigentlich bedeutet.
    Wenn ich es richtig verstanden habe, heißt das, dass use-after-free und double-free verhindert werden? Falls ja, könnte das Programm beim Speicherzugriff dennoch scheitern, wenn die erwartete Generation nicht mit der tatsächlichen übereinstimmt.
    In diesem Sinne wirkt es weniger sicher als Referenzzählung, nachverfolgende Garbage Collection oder Borrow-Checking.

    • Double-free wird durch Vales Single Ownership verhindert, also Single Ownership im Sinne von C++, und generational references ermöglichen eine sichere Erkennung von use-after-free.
      Wenn man versucht, über eine Referenz auf freigegebenen Speicher zuzugreifen, sollte das vorhersehbar und sicher zu einem Segmentation Fault oder einem Assertion-Fehler führen. Ich freue mich auf eine künftige Verbesserung mit erneutem Mapping des virtuellen Adressraums, die sogar Segmentation Faults beseitigen könnte.
    • Sicher in dem Sinne, dass es einen Segmentation Fault gibt, statt mit einem Dangling Pointer beliebigen Speicher lesen oder schreiben zu lassen.
      Bei einem Generationsindex sollte die Laufzeit allerdings auch prüfen können, ob der Zugriff gültig ist, bevor der eigentliche Zugriff versucht wird. Ich weiß nicht, ob das in Vale möglich ist.
    • Weniger sicher als GC, Borrow-Checking und Referenzzählung. Trotzdem sicherer als malloc/free, und es hat auch andere Vorteile.
    • Das frage ich mich auch. Ich verstehe nicht, wie das use-after-free und double-free verhindern soll.
      Die Funktion check braucht die Generationsnummer der Allokation und greift dafür auf die Allokation zu. Das heißt, um zu prüfen, ob die Referenz auf diese Allokation zugreifen darf, muss man zuerst auf genau diese Allokation zugreifen.
      Wenn die Allokation natürlich schon freigegeben wurde, ist schon der Zugriff auf diese Allokation und ihre Generationsnummer undefiniertes Verhalten und funktioniert daher nicht.
      Es erscheint mir zu offensichtlich, daher weiß ich nicht, ob ich etwas Grundlegendes übersehe oder ob „Speichersicherheit“ hier etwas ganz anderes bedeutet.
    • Wenn du fragst, ob es weniger sicher ist als meine bewusst eingeschränkte Definition von „sicher“, dann vielleicht ja.

  • Vale ist nicht dieselbe Sprache wie V. V bekam in https://mawfig.github.io/2022/06/18/v-lang-in-2022.html eine sehr kritische Rezension, und wegen des ähnlichen Namens hatte ich das fälschlich als Vale in Erinnerung.
    Ich lasse den Hinweis hier, falls noch jemand denselben Fehler gemacht hat.

    • Diese „sehr kritische Rezension“ ist nur eine Liste kleiner Bugs, die vor einem Jahr behoben wurden.
      Der Inhalt des Beitrags ist inzwischen nicht mehr relevant, steht aber weiterhin online, und es ist auch der einzige Beitrag in diesem Blog.
    • Diese „kritische Rezension“ wirkt eher wie alter Spam, den Gegner oder Trolle immer wieder verwenden. Eine „Rezension“ einer Alpha-Version der Sprache, eigentlich eher ein polemischer Angriff, also ohne weiteren Wert.
      Inzwischen ist 2023 und V ist Beta (0.4). Außerdem nutzte die Person, die den Beitrag erstellt hat, einen Wegwerf-GitHub-Account, stellte die Rezension/den Angriff online, sorgte für Kontroversen und verschwand dann.
      Der einzige Beitrag in diesem Blog ist ebenfalls ein Angriff auf V; andere Rezensionen gibt es nicht. Die Teile mit praktischem Gehalt wurden bereits behoben[1].
      Wenn man nach mawfig.github sucht, sieht man auch, dass das auf HN wiederholt verbreitet wurde und meist zur Verunglimpfung diente.
      [1]: https://github.com/vlang/v/issues/14803
      [1]: https://github.com/vlang/v/issues/14787
      [1]: https://github.com/vlang/v/issues/14786

  • Glückwunsch an Evan zu diesem erreichten Meilenstein. Ich habe zwar keine Erfahrung mit Programmiersprachen-Design oder Compilern, lese aber die Vale-Beiträge sehr gern.

    • Geht mir ähnlich, aber ich wünschte, der Name wäre anders.
      Jetzt gibt es Evan’s Vale und außerdem Val vom Adobe Software Technology Lab, wodurch es ziemlich schwierig werden dürfte, dazu Informationen zu suchen.
      https://www.val-lang.dev
    • Mir fehlt meist auch das Hintergrundwissen, um die Beiträge wirklich zu verstehen, aber interessant finde ich sie trotzdem.
    • Ich finde die Beiträge ebenfalls großartig und freue mich auf die Zukunft von Vale.

  • „Vale ist schnell: Vale wird mit LLVM AOT-kompiliert, verwendet statische Typen, nutzt die neue Technik der generational references für Speichersicherheit mit Geschwindigkeit und Flexibilität und wird bald region-basiertes Borrow-Checking einführen, um noch schneller zu werden.“
    https://vale.dev/

  • Es fühlt sich an, als würde man einem Streit zwischen zwei Leuten lauschen, der seit fünf Jahren läuft.
    Kann jemand erklären, was hier vor sich geht? Der Beitrag ist viel zu schwer verständlich.