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: 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