The lost art (Was: The VAX is running

Jochen Kunz wrote: Jochen -- First, I'd argue that then you aren't doing recursion; you have transformed recursion into iteration. For the stated problem, using recursion requires creating a stack frame for each node in the list, chewing up a lot of memory. It could be transformed into an iterative operation by having an auxiliary list to save the address of each node as you traverse the list, but that is eating up memory too (though likely much less than a stack frame per node). My proposed solution for low memory situations is iterative, but requires only a small, fixed amount of working space. /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ This is only tangentially related, but it is connected by the need to use a small, fixed amount of scratch space to operate on large lists of data. Once upon a time, I disassembled a lot of the TRS-80 model III ROM. Part of that was the garbage collection routine. Because strings were dynamically allocated without any explicit recovery mechanism, the interpreter would on occasion have to sweep dead strings from memory. This gave the appearance of locking up the computer for long stretches -- the amount of time varied based on the amount of free memory and the number of active strings. It could easily take more than half a minute. The code was written to use the tiniest amount of scratch space. The garbage collector was something like this. One pointer was used to sweep through the variable table, looking for all strings, and after it swept the variable table, it would also sweep through the the currently active expression stack to find live strings there too. It would find the string with the lowest address and move the string at that location to the start of free string memory if it wasn't already located there, and patch up the variable table or expression stack to point to the new location. Then a second round was done, again looking for the lowest string address it could find which was also greater than the address just found in the previous iteration. On and on it would go until no new string was found. This is a classic O(n^2) algorithm, which is why the thing ran so slowly. I seem to recall it required only four bytes of storage other than using the CPU registers to do this sweep. If instead of waiting to do garbage collection until there was only four bytes left it invoked the garbage collector when, say, 64 bytes were left, they could have swept 16 live strings per pass. It would still be O(n^2), but it would have finished roughly 16 times faster. I'm pretty sure other MS BASICs used the same simple & slow garbage collector. I wonder how hard it would have been to put in an incremental garbage collector that ran during input prompts, and perhaps even while waiting for disk I/O. It wouldn't have helped the worst case, but it would have helped in the average case.