Tree Shaking, der gartenbaulich fehlgeleitete Algorithmus (2023)

 (wingolog.org)
2 Punkte von GN⁺ 2024-04-15 | 1 Kommentare | Auf WhatsApp teilen
  • WebAssembly hatte zwar Erfolg dabei, große C++-Programme wie Photoshop ins Web zu bringen, doch bei DOM-zentrierten Apps blieb die Verbreitung wegen des anderen Programmiermodells im Vergleich zu JavaScript begrenzt
  • Die Unterstützung für Wasm GC und Referenztypen im Browser eröffnet Chancen für speicherverwaltete Sprachen wie Python und Scheme, aber im Web wird die Übertragungsgröße selbst zur Hürde für die Akzeptanz
  • Ein einfaches Wasm-Programm in Go ist 2 MB groß und kann mit zusätzlichen Imports auf über 10 MB anwachsen; das Pyodide-REPL lädt rund 20 MB herunter und ist damit für normale Web-Apps eine große Last
  • Der Hoot-Scheme-Compiler zielt auf Wasm mit GC-Unterstützung und hat die minimale Kompilierungseinheit „main“ auf etwa 70 KB reduziert; Hilfs-Kompilierungseinheiten können sogar unter 1 KB liegen
  • Effektives Tree Shaking geht über das Löschen nicht referenzierter Funktionen hinaus und ist ein Compiler-Problem, bei dem Flow-Analyse und das Design der Standardbibliothek zusammenspielen

Bereiche, in denen WebAssembly im Web Erfolge erzielt hat

  • WebAssembly hat sich im Web nicht so breit durchgesetzt, wie anfangs erwartet, konnte in bestimmten Bereichen aber begrenzte Erfolge erzielen
  • Ein typisches Beispiel ist die Portierung großer C++-Programme wie Photoshop ins Web
  • Auch Figma wurde vor fünf Jahren als Wasm-Beispiel genannt, stellt Wasm heute aber nicht mehr besonders in den Vordergrund
  • Viele kleine NPM-Bibliotheken, die aus C++ oder Rust kompiliert wurden, nutzen intern Wasm
  • Blazor könnte in einigen internen Unternehmens-Apps eingesetzt werden, wobei das möglicherweise auch vom Marketing überzeichnet wurde
  • Die 3D-FPS-Demo der Unreal Engine war ein Experiment auf Basis eines größeren Releases von vor mehr als fünf Jahren; Unreal 5 unterstützt derzeit kein WebAssembly-Target

Warum Wasm bei DOM-zentrierten Apps blockiert war

  • WebAssembly ist außerhalb des Webs erfolgreich und könnte auch auf der Webplattform noch wichtiger werden, im Web selbst scheint es aber gerade erst das Tal der Enttäuschung zu durchqueren
  • Wasm ist stark bei Aufgaben, die JavaScript nicht gut erledigt, oder wenn eine gemeinsame Implementierung zwischen Client und Server gebraucht wird
  • Bei DOM-zentrierten Apps war Wasm nicht erfolgreich
    • Niemand fordert, das Frontend von wordpress.com in Wasm neu zu schreiben
    • Das vorherrschende Programmiermodell im Web ist JavaScript mit dynamischer Typisierung und speicherverwaltetem Speicher
    • WebAssembly 1.0 wurde um statische Typisierung und linearen Speicher herum entworfen
    • Der Zugriff auf das DOM aus Wasm war so umständlich, dass ihn praktisch nur besonders engagierte Wasm-Befürworter auf sich nahmen
  • Sprachen wie C# müssen ihren Garbage Collector mit ausliefern, was die Wasm-Akzeptanz für andere Sprachen als C/Rust erschwert hat

Das Problem der Übertragungsgröße bleibt auch nach Wasm GC

  • Browser werden in den kommenden Monaten Unterstützung für Referenztypen und Garbage Collection bereitstellen
    • Chrome und Firefox unterstützen Wasm GC bereits
    • Auch Safari dürfte dank der Arbeit von Asumu Takikawa nicht mehr weit entfernt sein
  • Wasm GC ist eine Veränderung, die mehr Sprachen dazu bringen wird, ihre Toolchains für WebAssembly zu aktualisieren
  • Damit Web-Wasm erfolgreich wird, müssen Compiler kleinen Code erzeugen
    • Es ist vorteilhaft, wenn Sprach-Toolchains nützliche Wasm-Dateien im Bereich von wenigen KB Übertragungsgröße erzeugen können
    • Andernfalls muss man auf überhöhte Erwartungen oder eine gefangene Nutzerbasis setzen und verbleibt bis zur nächsten Lösung in einem instabilen Gleichgewicht
  • Im JavaScript-Ökosystem gibt es bereits eine große Werkzeugindustrie, die sich mit Auslieferungsgröße und Aufblähung beschäftigt
    • Bundler wie esbuild bündeln mehrere JS-Module in eine einzige Datei
    • Sie versuchen, nur die tatsächlich verwendeten Funktionen und Datentypen einzuschließen
    • Zusätzlich kommen Größenreduktionsstrategien wie Minification zum Einsatz, bei denen Namen verkürzt werden

