Re: Historical Implementations to Garbage Collectors

Kaz Kylheku <kaz@kylheku.com>
Mon, 5 May 2014 00:47:04 +0000 (UTC)

          From comp.compilers

Related articles
Historical Implementations to Garbage Collectors lpsantil@gmail.com (lpsantil@gmail.com) (2014-05-03)
Re: Historical Implementations to Garbage Collectors rpw3@rpw3.org (2014-05-04)
Re: Historical Implementations to Garbage Collectors robin51@dodo.com.au (Robin Vowels) (2014-05-04)
Re: Historical Implementations to Garbage Collectors kaz@kylheku.com (Kaz Kylheku) (2014-05-05)
Re: Historical Implementations to Garbage Collectors numerist@aquaporin4.com (Charles Richmond) (2014-05-05)
Re: Historical Implementations to Garbage Collectors robin51@dodo.com.au (Robin Vowels) (2014-05-06)
Re: Historical Implementations to Garbage Collectors gneuner2@comcast.net (George Neuner) (2014-05-06)
Re: Historical Implementations to Garbage Collectors acolvin@efunct.com (mac) (2014-05-06)
Re: Historical Implementations to Garbage Collectors genew@telus.net (Gene Wirchenko) (2014-05-06)
Re: Historical Implementations to Garbage Collectors gneuner2@comcast.net (George Neuner) (2014-05-07)
[3 later articles]
| List of all articles for this month |

From: Kaz Kylheku <kaz@kylheku.com>
Newsgroups: comp.compilers
Date: Mon, 5 May 2014 00:47:04 +0000 (UTC)
Organization: Aioe.org NNTP Server
References: 14-05-001 14-05-009
Keywords: GC, history
Posted-Date: 04 May 2014 21:23:41 EDT

On 2014-05-04, Robin Vowels <robin51@dodo.com.au> wrote:
>: <lpsantil@gmail.com> wrote:
>> I'm interested in studying historical implementations of garbage
>> collection in early programming languages (BASIC, Lisp, etc). I'm
>> especially interested in language/runtime interface descriptions.
>> Does anybody have references they can share?
>
> McKeeman, Horning, and Wortman's XPL compiler used garbage
> collection for strings on S/360. Collection was automatic
> and invisible to the user.
>
> No tags were needed.


Why would there be tags; strings don't point to other strings. There are no
arcs or cycles in the graph. You never have to solve the problem "has the
garbage collector already visited this string", since you can use a handles to
keep track of strings---hence there is no need to walk the graph of non-string
objects in order to find strings; just the array or list of string handles,
where no two handles reference the same string.


String-only garbage collection is relatively trivial and uninteresting.
The general idea behind compacting allocation is usually: sort the strings in
by address and blit them to one end of the string arena.
If compaction isn't the chosen approach, then the sorted list of strings can
instead be used used to identify the free space between the strings and put them into a free
list for new string allocations.


Post a followup to this message

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