(Comp.sys.hp48) Item: 1308 by schafmei@fraser.sfu.ca [Chris Schafmeister] Subj: Garbage collection, how does it work? Date: 13 Jul 1993 I'm starting to program my HP48 in Saturn Assembly code and I'm confused by garbage collection. If I allocate a string for scratch space will it automatically be recovered when garbage collection takes place? How does the HP48 determine what objects are no longer referenced for garbage collection? Does it follow all pointers in all objects, garbage collecting what it doesn't touch? To me, this would seem to be awfully slow. .Chris. ---------- Resp: 1 of 1 by ervin@pinbot.enet.dec.com [Joseph James Ervin] Date: 14 Jul 1993 Hi Chris, Here's briefly how GC works... GC collapses all the objects in TEMP0B, removing any objects to which there are no references. This happens in essentially 6 steps, as follows: 1. Every object in TEMPOB has an "in use" flag which indicates whether a given TEMPOB object is referenced (pointed to) by a pointer somewhere in the system. In this step, all the "in use" flags are initialized to "not in use". 2. Go through the RPL Stack, the RPL Return address stack, the key assignments, alarm list, and every other place where a TEMPOB object could be referenced. For each TEMPOB object that is referenced (i.e. there exists a pointer to that TEMPOB object), modify the TEMPOB Object's "in use" flag to indicate that it is, in fact, being used in the system. 3. Sweep through TEMPOB memory and build a table of how many nibbles each TEMPOB object will move when the TEMPOB memory is collapsed (i.e.when the unused objects are removed). This can be done because we now know which objects are "unused" and therefore will be deleted. 4. Sweep through the RPL stack, RPL Return address stack, and every other place where a TEMPOB object could be referenced and modify the pointer to that object by the number of nibbles that the TEMPOB object will move when the _unused_ TEMPOB objects are removed. This keeps all the pointers to TEMPOB objects, such as those on the RPL Stack, correctly pointing to their respective TEMPOB objects even though the TEMPOB objects are about to move around due to the removal of the unused TEMPOB objects, and the subsequent collapse of TEMPOB memory. 5. Sweep through TEMPOB memory, removing all unused TEMPOB objects and collapsing the TEMPOB area to fill in the free'd space. 6. Clean up TEMPOB memory and do some final houskeeping stuff. So to summarize, any object that is _not_ a TEMPOB object will not move as a result of garbage collection. Therefore, once your ML program has acquired a pointer to that object, you can rest assured that the pointer will not move so long as you don't go deleting objects from the user directory area, which obviously causes stuff to move around as well. In practice, what I do is to force a garbage collection at the very beginning of my ML code. This "packs" memory so that any objects I allocate in TEMPOB will not have any empty spaces, so even if a GC occurs, none of those objects will move. Then I just allocate as much RAM as I need in one big chunk as a string, being careful to push a pointer to this TEMPOB object onto the stack so that if GC occurs during subsequent attempts to allocate memory, the object will have a valid reference (pointer). Sometimes it is necessary to push multiple objects onto the stack from within an ML program. As long as you pack memory at the start by forcing a GC, and as long as each TEMPOB object has its own pointer pushed onto the stack, you are all set. I hope this helps, Regards, >>>Joe Ervin