| JK's Back-Link On Demand Garbage Collection | |
| Author: Johann E. Klasek | |
Patching the BASIC interpreter
There are four places the interpreter needs to be hooked to get BLOD-GC working. The BASIC ROM will be copied into the underlaying RAM and the old GC routine is redirected to the new BLOD-GC code which is locate in the range from $C000 to $CFFF. Three additional patches are needed which makes sure that every released strings on the heap (which is not actively used anymore) are marked as "free". There are three situation where a string input produces a string output and which has to be handled accordingly:
All other cases with temporarily created strings are immediatly removed from the heap. They have not to be marked as free.
The main difference of this implementation in regard to the well-known implementations from
BASIC 4.0 or later at BASIC 3.5 and BASIC 7.0 is that there is no need to reserve 2 bytes for each string on the string heap which contains the back-link or gap marker. BLOD-GC stores the back-link or gap marker into the string itself (overwritting the tail of the string). For active strings the overwritten data is temporarily stored into the descriptor (the addree is not needed in at this stage). There only one special case, if the string is of length 1 in which case it cannot take the back-link or gap marker ($FF with the gap length). For this situation a new gap marker with value 1 is introduced. This works because a back-link address never is in page $01 (the stack page).
Only active strings contains the back-link in the last two bytes. The so called "back-link" points back to the string descriptor which on the string descriptor stack, in a single variable, or part of an array.
Here is a diagram showing Variables, the String Descriptor Stacks and the String Heap for following command sequence:
B$="Y" A$="X" A$="ABC"+"DEF" PRINT FRE(0)
In comparison to the standard BASIC V2 the run-time of BLOD-GC is 2300 times faster (for 9600 strings).
BLOD-GC is on the same level as Super Garbage Collection and slightly faster than BASIC 7.0 on a C128 or BASIC 3.5 on a Plus/4 and C16, respectively. On a C64 only the also linear implementation GarbColl is faster, but suffers from the fact, that each string as an additional overhead of 2 bytes (which prevents a runable 9600 string test).
The testing programs can be found on D64 image, see section Download
| Program | GC-DEMO - stress test [h:mm:s] |
GC-STD-TEST 9600 strings [h:mm:s] |
|---|---|---|
| BLOD-GC | 1:43 | 3,1 |
| BASIC V2 | 26:22 | 2:04:27,0 |
| SuperGC | 1:43 | 3,1 |
| Garbage64 (NG) | 1:46 | 2,8 |
| GarbColl (NG) | 1:38 | − |
| BASIC 3.5 | 1:48 | 3,2 |
| BASIC 7.0 | 2:11 | 3,6 |
| BASIC 7.0 FAST | 1:03 | 1,8 |
| BASIC 4.0 CBM 8xxx | 1:30 | − |
| BASIC 4.0 CBM 4xxx | 1:26 | − |
| BASIC 4.0+ CBM-II (2 MHz 6509) | 1:10 | 2,1 |
0 "./blodgc-2021-di" jk 2a 1 "blodgc-loader " prg 4 "blodgc " prg 8 "gc-demo " prg 2 "gc-test " prg 649 blocks free.
demo and test programs:
In line number 1 the initialisation of BLOD-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).
LOAD "GC-DEMO",8 RUNStandard test with 5000 strings ...
LOAD "GC-TEST",8 RUN
The programs may be used and distributed freely as long the reference to author remains.
|
zurück zur Startseite |