Die Falle des Namens Tree Shaking

  • Tree Shaking hat die bildhafte Metapher, dass nur der für eine Seite benötigte Code hängen bleibt und alles andere herunterfällt
  • In dieser Metapher stellt man sich Module als Äste und Definitionen als Blätter vor, doch ein echter Baum verrät einem beim Schütteln nicht, welche Äste nötig und welche überflüssig sind
  • Der Name selbst lenkt das Denken in Richtung des Entfernens unnötigen Codes, während es aus algorithmischer Sicht treffender ist, einen Fixpunkt zu finden, der nur den benötigten Code erhält
  • Trotzdem ist Tree Shaking ein einprägsamer Name und wird trotz seiner gartenbaulichen und algorithmischen Ungenauigkeit weiterverwendet

Größenhürden durch schwere Laufzeitumgebungen

  • Bei Sprachen mit schwergewichtiger Runtime hatte maximal aggressives Tree Shaking bisher keine hohe Priorität
  • In Gos WebAssembly-Unterstützung ist selbst das einfachste Programm laut golang wiki 2 MB groß
    • Mit zusätzlichen Imports kann es auf über 10 MB anwachsen
  • Das REPL-Beispiel von Pyodide, einer WebAssembly-Portierung von Python, lädt etwa 20 MB an Daten herunter
  • Solche Größen sind für Tech-Demos oder sehr umfangreiche Anwendungen akzeptabel, taugen aber kaum als allgemeine Option für Webentwicklung

Alternative Toolchains und plattformangepasste Implementierungen

  • Gos eingebaute Wasm-Unterstützung und Pyodide stammen aus Upstream-Toolchains; auf dem Server muss Binärgröße oft nicht besonders wichtig sein
  • Wenn kleine Geräte Zielplattform sind, entstehen separate Implementierungen
  • Das Wasm-Backend von TinyGo scheint auf unter 1 KB herunterkommen zu können
  • Solche alternativen Toolchains bringen oft Einschränkungen oder Besonderheiten mit sich
  • Ein auf Wasm zielendes Python-Programm, das in einer DOM-Umgebung läuft, wird zwangsläufig anders sein als ein „natives“ Python-Programm
  • Toolchain-Autoren versuchen zwar, dieselbe Sprache bereitzustellen, aber die Implementierung der Standardbibliothek kann sich unterscheiden
  • Auch ClojureScript-Entwickler würden vermutlich gern die Dokumentation der Unterschiede zu Clojure loswerden, und falls Wasm zu einem praktischen Ziel für ClojureScript wird, könnte das möglich werden

Wie Hoot Scheme Tree Shaking angeht

  • Nach GC-Unterstützung macht Wasm DOM-Programmierung in Sprachen wie Python prinzipiell denkbar, für breite Nutzung braucht es aber kleine Module
  • Der Hoot Scheme compiler zielt auf Wasm mit GC
    • Die minimale Kompilierungseinheit „main“ liegt derzeit bei etwa 70 KB
    • Das Ziel ist, noch weiter herunterzukommen
    • Hilfs-Kompilierungseinheiten, die Runtime-Funktionen wie Exception-Handler ins Main-Modul importieren, können unter 1 KB bleiben
  • Der Hoot-Compiler fügt vor dem Benutzercode ein Prelude ein
  • Tree Shaking findet in mehreren Stufen statt
    • Partielle Auswertung kann ungenutzte Bindungen entfernen, nachdem nur ihre Effekte ausgewertet wurden
    • fixing letrec erledigt eine ähnliche Aufgabe
    • CPS durchläuft das Programm häufig und folgt nur referenzierten Funktionen, Werten und Kontrollflusskanten
    • Ein expliziter Pass zur Dead-Code-Elimination entfernt ungenutzte, wirkungslose Zuweisungen, die nach anderen Optimierungen entstehen können
    • Definitionen in der Standardbibliothek, die in beinahe rohem WebAssembly geschrieben sind, werden nur dann in die resultierende Binärdatei aufgenommen, wenn sie tatsächlich gebraucht werden

Einfach zu entfernender und schwer zu entfernender Code

  • Prozedurdefinitionen wie Funktionen oder Closures sind vergleichsweise leicht zu handhaben
    • Es genügt, nur die Funktionen einzuschließen, auf die der Code verweist
    • In Sprachen wie Scheme bringt schon das allein erhebliche Effekte
  • Es gibt dabei drei sofort sichtbare Schwierigkeiten

  • Auswertungsmodell von letrec*

    • Der Scope der Prelude-Definitionen ist rekursiv, aber geordnet
    • Bindungswerte können zuvor definierte Werte aufrufen oder referenzieren und zugleich später definierte Werte capturen
    • Müssen bei der Auswertung eines Bindungswerts erst später definierte Werte referenziert werden, ist das ein Fehler
    • Bei Prozeduren ist das meist kein Problem, bei Nicht-Prozedur-Definitionen kann der Compiler aber womöglich nicht beweisen, dass nur „frühere Bindungen referenziert werden“
    • In diesem Fall kann der Algorithmus aus fixing letrec reloaded gesetzte Bindungen per set! stehen lassen; um sie zu entfernen, ist dann ein sorgfältiger DCE-Pass nötig

  • vtable von Record-Typen

    • Einige Nicht-Prozedur-Definitionen sind Record-Typen
    • Record-Typen besitzen eine vtable, die etwa festlegt, wie Records ausgegeben oder Instanzen geprüft werden
    • vtable-Callbacks können viel Code am Leben halten, auch wenn sie in der Praxis gar nicht verwendet werden

  • Polymorphe Ausgabefunktionen

    • Polymorphe Funktionen wie display vergrößern den Umfang des benötigten Codes erheblich
    • Wer display aufruft, um einen String auszugeben, zieht damit die gesamte Infrastruktur für gepuffertes I/O hinein
    • Weil display alles Mögliche ausgeben kann, wird auch Code für Fälle wie Bitvektoren, Pairs und andere Typen mit hineingezogen
    • Wer stattdessen write-string nur für Strings aufruft, kann den allgemeinen Datenausgabe-Code vermeiden, zieht aber weiterhin allgemeine gepufferte I/O-Infrastruktur wie Ports mit hinein

