Optimierungsgrad KERNAL /BASIC - fiktiver Talk

Es gibt 337 Antworten in diesem Thema, welches 62.643 mal aufgerufen wurde. Der letzte Beitrag (16. September 2017 um 00:34) ist von Boulderdash64.

  • Kann es sein, dass beim Übergang von 32-Bit-Real-Speicherformat mit 3 Bytes Mantisse auf 4 Bytes Mantisse (9-digit-Basic) hier etwas schiefgegangen ist bzw. übersehen wurde?
    Scheint ja fast mit Händen greifbar:
    Der Programmierer dachte sich möglicherweise, sind beide übrigen Folgebytes = 0, also das zweite und dritte = letzte (bei deiser Implementierung!) ist in dieser Schleife nichts mehr zu tun und man kann vorzeitig den RTS anspringen. (Optimierung?) Auf dem 8080-Prozessor wäre das vermutlich mit einer einzigen Vergleichs-/Test-Instruktion abzuhandeln gewesen. (16 bit breit)

    Und dann kam aus dem Nichts ein 4. Byte daher für die Mantisse.
    Dann hätte man entweder die letzten 3 Bytes auf Null abprüfen müssen, oder nur die letzten beiden. Aber halt nicht die mittleren beiden ...

    Wie der Fehler zustande kommt, habe ich in dem genannten Thread in Bitte melde dich an, um diesen Link zu sehen. exakt erläutert.

    Die den Fehler auslösende Bedingung, daß zwei Mantissenbytes hintereinander 0 sind, kann auch im 3-Byte-Mantissen-Format vorkommen - nur befindet sich zu diesem Zeitpunkt kein nicht-0 Wert in dem Puffer der die Zwischenergebnisse der Multiplikation aufsammelt. Genausowenig ist es auffällig, wenn die untersten zwei Bytes der 4-Byte-Mantisse oder gar die untersten 3 Bytes Null sind. Das Zwischenergebnis ist in den drei genannten Fällen vor der Ausführung der fehlerhaften Schieberoutine komplett mit Nullen gefüllt und da macht es dann auch nichts aus, wenn (versehentlich) noch ein Bit weiter geschoben wird.

    Kritisch ist eben jener Fall, wo bei einer 4-Byte-Mantisse im untersten Byte ein nicht-0 Wert drin steht, also in der Folge dann ein nicht-0 Wert im Zwischenergebnis da ist. Kommen dann zwei 0-Bytes in der Mantisse des anderen Faktors rein, wird das Zwischenergebnis auch um ein zusätzliches Bit weiter geschoben und ab da ist das Ergebnis falsch.

    ...

    Die obskure Bedingung hatte ja auch bei mir 30 Jahre gebraucht, bis mir die fehlerhafte Multiplikation aufgefallen war. CBM hat den Fehler vor dem Release von BASIC V7 dann auch bemerkt, als "Double-0 Bug" bezeichnet und gefixt - indem die Optimierung auf Nullbytes in der Mantisse gleich ganz deaktiviert wurde und damit die Multiplikation nun generell langsamer ist. :(

    Mein Fix führt hingegen einen Rucksack ein, der einfach die vorgesehene Aktion der Optimierung ausführt (Zwischenergebnis um ein ganzes Byte nach rechts schieben) ohne eine andere Routine wiederzubenutzen, die zwar meistens auch das tut was sie soll - aber eben nicht immer.

  • Ich hoffe das wird nicht allzu OT empfunden, aber ich muss es einfach loswerden, weil es so schön dazu passt:

    Es gibt die Anekdote, dass Donald E. Knuth in jungen Jahren einst für eine Firma (es ging da um irgendwelche technischen Berechnungen) die Float-Algorithmen auf einer neuen Maschine verfasst hat, weil sie die HW gewechselt haben. Dann wollten sie (bzw. er) natürlich testen, ob die neue SW korrekt ist, und haben die Ergebnisse mit den alten Ergebnissen verglichen. Resultat: enorme Abweichungen.

    Knuth hat dann beide Implementierungen analysiert, und ist draufgekommen, dass seine Algorithmen korrekt waren, aber die alten - die sie seit Jahren benutzt hatten - fehlerhaft (wenn ich mich recht erinnere, hat sich an einer Stelle ein Op-Code in die Zahlen verirrt oder so ähnlich). Seine Auftraggeber hat vermutlich ein wenig der Umschlag getroffen, als sie es erfahren haben. :wink:

  • Vielleicht könnte man noch einen Zeiger einführen, der auf den untersten Garbage zeigt? Damit müsste ein Teil des Speichers nicht mehr aufgeräumt werden, wenn die GC zuschlägt.
    Allerdings kommt der Aufwand hinzu, den Zeiger zu führen, und u.U. ist der Nutzen 0.
    Finde ich jetzt schwer abzuschätzen, ob sich das lohnt oder gar ein Verlustgeschäft ist.

  • Dieser Zeiger muß in der Art ohnehin mitgeführt werden, damit die GC überhaupt funktioniert.

    Hauptproblem ist folgendes: in V2 sind die Zeichenketten hinten im Speicher komplett unstrukturiert, nicht nach Adresse sortiert und die ungültigen Strings liegen mit den gültigen wild vermischt.

    Die GC muß nun alle - wirklich *alle* - Stringdeskriptoren abackern, um den String zu finden, der an der größten Adresse abgelegt ist. Der wird nun ans Ende geschoben. Hier merkt sich die GC dann die untere Adresse aller Strings, die bereits aufgeräumt wurden. Damit ist zunächst nur ein String behandelt. Dieses Prozedere wiederholt die GC jetzt N mal - sucht also jeweils den String mit der höchsten Adresse, der noch nicht aufgeräumt wurde, kopiert diesen dann nach oben und führt die untere Adresse der bereits aufgeräumten Strings mit. Daher das O(N²)-Verhalten - irgendwann findet die GC keine Strings zum Aufräumen mehr und ist dann fertig.

    Die Backdescriptoren ab BASIC V4 (bzw. V3.5) vereinfachen das Aufräumen ganz gewaltig: an jedem String hängt ein Zeiger dran, der auf den originalen String-Deskriptor verweist. Wird ein String im Heap invalidiert, so wird der Pointer ersetzt durch $FFxx, wobei xx die originale Stringlänge bezeichnet. Bei der GC wird der Heap nun von hinten aufgerollt. Es gibt zwei Pointer, src und dst, die zunächst auf das Ende des Stringheaps gesetzt werden. Trifft die GC auf einen ungültigen String, so wird *nur* der src-Pointer einfach um dessen Länge+2 erniedrigt, zeigt also auf den nächsten Backdeskriptor. Trifft die GC auf einen gültigen String, so wird von src nach dst kopiert - die Länge erfährt die GC über den Deskriptor auf den der Backdeskriptor weist. Ist der String hochkopiert, so korrigiert die GC noch den Pointer auf den String in dessen Deskriptor. src weist jetzt wieder auf den nächsten Backdescriptor. Auf diese Weise hangelt sich die GC ein einziges Mal durch den Stringheap und ist dann fertig: O(N).

    Tja... mit ein wenig mehr Speichereinsatz so ein überragender Geschwindigkeitsgewinn.

  • Dieser Zeiger muß in der Art ohnehin mitgeführt werden, damit die GC überhaupt funktioniert.

    Hauptproblem ist folgendes: in V2 sind die Zeichenketten hinten im Speicher komplett unstrukturiert, nicht nach Adresse sortiert und die ungültigen Strings liegen mit den gültigen wild vermischt.

    Die GC muß nun alle - wirklich *alle* - Stringdeskriptoren abackern, um den String zu finden, der an der größten Adresse abgelegt ist. Der wird nun ans Ende geschoben. Hier merkt sich die GC dann die untere Adresse aller Strings, die bereits aufgeräumt wurden. Damit ist zunächst nur ein String behandelt. Dieses Prozedere wiederholt die GC jetzt N mal - sucht also jeweils den String mit der höchsten Adresse, der noch nicht aufgeräumt wurde, kopiert diesen dann nach oben und führt die untere Adresse der bereits aufgeräumten Strings mit. Daher das O(N²)-Verhalten - irgendwann findet die GC keine Strings zum Aufräumen mehr und ist dann fertig.

    Schöne Beschreibung. Genau diesen ...der höchsten Adresse, der noch nicht aufgeräumt wurde... meinte ich.
    Die jetzige GC fängt bei 0 an, sie muss davon ausgehen, dass gar nichts aufgeräumt ist.
    Man könnte diesen Zeiger aber auch als Zeiger auf den kleinsten Garbage das ganze Basic-Leben mitführen. Bei jeder Änderung an einem String-Descriptor vergleicht man dessen alte Adresse mit der Adresse des Garbage. Ist sie kleiner, dann wird die gespeichert. Das erspart der GC dann die ersten Durchläufe und erscheint mir vom Aufwand noch akzeptabel.
    Nur: Jedesmal ein paar Takte Aufwand je Speichern eines Strings läppern sich ja auch, und es ist überhaupt nicht garantiert, dass das überhaupt was bringt. Andererseits: unveränderte Strings würden bei der GC im Stapel nach unten rutschen, so dass die folgenden GC wahrscheinlich noch weniger prüfen müssten.

    Die Backdescriptoren ab BASIC V4 (bzw. V3.5) vereinfachen das Aufräumen ganz gewaltig: an jedem String hängt ein Zeiger dran, der auf den originalen String-Deskriptor verweist. Wird ein String im Heap invalidiert, so wird der Pointer ersetzt durch $FFxx, wobei xx die originale Stringlänge bezeichnet. Bei der GC wird der Heap nun von hinten aufgerollt. Es gibt zwei Pointer, src und dst, die zunächst auf das Ende des Stringheaps gesetzt werden. Trifft die GC auf einen ungültigen String, so wird *nur* der src-Pointer einfach um dessen Länge+2 erniedrigt, zeigt also auf den nächsten Backdeskriptor. Trifft die GC auf einen gültigen String, so wird von src nach dst kopiert - die Länge erfährt die GC über den Deskriptor auf den der Backdeskriptor weist. Ist der String hochkopiert, so korrigiert die GC noch den Pointer auf den String in dessen Deskriptor. src weist jetzt wieder auf den nächsten Backdescriptor. Auf diese Weise hangelt sich die GC ein einziges Mal durch den Stringheap und ist dann fertig: O(N).

    Tja... mit ein wenig mehr Speichereinsatz so ein überragender Geschwindigkeitsgewinn.

    Könnte der zusätzliche Speicherverbrauch in V2 ein Problem sein? Immerhin kann man heute ein Array mit ~9000 Strings haben (3 Byte Descriptor, + 1 Zeichen), künftig nur etwa 6000 (3 Byte Descriptor, 1 Zeichen, 2 Byte rückwärts-Zeiger). Ich denke aber nicht, dass das im echten Leben ein Problem wäre.

  • [...] Man könnte diesen Zeiger aber auch als Zeiger auf den kleinsten Garbage das ganze Basic-Leben mitführen. [...]

    Die GC braucht aber tatsächlich die Startadresse des zuletzt aufgeräumten Strings, um beim (erneuten) Scannen aller Stringdeskriptoren diejenigen auszuschließen, die bereits aufgeräumt wurden.

    In der normalen "Arbeitsphase" kann man den tatsächlich dadurch gewinnen, daß man bei der Invalidierung eines Strings dessen Länge addiert (also auf das Byte hinter dem String) und mit dem vorherigen Pointer vergleicht; der größere der beiden ist dann der nächste Wert - initialisiert wird der Pointer wegen mir mit $0800.

    Das ist eine denkbare Optimierung, die aber an der Laufzeitordnung nichts ändert. Schlimmstenfalls faßt der Programmierer vor einer GC eben den String mit der höchsten Adresse an und dann muß alles nach oben geräumt werden.

    In V2 gibt es übrigens tendenziell gar nicht so viele konstante Zeichenketten im Stringheap ...

    Könnte der zusätzliche Speicherverbrauch in V2 ein Problem sein? Immerhin kann man heute ein Array mit ~9000 Strings haben (3 Byte Descriptor, + 1 Zeichen), künftig nur etwa 6000 (3 Byte Descriptor, 1 Zeichen, 2 Byte rückwärts-Zeiger). Ich denke aber nicht, dass das im echten Leben ein Problem wäre.

    ... da die dadurch gespeichert werden, daß der String-Deskriptor in das BASIC-Programm weist! Das klappt sogar bei Arrays, und noch besser, selbst bei READ Anweisungen auf Zeichenketten in DATA-Zeilen! 8\|

    Die Verwendung von Backdescriptoren "beißt" sich aber mit dieser Optimierung (bzw. erfordert Fallunterscheidungen für Strings mit und ohne Backdescriptor), weswegen das bei BASICs mit schneller GC nicht mehr drin ist.

    Und richtig: ob man jetzt 9000 oder 6000 Strings im BASIC-RAM untergebracht bekommt, ist nur bei GC-Tests von Belang. ;)


    Edit: ich hab' gerade noch mal nachgeschaut. V2 fängt bei der GC definitiv immer ganz hinten an (siehe: $B526)

  • Wäre es eine Alternative, die Strings wie Blöcke auf einer Festplatte zu verwalten? In freiwerdende Lücken "Files" = Neu-Strings hineinverteilen ..

    Also nach dem Motto, lieber etwas Verschnitt und ziemlich viel Fragmentierung (wie Mike weiter oben schrieb: Alt und neu kunterbunt durcheinander) - Fragmentierung macht im RAM-Speicher nicht soviel aus wie auf Platte - als Regelmässige Kopier-Orgien, die einem ziemlich unproduktiv vorkommen und das Zeitverhalten ruckartig machen (was für den Anwender ja gefühlt sehr unangenehm ist, auch wenn er sonst von einer relativ flotten Stringbenutzung profitiert).

    Nachtrag: Jemand (Bif? schrieb weiter oben im Thread?), man könnte kurze Strings bis ca. 3..4 Zeichen (entspräche Char) in die Deskriptorvariable selbst hineinpacken. Mir gefällt das recht gut; im größeren Maßstab macht es Windows im NT-Dateisystem auch so. (Dateien unter 2048 Bytes in den Belegungsblock selbst hineinwurschteln; belegen dann keinen - weiteren - Platz.)

  • Das blöde bei der V2 GC ist einfach, daß sie aus dem puren *Inhalt* des Stringheaps keine Information herausziehen kann, wo die Lücken sind. Das erledigen die Backdescriptoren der schnellen GC (ab V3.5/V4) - praktisch eine verlinkte Liste, die von hinten gelesen wird.

    Ich wüßte jetzt nicht, was eine vorsätzliche Fragmentierung hier für einen Vorteil bieten sollte. Schlimmstenfalls ist in der Summe noch genug Platz da, der String ist aber für alle Lücken zu groß und paßt nicht rein - und diese Lücken werden durch eine - wie auch immer geartete - Blockspeicherung immer noch mal extra aufgetrennt. Auch ohne die "Sektorverwaltung" muß entweder der ganze Heap gescant werden (auf eine freie Lücke) oder es muß für jede Größe eine eigene verlinkte Liste gehalten werden (lohnt sich wahrscheinlich nur in 4er-Schritten, also 4, 8, 12, ...), etc. Alles langsamer, als einfach den alten String zu invalidieren und den neuen String "unten" anzuhängen.

    Die genannten Verwaltungsmethoden sind übrigens durchaus gängig. Aber da muß der Heap dann davon ausgehen, daß die allozierten Speicherblöcke nicht verschoben werden (dürfen). Bei Strings und Stringarrays in BASIC ist aber der Zugriff *gekapselt* und darum ist es egal wo sie liegen, und damit wird eine GC ohnehin überhaupt erst möglich!

    So wie ab V3.5/V4 ist das schon ziemlich optimal gelöst. Eine Fußangel gibt es aber noch zu beachten: wird eine neue Einzelvariable vereinbart, schiebt das alle Arrays nach oben - auch die mit Stringdeskriptoren! Bedeutet, daß dann alle betroffenen Backdescriptoren korrigiert werden müssen. Das führt beobachtbar bei Programmstart zu einigen Verzögerungen wenn man das nicht weiß - daher empfiehlt es sich, alle Einzelvariablen bei Programmstart explizit zu initialisieren. :)

  • Danke , sehr interessant! Die zuletzt genannten Verzögerungen dürften aber ebenfalls linearen Aufwand haben (O(n)) , oder? Zwar u.U. merklich, aber nicht katastrophal wie bei der V2-Garbage Collection zuweilen anmutend, nehme ich an.

    Noch diese Gedanken möchte ich beitragen:
    Überlegenswert ist auch, wie Stringzugriffe (Variablenzugriffe allgemein) so gestaltet werden, dass zu häufiges hin-und-herschalten zwischen RAM und ROM speziell auf dem 64'er vermieden werden kann.

    bzw. ich frage mich, ob man das RAM unter dem ROM so reibungslos wie auf dem C(1)16/+4 nutzbar machen kann, ohne dass es zuviel Performance im Normalbetrieb und bei Bytes unterhalb < $A000 kostet.
    Meine Überlegung war, dass das neue Basic nur ein Zeigerpaar kennt, das die aktuelle Anfügestelle markiert und alle Speicherung eines neuen Strings einfach blind drauflos auf das "ROM" zielt (und das darunterliegende RAM trifft) , also Write-only, kein Lesen irgendwelcher Verzeigerung oder von Flags die im Speicher verstreut sind um Bits einzublenden o.ä.. Dann würde man sich das Einblenden von RAM erstmal sparen und erst bei der Garbage Collection müsste es wieder (dauernd/intermittierend) eingeblendet werden. Dürfte aber nur bei Kopieren aus dem Input-Buffer (oder, trivial, Laden von Disk / Tape) klappen. Sobald ein "bereits vorhandener String" Quelle ist, muss wieder hin- und hergeschaltet werden:
    B$ = "XYZ" + A$: REM <---- A$ bereits vorhanden, Lesezugriff erforderlich; ROM muss kurzzeitig weggeblendet werden

    Daran knüpft also die Frage an, wie weit eine Nutzung des zusätzlichen RAM unter den ROMs bei einem "Basic V 2.5 " bei der Optimierung eingebaut werden kann.

    Um festzustellen, wieviel "virtuelles Mehr" an ROM noch freigemacht werden kann um zusätzliche Funktionalität unterzubringen, habe ich einerseits einen anderen Thread beansprucht
    Bitte melde dich an, um diesen Link zu sehen.
    und andererseits "Gemessen" wieviel Redundanz wohl im Basic V2 enthalten ist.

    Vorläufiges Ergebnis:
    Altair Basic (4K) ist komprimiert ca. 3,3 KB "groß", das heisst es sind noch ca. 14% Redundanz drin, was mir ausserordentlich gering vorkommt;
    bei der 8K-Version ist die gepackte Größe 6 KB, das heisst es sind 25 % Redundanz drin.
    Wenn man für einen P-Code-Interpreter genügsame 1 KB veranschlagt, dann wären noch "bis zu 1 KB" für zusätzliche BASIC - Funktionalität drin - könnte man im Kernel / Editor-Bereich noch was freiklopfen, entsprechend mehr. In Wirklichkeit wird man deutlich unter 1KB bleiben, z.b. überschlägig 512 Bytes weil man nicht den letzten Tropfen Entropie wird rausquetschen können.

    Die Frage dieses Threads nach dem Optimierungsgrad lässt sich daher neu formulieren:
    "Was würdet ihr einem BASIC V2.5 an zusätzlicher Funktionalität spendieren, wenn ihr dafür 512 Bytes frei zur Verfügung hättet?"

  • Danke , sehr interessant! Die zuletzt genannten Verzögerungen dürften aber ebenfalls linearen Aufwand haben (O(n)) , oder? Zwar u.U. merklich, aber nicht katastrophal wie bei der V2-Garbage Collection zuweilen anmutend, nehme ich an.

    Jo. Linear in der Größe der bereits ge-DIM-ten Stringarrays. Das war mir zu der Zeit bereits aufgefallen, als ich ein paar Programme auf dem C128 geschrieben hatte, die ein oder zwei größere Stringarrays nutzten - die 'stotterten' am Anfang immer mal für ein paar halbe Sekunden, bis sie dann ohne weitere Verzögerungen liefen.

    Ich konnte mir erst nach Lektüre diverser 64'er-Sonderhefte und dem "128 intern" einen Reim drauf machen. Danach wußte ich ja dann, wie man diesen Effekt mit Bordmitteln beheben kann. :D

    Überlegenswert ist auch, wie Stringzugriffe (Variablenzugriffe allgemein) so gestaltet werden, dass zu häufiges hin-und-herschalten zwischen RAM und ROM speziell auf dem 64'er vermieden werden kann.

    Ein Tipp: schau dir die Stringroutinen im ROM mal an. Dann stellst Du fest, das die eigentlichen Zugriffe auf die Zeichenkettendaten, egal ob lesend oder schreibend von der Laufzeit her weniger als 10% ausmachen. Ob die nun per 'einfachen' LDA/STA (),Y oder über Banking-Routinen laufen macht also praktisch fast gar nichts aus. Der Rest der Routinen kümmert sich um den unvermeidlichen Verwaltungskram (hauptsächlich Adressberechnungen). (<- Tja, ich muß mich da leider selbst korrigieren. Siehe den Edit unten...) Paradoxon-BASIC macht das mit den Banking-Routinen genau so.

    Wenn Du an der Stelle das Banking elimieren willst gibt's da schon einen Weg: verlagere die relevanten Teile des BASIC-Interpreters in ungebanktes RAM. Du tauschst damit wieder - klassisch! - Speicher gegen Geschwindigkeit.

    Numerische Variablen werden ja über die FACs in der Zeropago verrechnet - da dürfte sich der Anteil der Banking-Operationen ebenfalls auf das eigentliche Lesen und Schreiben bei Zuweisungen beschränken.

    Die zeitkritischste Routine dürfte übrigens CHRGET/CHRGOT sein - die wird *ständig* aufgerufen und sollte nicht unnötig ausgebremst werden. :)

    ...

    Paradoxon-BASIC war *so* nah dran am Ideal - wenn nur nicht die langsame GC drin gelassen worden wäre. :(


    Edit: Aaaalso - nach meiner strammen Behauptung oben habe ich das dann doch mal in der Praxis überprüft, mit nachfolgendem Programm sowohl auf dem C64 als auch auf dem +4. Bei letzterem ist das BASIC nicht noch weiter 'aufgebohrt' wie beim C128, wodurch der daraus resultierende zu erwartende Overhead von V3.5 ggü. V2 geringer ist. Aber zum Zugriff zum RAM unter dem ROM kommt schon Banking zum Einsatz:

    Code
    1 B$="0123456789ABCDEF"+""
    2 T1=TI:FORT=1TO1000:A$="":NEXT
    3 T2=TI:FORT=1TO1000:A$=B$:NEXT
    4 T3=TI:PRINT (T2-T1),(T3-T2),(T3-T2)-(T2-T1)

    zur Erklärung: Zeile 1 erzeugt einen mittellangen String, der bei V2 garantiert (aufgrund des +"") im Stringheap landet. Zeile 2 mißt 1000 Leerzuweisungen - T1 und T2 bezeichnen zwei Zeitmarken davor und dahinter. Zeile 3 mißt 1000 Zuweisungen von B$ an A$ - T2 und T3 wiederum zwei Zeitmarken davor und dahinter.

    Mit (T3-T2)-(T2-T1) zieht man also bei den 1000x A$=B$ den anderen Overhead (1000x FOR...NEXT ausführen) ab und gelangt so im wesentlichen zu der reinen Ausführungszeit der Zuweisung A$=B$.

    Ergebnis:

    C64: 138 177 39
    +4: 181 258 77

    Wesentlich sind hier die jeweils letzten Zahlen in jeder Zeile, 39 Jiffies beim C64, 77 Jiffies beim +4.

    Das Banking kostet also doch einiges. Aber dafür kommt man eben unters ROM.

  • Vielen Dank für diese systematische und bedachte Untersuchung! Dass der Plus/4 hierfür -Stringzuweisung- fast doppelt so lang braucht wie Basic V2, schmerzt besonders, weil er ja des öfteren mit doppeltem Takt läuft.

    Um also auf dem C64 statt knapp unter 40 KB etwa 60 KB frei zu haben , also 50% mehr, (was ja evtl. einen entsprechenden Trade-off Speicher -> Geschwindigkeit zugunsten letzterer auf Basic-Programmebene ermöglichen würde) müsste man fast 100% Laufzeit-Penalty in Kauf nehmen. Es sei denn es fiele einem ein klügerer Umschaltmechanismus ein.
    Z.b., Basic kopiert sich zu beginn nach $C000 - $DFFF und blendet danach das ROM aus o.ä. Die "Empörung" aller $C000-Nutzer ist vorhersehbar, ebenso die Komplikationen mit Interrupts und temporärem I/O-Wegblenden etc.

    Meine persönliche Folgerung wäre: Finger weg vom RAM unter dem ROM. Allenfalls für Bitmaps und diese ausserhalb der übrigen Stringverwaltung angesiedelt..

  • Also wenn sich die String-Routinen oder zumindest das String-Lesen in den oberen 8K unterbringen lassen, dann beschränkt sich das Umschalten doch auf Dec $01 und Inc$01. Das kann jetzt nicht DER Overhead sein. Aber es könnte schwer sein, das nach oben zu schieben, ohne inkompatibel zu werden.

    Die Verwendung von Backdescriptoren "beißt" sich aber mit dieser Optimierung (bzw. erfordert Fallunterscheidungen für Strings mit und ohne Backdescriptor), weswegen das bei BASICs mit schneller GC nicht mehr drin ist.

    Warum? Die GC sieht doch nur Strings auf dem Heap, Pointer ins Basic-Programm sind für die GC doch unsichtbar?

  • Warum? Die GC sieht doch nur Strings auf dem Heap, Pointer ins Basic-Programm sind für die GC doch unsichtbar?

    Stichwort: Fallunterscheidung. Beim C16/C116/+4 hätte man evtl. über einen Pointer-Vergleich bei den Backdescriptor-Korrekturen noch was machen können (Deskriptor zeigt ins BASIC-Programm? -> Backdeskriptor nicht korrigieren, da nicht vorhanden) und richtig - bei der eigentlichen GC ist das pupsegal.

    Allerdings lohnt sich ein Blick auf die "Herkunft" der schnellen GC. Viele V4 Rechner hatten, ähnlich wie der C128, eine zweite RAM-Bank für Variablen. Und da scheint mir die eigentliche Problematik zu liegen: man kann nicht (konstante) Zeichenketten im BASIC-Programm und veränderliche Zeichenketten im Stringheap haben, wenn der Zeiger im String-Deskriptor keine Bankinformation enthält... und CBM wollte wohl keine dritte Variante der Stringroutinen bauen.

  • Also mein Ansatz als Basic-Programmierer war immer die GBC-Vermeidung.

    Wenn man z.B. ein :GET A: statt ein GETA$ hat, gibt es bei GET schon man keine Stringanlegung im String RAM also auch keine GBC.
    Ansonsten kann man überflüssige Strings selbst bereinigen wie z.B. im Listing Feststring-Verwaltung beschrieben.
    Bei String-Tausch kann man übrigens auch das Stringanlegen per Poke ausschalten, wodurch es z.B. bei Sortierprogrammen keine GBC mehr gibt.

    Schönen Gruß.

  • hallo, ich weiß nicht ob ich es nur übersehen habe oder nicht, kannst du bitte einen Link angeben oder erläutern, wie diese Pokes im einzelnen wirken?

    Bei GET hab ich im Informatikunterricht damals "beigebogen bekommen" dass man Type mismatch o.ä. vermeiden soll, wenn eine nichtnumerische Taste gedrückt wird (was man ja nicht unter Kontrolle hat was der Benutzer so eintippt...), oder lässt sich diese Prüfung etwa auch per Poke abschalten!?

    Danke!

  • Wenn man z.B. ein :GET A: statt ein GETA$ hat, gibt es bei GET schon man keine Stringanlegung im String RAM also auch keine GBC.

    Aus Sicht der GBC wäre es bei Einführung des C64 vielleicht keine schlechte Idee gewesen, aus GET eine rein numerische Funktion zu machen, die das EOF-Bit im Status verwendet (falls sie das nicht eh schon tut). Vom Verständnis für Anwender her ist ein String aber schöner, der keine Eingabe als Leerstring darstellen kann.

    Zu GET A war ja glaub ich schon im Handbuch beschrieben, dass eine Eingabe eines Buchstabens einen Fehler erzeugt. Ich könnte mir daher vorstellen, dass das nie benutzt wurde und man eine Rückgabe des Ascii-Codes einbauen könnte. Wäre dann aber nicht mehr Rückwärts-kompatibel.

    Vielleicht eher für den anderen Thread: Eigentlich wären GET und INPUT doch eher Funktionen statt Befehle? Es ist irgendwie doof, sich ändernde Variablen auf der rechten Seite zu haben, A$=GET wäre einheitlicher (Vorsicht flach: STRINGenter :kill: ). und evtl. könnte dann das Unterprogramm entfallen, das explizit eine Variable sucht.

    Another workaround? Stay a while... STAY FOREVER!!

    Einmal editiert, zuletzt von Hoogo (6. Juni 2017 um 07:26)

  • Zu GET A war ja glaub ich schon im Handbuch beschrieben, dass eine Eingabe eines Buchstabens einen Fehler erzeugt. Ich könnte mir daher vorstellen, dass das nie benutzt wurde und man eine Rückgabe des Ascii-Codes einbauen könnte. Wäre dann aber nicht mehr Rückwärts-kompatibel.

    Vielleicht eher für den anderen Thread: Eigentlich wären GET und INPUT doch eher Funktionen statt Befehle? Es ist irgendwie doof, sich ändernde Variablen auf der rechten Seite zu haben, A$=GET wäre einheitlicher (Vorsicht flach: STRINGenter ). und evtl. könnte dann das Unterprogramm entfallen, das explizit eine Variable sucht.

    Stringenter .. :wink:

    Ernste idee dazu: Warum nicht GET als Funktion definieren, die den ASCII-Wert zurückgibt, und nur dann einen String produziert, wenn eine Variable angegeben ist? Benutzen könnte man sie auf beide Weisen, auch auf einmal, wenn man will. Dann wäre das Ding vollständig rückwärtskompatibel, und um eine viel schnellere und praktischere Option erweitert.

  • ...man kann nicht (konstante) Zeichenketten im BASIC-Programm und veränderliche Zeichenketten im Stringheap haben, wenn der Zeiger im String-Deskriptor keine Bankinformation enthält... und CBM wollte wohl keine dritte Variante der Stringroutinen bauen.

    Ich kann mir auch vorstellen, dass es extrem unhandlich wird, 2 Strings aus 2 Bänken miteinander zu verketten.

    Noch ein Gedanke zur GC mit Rückwärts-Pointern, der aber besser in den anderen Thread passt:
    Mit nur 1 Rückwärts-Pointer können nicht 2 Variablen auf den gleichen String zeigen. Die jetzige GC wird das aber vermutlich auch voraussetzen und sich nur 1 Variable merken, die in diesem Durchlauf verschoben wird.

  • Mit nur 1 Rückwärts-Pointer können nicht 2 Variablen auf den gleichen String zeigen.

    Das ist aber nicht kritisch, da zwei (oder mehr) Variablen nur dann *einfach für den Interpreter nachvollziehbar* auf den gleichen String zeigen können, wenn die erste Zeichenkette bereits als Konstante im BASIC-Programm referenziert wird und danach auch nur eine einfache Zuweisung an weitere Variablen erfolgt. In diesem Fall können die Kopien tatsächlich nur den Stringdeskriptor erben und es braucht keine Kopie im Stringheap angefertigt zu werden. Diese Optimierung ist tatsächlich *ebenfalls* in V2 drin(!) - könnte aber problemlos für eine schnelle GC in einer gemeinsamen Programm/Variablen-Bank übernommen werden.

    Aus diesem Grund habe ich bei dem Testprogramm die Zeichenkette B$ so gestaltet, daß sie tatsächlich im Stringheap landet. Sonst kopiert V2 wie bereits gesagt, nur den Stringdeskriptor und dann sind die Messungen nicht mehr vergleichbar (V2 braucht dann nur noch 7 Jiffies!).

    Auf den Fall, daß zwei Zeichenketten zur Laufzeit "zufällig" mal den gleichen Inhalt enthalten, kann man wohl nicht sinnvoll setzen - die Tests und Vergleiche mit allen anderen Zeichenketten um das zu ermitteln, bräuchten ja ewig Zeit. Und das notwendige auseinanderfieseln wenn eine der "verschränkten" Variablen sich doch wieder ändert - darauf wolltest Du hoffentlich ja nicht ernsthaft hinaus. ;)


    (In C können mehrfach vorkommende gleiche konstante Zeichenketten ebenfalls durch den Compiler als lediglich eine Zeichenkette, mit nur einem Pointer abgelegt werden. Können, müssen aber nicht. Deshalb ist es keine gute Idee, so eine Zeichenkette dann doch (mit Tricks) zu beschreiben: das ändert die Kopien gleich mit - oder auch nicht, je nach Implementation. Also klassisch undefiniertes Varhalten.)

  • Nice. Ich hab kurz überlegt, ob man nicht auch einen 2. String in den Speicher des ersten zeigen lassen könnte, dürfte aber bei einer GC sehr unschön werden.

    Bei den 'langen' (2GB) Strings in Delphi gibt es eine Referenzzählung , die bei jedem String vermerkt, wieviele Variablen 'auf ihn zeigen'. Also hat man das Problem dort erkannt und auch dort gibt es zur Laufzeit eine Art Garbage-Collection auch wenn es vornehm Heap- oder Memory-Management heisst.

    Auch gibt es anderwärts ja auch Variablen und (seit Borland Pascal for Windows, IIRC) den Typ "CONST ... PChar", was m.E. auch eine Art Feststring darstellt. Das Entsprechende in Basic V2 wären die Stringzeiger die auf DATA-Zeilen bzw. in den Basic-Quelltext zeigen.