c't

c't-Projekte - Mailinglisten


[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

Re: [ct-bot] Updates

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