The garbage collector in 80s MS BASIC was incredibly inefficient. The routine was written on to minimize the amount of memory to perform the GC, something like 8 bytes.
It would simply iterate through every entry in the temp string stack and then all the entries in the symbol table to find the string with the lowest address above whatever was the previous lowest address. After that full sweep, it would move that string to its new home and adjust pointers to it, then set the new low bound to the string just identified. It would keep iterating until all strings had been visited.
As a result, it required (n2)/2 sweeps of memory (n=# of strings). Having BASIC lock up for 30 seconds every once in awhile was just how it went.
[ and in case someone is going to correct me, it might have swept from top of memory to bottom, I have forgotten the details ]
It would simply iterate through every entry in the temp string stack and then all the entries in the symbol table to find the string with the lowest address above whatever was the previous lowest address. After that full sweep, it would move that string to its new home and adjust pointers to it, then set the new low bound to the string just identified. It would keep iterating until all strings had been visited.
As a result, it required (n2)/2 sweeps of memory (n=# of strings). Having BASIC lock up for 30 seconds every once in awhile was just how it went.
[ and in case someone is going to correct me, it might have swept from top of memory to bottom, I have forgotten the details ]