BASIC-Code beschleunigen/optimieren

Zitat von Chagizzz

[..]

Entscheidend ist hier wohl zur Zeitersparnis hauptsächlich die weitestgehende Vermeidung von IF...THEN.

[..]

Ich finde es jedenfalls erstaunlich, was für Unterschiede kleine Feinheiten machen.
Vielleicht sollten wir kleine Programmroutinen wie z.B. einen STRING in Grossbuchstaben wandeln als Wettbewerb machen.

Alles anzeigen

In der Tat, alles was nach mehr aussieht dauert bei einem BASIC-Interpreter in der Regel auch länger (da gibt es freilich auch Ausnahmen). Schon alleine vom "Parsing" im Zuge der Abarbeitung.

Bei den IF-Varianten könnte man etwas effizienter vorgehen, indem man die Füllleerzeichen weg lässt. Konstanten, speziell die 3-stelligen brauchen verhältnismäßig lange, um in Floats umgerechnet zu werden, die dann für den Vergleich benötigt werden. Könnte man in Variablen ablegen (dann hängt es nur noch von der Variablensuche ab ). Kann auch 15 % für eine Abfrage wie unten bringen (wenn die Variablen als eine der ersten definiert sind).
Sachen wie

Zitat von Chagizzz

8310 IF A1>64 AND A1<91 THEN A2$=A2$+CHR$(A1+32):NEXT:RETURN

sollten schneller sein, wenn man sie als
310 IF A1>64 THEN IF A1<91 THEN A2$=A2$+CHR$(A1+32):NEXT:RETURN
schreibt. Sonst wird der Ausdruck immer vollständig ausgewertet. Das macht die Abfrage rund 10 bis 50 % schneller.

Ok...

• FORJ-Schleife habe ich in die einzelnen Varianten gezogen
• Zeilen soweit wir möglich zusammengezogen - dabei auf ähnlichen Aufbau in den Varianten geachtet
• Leerzeichen entfernt
• DIMA$... scheint die Einzelvarianten schneller, die DIM-Variante geringfügig langsamer zu machen
• IF x AND y durch IF x then if... ersetzt (brachte nur wenig, aber immerhin)

Zitat von JeeK

Das GOSUB (wie auch GOTO) prinzipiell, da ja dessen Ausführungszeit von der "Entfernung" zur Zielzeile abhängt und damit trotz aller Eleganz des ON-Konstrukts, die Späteren Varianten stets eine Laufzeitdraufgabe erhalten.

Entfernung von aufrufender Zeile zu Zielzeile oder Rang der Zielzeile insgesamt? Vorwärts wie rückwärts?
(das wäre ja dann in Zukunft für die Umsetzung von Bedeutung)

Zitat von JeeK

Ad Platzverbrauch: Der Platzverbrauch des gefüllten AA$-Arrays? 5 (Array-Variable an sich) + 2*1 (1-Dimensional) + 3*256 (Stringdescriptor pro Element) + 255 (Zeichen auf dem Stringheap, Index 0 wir ja nicht gesetzt, Achtung: Leerstring "" ist nicht gleich CHR$(0)!).

Ok, ist tatsächlich noch etwas weniger, als ich gerechnet hatte. War mir auch nicht sicher, ob überwiegend einzelne Zeichen im Array möglicherweise Platzverschwendung wären. Aber das ist dann ja eher nicht der Fall.

Zitat von JeeK

Konstanten, speziell die 3-stelligen brauchen verhältnismäßig lange, um in Floats umgerechnet zu werden, die dann für den Vergleich benötigt werden.

??? Kannst Du da etwas mehr ausholen???
Welche dreistelligen Konstanten, was für Floats?

... und dann fällt mir noch ein:

macht das Sinn es so aufzuschlüsseln oder wäre im Prinzip

mit anschließendem FRE(0) auch ok? Würden dabei die zuvor zugewiesenen Speicherstellen (z.B. zu aa$(65-90)) überschrieben, oder an anderer Stelle neu erstellt und die alten freigegeben?

Zitat von Chagizzz

??? Kannst Du da etwas mehr ausholen???
Welche dreistelligen Konstanten, was für Floats?

Bei Auswertung wird immer mit Floats gerechnet - leider. Selbst wenn z.b. nur mit Integer-Variablen hantiert wird. Die werden fein säuberlich in Floats umgewandelt, dann gerechnet und wieder zurück.

