JK's Super Garbage Collection

Author: Johann E. Klasek

History

This project has its origin in the year 1985 caused by BASIC projects that grow larger and larger. The BASIC 2.0 garbage collector turned out to be unacceptable with its undeterministic pausing behavior. After taking over a project called "Programmbibliothek" (managing, sorting and printing disk directory collections for our Freaks Computer Club) the requirements grows higher. The usability, reliability and stability of the program was a major issue. With the original GC of BASIC 2.0 this won't be feasible. The devolopment of some alternative GC implementation was necessary and a solution came into mind. At this time back-link based implementions are already in use by BASIC 4.0, BASIC 3.5 and BASIC 7.0 but this was not an option because each string takes two more bytes, reducing the overall number of available strings. My idea was to take the unused space below the ROMs as a buffer where a whole bunch of active strings can be collected in just one single run. This prevents the otherwise quadratic effort to search the highest string over and over. In addition the string data structure does not change in any way.

The initial version has been finished during 1985 and with version 1.1 it was nearly ready for publication. But the plan to publish this program in the german 64'er magazine was abandoned abruptly because the February issue of 64'er had published a garbage collection implementation with the same basic idea from some other author ("Garbage64"), but which was faulty (what I found out years later through a deeper code analysis).

Technical aspects

How is the Super-GC embedded into BASIC's environment?

• Classic BASIC interpreter patch hook
  

  Very simply, not to say clumsy in some way. The BASIC ROM is copied into RAM and the old GC routine is patched with a hook to the new implementation (which resides in the area from $C000 to $CFFF). The buffer area was the RAM below the KERNAL ROM from $E000 to $F000.
  The 1985 version has a small drawback because it masks interrupt during the whole run-time (just to prevent problems if the KERNAL ROM is hidden).In newer versions the masking time is reduced to the most necessary.

• Interrupt hook (standard method)
  

  This is some elegant approach which hooks into the interrupt request handling. There is no need to copy the BASIC ROM into RAM anymore. The RAM area below the BASIC ROM can be also used as buffer if the RAM below the KERNAL is needed otherwise (e.g. graphic bitmap). In an alternative version the buffer is placed below the KERNAL and the RAM under the BASIC ROM remains free.
  The garbage collection is called as usual but the next interrupt (IRQ), within a time-frame of 1/60 sec. checks if the legacy GC is currently running. This is more or less complex procedure because there are several cases which requires the correction of the string heap state or stack to keep it consistent, before the new GC is run.
  The downside of this variant is that it takes around 200 bytes more in space, but it is nearly as fast as with the classic hook embedding.

Historical usage

The Super-GC was part of a library which provides a couple of functions was used for several projects. These programs proved the reliability over month and years of practical use. But the main application was the "Programm-Bibliothek" for the Freaks Computer Club which ran with sucess for several years.

Download

• Version 1985: V1.1 (Rev. 8), 1985-12-27
  Github repository (hyprass and acme)
  1. documented (german) source (ASCII) (ASCII format in Hypra-Ass syntax without linenumbering)
     Notes:
     This is an uncorrected version, which has been patched by means a monitor before practical use. The correction consists of swapping the lines 1050 to 1100 with 1105 to 1120 and with some special handling of string-overflow situations by reserving some space in the buffer area.
  2. documented (german) source (PRG) (Hypra-Ass format as PRG file)
     
  3. documented (german) listing output (ASCII) (Hypra-Ass listing output format)
     
  4. Code - binary file (PRG) (created with Hypra-Ass, with applied bug-fix patches, PRG file)
     
  5. D64 Image Super Garbage Collection (binary, BASIC loader, demo)
     Binary: $CDEF-$CFFF
     Usage:

     LOAD "GARBAGE COLLECT",8,1
     NEW
     LOAD "GC-DEMO",8
     RUN
     

     In line number 1 the initialisation of Super-GC is set inactive. To activate it for the demo just remove the REM command.
     The demo program limits artificially the string heap (by means of creating a rightly sized float array). the main task is to concat 700 strings generating a lot of string garbage. Every string is marked with a "." character filling up the display. The more strings will be created the less free string spaces remains and garbage collector is called more frequent. The speed of appearing dots shows how a GC slows down the run-time. Finally the demo waits for the space key and shows all the 7 hundred strings for visual verification (an error in the implemention can be easily recognized).
  
  
