Diskussion:Garbage Collection

Schnellere GC
Irgendwann gabs mal in der 64er einen "Patch" für den Basic-Interpreter um die GC zu beschleunigen. Weiß jmd in welcher Ausgabe das war? (Keine Lust alles hier zu durchsuchen: ftp://arnold.c64.org/pub/magazines/64%27er/)--Kawentsmann 23:03, 22. Okt. 2009 (CEST)

Habs gefunden (10/88), aber leider werden 2 Byte mehr pro String gespeichert. Links mit dem Patch, rechts ohne.--Kawentsmann 17:41, 27. Okt. 2009 (CET)

Da gabs aber auch noch einen anderen Artikel, der wie auch in meiner Implementierung, die GC mit Hilfe eines Bufferspeichers im Aufwand linearisiert. Ich hatte die Nöte bereits 1985 das Problem zu lösen, Anfang 1986 hatte ich vor das Programm, dass sich im Praxisbetrieb bestens bewährt hat, zu publizieren. In einer 64er Ausgabe, 1986/2, ftp://arnold.c64.org/pub/magazines/64'er/feb86.zip, ist mir ein anderer Autor mit ähnlichem Ansatz zuvorgekommen mit dem Projekt GARBAGE64. Wenn ich mich recht erinnere wird dort der 4K-Bereich $C000-$D000 als Pufferspeicher verwendet. In meiner Implementierung verwendet ich die 8K unter dem Kernal-ROM, weil ich den 4K-Bereich für anderes benötigt habe. Macht im Endeffekt nicht mehr viel Unterschied. Ich hab mir den Code nicht genauer angesehen, aber aufgrund des 64er-Artikels war die Funktionsweise prinzipiell die gleiche.

Der Patch mit einer Backreferenz auf den String ist natürlich algorithmisch und datenstrukturmäßig am elegantesten, aber insgesamt ineffizient und damit hätte sich z.B. mein konkretes Projekt nicht zufriedenstellend lösen können. Insofern stellen sich in 8bitter-Umgebungen nicht umbedingt die saubersten informatiktechnischen Ansätze als die wirklich elegantesten oder effizientesten heraus ... - aber wem sag ich das da in diesem Wiki ;)

---

Irgendwas stimmt mit meinem Basic-Provokationsprogramm noch nicht (hab's auf diversen EMUs versucht zu testen). Ich hab es aus meinen Handschriftlichen Notizen übernommen (und meine elektronischen Aufzeichnungen sind derzeit nicht verfügbar), aber irgendwie fehlt da was/stimmt nicht ganz, weil die GC nicht das erhoffte, dramatische Ausmaß annimmt. Da muss ich noch nachbessern ... ;) --JohannKlasek 13:31, 6. Okt. 2009 (CEST)

Irgendwas mit "+" hast du ja empfohlen, also etwa so:

  10 DIM A$(9000)
  20 FOR I=0 TO 9000: A$(I)=A$(I)+"*":NEXT
  30 PRINT"ARRAY FERTIG":PRINT
  40 T1=TI:PRINT FRE(0):T2=TI
  50 PRINT (T2-T1)/3600;" MIN."

Die GC braucht mehr als 109 Minuten (gelobt sei der Warp-Modus:) --Petrus 22:21, 6. Okt. 2009 (CEST)

Danke - In der Tat, das ist eine Variante, die es wirklich provoziert. Offenbar hab ich beim damaligen Abschreiben ein unbewusstes Optimieren gemacht. Ein Zuweisung nur mit "*" bewirkt in der Tat lediglich, das die 9000 Stringdescriptoren allesamt auf genau den einen String im Basic-Code verweisen. Der verbrauchte dynamische Stringspeicher ist defacto 0 und die GC hat dann nix zu tun. --JohannKlasek 23:51, 6. Okt. 2009 (CEST)

Nachtrag: Ich weiss jetzt, woran es lag, das meine erste Beispielversion nicht wie erwartet funktioniert hat. Es lag schlicht daran, dass es für den Direktmodus bestimmt war. Dort werden nämlich Stringkonstanten natürlich nicht als in Programmzeilen liegende Strings verwendet, da es ja keinen persistenten Programmcode gibt. ;) Daher sind keine besonderen Umstände notwendig, den String irgendwie auf den String-Heap zu bringen. Die Zuweisung eines Konstantstrings reicht hier dann völlig!

Im Direktmodus reicht demnach wirklich (in VICE sicherheitshalber nochmal verifiziert) folgenden Code

  DIM A$(9000)
  FOR I=0 TO 9000: A$(I)="*":NEXT
  TI$="000000":? FRE(8):PRINT TI$,TI

auszuführen. Sieht dann so aus:

---