Also auch bei 2-stelligen Konstanten bringt es bezogen auf die Zeile rund 15 %. Aber wie gesagt unter der Voraussetzung, dass die Variablen "früh" definiert sind. Jede Stelle mehr einer Konstante braucht "länger", da hier immer eine Float-Multiplikation mit 10 verbunden ist.
Ausnahme sind die Zeilennummerkonstanten von RUN, GOTO, GOSUB (natürlich auch in den ON-Varianten)., wo die Zeilennummerkonstanten in "normaler" Integer-Arithmetik aufgebaut werden ...

Zitat von JeeK

Jede Stelle mehr einer Konstante

Also zehner, hunderter, tausender?!
Ok, werd' ich dann in Zukunft versuchen dran zu denken. Vielen Dank für Deine Ausführungen.

Zitat von Chagizzz

Würden dabei die zuvor zugewiesenen Speicherstellen (z.B. zu aa$(65-90)) überschrieben, oder an anderer Stelle neu erstellt und die alten freigegeben?

Kannst dazu noch jemand was sagen? Also überschreiben von Array Inhalten.
(zwei Einträge zurück)

Strings werden bei jeder Zuweisung neu im Speicher abgelegt, vor Ort verändert werden die nicht.

Jepp, das war meine Frage. Danke Euch...

Zitat von ThomBraxton

- Variablen sofort als Fließkomma-Variable anlegen, damit die Umwandlung von Int nach Fließkomma entfällt.

Zitat von ThomBraxton

- Anstelle einer NULL lieber den Dezimalpunkt nehmen. z.B. bei if a=0 then lieber if a=. then nutzen.

Nach meiner Erfahrung - und so besagt es auch die Theorie - zumindestens solange man keine FPU, keinen DSP oder MMX/SSE oder sowas hat - ist das Rechnen mit Integer-Zahlen doch viel schneller als Fließkomma. Ihr macht anscheinend den Fehler, Fließkomma-Variablen für Sachen zu verwenden, wo ihr nur kleine Ganzzahlen braucht. Das CBM Basic kennt ja auch Integer-Variablen, man muss an den Variablennamen nur ein % anhängen.

10 ti$="00:00:00"
11 for i=0to255:for j=0to255:next j:next i
12 print ti$

20 ti$="00:00:00"
21 for i%=0to255:for j%=0to255:next j%:next i%
22 print ti$

Man muss bei den Integer-Variablen nur aufpassen, dass man im Wertebereich (ich meine 0-255, also 1 Byte) bleibt. Z.B. für Arrays reicht das doch.

1. Integer-Variablen haben in BASIC V2 den Wertebereich -32768 bis 32767.
2. Alle Berechnungen mit Ausnahme der logischen Operatoren AND, OR, NOT rechnet BASIC V2 mit Fließkommazahlen aus.
3. FOR läßt keine Integer-Variablen als Laufvariable zu!

Bei dem Ausdruck (Beispiel) S% = T% AND U%, wird man übrigens gleich mehrfach bestraft: die Inhalte von T% und U% werden zunächst von Integer nach Float, dann wegen dem AND-Operator wieder nach Integer gewandelt, das Ergebnis wieder von Integer nach Float und vor der Zuweisung an S% wieder nach Integer.

Also: in BASIC V2 nutzt man Integer-Variablen nur dann sinnvoll, wenn man ein großes Feld braucht und mit den eingeschränkten Wertebereich und ohne Nachkommastellen auskommt. Nur dann macht sich eine Speicherersparnis (2 Byte ggü. 5 Byte) bemerkbar. Integer-Einzelvariablen belegen (incl. 2 Byte für den Namen) ansonsten genauso 7 Byte in der Variablenliste wie Float-Einzelvariablen: drei Bytes sind dann 0-Füllbytes, der Interpreter springt in der Liste immer zur nächsten Einzelvariable, indem er 7 zur Adresse addiert.

Was machen BASIC V3.5 (C16 / Plus 4) und BASIC V7 (C128) in jener Situation, d.h. bei Integer-Variablen?

BASIC 3.5 und 7.0 machen das nicht besser.

Das liegt aber auch daran, wie der Interpreter arbeitet: er kann prinzipiell den Ausdruck nur von links nach rechts abarbeiten. Im genannten Beispiel kann der Interpreter nicht wissen, daß hinter T% ein AND-Operator steht - darum liegt der Wert von T% erstmal nach der ersten Umwandlung als Float im FAC#1.

