I did some work to speed up string garbage collection under Applesoft (for my BBS). Applesoft Basic didn't use any back pointers or anything of the sort, if I recall, or garbage markers. It bump-allocated new strings at the top of the stack, and let unused strings naturally become garbage. Strings were garbage collected by visiting the reachable strings in order of descending address and compacting them toward the bottom of the heap (high address).
Unfortunately, this created a challenge. There was no place to sort the strings into the required order to do this traversal. The built-in garbage collector used a horrible O(N*N) algorithm, making multiple passes over the strings to find the highest remaining one, and move it.
The string pointers could not be sorted because they sat in string variables and arrays; an external copy of those locations would have been required to hold the sorted strings, with back-pointers to the original locations to update their addresses. There was no space for this; the garbage collector was invoked exactly when the machine was almost completely out of RAM.
Nearly 40 years ago I disassembled the ROM from a TRS-80 model III and it used the exact same O(N*N) algorithm. As you point out, garbage collection is being performed due to lack of free memory, and so the algorithm used only the 8080 registers and something like six bytes of dedicated RAM to keep track of everything.
Bill: "Hi! Thanks for your interest in this heart-warming old stuff! I implemented the simplest possible algorithm that was obviously correct, while fitting in the severely constrained memory. I didn't have any weird explicit garbage markers (which are an earmark of de facto manual reclamation) or back pointers. Consequently, you're not reading about the oldest and nastiest string garbage collection bug in Microsoft Basic. I also used more capable big iron machines to emulate 8 bit computers to debug and validate my work. I sold my Basic to multiple computer vendors, which made it more battle-tested than single-vendor implementations, and had more eyes scrutinizing it."
GC bugs are a lot like race conditions, even if everything is in one thread, because it is nondeterministic which action will trigger GC. Disabling GC over a range of code is reminiscent of locking a mutex or disabling interrupts.
When you're developing a run-time with GC, it behooves you to run at least some of your test cases in GC torture mode, which triggers collections often (like before every allocation). Anything that is not properly nailed down over a complex operation gets scavenged. If you make it so that a reclaimed object has a garbage type tag, then the use of a prematurely reclaimed object can be caught quite soon as a type issue.
Unfortunately, this created a challenge. There was no place to sort the strings into the required order to do this traversal. The built-in garbage collector used a horrible O(N*N) algorithm, making multiple passes over the strings to find the highest remaining one, and move it.
The string pointers could not be sorted because they sat in string variables and arrays; an external copy of those locations would have been required to hold the sorted strings, with back-pointers to the original locations to update their addresses. There was no space for this; the garbage collector was invoked exactly when the machine was almost completely out of RAM.