Stack & Befehl CLR & GC:
Mal was interessantes: Der Befehl CLR löscht ja bekanntlich den Stack. Liegt die GC auch im Stack bzw. am Stackende? Da nach einem CLR über den FRE-Befehl genausoviel RAM angezeigt wird, wie vor dem Start des BASIC-Programms? Es wurden in dem Testprogramm die Variablen A$, B$, C$ benutzt und mit + verknüpft. --Jodigi 04:26, 8. Okt. 2009 (CEST)

Die Bescheibung von CLR ist nicht ganz richtig, CLR löscht Stack und Heap (oder wie auch immer das bei BASIC heißt). Auf dem Stack werden Rücksprungadressen bei GOSUB und Informationen für FOR/NEXT gespeichert, normale BASIC-Variablen liegen aber im Heap, nicht im Stack (der CPU-Stack wäre mit rund 255 Bytes auch zu klein dafür). Das BASIC-Programm an sich und der Heap teilen sich AFAIR den Speicherbereich zwischen $0801 und $9FFF, der Heap wächst vermutlich nach unten. GC bezieht sich nur auf den Heap, im Stack gibt's nichts aufzuräumen.

GC "liegt" nirgendwo, sondern ist ein Vorgang, bei dem der Heap wieder aufgeräumt wird. Nach CLR ist der Heap schon leer, also gibt's da natürlich nichts zu tun. -- 1570 14:47, 8. Okt. 2009 (CEST)

Der Heap wächst zum einen von unten (niedrigen Adressen) hinauf bei weiteren Variablen-Verwendung bisher nicht verwendeter Variablen oder durch DIM-Deklarationen und andererseits von oben (höheren Adressen) hinunter durch dynamisch angelegt Strings. Die GC räumt also "nur" den oberen, Stringbereich auf.--JohannKlasek 17:42, 8. Okt. 2009 (CEST)

Mal CLR etwas angepaßt --Jodigi 15:38, 8. Okt. 2009 (CEST)

Ja, ist besser so. :-) Über kurz oder lang muss wohl auch ein Speicherbelegung (BASIC), Stapel (BASIC) und Heap (BASIC) oder sowas her (ähnlich wie bei Chip und CPLD etc. könnte man ja erstmal alles auf einer Seite zusammenfassen und Weiterleitungen definieren); Links zu den relevanten BASIC-Routinen z.B. auf AAY64 wären auch nicht schlecht. -- 1570 16:05, 8. Okt. 2009 (CEST)

Muß man denn nochmals alles unterteilen Beispiel Stack: In Stack normal und Stack(BASIC)?

Nicht das dies dann zu unübersichtlich wird ! --Jodigi 16:14, 8. Okt. 2009 (CEST)

Der BASIC-Stack (für GOSUB/RETURN, FOR/NEXT und Floating Point Arithmetik - Klammerungen) ist am normalen Stack der CPU. Der Basic-Interpreter kontrolliert aber den Gebrauch, sodass genügend für den Interpreter übrig bleibt. Daher ist die Verschachtelungstiefe bei FOR/NEXT bei GOSUBs für heutige Verhältnis freilich ziemlich bescheiden (z.B. 24 verschachtelte GOSUBs, ergibt beim nächsten ein "OUT OF MEMORY" ;-) ) - Rekursionen sind aber hier auch nicht das klassische Programmierparadigma.

Ich glaub nicht, dass das allzu kompliziert oder verwirrend ist. Einzig der frei gebliebene Speicher (wenn man will Heap) wird von den Variablen und den Stringinhalten von 2 Richtungen "aufgefressen". Der (einzige) Stack wird von Betriebssystem, Basic-Interpreter und CPU im allgemeinen gemeinsam genutzt. Dann gibt es nur noch den variablen Programmbereich. Alles andere ist MW dann ziemlich statisch.

BTW: Mit dem Ausdruck "gelöscht" sollte man etwas vorsichtig umgehen. Das impliziert mitunter mehr, als tatsächlich passiert. In den meisten Fällen, wir - wenn etwas "gelöscht" wird - bestenfalls etwas freigegeben, indem meist nur entsprechende Zeiger in Systemvariablen zurückgesetzt werden - da wird üblicherweise nicht mit 0 oder anderen Werten ein Speicherbereich überschrieben. Je nach Anwendungsfall hielte ich "freigeben" oder "zurücksetzen" etc. für entsprechend bessere Ausdrücke--JohannKlasek 17:42, 8. Okt. 2009 (CEST)

Ich habe mal Stapel etwas umformuliert und deutlicher nach Konzept/CPU-Stack/ASM/BASIC getrennt. Verwirrend wird's denke ich, wenn man die Begriffe miteinander vermischt. Gerade Anfängern ist nicht geholfen, wenn alles nach einer Suppe aussieht. -- 1570 18:11, 8. Okt. 2009 (CEST)

Gerade als Anfänger würde ich gar nicht so tief in der Theorie mich einlesen, sondern ausprobieren... --Jodigi 23:12, 8. Okt. 2009 (CEST)