Hello, Guest the thread was viewed22k times and contains 140 replies

last post from TD1334 at the

BASIC-Code beschleunigen/optimieren

    Hallo Leute,


    irgendwie spuckt die Suchfunktion kein Ergebnis zu meiner Frage aus.


    Inwieweit kann man einen BASIC-Code beschleunigen?


    Dazu habe ich ein paar Sachen gefunden:
    - Unterprogramme an den Programmanfang stellen.
    - Variablen sofort als Fließkomma-Variable anlegen, damit die Umwandlung von Int nach Fließkomma entfällt.
    - Anstelle einer NULL lieber den Dezimalpunkt nehmen. z.B. bei if a=0 then lieber if a=. then nutzen.
    - For-Schleifen sind Schleifen mit IF zu bevorzugen.
    - Anstelle von Zahlen beispielsweise in Berechnungen lieber Variablen nutzen. Diese müssen nicht erst von Text nach Int und dann nach Fließkomma umgewandelt werden.



    Kennt ihr noch weitere Optimierungsmöglichkeiten?


    Wie war das bei der Multiplikation mit der Reihenfolge der Werte? Den größeren mal den kleineren Wert oder umgekehrt?
    Bringt es einen Geschwindigkeitszuwachs, wenn man anstelle von if a$="a" then gosub 1000 die Form "if a$="a" gosub 1000" benutzt?



    Liebe Grüße!
    ThomBraxton

    Quote from ThomBraxton


    - Variablen sofort als Fließkomma-Variable anlegen, damit die Umwandlung von Int nach Fließkomma entfällt.- Anstelle einer NULL lieber den Dezimalpunkt nehmen. z.B. bei if a=0 then lieber if a=. then nutzen.
    - For-Schleifen sind Schleifen mit IF zu bevorzugen.
    - Anstelle von Zahlen beispielsweise in Berechnungen lieber Variablen nutzen. Diese müssen nicht erst von Text nach Int und dann nach Fließkomma umgewandelt werden.

    • Generell alle Schleifen durch FOR-NEXT ersetzen (egal ob endlos oder mit Bedingung).
    • "Variable als Fließkomma-Variable anlegen" würde ich eher als Variablen des Typs "Integer" vermeiden, es sei denn man benötigt ein Array, wo aus Platzgründen ein Wert mit "nur" 2 Bytes gegenüber 5 Bytes bei Fließkomma ausschlaggebend sind.
    • "Anstelle von Zahlen ..." gilt nur bedingt: Einstellige Zahlen als Konstanten belassen - speziell wenn es viele Variablen gibt (und diese ja nur linear durchsucht werden) - da diese in der Regel schneller in Fließkommadarstellung umgerechnet, als in der Var.-Tabelle gefunden werden können.
    • Alle Überflüssige Zeichen weglassen (Mehrfachdoppelpunkte, Leerzeichen, Variablennamen länger als 2 Zeichen, häufig genutzte Variablen nur mit einem Zeichen).
    • Variablen (auch simple, nicht nur Arrays) mittels DIM in gezielter Reihenfolge anlegen (nicht durch die erste Verwendung mehr oder weniger "zufällig")
    • Maximale Zeilenlänge ausnützen.
    • Allgemeine Optimierung in Bezug auf Schleifen (nicht von der Schleife abhängigen Berechnungen herausziehen).
    • Arithmetische Optimierungen jeglicher Art (z.B. A*A statt A^2)
    • Vorberechnungen in Tabellen (z.B. Bitwerte statt Exponentialberechnungen)
    • Stringvariablen mit String-Konstanten nicht neu zuweisen (Platzverschwendung).
    • String-Variablenanzahl gering halten (speziell String-Array-Größe), wenn viele String-Manipulationen passieren oder der freie Speicher knapp zu werden droht (Dauer der Garbage-Collection).
    • Ungenutzte nicht mehr benötigte Stringvariablen explizit einen Leer-String zuweisen (Häufigkeit der Garbage-Collection).
    Quote from ThomBraxton


    Bringt es einen Geschwindigkeitszuwachs, wenn man anstelle von if a$="a" then gosub 1000 die Form "if a$="a" gosub 1000" benutzt?

    Diesen Fall kann es nicht geben, weil nicht erlaubt. Statt THEN ist nur GOTO erlaubt. Soweit ich mich erinnere (an meine Messungen), sind IF ... GOTO ... und IF ... THEN ... gleich schnell.

    Tach,


    kennt jemand ein paar "Messwerte" für besonders zeitzährende Basic-Befehle?


    Ist GOSUB x ... RETURN vom Zeitaufwand evtl. besser als GOTO X .... GOTO (BACK) ?
    Wenn bei FOR...NEXT das Rücksprungziel direkt am BASIC-Stapel vermerkt ist (c64 wiki), wie sieht es dann bei GOSUB aus?


    Oder wenn ich in einer FOR...NEXT Schleife mit GOTO springe, bringt der Rücksprung durch direktes NEXT dann Zeitersparnis?


    Ciao

    Quote from Chagizzz

    Ist GOSUB x ... RETURN vom Zeitaufwand evtl. besser als GOTO X .... GOTO (BACK) ?

    Ja, ist es. RETURN holt die Rücksprungadresse vom Stapel und benutzt sie, GOTO muss erst die Zeile suchen.
    Außerdem hat GOSUB/RETURN natürlich noch den Vorteil, dass das Unterprogramm von mehreren unterschiedlichen Stellen aus angesprungen werden kann und immer an die richtige Stelle zurückgesprungen wird (was der eigentliche Grund für die Existenz dieser Anweisungen ist).

    Quote from Chagizzz

    Oder wenn ich in einer FOR...NEXT Schleife mit GOTO springe, bringt der Rücksprung durch direktes NEXT dann Zeitersparnis?

    Ja, aus dem gleichen Grund. Auch NEXT holt die Rücksprungadresse vom Stack und muss nicht erst die Zeile suchen. Übersichtlicher wird das Programm durch solche Zusatz-NEXTs aber nicht - wenn man sowas braucht, sollte man evtl. die Programmiersprache wechseln.

    Also sind meine denkweisen nicht so verkehrt.


    Habe für mich die Feststellung gemacht, dass man nicht allgemein sagen kann, ob mehrere Befehle in einer Zeile schneller oder langsamer sind.


    Was mir gar nicht klar wird...


    Ich habe 5 verschieden arbeitende Varianten einer Stringumwandlung zu Testzwecken programmiert.
    Diese rufe ich mit ON X GOSUB hintereinander ab.
    Da 1 und 4 deutlich schneller als 2 und 3 sind, habe ich 2,3 übersprungen und nach 4 beendet.


    Das Überspringen von 2 und 3 verlangsamt Nr. 4 deutlich (ca. 21 sek statt 14 sek).
    Das Beenden mit END nach 4 verlangsamt ebenfalls etwas.


    In den übersprungenen Varianten gibt es eine Schleife, die Zeichen für Zeichen durchläuft und mit vielen IF Abfragen einen neuen String erstellt.
    Da gibt es nichts, was für die Variante 4 von Vorteil wäre oder weiter genutzt würde.


    Kann es sein, dass dadurch die anschließende Verwendung von Variablen irgendwie in eine günstigere Speicheradresse gelangt oder der Code der Variante 4 einfach besser verarbeitet wird durch Interpretation / Speicheradresse auf die ich keinen direkten Einfluss habe?

    Naja, das ganze läuft eher unter dem Motto "Was kann ich aus einfachem c64 Basic rausholen?". Eine andere Programmiersprache ist sicher irgendwann mal eine Alternative. Irgendwie hänge ich aber an diesem nostalgischen Basic. :thumbup:


    Ich könnte allerdings tatsächlich mal zwei drei verschiedene Versionen erstellen und compilieren um zu prüfen, ob die Unterschiede dort ähnlich gravierend sind - abgesehen von der zu erwartenden deutlichen Steigerung zur unkompilierten Version.

    Quote from Chagizzz

    Ich habe 5 verschieden arbeitende Varianten einer Stringumwandlung zu Testzwecken programmiert.
    Diese rufe ich mit ON X GOSUB hintereinander ab.
    Da 1 und 4 deutlich schneller als 2 und 3 sind, habe ich 2,3 übersprungen und nach 4 beendet.


    Das Überspringen von 2 und 3 verlangsamt Nr. 4 deutlich (ca. 21 sek statt 14 sek).

    Je nachdem, was du da in der GOSUB-Routine machst, kann sein, dass da die Garbage Collection zugeschlagen hat. Zuvor passierte das dann evtl. schon in 2 oder 3 und hat sich nun in die 4 verlagert.

    Also, diese ganze "Optimiererei" an Einzelbefehlen ist doch völlig für die Katz, wenn man sich den falschen Algorithmus augesucht hat.


    Außerdem arbeitet der C64 per se schon mal das Programm 10% langsamer ab, wenn man beim Ablauf z.B. versehentlich mit dem dicken Finger auf der RETURN-Taste hängenbleibt... die Tastaturabfrage im Interrupt nimmt bei nur einer gedrückten Taste wesentlich mehr Zeit in Anspruch.


    Also - wenn man ohnehin schon die Programme mit angezogener Handbremse laufen läßt, spielt's keine große Rolle ob die Handbremse etwas fester oder weniger fester angezogen ist. ^^


    Quote from Chagizzz

    Ich habe 5 verschieden arbeitende Varianten einer Stringumwandlung zu Testzwecken programmiert. [...]

    Setz' den Code mal hier rein, sag' was er genau tun soll, und dann sehen wir weiter - geht mit Sicherheit auch noch eine weitere Variante.

    Das ist schon sehr vage, wie das Rahmenprogramm für den Test aussieht. Bitte den Code hier einstellen! Wie etwa das mit "2,3 überspringen" konkret aussieht.
    Jedenfalls sehe ich da schon eine prinzipielle Abstufung schon alleine dadurch, wie weit die jeweilige Variante von der Zeile mit dem ON...GOSUB (oder vom Programmanfang, wenn zurückgesprungen wird) entfernt ist. Egal, ob davor oder dahinter, sie liegen sicher nicht an der gleichen stelle und damit ist zumindest das "Hinspringen" gewissermaßen abhängig von der Entfernung (in Zeilen).


    Wenn man einen Code-Teil überspringt, dann kann das freilich einen Einfluss auf andere Teile haben. Z.B. könnten im übersprungenen Teil Variablen erstmalig in Verwendung geraten und damit die Variablenanzahl (und damit die Liste der zu durchsuchenden Variablen) für den nachfolgenden Code länger machen. D.h. später definierte Variablen brauchen für jeden Zugriff entsprechend länger.
    In solchen Fällen zahlt sich der Wiederverwendung von Variablen und deren kontrollierte Erzeugung (mittels DIM, gilt auch für einfache Variablen) schon aus. Natürlich müsste man das Programm hinsichtlich der Variablennutzung "profilen", um herauszubekommen, welche Variablen früher und welche später zu definieren sind. Mit etwas Gefühl und Übung geht das Näherungsweise freilich auch so.


    Der Einfluss der Garbage-Collection ist vielleicht eher geringfügig. Relevant wäre es nur, wenn es wirklich viele Stringvariablen bzw. große Arrays gäbe und/oder der freie Speicherplatz im Verhältnis zu den erzeugten Stringdaten klein ist (da nützt dann ein präventives FRE(0) nicht mehr viel). Beides kann ich mir jetzt bei einem Testprogramm (dem obigen nach) nicht so vorstellen. Aber wie gesagt: Listing her, dann sehen wir weiter. :D

    ...also jede kleine Änderung führt zu neuen Ergebnissen.
    Jetzt habe ich kaum einen Unterschied, nachdem ich print fre(0) jedes Mal ausführe.


    Anmerkung: Es geht nicht um die Optimierung der Zeilennummern usw.


    Zeiten bei mir: ca. 12,3 Sekunden für die DIM-Variante (1) und ca. 14,3 Sekunden für die MIDSTRING - Variante (4)


    Änderung folgender Zeilen:
    Nach Änderung der Zeile 8 (Wegfall von GOTO 40) und Zeile 11 (Wegfall von END) erhielt ich nun ein fast identisches Ergebnis.


    Also

    Code
    1. 912 PRINT"fre(0):";FRE(0)

    wieder gelöscht. Nun erhalte ich 19,3 Sekunden für die DIM Variante (deutlich länger) und 14,2 Sekunden für die MIDSTRING-Variante.


    GOTO 40 und END wieder eingefügt, DIM-Variante: 19,3 sek. und MIDSTRING Variante 20,6 sekunden (!!!)


    Compilierte Version:
    (komplettes Listing): DIM: 4,7 sek, MIDSTRING: 5,3 sek
    (ohne goto40/end) : DIM: identisch
    DIM und MIDSTRING ohne Zeile 912: DIM: 11,8 sek, MIDSTRING: 11,8 sek
    (ohne goto40/end) : DIM 12,3 sek, MIDSTRING: 11,8 sek


    Also PRINT FRE(0) bringt auf jeden Fall was... wenn man denn mal außer acht lässt, dass printfre(0) möglicherweise auch wieder etwas Zeit braucht.

    Ja ok, da wird natürlich viel Stringmüll produziert. Schon alleine der Aufbau von AB$ ab Zeile 1000 füllt den Speicher mit 32680 Bytes. Jetzt fehlt dann nicht mehr viel, bis der verbleibende frei Speicher (abzüglich Array Programm, Variablen), wird es dann schnell eng. Wenn nach der Initialisierung kein FRE(0), frisst irgend eine der Testverianten die sogenannte Krot und bei der kommt dann die implizite Garbage-Collection zum Tragen. Das ist dann bisserl Roulette, bei welchem der Tests dann die GC zuschlägt.
    Jeder Testlauf produziert seinerseits wieder 15 KByte Müll (39*40/2 * 20). Daher ist vor jedem Test ein FRE(0) ist unbedingt notwendig - sonst kommt die GC irgendwann. im Schnitt nach 2,5 Tests (geschätzt - exklusive Initialisierung).
    Wenn das der Fall ist, dann spielt nur noch die mehr oder weniger verschwenderische Codierung in den Testvarianten eine Rolle.
    Und da ist da sorgt schon alleine ON...GOSUB für eine nicht faire Verzerrung. Das geht in BASIC in einem Programm nicht wirklich schön. Das GOSUB-Zeug weg und die J-Schleife in jede Variante hineinziehen. Auch wenn es nur 20 Aufrufe sind ... es wirkte sich dennoch aus und die Werte bleiben wirklich vergleichbar. Die Varianten sollten dann auch wirklich alle gleich aufgebaut sein, von der Struktur her (Zeilenaufteilung, Leerzeichen etc.).

    Klingt soweit plausibel. Da die J-Schleife bei jeder Variante gleich ist, kann ich das jetzt erst mal vernachlässigen. ON x GOSUB ist ja nur für die ohnehin nicht gleichzeitig in einem Programm benötigten Varianten. So ist das zwar unnötig verstrickt, aber jedes mal gleich.


    Also FRE(0) definitiv nach solchen Initialisierungen.


    Meinst Du ON... GOSUB als zährend im Allgemeinen oder nur so wie hier verwendet?


    Wie ich diese unterschiedlichen Varianten gleich aufbauen soll, leuchtet mir allerdings nicht so ganz ein. Auf die Unterschiede kommt es ja gerade an. Alle machen das gleiche - nur auf andere Art.
    Die DIM Variante favorisiere ich, da hier die Möglichkeit besteht einem Zeichen auch mehrere Zeichen zuzuweisen. Wenn ich jetzt richtig rechne würde sie in der hier genutzten Variante (1 Zeichen)
    2+1+256*2+4*256 = 1536 Byte belegen. Haut das hin?

    Lag' ich wohl nicht ganz verkehrt mit der GC.


    Ich frag' mich aber, wozu du die Zeichen wieder in einen gemeinsamen String zwängen willst (und somit wieder per MID$ rausholen musst), wenn du sie schon einzeln in AA$(I) vorliegen hast :gruebel ?


    Wenn nötig, warum nicht einfach (größtenteils) händisch zusammenbasteln (hier nur die Codes bis 122):



    Code
    1. 5 for i=1 to 31 : ch$(1)=ch$(1)+chr$(i) : next : rem 1-31 nach 1-31
    2. 10 ch$(2)="!"+chr$(34)+"#$%&'()*+,-./01234567890:;<=>?@" : rem 32-64 nach 32-64
    3. 20 ch$(3)="ABCDEFGHIJKLMNOPQRSTUVWXYZ" : rem 97-122 nach 65-90
    4. 30 ch$(4)="[\]^_." : rem 91-96 nach 91-96
    5. 40 ch$(5)="abcdefghijklmnopqrstuvwxyz" : rem 65-90 nach 97-122
    6. 50 ch$=ch$(1)+ch$(2)+ch$(3)+ch$(4)+ch$(5)

    Speicherbedarf so nur ca. 936 Bytes.

    Um die Art der Erzeugung von AA$(x) bzw. AB$ geht es ja hier nicht. Das liegt außerhalb der Zeitmessungen.


    Natürlich brauche ich entweder AA$(x) ODER AB$.
    Das ganze sollte eher ein Test sein, wie in reinem Basic am effektivsten die Zeichenkette umgewandelt werden kann. Ob jetzt wie hier oder z.B. alles nach Gross- oder Kleinbuchstaben.


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


    Ab 8400 sind noch die Reste eines Versuchs zu erkennen die Zeichen ab 128 getrennt von den anderen zu behandeln (wenn auch hier das gleiche passiert). Änderung in

    Code
    1. 8400 FOR I = 1 TO LE
    2. 8401 (entfällt)
    3. 8403 A1=ASC(MID$(P$,I,1))
    4. 8405 IFA1<128 THEN A2$=A2$+MID$(AB$,A1,1):NEXT:RETURN

    verlangsamt das ganze wieder auf ca. 150% Dauer. Zumindest in uncompiliertem Basic. Bei Nicht-Verwendung von A1 sondern analoger Direktverwendung zuu 8410 wird es noch langsamer.


    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. ;)

    Quote from Chagizzz

    Klingt soweit plausibel. Da die J-Schleife bei jeder Variante gleich ist, kann ich das jetzt erst mal vernachlässigen. ON x GOSUB ist ja nur für die ohnehin nicht gleichzeitig in einem Programm benötigten Varianten. So ist das zwar unnötig verstrickt, aber jedes mal gleich.

    Die Schleife schon, aber die Zeilensuche bei GOSUB (das Parsing der Zeilennummern vernachlässigen wir mal, da sind die hinteren Varianten auch "schlechter" dran) muss die Zeile suchen und das dauert länger, je weiter hinten die die Variante im Programm steht. Und das halt mal 20. Wirkt sich nicht extrem aus, aber wenn man jetzt eine seriöse Zeittabelle der Varianten macht, dann verzerrt das


    Quote from Chagizzz

    Also FRE(0) definitiv nach solchen Initialisierungen.

    Besser vor jeder Testvariante. Weil ja jede davon ca. 15 KByte Stringmüll produziert und sonst nach 2,5-Testläufen wieder eine GC gemacht werden muss.
    Mach man dies nicht, kommt erst die Initialisierung (32 KByte), dann braucht es den ersten halben Test bis der freie Speicher aufgebraucht ist (1. Test "langsam"), dann gehen sich vielleicht noch 2 Tests ohne GC aus (7 von vorher, +30 KByte die Tests), der 4. erwischt dann möglicherweise wieder die GC (vielleicht schon beim 3.).


    Quote from Chagizzz

    Meinst Du ON... GOSUB als zährend im Allgemeinen oder nur so wie hier verwendet?

    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.


    Quote from Chagizzz

    Wie ich diese unterschiedlichen Varianten gleich aufbauen soll, leuchtet mir allerdings nicht so ganz ein. Auf die Unterschiede kommt es ja gerade an. Alle machen das gleiche - nur auf andere Art.
    Die DIM Variante favorisiere ich, da hier die Möglichkeit besteht einem Zeichen auch mehrere Zeichen zuzuweisen. Wenn ich jetzt richtig rechne würde sie in der hier genutzten Variante (1 Zeichen)
    2+1+256*2+4*256 = 1536 Byte belegen. Haut das hin?

    Diese Unterschiede, die aus dem Verfahren selbst entstehen meine ich nicht. Das Drumherum ist gemeint.
    Beim FOR I = 1 TO LE sollte es bei allen Varianten mit ":" in der gleichen Zeile weitergehen und nicht mal so und dann wieder anders. Konsequent sollten also Zeilenwechsel vielleicht nur dort gemacht werden, wo sie sich nicht vermeiden lassen (nach einem IF-Zweig etwa), alle Füllzeichen (Leerzeichen, REMs) weg.
    Außerdem müssen alle Variablen die in den Varianten vorkommen schon vorher definiert sein! Z.B. zu Beginn mit
    DIM A1
    Wenn nicht, wir die Variable bei der ersten Nutzung angelegt (z.B. in der 2. Variante). Eigentlich nicht wirklich schlimm, außer, wenn Arrays definiert sind, die *hinter* den Variablen liegen mit mit jeder neuen Variable verschoben werden müssen. Also hier immerhin 256*3 Bytes (256 Stringdescriptoren = Array-Elemente). Auch etwas, was das Ergebnis im Sinne der Vergleichbarkeit verzerrt.


    Ja, der DIM-Variante hätte ich der Erfahrung nach auch die besten Chancen gegeben. :D


    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)!).