Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1237

Re: Historical Implementations to Garbage Collectors

Show all headers | View raw

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.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Historical Implementations to Garbage Collectors "lpsantil@gmail.com" <lpsantil@gmail.com> - 2014-05-03 16:02 -0400
  Re: Historical Implementations to Garbage Collectors rpw3@rpw3.org (Rob Warnock) - 2014-05-04 07:04 +0000
  Re: Historical Implementations to Garbage Collectors "Robin Vowels" <robin51@dodo.com.au> - 2014-05-04 19:06 +1000
    Re: Historical Implementations to Garbage Collectors Kaz Kylheku <kaz@kylheku.com> - 2014-05-05 00:47 +0000
      Re: Historical Implementations to Garbage Collectors "Robin Vowels" <robin51@dodo.com.au> - 2014-05-06 01:23 +1000
      Re: Historical Implementations to Garbage Collectors George Neuner <gneuner2@comcast.net> - 2014-05-06 10:55 -0400
        Re: Historical Implementations to Garbage Collectors George Neuner <gneuner2@comcast.net> - 2014-05-07 00:12 -0400
          Re: Historical Implementations to Garbage Collectors "Robin Vowels" <robin51@dodo.com.au> - 2014-05-21 18:37 +1000
            Re: Historical Implementations to Garbage Collectors Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-05-22 13:37 +0200
      Re: Historical Implementations to Garbage Collectors mac <acolvin@efunct.com> - 2014-05-06 18:02 +0000
        Re: Historical Implementations to Garbage Collectors Kaz Kylheku <kaz@kylheku.com> - 2014-05-07 05:34 +0000
  Re: Historical Implementations to Garbage Collectors "Charles Richmond" <numerist@aquaporin4.com> - 2014-05-05 08:28 -0500
    Re: Historical Implementations to Garbage Collectors Gene Wirchenko <genew@telus.net> - 2014-05-06 20:23 -0700

csiph-web