AND wandelt diesen dann am Anfang wieder nach Int. Im weiteren Verlauf wird die rechte Seite von AND ausgewertet. Dabei geht AND auch wieder davon aus, daß dieser Wert als Float angeliefert wird und wandelt diesen darum wieder nach Integer um. Spielt keine Rolle, daß der Wert vorher dadurch erzeugt wurde, indem der Wert aus U% nach Float gewandelt wurde.

Damit das Ergebnis von AND nachher dann im üblichen Umfeld von numerischen Ausdrücken verwendet werden kann, wird das Ergebnis wiederum am Ende der AND-Routine nach Float gewandelt. Zuguterletzt geht die Zuweisung an S% eben davon aus, daß der numerische Wert als Float angeliefert wird - und wandelt darum Float nach Integer.

Die Integer-Routinen in 3.5 sind übrigens leicht verbugt: im Gegensatz zu V2 und V7 akzeptieren einerseits Variablen bei der Zuweisung auch Werte außerhalb des Bereichs -32768..32767 (und reduzieren den Wert durch mehrfache Addition oder Subtraktion von 65536 in diesen Bereich) - was mögliche Programmfehler aber nur maskiert, andererseits wird der (zulässige!) Wert -32768 bei logischen Verknüpfungen mit einer Fehlermeldung abgewiesen.

Verstehe.
Es hätte trotzdem sein können, dass Integer-Arithmetik implementiert wäre und die Umwandlung folglich nur dann erfolgt, wenn sie unvermeidbar ist (Division, Trigonomerische Funktionen etc.)).

Ich entnehme aber deiner Antwort, dass das nicht der Fall ist.

Ich bin geradezu schockiert. Das hat doch sicher Bill Gates höchstpersönlich verbuggt. Da bin ich ja froh, dass er an Windows nicht selbst mitentwickelt hat...

Zitat von markusC64

Es hätte trotzdem sein können, dass Integer-Arithmetik implementiert wäre [...]

Der BASIC-Interpreter ist auf möglichst geringe Codegröße bei einigermaßen passabler Ausführungsgeschwindigkeit optimiert. Dann hat man keinen Platz für Extrawürste im Code um allzu seltene Fälle zu optimieren.

Grundsätzlich kommen die Arithmetik-Routinen dennoch ganz gut weg. In der Multiplikations-Routine ist z.B. eine Optimierung drin, wodurch bei Null-Bytes in der Mantisse eines Faktors das Zwischenergebnis nicht bitweise sondern gleich byteweise verschoben wird. Gerade kleine ganzzahlige Werte profitieren bei einer Multiplikation dadurch schon erheblich.

Leider ist aber auch diese Optimierung verbuggt: liegt bereits ein nicht-0 Zwischenergebnis bei der Multiplikation vor, und kommen dann zwei 0-Bytes in der Mantisse des Faktors hintereinander vor, so wird das Zwischenergebnis beim zweiten Mal nicht nur um ein Byte, sondern extra nochmal um ein Bit verschoben - womit das Ergebnis ab da falsch ist!

Als Beispiel: der Wert 16777217 kann im Fließkommaformat von BASIC V2 exakt dargestellt und gespeichert werden. Ohne irgendwelche Rundungsfehler. Dies gilt ebenso für den Wert 167772170 (sind beide kleiner als 2^31).

Nun probier mal folgendes aus:

Hint: es kommen zwei verschiedene Werte raus. Einer davon ist falsch (und nicht nur "ungenau"). Und bei dem falschen Wert passiert genau das, was ich oben beschrieben hab.

Zitat von Mike

Der BASIC-Interpreter ist auf möglichst geringe Codegröße bei einigermaßen passabler Ausführungsgeschwindigkeit optimiert. Dann hat man keinen Platz für Extrawürste im Code um allzu seltene Fälle zu optimieren.

Es war historisch umgekehrt der Fall, dass bei der chronischen ROM-Platzknappheit, die ersten Basic-Interpreter überhaupt nur Integer konnten (um sich die Float-Routinen zu sparen). Die ersten Interpreter aus Gates' Hand (für 8080 etc.) war noch so. Der ging sich damit auch in 4 KByte aus. Apple hat ja zu Beginn auch nur ein Integer-Basic z.B. beim Apple II.

Zitat von Mike