• Version 2020: V2.2 Release 3, 2020-12-14
  Github repository
  1. Source (ASCII format in ACME syntax, english comments)
     Source (ASCII format in ACME syntax, german comments)
     Successor of version 2.1 from 2019.
     Beware:
     This version replaces also version 2013 V2.0 which contains 2 bugs, which has been fixed here. These bugs are rather severe. One occurs very rarly, but if, the GC will hang up. The other bug may currupts the data. Therefore never use the 2.0 version!
     Note:
     This is an reworked version with some minor optimizations and corrections. If the garbage collection is in progress in the right lower corner a "*" appears to indicate its operation.
     In addition interrupt masking is limited to the read access of the buffer (while hiding the KERNAL ROM). This let the influence from this rather small.
  2. Makefile (creates the different PRG versions from source)
     
  3. Source of the debug module (ASCII format in ACME output format)
     It's just optional. If used with activated debugging option in the source-code the resulting version has the ability to show the buffer as hires-image which let one watch the GC at work.
  4. Code - binary with BASIC hook, buffer below KERNAL (PRG) (PRG file)
     Report file - listing output (ASCII) for the BASIC hook (ASCII format in ACME output format)
     Memory layout (RAM):
     • $A000-$BFFF patched BASIC ROM copy
     • $C500-$C710 Super-GC - the binary
     • $E000-$FFFF buffer area
  5. Code - binary with IRQ hook, buffer below BASIC (PRG) (PRG file)
     Report file - listing output (ASCII) for the IRQ hook, buffer below BASIC (ASCII format in ACME output format)
     Memory layout (RAM):
     • $A000-$BFFF buffer area
     • $C500-$C7DE Super-GC - the binary
  6. Code - binary with IRQ hook, buffer below KERNAL (PRG) (PRG file)
     Report file - listing output (ASCII) for the IRQ hook, buffer below KERNAL (ASCII format in ACME output format)
     Memory layout (RAM):
     • $C500-$C7D4 Super-GC - the binary
     • $E000-$FFFF buffer area
  7. D64 Image Super Garbage Collection 2020-Edition (binary, BASIC loader, demo program, test program)
     Small documentation
     Content:

     0 "supergc-2020-dis" jk 2a
     9     "gc-demo         "  prg
     3     "gc-std-test     "  prg
     2     "gc-test         "  prg
     3     "supergc-basic   "  prg
     3     "supergc-irqa    "  prg
     3     "supergc-irqe    "  prg
     1     "supergc-loader  "  prg
     3     "supergc         "  prg
     637 blocks free.
     

     PRG supergc corresponds to te supergc-irqa version!

     Demo and test programs:
     stress-test for a GC ...

     LOAD "GC-DEMO",8
     RUN
     

     standard test with 5000 strings ...

     LOAD "GC-STD-TEST",8
     RUN
     

  SUPERGC-LOADER contains only the loader intro for BASIC programs to automatically load and activate the SuperGC.

Copyright and legal notice

The programs may be used and distributed freely as long the reference to author remains.

Further plans

• [_] Working on the documentation (in progress).
• [X] Improving the embedding and hook-up (without copy the BASIC ROM into RAM) (since V2.2)
• [X] Improving the interrupt handling (less blocking the interrupts)
• [X] Small improvements on several places more or less bautifications, but some also for run-time efficiency).

References

1. C64-Wiki.com: Garbage Collection
2. C64-Wiki.de: Garbage Collection (german)
3. ROM listing of the original routine:
   the automatically added comments are not very useful, rather irritating.
   • $B526/46374: Garbage Collection
   • $B5BD/46525: Search for Next String
   • $B606/46598: Collect a String
4. Jim Butterfield article list from Compute!
   1. Compute! Issue 10 - March 1981: Learning About Garbage Collection
   2. Compute! Issue 49 - June 1984: Garbage Collection On Commodore Computers
   3. Compute! Issue 50 - July 1984: Commodore Garbage Collection Part 2
5. 64'er-Magazin Februar 1986: Garbage64 Alternative implementation with buffer basis (like SuperGC), but faulty.
6. Article from c't magazine 1984/6 S. 72: BASIC intern - Was nicht im Handbuch steht: Teil 3: Strings und 'Garbage collection' (german)
7. Book "Microsoft-Basic: Konzepte, Algorithmen und Datenstrukturen", Luidger Röckrath, Franzis' Verlag, ISBN: 3772380115 (german)
   6.2.3 Die Stringspace-Reorganisation Garbage collection (GARCOL), S. 123

zurück zur Startseite

14.12.2020 Webmaster