Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newspeer1.nac.net!border4.nntp.dca.giganews.com!backlog4.nntp.dca3.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: Kaz Kylheku Newsgroups: comp.compilers Subject: Re: Historical Implementations to Garbage Collectors Date: Mon, 5 May 2014 00:47:04 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 26 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-05-012@comp.compilers> References: <14-05-001@comp.compilers> <14-05-009@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: miucha.iecc.com 1399253021 49774 2001:470:1f07:1126:0:676f:7373:6970 (5 May 2014 01:23:41 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Mon, 5 May 2014 01:23:41 +0000 (UTC) Keywords: GC, history Posted-Date: 04 May 2014 21:23:41 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com X-Original-Bytes: 2332 Xref: csiph.com comp.compilers:1237 On 2014-05-04, Robin Vowels wrote: >: 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.