Optimales Tree Shaking ist ein Problem der Flow-Analyse

  • Optimales Tree Shaking ist letztlich ein Problem der Flow-Analyse
  • Wenn es im Programm niemals Bitvektoren gibt, kann der Code in display, der Bitvektoren behandelt, toter Code sein
  • Um das zu wissen, muss man wissen, mit welchen Arten von Argumenten display aufgerufen wird; dafür braucht es eine Flow-Analyse auf hohem Niveau
  • In Python wird das Problem noch schwieriger
    • Objektorientierter Dispatch ist Higher-Order-Programmierung, daher hängt die Bedeutung von foo.bar davon ab, was foo ist
    • Pythons Lookup ist noch dynamischer als das in Scheme, und Methoden wie __getattr__ können an vielen Stellen verwendet werden
    • In der Praxis könnte eine Flow-Analyse solche dynamischen Lookups vielleicht ausschließen können
    • Das Ziel von Tree Shaking in Python ist kein großer Block mit lexikalischen Bindungen, sondern eine komplexe Menge von Modulen
    • Das ähnelt JavaScript, nur dass es für Python kein etabliertes Ökosystem von Tree-Shaking-Bundlern gibt

Voraussetzungen für Sprach-Toolchains für Web-Wasm

  • Wasm GC könnte DOM-Programmierung in anderen Sprachen als JavaScript ermöglichen
  • Damit daraus breite Nutzung entsteht, müssen die resultierenden Wasm-Module klein sein
  • Jede Sprach-Toolchain erfordert erhebliche Investitionen
  • Solche Investitionen zeigen sich oft in alternativen Toolchains, einschließlich experimenteller Tree-Shaking-Algorithmen
  • Alternative Standardbibliotheken müssen so entworfen werden, dass Tree Shaker besser damit arbeiten können

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-04-15
Meinungen auf Hacker News

  • Der Wasm-Blob von openEtG (eine Kartenspiel-Engine) wurde bei unter 400 KB gehalten, während viel Logik wie die Generierung von Kartentexten nach Wasm verlagert wurde; geschrieben ist er in Rust.
    Um die Größe zu reduzieren, war gezielte Pflege nötig: Fixed-Point-Arithmetik statt Gleitkommazahlen, Vektoren statt Hashmaps, Strings vermeiden, einen kleinen Allocator wie talc verwenden und Abhängigkeiten reduzieren.
    Es werden nur rand und fxhash genutzt, wobei sich rand vermutlich ebenfalls entfernen ließe; fxhash wird nur verwendet, um per Hash des Spielzustands zu prüfen, ob eine Desynchronisierung vorliegt.
    Auch die Zahl der Generic-Instanziierungen wurde reduziert: Da Vec bereits vorhanden ist, sollten zusätzliche Typen wie Box<[i16]> nicht noch hineingezogen werden; das Entfernen von Gleitkommazahlen und Hashmaps half ebenfalls, die Typvielfalt zu verringern.
    Auch die Algorithmen wurden mit Blick auf die Größe entworfen; zum Beispiel wird die Adrenaline-Mechanik, bei der Kreaturen mit niedriger Angriffskraft häufiger angreifen, über eine bitgepackte Lookup-Tabelle codiert.
    Dabei wurden die Kosten für das Speichern unkomprimierter Werte gegen die Kosten der Decoding-Logik abgewogen; die KI-Bewertung nutzt 6-Bit-Fixed-Precision, weil 64 in WebAssembly effizienter codiert wird als 128.
    Auch der Targeting-Mechanismus war früher eine AST-Form, bei der jedes Prädikat als enum vorlag und AND/OR als Expression-Slices ausgedrückt wurden; heute werden Ausdrücke in polnischer Notation in 32-Bit-Integern codiert, mit 2 Bit für AND/OR und 6 Bit für Prädikate.
    Hier war polnische Notation besser als umgekehrte polnische Notation, weil damit Short-Circuit-Evaluation für AND/OR möglich war.

    • Interessant ist, dass Fixed-Point-Arithmetik offenbar einiges an Platz gespart hat, obwohl Wasm Gleitkommatypen nativ hat.
      Ich überlege, ob Fixed-Point bei Problemen im Job helfen könnte, bei denen die maximale erforderliche Auflösung bekannt ist, etwa wenn keine Positionsgenauigkeit unterhalb eines Millimeters nötig ist, und würde gern mehr über entsprechende Erfahrungen hören.
    • Zusätzlich hilfreich war der Einsatz von binaryens wasm-opt.
      Es scheint die Wasm-Größe zuverlässig um etwa 20–30 % zu reduzieren: https://github.com/WebAssembly/binaryen
      Wenn man Wasm-Bundles im Browser ausliefert, lohnt es sich außerdem, Brotli-Kompression zu verwenden und den Webserver so zu konfigurieren, dass er die Brotli-komprimierten Dateien nutzt.
      Bei nginx geht das mit einer einzeiligen Änderung; Brotli reduziert die Größe von Wasm-Bundles um etwa den Faktor 3 und ist deutlich besser als gzip.
    • Ich habe die C++-Deep-Reinforcement-Learning-Bibliothek RLtools gebaut und auch Wasm-Beispiele erstellt (https://rl.tools); obwohl ich überhaupt nicht auf die Binary-Größe geachtet habe, lag das Ganze bei etwa 200–300 KB.
      Darin enthalten sind Vorwärts- und Rückwärtsdurchläufe für Deep Learning, Reinforcement-Learning-Algorithmen und Dynamiksimulationen.
      Auch jetzt ist das nicht wirklich problematisch, aber ich bin neugierig, wie viel kleiner es noch werden kann, und möchte es demnächst einmal verkleinern.
    • Ich dachte, JavaScript verwendet für alle Zahlen double; ich frage mich, ob Wasm in dieser Hinsicht völlig anders ist.
      Ich würde gern verstehen, wie die Aussage Sinn ergibt, dass man durch das Vermeiden von Gleitkomma und den Einsatz von Fixed-Point-Arithmetik Platz spart.
    • Ich würde gern Zahlen dazu sehen, wie viel Platz tatsächlich gespart wurde.
      Besonders Dinge wie in Punkt 6, Vec wie Box zu verwenden, scheinen mir nicht zu großen Einsparungen zu führen.

  • Der Name Tree Shaking wirkt wie eine ziemlich falsche Bezeichnung.
    Der Virgil-Compiler nennt es „Reachability Analysis“ und hat es in sein Kompiliermodell eingebaut.
    Der Compiler parst Programm- und Bibliothekscode, führt Type-Checking durch und führt Initialisierungscode aus; danach untersucht er jedoch vom Haupteinstiegspunkt aus nur den erreichbaren Code und nimmt auch nur diesen in das finale Binary auf.
    Er erzeugt auch problemlos Programme mit nur einer einzelnen main-Funktion und ohne Laufzeitsystem; das Laufzeitsystem wird nur für Stacktraces und Garbage Collection benötigt und kann auf Wunsch weggelassen werden.

    • Treeshaker als Name für ein Tool zur Anwendungsbereitstellung stammt möglicherweise aus Lisp.
      Der erste gefundene Fall war das Treeshaker-Tool in Lucid Common Lisp 4.1 von 1992, einer kommerziellen Common-Lisp-Implementierung für UNIX.
      Lucid CL hatte das Konzept eines Images, also eines gespeicherten Memory-Dumps des laufenden Lisp-Heaps, und eine Anwendung bestand aus Image und Runtime.
      Ein Image enthielt normalerweise fast sämtlichen Code und alle Daten im Speicher, daher wollte man für die Auslieferung kleinere Images erstellen; Treeshaker entfernte vor dem Speichern des Images Code und Daten, die als „unbenutzt“ eingestuft wurden.
      Dabei wurden im Graphen erreichbarer Lisp-Daten und -Codes Verbindungen beschnitten, und GC oder spezieller Code sammelte den Müll ein, um den Speicher zu reduzieren, bevor ein kleineres Image gedumpt wurde.
      Treeshaker war also kein Compiler-Tool, sondern ein Tool zum Entfernen unbenutzten Codes und unbenutzter Daten aus einem Lisp-Heap.
      Da ein Standard-Lisp-Image sogar den Compiler, den Interpreter und die REPL-Implementierung enthielt, konnte man ein laufendes Programm unterbrechen, in die REPL wechseln und weiterhin sämtlichen Code im aus dem Image wiederhergestellten Heap nutzen.
      Deshalb ergab es Sinn, sogar Compiler und REPL zu entfernen.
    • Der allgemein passende Begriff ist Dead-Code Elimination: https://en.wikipedia.org/wiki/Dead-code_elimination
      Reachability Analysis wird häufig verwendet, um zu bestimmen, welcher Code entfernt werden kann, aber die Analyse selbst entfernt keinen Code; das Entfernen ist ein nachgelagerter Schritt.
      „Tree Shaking“ impliziert meist eine Entfernung auf Funktionsebene, während Dead-Code Elimination auch auf deutlich feinerer Ebene möglich ist, etwa beim Entfernen von Zweigen in Bedingungen, und auf unterschiedlichen statischen Analysen beruhen kann.
    • In Software gibt es viele falsch benannte Dinge, aber persönlich halte ich Tree Shaking für einen hervorragenden Namen.
      Als ich ihn zum ersten Mal sah, habe ich die Bedeutung ohne weitere Recherche sofort verstanden.
      Man schüttelt einen Baum, damit lose anhaftende Dinge herunterfallen, und hier war klar gemeint, dass ungenutzte Pakete aus dem Tree „herausgeschüttelt“ werden.
    • Ich habe nie gedacht, dass sich Tree Shaking auf einen botanischen Baum bezieht, sondern an einen Tree als Datenstruktur gedacht.
      Wenn man sich ein Quellcode-Diagramm als physisches Objekt vorstellt, fallen beim Schütteln die Dinge ab, die von der Wurzel aus nicht erreichbar sind.
      Das unterscheidet sich nicht groß von Reachability Analysis; die eine Formulierung ruft nur stärker räumliches Denken hervor.
    • Es gibt viel Code, und dieser Code ist ein Tree.
      Ein Teil des Codes ist nicht mit dem Stamm, also dem Einstiegspunkt, verbunden.
      Tree Shaking entfernt die nicht verbundenen Teile, also lose Blätter und tote Äste.

  • Wenn die Compiler-Toolchain einer Sprache nützliches Wasm erzeugen kann, das gemessen an der Netzwerkübertragung nur wenige KB groß ist, eröffnet das neue Möglichkeiten.
    Sehr kleine Binaries werden neue Einsatzfälle für Wasm ermöglichen, und WasmGC hilft dabei eindeutig.
    Auch Java und Kotlin können heute mit etwa 2–3 KB ziemlich gute Ergebnisse liefern: https://developer.chrome.com/blog/wasmgc, https://twitter.com/bashorov/status/1661377260274720770
    Allerdings muss man vorsichtig sein, weil je nach verwendeter API viel Code mitgezogen werden kann.
    Trotzdem sind diese Sprachen dank WasmGC bei der Codegröße bereits deutlich besser aufgestellt als C++ und Rust, weil sie nicht mehrere KB Speicherverwaltungscode ins Bundle packen müssen.

    • Ich frage mich, ob WasmGC auch Rust helfen wird.
      Beim Umgang mit JavaScript-Objekten könnte es helfen, und es ließe sich wohl auch als weniger effizienter alternativer Memory Allocator verwenden.
      Trotzdem dürfte der Standard-Allocator von Rust in Wasm in den meisten Fällen gut genug sein.
      Wenn man Größenoptimierung aktiviert, wasm-opt verwendet und mit Brotli komprimiert, bekommt man eine enorme Menge Code in weniger als 100 KB Downloadgröße unter.
      Es ist ein Fehler, die Kosten von 100 KB Wasm direkt mit 100 KB gebündeltem JavaScript zu vergleichen, denn JavaScript ist beim Parsen und Initialisieren um ein Vielfaches langsamer.
      Die Downloadzeit ist ein realer Kostenfaktor, aber für die Zeit bis zur ersten Darstellung sind 100 KB Wasm deutlich besser als 100 KB JavaScript.
      Trotzdem gilt: kleiner ist besser, und es ist spannend, dass Java, Kotlin, C#, Python, Go usw. zu praktischen Sprachen für Webanwendungen werden.
      Ich bin auch gespannt, wie groß echte Anwendungen sein werden.
      Der größte Unterschied dürfte aus dem Framework-Design kommen; Virtual-DOM-Diffing ist zwangsläufig immer komplexer und langsamer als reaktive Komponentenbibliotheken wie Svelte, SolidJS oder Rusts Leptos.
      Sobald WasmGC überall unterstützt wird, dürfte die Wahl des Web-Frameworks für die Performance einen deutlich größeren Einfluss haben als die Sprache.

  • Ich bezweifle, dass die Aussage „Wasm macht DOM-Programmierung in anderen Sprachen als JavaScript denkbar“ wirklich stimmt
    Soweit ich weiß, braucht man für DOM-Manipulation in Sprachen wie Rust letztlich Bindings, die Aufrufe serialisieren, die dann auf der JavaScript-Seite ausgeführt werden
    In der heutigen Form von Wasm scheint man mir weiterhin an JavaScript gebunden zu sein

    • Wichtig ist, die vorherige Bedingung „mit GC“ einzubeziehen
      Theoretisch kann man jetzt DOM-Funktionen zur Laufzeit importieren und sie mit Referenzen auf DOM-Objekte aufrufen, damit JavaScript umgehen und die Runtime direkt aufrufen
      Ob das praktisch tatsächlich möglich ist, weiß ich nicht sicher, aber GC liefert zumindest den vorausgesetzten Mechanismus, um dorthin zu gelangen
    • Ich habe kürzlich Leptos für Rust ausprobiert; es ist ein sehr schnelles Framework, um Web-Frontends mit Wasm zu bauen, und ehrlich gesagt wirkt es ziemlich gut
      Im Grunde ähnelt es SolidJS
      #[component] fn App() -> impl IntoView { let (count, set_count) = create_signal(0); view! { "Click me: "{move || count()} } }
      Gegenüber JavaScript gibt es zwar einen Größen-Overhead durch Wasm, aber der ist nicht gravierend
      Nach wasm-opt und Brotli-Kompression war das Wasm-Bundle dieser Counter-App 37 KB groß, also in einer ähnlichen Größenordnung wie React, und nach dem Start deutlich schneller
      Direkte DOM-Manipulation habe ich nicht ausprobiert, aber für normale Komponenten wirkt es gut geeignet
    • Soweit ich es verstanden habe, ist eine der Absichten von WASI, APIs bereitzustellen, die direkt zum DOM führen
      Also etwa eine in Rust implementierte DOM-API, die ein in Rust geschriebenes Wasm-Modul ohne JavaScript-Ausführung nutzen kann
      Allerdings ist das schwierig, weil Teile der DOM-API auf JavaScript-Semantik zugeschnitten spezifiziert sind; deshalb fängt man offenbar zuerst mit Dingen an, die weniger JavaScript-Erbe haben, wie HTTP-Requests, TCP-Sockets und Dateisystemzugriff

  • Den Begriff „Dead Code Elimination“ gibt es schon lange; ich frage mich, warum dann der Ausdruck Tree Shaking entstanden ist

    • „Dead Code Elimination“ bezeichnet normalerweise eine eher kleinmaßstäbliche Compiler-Optimierung, die Codefragmente innerhalb einer Funktion verwirft, die niemals erreicht werden
      „Tree Shaking“ bezeichnet eine Whole-Program Analysis, bei der ganze Module und Funktionen verworfen werden, die nicht aufgerufen werden
      Konzeptionell ist es dasselbe, aber Compiler-Autoren müssen es meist getrennt implementieren, daher ist es hilfreich, zwei Namen zu haben
    • Welche Wörter überleben und Mainstream werden, hat wenig damit zu tun, wie alt sie sind
      Tree Shaking ist leicht vorstellbar, lässt sich besser sagen als „Dead Code Elimination“ und ist zugänglicher; deshalb scheint es der populärere Begriff geworden zu sein
      Als ich nachgesehen habe, welcher Begriff tatsächlich zuerst da war, fand ich die früheste Verwendung von „dead-code elimination“ in einer Arbeit von 1973: https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/22636/NicholasAlexandrakisMScThesis1973_original_C.pdf?sequence=1
      In Google Scholar konnte ich keine Verwendungen von „tree shaking“ oder „tree shaker“ im Computing-Kontext finden; die meisten Treffer bezogen sich auf Bäume wie Zitrusbäume
      Die wohl früheste Diskussion war ein Beitrag in comp.lang.lisp: https://groups.google.com/forum/#!topic/comp.lang.lisp/pspFr1XByZk
    • Falls der Begriff wirklich aus dem Lisp-Kontext stammt, dann wohl deshalb, weil dort nicht nur ausführbarer Code, sondern auch das Entfernen unnötiger Daten und Metadaten mit gleichem Gewicht behandelt wird
    • Der Ausdruck „Dead Code Elimination“ ist deutlich besser
    • Es ist eine lebendigere Formulierung und klingt umgangssprachlicher als „Dead Code Elimination“, daher ist nicht schwer zu verstehen, warum sie sich verbreitet hat

  • Ich vermute, die Tree-Shaking-Metapher stammt von bestimmten Erntemethoden bei Obstbäumen
    Wenn man den Baum schüttelt, fallen die reifen Früchte herunter
    Allerdings ist es keine besonders gute Metapher, weil man bei der Obsternte das Heruntergefallene haben will, während man es beim Speichern eines serialisierten Images wegwirft

    • Üblicherweise erntet man durch Schütteln Nüsse
      Obst ist empfindlicher und bekommt Druckstellen, wenn es zu weit fällt, deshalb wird es meist von Hand gepflückt
      Das Schütteln ist ziemlich grob, schadet dem Baum aber nicht

  • Meine Philosophie ist es, in JavaScript durch Algorithmen und vereinfachtes Design Größe und Performance konsequent zu optimieren, um Bundle-Größe und CPU-Reserven für Code zu schaffen, der rohe Rechenleistung braucht.
    Im ClubCompy-Projekt verwende ich Wasm, um ein FAT-Dateisystem auf Local Storage zu implementieren, was sich als sehr rechenintensiv herausgestellt hat.
    Später in diesem Jahr plane ich außerdem, Wasm zu verwenden, wenn ich die pixelgenaue Sprite-Kollisionserkennung wieder einbaue.
    Die erste Implementierung war reines JavaScript, und als 256 Sprites auf dem Bildschirm miteinander kollidierten, fiel die Framerate unter 1 fps.
    Ich denke, dass sich das in einem Worker-Thread praktisch kostenlos erledigen lässt, ohne Performance-Einbußen zu verursachen.

    • Pixelgenaue Kollisionserkennung klingt beim ersten Hören gut, kann sich beim tatsächlichen Spielen aber unangenehm anfühlen.
      Die meisten 2D-Spiele verwenden nicht ohne Grund rechteckige Collision Boxes: Spieler können dadurch leichter vorhersagen, ob es zu einer Kollision kommt.
      Bei pixelgenauer Kollision kann dieselbe Bewegung je nach Phase im Animationszyklus kollidieren oder auch nicht.
      Wenn eine Bewegung, die früher immer funktioniert hat, wegen ungünstigem Animationstiming fehlschlägt, fühlt sich das schlecht an.
      Außerdem ist pixelgenau nicht immer realistisch: Kleine Details eines Sprites können Dinge wie Stoff oder Haare sein, die in Wirklichkeit keine harte Kollision auslösen würden.
      Sprites bewegen sich oft auch mehrere Pixel pro Frame, sodass Kollisionen einzelner Pixel die Wahrscheinlichkeit erhöhen, dass sie durcheinander hindurchgehen.
      Einfache, vorhersehbare Kollisionserkennung ist in der Regel am besten.
    • Wenn man bei 256 Kollisionen bei 1 fps landet, ist nicht die Programmiersprache der Flaschenhals, sondern der Algorithmus.
      1 fps ist eine Framerate, die erst bei ungefähr 20.000 Kollisionen auftreten sollte.
      Bei pixelgenauer Erkennung könnte man, wenn genügend Speicher vorhanden ist, als einfache Methode ein Offscreen-Canvas für das gesamte Spielfeld rendern, jedes Sprite als Stencil in einer anderen Farbe zeichnen und das anschließend auswerten.
      Das läuft in linearer Zeit und braucht keine zusätzliche Partitionierung.
      Allerdings können Anti-Fingerprinting-Maßnahmen die unteren Bits der Canvas-Daten durch Rauschen ersetzen, daher muss man möglicherweise die oberen Bits verwenden.

  • Dieser Beitrag hat recht. Wasm hat ein Problem mit der Codegröße.
    Im Browser ist das ein Problem, weil vor dem Start einer Site der gesamte Code heruntergeladen werden muss; und auch bei Serverless-Architekturen ist es ein Problem, weil Code bei Bedarf aus Cold Storage auf einen bestimmten Server geladen wird, während der Client wartet.
    Tree Shaking kann helfen, dürfte aber nur eine inkrementelle Optimierung bleiben.
    Der grundlegende Grund dafür, dass Wasm-Programme so groß werden, ist, dass sie jeweils die eigene Sprach-Runtime und Standardbibliothek komplett mitbringen müssen.
    JavaScript dagegen bekommt Implementierung und Basisbibliotheken vom Browser bereitgestellt.
    Man könnte nun meinen, der Browser könne nicht alle Sprach-Runtimes vorab mitliefern, aber man sollte auch einen anderen Ansatz in Betracht ziehen: Shared Libraries und dynamisches Linken.
    WebAssembly unterstützt dynamisches Linken, und mehrere Wasm-Module können gleichzeitig geladen werden und sich gegenseitig aufrufen.
    Viele Wasm-Toolchains wollen das jedoch nicht unterstützen und sind darauf ausgelegt, das gesamte Programm samt Sprach-Runtime statisch zu einem riesigen Modul zu linken.
    Pyodide (CPython auf Wasm) ist ein Gegenbeispiel: Es ist derzeit mit dynamischem Linken im Hinterkopf entworfen.
    Genau deshalb konnte Cloudflare Workers Python kürzlich als First-Class-Unterstützung hinzufügen: https://blog.cloudflare.com/python-workers
    Aus Sicht des technischen Leads der gesamten Workers-Plattform teilen sich alle Workers, die auf derselben Maschine laufen, eine einzige kompilierte Pyodide-Runtime; sie muss also nicht für jeden Worker separat geladen werden.
    Wenn dynamisches Linken breiter unterstützt würde, könnte man sich eine Struktur vorstellen, in der der Browser populäre Sprach-Runtimes und darüber hinaus populäre Bibliotheken vorab lädt und alle Webseiten, die diese Runtime benötigen, dieselbe schreibgeschützte Code-Kopie teilen.
    Diese Runtimes laufen weiterhin in einer Sandbox, der Browser muss ihnen also nicht vertrauen, sondern sie nur bereitstellen.
    So ließe sich ein Browser bauen, der Sprachen außerhalb von JavaScript „eingebaut“ unterstützt, ohne dass Browser-Maintainer die Sprachimplementierungen vollständig prüfen oder sich ausführlich damit befassen müssten.

    • Die Vorstellung, dass Browser mehrere populäre Runtimes und Bibliotheken vorab laden und Webseiten sie gemeinsam nutzen, klingt ähnlich wie die frühere Idee, gängige JavaScript-Frameworks über ein gemeinsames CDN bereitzustellen: Dann wären sie in den meisten Browser-Caches bereits vorhanden, ein Download wäre nicht nötig, und die Größe des Frameworks wäre weit weniger wichtig.
      Ich kenne mich damit nicht sehr gut aus, aber nach meinem Verständnis hat dieser Ansatz nicht gut funktioniert.
      Es gab zu viele Bibliotheksversionen, sodass einzelne Versionen tatsächlich nicht besonders weit verbreitet waren; später gingen Browser wegen Datenschutzbedenken dazu über, Caches nach Site oder Origin zu partitionieren.
      Vielleicht war das gar nicht primär auf Caching ausgelegt, aber es ist ein schwieriges Problem, das eher ein soziales Problem als ein technisches ist.
      Wenn man mehr Sprach-Runtimes zur Standardunterstützung des Browsers hinzufügt, erhöht das die Einstiegshürde für neue Browser, und man kann auch nicht alle Bibliotheken und Runtimes unterstützen, die Leute haben wollen.
      Wenn jeder sie selbst mitbringt und man auf den Cache hofft, bleibt die Frage, wie man die Probleme vermeidet, die es zuvor beim Caching von JavaScript-Bibliotheken gab.
    • Schon eine eingeschränkte Unterstützung für dynamisches Linken dürfte ziemlich große Wirkung haben.
      Zum Beispiel könnte man in eine Go-Shared-Library die Runtime und die zentralen Teile der Standardbibliothek packen, die von vielen Programmen genutzt werden.
      Auch ohne Unterstützung für dynamische Bibliotheken innerhalb der App ließe sich die Größe aller Go-Programme reduzieren, und die Sprach-Runtime müsste nicht extrem auf Platz optimiert werden.
      Denn sie ist bereits geladen, und sobald irgendein Programm auch nur eine ihrer Funktionen nutzt, ist sie kein verschwendeter Speicherplatz.
      Damit verändert sich das Kostenmodell für Größenoptimierung bei Programmen in dieser Sprache.
      Enthaltene Standardbibliotheksfunktionen sind praktisch kostenlos, sobald man die Sprache verwendet, also kann man sie einfach nutzen.
      Allerdings wiederholt sich das Problem bei häufig genutzten Bibliotheken und Frameworks.
      Wenn man auf Cloudflare läuft, würde man vermutlich auch die Cloudflare-Standardbibliothek für Go gemeinsam nutzen wollen.
      Das Problem ist, dass sich Sprachen nicht im selben Tempo weiterentwickeln wie Runtimes.
      Entweder ist die Unterstützung für mehrere Sprachversionen begrenzt, oder Shared Libraries sammeln sich mit der Zeit an, wodurch der Sharing-Effekt zwischen Apps abnimmt.
      JavaScript hat ein Versionsmodell nach dem Prinzip „man hat keine Wahl“ und verlangt starke Abwärtskompatibilität sowie gelegentlich Polyfills.
      Für andere Sprachen passt das möglicherweise weniger gut.
      Wenn die Runtime wirklich Platz sparen will, kann sie die Plugin-Vielfalt einschränken.
      Es gab zwar Unzufriedenheit, aber der Ansatz „man muss JavaScript verwenden“ hat im Browser ziemlich gut funktioniert.
      Vielleicht müssen WebAssembly-basierte Sprachen gar nicht so vielfältig sein; wie bei einer Turmbau-zu-Babel-Situation hat Vielfalt ihren Preis.
    • Ich frage mich, ob ein Ansatz mit profilbasiertem Tree Shaking möglich wäre: kleine Module, die nur den für die Anwendung benötigten Code enthalten, während seltener genutzte Funktionen bei Bedarf per dynamischem Linken nachgeladen werden.
      Wenn man Tree Shaking auf Basis realer Produktionsinformationen betreibt, könnte man vermutlich viel toten oder fast toten Code entfernen, ohne ausgefeilte statische Analysealgorithmen implementieren zu müssen.
    • Eine Struktur, bei der der Browser populäre Runtimes vorab lädt, birgt am Ende die Gefahr, dass Hunderte Runtime-Versionen in den Browser heruntergeladen werden, jede Binärdatei nur von einer einzigen Site genutzt wird und der Cache damit vollläuft.
    • Insgesamt stimme ich zu, möchte aber darauf hinweisen, dass man auch bei Wasm ziemlich viel eingebautes JavaScript im Browser nutzt, sobald man mehr als reine Berechnungen machen will.
      Besonders in Kontexten wie Hoot sind Dinge wie appendChild externe Funktionen, die aus Scheme heraus aufgerufen werden: https://spritely.institute/news/building-interactive-web-pages-with-guile-hoot.html
      Theoretisch kann man in jeder Wasm-Umgebung auf diese Weise große Teile der JavaScript-Standardbibliothek nutzen.

  • Zig ist für solche Zwecke perfekt.
    Persönlich halte ich die Größe einer Wasm-Datei für keinen wichtigen Faktor, solange sie unter 100 KB liegt; wenn sie über MB hinausgeht, wird sie wichtig.
    Eingebaute GC ist für manche Apps wichtig, aber nicht für alle, und Web-Apps baut man am besten ohne GC.
    Der wichtigste Faktor für den Erfolg einer App, die Wasm verwendet, bleibt weiterhin der Performance-Vorteil.

  • Ich betreibe eine Blazor-App auf Cloudflare Pages; die Downloads sind schnell und die Performance ist gut, aber die Ladezeit ist schrecklich.
    Ich glaube, dass sich das mit .NET nicht lösen lässt, und das Kernproblem scheint zu sein, dass objektorientierte Sprachen konstruktionsbedingt dazu neigen, dass alles miteinander verflochten ist.
    Außerdem ist es schwer, mit dem Umfang der Mittel zu konkurrieren, die in JavaScript geflossen sind, und JavaScript hat Copy/Paste quasi als Sprachfeature, was sich wie ein Cheat-Code anfühlt.
    Drittens braucht man auch bei Blazor weiterhin JavaScript und entsprechende Kompetenzen; darin sehe ich das Hauptproblem.

    • Das ist kein Problem von Objektorientierung.
      Das Problem ist, dass Sprachen jener Zeit für viele Anwendungsfälle auf Reflection angewiesen waren.
      Viele Leute arbeiten hart daran, solche Anwendungsfälle in großen Teilen von .NET zu beseitigen und sie als sicher für die Entfernung ungenutzten Codes zu markieren.
      Wenn die Möglichkeit besteht, dass Methoden per Reflection aufgerufen werden, ist schwer zu erkennen, was man sicher entfernen kann.
      Auch wenn es so aussieht, als würde niemand Foo.Bar() aufrufen: Was, wenn jemand Reflection.getClass(someClass).runMethod(someVar) ausführt und diese Variablen auf "Foo" und "Bar" gesetzt sind?
      Dart erlaubt zum Beispiel in vorab kompilierten Apps keine Reflection, wodurch ungenutzter Code sicher entfernt werden kann: https://docs.flutter.dev/resources/faq#does-flutter-come-with-a-reflection-mirrors-system
      Dart ist eine objektorientierte Sprache, vermeidet aber Runtime-Codegenerierung und Runtime-Reflection und setzt stattdessen auf Codegenerierung zur Compile-Zeit.
      .NET bewegt sich ebenfalls in diese Richtung, aber das passiert nicht über Nacht.
      Allerdings haben Nicht-JavaScript-Sprachen, wie andere schon gesagt haben, zusätzlich das Problem, dass sie die genutzten Teile der Standardbibliotheksfunktionen, die in der JavaScript-Runtime des Browsers enthalten sind, selbst mitliefern müssen.
    • Blazor ist in dieser Hinsicht nicht besonders stark.
      Das aktuelle Packaging-Modell kann die Fähigkeiten des .NET-Trimmings wegen der Einschränkung, dass Wasm auf Mono paketiert wird, nicht richtig ausnutzen.
      Wenn man sehen will, wie stark sich tatsächlich reduzieren lässt, sollte man besser eine normale Anwendung mit AOT bauen; dann erhält man ein kleines Binary.
      Die experimentelle Unterstützung des NativeAOT-LLVM-Wasm-Targets in dotnet/runtimelab liefert deutlich kleinere Bundle-Größen und deutlich bessere Performance, liegt aber noch unter dotnet/runtimelab und nicht in dotnet/runtime, daher weiß man nicht, wann sie nutzbar sein wird.