Das liegt aber auch daran, wie der Interpreter arbeitet: er kann prinzipiell den Ausdruck nur von links nach rechts abarbeiten. Im genannten Beispiel kann der Interpreter nicht wissen, daß hinter T% ein AND-Operator steht - darum liegt der Wert von T% erstmal nach der ersten Umwandlung als Float im FAC#1.

Prinzipiell wäre (abgesehen vom konkreten Beispiel auf das Bezug genommen wurde) in Theorie (ich phantasiere jetzt bisschen vor mich hin) schon ein Mischbetrieb möglich (das hat m.E. nichts mit der Ausdruckauswertung an sich oder deren Richtung zu tun), nur der Interpreter müsste mit einem weiteren Typ, nämlich Integer, erweitert werden (zusätzlich zum Zahl (=Float) und Zeichenkette). Nur das bläht die Formelauswertung und alle beteiligten Routinen (des Variablen-Handling) weiter aus. Dann hätten auch die Single-Integer-Variablen (nicht Array), auch mit wirklich nur 2 Byte Verbrauch, statt wie jetzt mit 5 (wo 3 Bytes brach liegen). Das verkompliziert die Variablensuchrouting usw.
Ein implizites Type-Casting für einen Integer-Ausdruck (z.B. bei einer Zuweisung zu einer Integer-Variable), wo alles mit Integer-Arithmetik gerechnet wird und Float-Variablen nebenbei in "Integer" umgewandelt" werden, ist schon denkbar. So selten wäre der Einsatz nicht. Viele Programme hätten bewusst davon profitieren können.
Kompliziert wäre auch, solche echten Integer-Variablen in FOR-NEXT-Schleifen einsetzen zu können. Der Stack-Eintrag müsste das berücksichtigen (könnte auch kleiner sein) und es müsste der Typ vermerkt sein (oder ein weitere Stack-Frame-Typ zu den bisherigen 2 für GOSUB-RETURN und dem Fload-FOR-NEXT), wie die Daten dort vermerkt sind, damit sich eine NEXT darauf einstellen kann. Schließlich muss FOR-NEXT sowieso faktisch parallel als Integer-Variante noch mal implementiert werden.
Das alles bräuchte seinen Platz im ROM ...
BASIC V2 brauchte schon so rund 9 KByte. Also ohne grundsätzlich anderes ROM-Konzept wäre es nicht gegangen. Ich glaub, diese schiene gibt es bei (anderen) MS-basierten Interpretern auch gar nicht. Das wäre ja so Neuland für die CBM-Leute gewesen, dass ohne ausreichend Zeit - die wohl nicht da war - das nicht so schnell hinzubekommen ist, mit dem Entwickeln und Testen und Ausmerzen von Bugs bis zu einer stabilen Version. Da blieb man wohl lieber beim Spatz in der Hand, als einer Taube am Dach.

Zitat von JeeK

Es war historisch umgekehrt der Fall, dass bei der chronischen ROM-Platzknappheit, die ersten Basic-Interpreter überhaupt nur Integer konnten (um sich die Float-Routinen zu sparen).

Du sprichst da jetzt von den diversen Tiny-BASIC Varianten, die teilweise auch nur 2K groß waren. Richtig ernst nehmen konnte man die nicht wirklich. BASIC war immer schon als Sprache gedacht, in der man richtig rechnen konnte, mit Fließkommazahlen. Und da der Wertebereich der Fließkommazahlen (egal ob mit 24- oder 32-Bit-Mantisse) auf jeden Fall eine Obermenge der 16-Bit Integer darstellt, war es sicher vernünftig einfach für *alle* Berechnungen erstmal Fließkommaroutinen herzunehmen. Für die Ablage in 2 Byte (und die Berechnungen von AND, OR, NOT) brauchten so nur die Konversions-Routinen Float <-> Int ergänzt werden.

Zitat

Ein implizites Type-Casting für einen Integer-Ausdruck (z.B. bei einer Zuweisung zu einer Integer-Variable), wo alles mit Integer-Arithmetik gerechnet wird und Float-Variablen nebenbei in "Integer" umgewandelt" werden, ist schon denkbar.

Das kann aber auch zu unerwarteten Ergebnissen führen, wenn ein Ausdruck mit Integer-Zahlen daher kommt, aber vom Programmierer eigentlich ein Fließkommaergebnis erwartet wird: wenn PRINT 1/2 auf einmal 0 statt 0.5 ausdruckt, ist das Stirnrunzeln garantiert.

