Re: Historical Implementations to Garbage Collectors

From: "George Neuner" <gneuner2@comcast.net>
> Our esteemed moderator wrote:


>>[You don't need anything that fancy for strings to overlap. With null
>>terminated readonly C-style strings, you can combine "storage" and
>>"rage" and "age". Wih strings represented by a pointer and length,
>>they can overlap anywhere.
>
> Yes. Tricks like that were used frequently in memory constrained
> implementations.


I wouldn't call it a "trick". It's a carefully-planned algorithm.


> Pointer:length pairs permit multiple use of substrings, but don't
> permit constructing a new string from arbitrary pieces of existing
> ones. The tree representation can permit completely arbitrary
> substring sharing.


The overheads of that would be intolerable. The address-length
pair is simple to use, can be passed easily as an argument
(and returned easily from a function), and there is -- essentially --
no overhead until the dynamic string space gets used up,
after which garbage collection is necessary.


> Of course, given the small amount of memory available to early
> implementations, tree representation of strings would have been
> unworkable.


Even with lots of memory, not really a proposition on account of
overheads. With lots of memory, the garbage collection routine
might not even be called.
--
This email is free from viruses and malware that avast! Antivirus
protection knows about, but is likely riddled with ones that it
doesn't.

Return to the comp.compilers page.
Search the comp.compilers archives again.