Absender: Uwe Berger
Datum: Fr, 08.07.2011 09:37:04
In-reply-to:
<486F950B-9CD1-476A-AD42-EB734AFCB1EC@xxxxxxxxxxxxxxx>
References:
<06FDD79E-4108-46F2-9912-C51255355A81@xxxxxxxxxxxxxxx> <486F950B-9CD1-476A-AD42-EB734AFCB1EC@xxxxxxxxxxxxxxx>
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