Absender: Timo Sandmann
Datum: Mo, 11.07.2011 23:40:16
In-reply-to:
<3fa2a0ffcb971c3ba20ff2956901265e.squirrel@xxxxxxxxxxxxxxxxxxx>
References:
<06FDD79E-4108-46F2-9912-C51255355A81@xxxxxxxxxxxxxxx> <486F950B-9CD1-476A-AD42-EB734AFCB1EC@xxxxxxxxxxxxxxx> <3fa2a0ffcb971c3ba20ff2956901265e.squirrel@xxxxxxxxxxxxxxxxxxx>
Hallo Uwe, vielen Dank für die ausführlichen Erklärungen. Mir sind noch zwei Dinge aufgefallen, auf die ich dich hinweisen möchte, weil sie vermutlich so nicht beabsichtigt sind: 1.) Bei fast allen Dateien in avr_basic und doku ist das executable-Flag (x) gesetzt. 2.) Die Sourcecode Dateien haben unterschiedliche Zeilenumbruch-Zeichen, teilweise CRLF ("Windows-Mode") und teilweise LF ("Unix-Mode"). Das ist insbesondere dann nervig, wenn man alle Änderungen in einen Patch packen möchte, dann gibt es innerhalb der Patchdatei unterschiedliche Zeilenende-Zeichen. Beides nur als Hinweis, es ist natürlich nicht so tragisch. Grüße, Timo Am 08.07.2011 um 09:37 schrieb Uwe Berger: > MoinMoin, > > Am Do, 7.07.2011, 23:29, schrieb Timo Sandmann: >> auch uBasic ist jetzt wieder aktuell (rev. 60). >> Die Option "TOKENIZER_FASTPARSER" habe ich ausgeschaltet, weil ich keine >> Ahnung habe, was genau sie tut bzw. welche Auswirkungen sie hat... (sieht >> irgendwie nach Suchbaum für die Schlüsselwörter aus oder so etwas in der >> Art?). >> > korrekt, es handelt sich um ein beschleunigtes Suchverfahren nach > Schlüsselwörtern im BASIC-Quelltext und deren "Tokenizierung" in einem > Binärbaum. > > Das bisherige Verfahren, einschaltbar via TOKENIZER_STANDARD in > ubasic_config.h, beruht auf einer Liste aller gültigen Schlüsselwörter und > deren Zuordnung zu einem Token. Bei der Analyse wird diese Liste vom > Anfang bis zum gesuchten Schlüsselwort elementeweise durchgescannt. > Nachteile: > * die Liste wird immer von Anfang an gelesen, ist das gesuchte > Schlüsselwort sehr weit hinten, muss auch entsprechend lange gesucht > werden > * es werden String-Vergleiche verwendet, die auch nicht gerade schnell sind > > Das neue Verfahren, einschaltbar via TOKENIZER_FASTPARSER in > ubasic_config.h, verwendet einen Binärbaum zur Suche/Umsetzung der > Schlüsselwörter in Token. Der erste Buchstabe des zu suchenden Wortes wird > als Einsprung in den Baum verwendet, danach hangelt sich der Parser > buchstabenweise durch den Baum bis er auf ein entsprechendes Blatt trifft, > in dem das entsprechende Token kodiert ist. Vorteile: > * die Suche ist effizienter, da keine Liste durchgescannt werden muss, > sondern zielgerichtet gesucht wird --> die Anzahl der Zugriffe verringert > sich im Durchschnitt > * es werden nur Byte-Vergleiche verwendet > * lustigerweise scheint der generierte Code incl. Binärbaum platzsparender > zu sein (habe ich zumindestens bei der Übersetzung des Interpreters > unter Linux festgestellt). U.a. fällt dabei auch die Funktion singlechar() > in tokenizer.c weg, weil auch diese Zeichen im Binärbaum abgebildet sind. > > Durch dieses Suchverfahren verbessert sich die Geschwindigkeit des > Interpreters teilweise erheblich (je nach Umfang des BASIC-Programmes). > Einige Tests mit unterschiedlichen BASIC-Programmen ergaben einen > durchschnittlichen Faktor von 1:4! > > Einziger (derzeitiger) Nachteil ist, dass zur Generierung des Binärbaums > ein Programm notwendig ist, welches noch nicht veröffentlicht wurde. > Grund: Rene (der Entwickler dieses Algorithmus) hat mich darum gebeten mit > der Freigabe des Build-Tolls noch ein wenig zu warten, bis er mit einem > paralellen Projekt, welches ebenfalls diesen Parser benutzt, fertig ist. > Bis dahin bin ich aber gern bereit, bei individuellen Erweiterungen des > BASIC-Sprachumfangs, den Binärbaum zu generieren, wenn ich entsprechende > Anfragen via Mail bekomme. Der derzeitige Sprachumfang (Revision 60 im SVN > auf mikrocontroller.net) ist im derzeitig veröffenlichten Binärbaum > enthalten. > >> String-Support lässt sich in ubasic_config.h aktivieren, falls gewünscht. >> > jupp, seit ein paar Versionen des Interpreters gibt es einige > BASIC-Elemente, die die Verarbeitung von Zeichenketten, inclusive > Zeichenketten-Felder, ermöglichen. Dabei muss man sich aber bewußt sein, > dass dies teilweise sehr viel dynamischen RAM zur Laufzeit (Speicherplatz > für Zeichenkettenvariable werden erst dann reserviert, wenn diese > angesprochen werden...) benötigt, was auf einer MCU tötlich sein könnte. > Also man sollte diese Option nur dann einschalten wenn man wirklich > Zeichenketten in BASIC verarbeiten möchte, ...und dies dann wirklich > wohlbedacht dosiert. > > Ich habe Zeichenkettenverarbeitung in den Interpreter reingenommen, weil > er nicht nur für ressourcenarme MCUs gedacht ist. So teste ich z.B. > Weiterentwicklungen des Interpreters gar nicht auf eine MCU, sondern unter > Linux. Erst ganz zum Schluss, kurz vor Veröffentlichung, flashe ich das > Zeugs mal auf ein Arduino-Board (mit einem Mega328p) und einem > SD-Card-Shield (von dem die BASIC-Programme eingelesen werden), um zu > sehen, ob auch dort alles funktioniert. > > Grüße Uwe