Pete Turnbull wrote:
...
Garbage collection isn't as trivial as one might
think.
I'm not sure if I'm the "one" you are addressing. :-) I am aware that
there are many theses written on the subject. The "best" allocation and
garbage collection algorithm to use is very domain specific.
In the restricted case of MS BASIC, GC isn't very difficult. The root
of all live strings are known, unlike, say C, where you can't tell which
things are pointers, or even if you know it is a pointer, you don't know
if the pointer is valid.
In MS BASIC, all strings are rooted in one of two places: a simple
variable table, or the string evaluation stack, as I described before.
No heuristics are required, just a simple linear sweep. New strings are
simply allocated from the single, unfragmented chunk of memory at the
end of the string pool. (I don't recall if the end is in lower or
higher address of that range though). There is no attempt to have an
intelligent allocator or to coalesce dead fragments (as they aren't
known to be dead until GC time).
There's a
trade-off between space and time,
... and complexity
like in the simple example I gave.