Klar kann man solche Situationen mit einer speziellen Markierung von Zahlkonstanten vermeiden, oder Float-Konstanten durch anhängen von "." oder gar ".0" explizit als solche kennzeichnen - aber das braucht alles Platz. Der beim V2 Interpreter sicherlich besser genutzt wurde, um eben neben der Arithmetik mit Grundrechenarten auch noch den Potenz-Operator, SQR(), LOG(), EXP() und die trigonometrischen Funktionen einzubauen.

Naja, warum gleich so extrem: Divison sowie exp, log, sqrt, trig. Funktionen etc. immer automatisch nach Fließkomma umwandeln und der Rest wenn es geht Integer ginge auch.

Aber wie wir wissen, hat man sich dagegen entschieden. Dabei wäre es schon gut gewesen, wenn man bestimmte Berechnungen rundungsfehlerfrei machen könnte.

Welche Art von Berechnungen meinst Du damit?

Solange man bei Addition, Subtraktion und Multiplikation mit kleinen Zahlen ohne Nachkommastellen rechnet, lassen sich die Ergebnisse auch in Fließkommaarithmetik exakt darstellen (wenn man mal von dem oben von mir bereits erwähnten Bug absieht - eine "Quality of Implementation"-Geschichte).

Bei der Division hängt es dann davon ab, ob man im Zusammenhang mit der INT() Funktion ein sauberes nach unten abgerundetes Ergebnis bekommt, so daß bei *richtiger* Rechnung auch ein ganzzahliger Rest rauskommt. Sind N und D Zahlen ohne Nachkommastellen, so ist auf jeden Fall diese Variante: Q=INT(N/D):R=N-Q*D der Variante: F=N/D:Q=INT(F):R=(F-Q)*D vorzuziehen.

(Einfach ausprobieren: z.B. schon bei N=355 und D=113 steht in der zweiten Variante in R ein nicht ganzzahliges Ergebnis! Dabei ist es auch völlig egal, ob die Kiste in Binär- oder BCD-Arithmetik rechnet!)

Soll heißen: wenn kein Defekt vorliegt, lassen sich alle Rechnungen mit ganzen Zahlen natürlich auch sauber mit Fließkomma-Routinen nachbilden. Mit den genaueren Details beschäftigt sich gegebenenfalls die numerische Mathematik.

Noch eine Sache: ich hab' die Erfahrung gemacht, daß man die meisten Routinen etwa um den Faktor 3 beschleunigt bekommt, wenn man an Stelle von weitgehend optimierten Routinen in BASIC (incl. "vorsortierter" Variablen, etc.) in Maschinensprache die Arithmetik-Routinen direkt ansteuert.

Damit machen die eigentlichen Berechnungen im BASIC-Interpreter also nur ca. 1/3 der Laufzeit aus, den Rest ist der Interpreter mit Verwaltungsaufgaben (Zeichen parsen, Operator-Vorrang bestimmen, Variablen suchen, etc.) beschäftigt! Selbst wenn im Idealfall die Integer-Routinen ihre Arbeit instantan erledigen würden, würde dies die Laufzeit nur um 33% verringern.

Möglicherweise käme noch nicht einmal dieser Geschwindigkeitsvorteil heraus: da der Interpreter zusätzlich zu Floats und Strings in Ausdrücken auch noch in Integer rechnen können muß, erhöht sich der Verwaltungsaufwand. Schlimmstensfalls um genau die 50% mit denen dann Integer-Rechnungen dann nur noch genauso schnell sind wie Floats vorher, und Floats noch langsamer.

Wie gesagt, das bezieht sich jetzt nur auf einen ggfs. geänderten Interpreter. Die verfügbaren Compiler zeigen ja, daß für Integer-Berechnungen optimierte Routinen funktionieren. Aber hier kommt dann auch zum Tragen, daß die Compiler, genau wie handgeschriebener Code, den "normalen" Verwaltungsaufwand des Interpreters draußen lassen, weil eben Zahlkonstanten nur einmal ausgerechnet werden, das Parsen zur Laufzeit entfällt, die Auswertungsbäume für Ausdrücke eben nur beim kompilieren einmal ermittelt werden müssen und dann festliegen und die Adressen von Variablen hart einkodiert werden können. Damit fällt ein Großteil des o.g. 2/3 Overheads weg, und der Geschwindigkeitsvorteil von Integer-Rechenroutinen kann voll zum Tragen kommen.