Re: Historical Implementations to Garbage Collectors

Our esteemed moderator wrote:




On Tue, 06 May 2014 10:55:03 -0400, George Neuner
<gneuner2@comcast.net> wrote:
>>
>>https://en.wikipedia.org/wiki/Rope_%28data_structure%29
>>


>[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.


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.


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




>To garbage collect those I'd think you'd need a per cell bitmap,
>unless you knew everything was 7-bit ASCII and used the high bit
>as the flag. -John]


Use of the high bits would be more likely because a separate bitmap
would require additional space equal to 1/8th of the string space.


However, further widening the "pointer" to a pointer:offset:length
triple would enable collection, and also compaction, of the string
space using Deutsch-Schorr-Waite on the pointers without having to
mark the characters at all.


George

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