![[ICO]](/icons/blank.gif){kind=icon}
![[DIR]](/icons/back.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}
![[ ]](/icons/binary.gif){kind=icon}
![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/folder.gif){kind=icon}
tar xfJ /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe20/effizienz-aufgabe20.tar.xzauspacken. Mit
make test
(bzw. einfach make) können Sie das
Programm gforth9 und die
Test-Eingabe brew-sequences.bin erzeugen.
Das Programm gforth9 wird wie folgt aufgerufen:
gforth9 infile rulesfile costsfile [0-8]
Wobei infile die Eingabe in einem Binärformat ist, und rulesfile und
costsfiles die Ausgaben, ebenfalls in einem Binärformat. [0-8] ist
noch ein weiterer Parameter, den wir dazu verwenden, um beim Testen
ein bisschen mehr Breite zu bekommen (weil wir nur eine Eingabedatei
verwenden).
Weiters lässt make test das Programm mit verschiedenen
Parametern laufen, und prüft, ob das Ergebnis bezüglich der optimalen
Kosten mit dem gegebenen Programm übereinstimmt. Da es oft mehrere
optimale (und damit gültige) Lösungen gibt, bei denen sich dann die
rulesfile-Ausgabe unterscheidet, wird das rulesfile nicht mit der
Ausgabe des Ursprungsprogramms verglichen.
Mit
make perf
erhalten Sie Performance-Resultate für den Vergleich mit der
vorgegebenen Lösung. Die vorgegebene Lösung braucht 125M cycles:u
auf der g0. Bitte beziehen Sie sich in Ihren Vergleichen auf diese
Zahl und machen Sie Ihre Messungen auch auf der g0, um die
Vergleichbarkeit zu gewaehrleisten. Wenn Ihre Optimierung den
Platzbedarf (statisch im Programm und/oder den dynamisch allokierten
Speicher) nennenswert ändert, präsentieren Sie bitte auch Messungen
dazu (mit objdump -h oder readelf -S sehen
Sie die Größe diverser Sections im Binary; size zählt
leider z.B. .rodata nicht zu data).
Mit
make clean
können Sie die erzeugten Dateien löschen. Beachten Sie, dass Sie dann
zum Neubauen iburg brauchen (ist auf der g0 installiert).
gforth9 ist von der optimalen Codeauswahl für Gforth (aus dem Jahr
2007 für die PowerPC-Architektur) abgeleitet. Und zwar gibt es
355 primitive Wörter in Gforth, die in gforth9.burg
die Namen op0-op354 haben (die Forth-Namen sind mit iburg und C
nicht kompatibel und wurden deswegen durch diese wenig sprechenden
Namen ersetzt).
Die Wörter arbeiten auf einem Stack. Im einfachsten Fall gibt es
eine Darstellung des Stacks, und jedes Forth-Wort erwartet den Stack
am Anfang in dieser Form und hinterlässt den Stack am Schluss in
dieser Form; diese kanonische Darstellung wird
in gforth9.burg durch das Nonterminal S0 repräsentiert.
Eine typische Regel ist:
S0: op53(S0) = 54 (16);
Das bedeutet, dass der Stack in S0 beginnt und S0 endet, das Wort
op53 aufgerufen wird, und der Code dafür 16 Bytes kostet. Die Regel
hat die eindeutige Nummer 54 (und das sagt dem Codegenerator auch,
welcher Code erzeugt werden muss; die eigentliche Codeerzeugung
kommt aber in diesem Beispiel nicht vor, es endet mit der Ausgabe
der Regeln).
Jetzt kann man aber noch andere Stack-Darstellungen einführen, z.B. eine, in der die obersten drei Elemente des Stacks in Registern (und nicht im Speicher) sind. Es kann billiger sein, wenn ein Wort den Stack nicht im kanonischen Zustand hinterlässt und das nächste Wort dann in diesem Zustand weitermacht. Zum Beispiel gibt es für op53 noch eine Reihe anderer Regeln, z.B.:
S2: op53(S0) = 441 (8);
Hier hat ist der Stack vor dem Wort im Zustand S2, und nach dem Wort
in S0 und der Code dafür kostet nur 8 Bytes. [Leute, die sich mit
burg/iburg besser auskenen, werden sich fragen, warum der Zustand
vorher auf der linken Seite der Regel ist und der Zustand danach auf
der rechten Seite; ja, man könnte es auch genausogut umgekehrt
machen, hier wurde eben diese Richtung gewählt.]
Man kann auch Code einfügen, um direkt von einem Stackzustand in den anderen überzugehen, z.B. repräsentiert durch diese Regel:
S0: S2 = 1137 (8);
Damit eine Sequenz enden kann, brauchen wir auch noch ein Terminal
bzw. Blatt (Terminal aus der Grammatiksicht und Blatt aus der
Baumsicht). Dazu haben wir ein Blatt s0 und die Regel
S0: s0 = 1200;
(mit Kosten 0), die aber beide dazu da sind, um in den
Baumgrammatik-Formalismus hineinzupassen.
Es kann also für eine Sequenz von Wörtern auf verschiedenste Weise Code erzeugt werden, mit beliebigen Stack-Zuständen am Anfang und Ende jedes Wortes, und dann noch direkte Übergänge zwischen Stack-Zuständen.
Am besten wählen wir den Code mit den geringsten Kosten aus. Für die optimale Codeerzeugung mit solchen Regeln gibt es die Werkzeuge iburg und burg, wobei iburg mittels dynamic programming zur Laufzeit von gforth9 arbeitet (siehe auch Kapitel 9.1 des Übersetzerbau-Skriptums), während bei Verwendung von burg gforth9 nur mehr einen Baumautomaten abarbeitet und damit deutlich schneller ist. Allerdings schafft burg es nicht, den Automaten für gforth9.burg zu erzeugen (der Automat wird so groß, dass burg bei seiner Erzeugung abstürzt), deswegen verwenden wir iburg und deswegen gibt es dieses Beispiel.
Dokumentation zu iburg gibt
es hier
und hier,
und mittels man iburg.
In brew-sequences.bin gibt es ca. 28000 Sequenzen mit
zusammen 62000 Wörtern. Jede Wort ist durch eine 16-bit-Zahl (short)
dargestellt, jede Sequenz wird durch die Zahl 0 abgeschlossen. Die
rules-Ausgabe enthält einfach die angewendeten Regeln (als
16-bit-Zahlen) ohne Separation zwischen den Sequenzen. Die
costs-Ausgabe enthält die Kosten für jede Sequenz als 16-bit-Zahl.
Im Normalfall fängt jede Sequenz im Zustand S0 and und endet im Zustand S0 (und für das Programm gforth9 übergibt man dann 0 als letzten Parameter). Um das Testen ein bisschen breiter zu machen, gibt es noch die Möglichkeit, einen anderen Zustand als Normalzustand zwischen den Sequenzen einzustellen (letzter Parameter von gforth9, darf 0-8 sein).
Ist es praktisch relevant, schneller zu sein als die von iburg produzierte Codeauswahl? Da bei Gforth (wie auch bei JIT-Compilern allgemein) der Code jedes mal beim Starten erzeugt wird, spielt das schon eine wichtige Rolle, vor allem wenn man das System in einem Shell-Script eingesetzt wird, wo es vielleicht in einer Schleife aufgerufen wird.
Zunächst einmal ist iburg auf Bäume ausgelegt (mit Knoten mit mehr als einem Kind), während in diesem Beispiel nur Knoten mit einem (bzw. bei Blattknoten keinem) Kind vorkommen.
Wir können zwar keinen Automaten mit burg bauen, aber es gibt die Möglichkeit, die Zustände eines Automaten bei Bedarf zu erzeugen (siehe Fast and Flexible Instruction Selection with On-Demand Tree-Parsing Automata), einen Teil des Automaten schon im vorhinein zu erzeugen, oder für Gesamtsequenzen das Ergebnis (z.B. mittels Memoization oder compile-time initialization) nachzuschauen statt neu zu berechnen.
Das sind nur ein paar Vorschläge, die gedacht sind, Ihre Phantasie anzuregen; wenn Ihnen noch etwas anderes einfällt, umso besser.
Es ist natürlich leicht, eine Version zu machen, die genau für diese Eingabe schnell ist (und für alle anderen so langsam wie vorher), aber damit würden Sie das Lehrziel verfehlen. Es geht also darum, eine Version zu produzieren, bei der man auch für andere Eingaben ähnliche Beschleunigungen erwarten würde.
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| Makefile | 07-Dec-2020 11:24 | 1.1K | |
| brew-sequences | 07-Dec-2020 11:24 | 184K | |
| brew-sequences.bin | 07-Dec-2020 11:24 | 175K | |
| brew-sequences.c | 07-Dec-2020 08:48 | 493K | |
| brew-sequences.txt | 06-Dec-2020 17:04 | 372K | |
| brew-sequences0.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences0.rules | 07-Dec-2020 18:56 | 198K | |
| brew-sequences1.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences1.rules | 07-Dec-2020 18:56 | 279K | |
| brew-sequences2.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences2.rules | 07-Dec-2020 18:56 | 277K | |
| brew-sequences3.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences3.rules | 07-Dec-2020 18:56 | 277K | |
| brew-sequences4.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences4.rules | 07-Dec-2020 18:56 | 279K | |
| brew-sequences5.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences5.rules | 07-Dec-2020 18:56 | 279K | |
| brew-sequences6.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences6.rules | 07-Dec-2020 18:56 | 279K | |
| brew-sequences7.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences7.rules | 07-Dec-2020 18:56 | 283K | |
| brew-sequences8.costs | 07-Dec-2020 18:56 | 55K | |
| brew-sequences8.rules | 07-Dec-2020 18:56 | 289K | |
| effizienz-aufgabe20.tar.xz | 07-Dec-2020 18:56 | 193K | |
| effizienz-aufgabe20/ | 07-Dec-2020 18:56 | - | |
| gforth9 | 07-Dec-2020 11:24 | 213K | |
| gforth9.burg | 07-Dec-2020 08:54 | 35K | |
| gforth9.c | 07-Dec-2020 11:24 | 401K | |
| gforth9.h | 07-Dec-2020 09:35 | 5.8K | |
| gforth9.o | 07-Dec-2020 11:24 | 248K | |
| main.c | 07-Dec-2020 10:12 | 4.1K | |
| main.o | 07-Dec-2020 11:24 | 6.9K | |
| perf.data | 07-Dec-2020 10:41 | 177K | |
| perf.data.old | 07-Dec-2020 10:40 | 414K | |
| test.costs | 07-Dec-2020 14:11 | 55K | |
| test.rules | 07-Dec-2020 14:11 | 198K | |