The lost art (Was: The VAX is running

[Jim Battle]

Jochen Kunz wrote:
> On Mon, 06 Apr 2009 17:37:08 -0500
> Jim Battle <frustum at pacbell.net> wrote:
> 
>> Recursion will eat up a lot of memory if the list is long.
> Not necessarily: http://en.wikipedia.org/wiki/Tail_recursion

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.