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

Groups > comp.compilers > #1226 > unrolled thread

Historical Implementations to Garbage Collectors

Back to article view | Back to comp.compilers

Contents

  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

#1226 — Historical Implementations to Garbage Collectors

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?

[My LISP 1.5 manual says they used a straightforward mark and sweep
GC.  The only complication was that list storage cells had a free bit
they could use for marking, while cells used for strings didn't so
it was a separate area and they used a separate bitmap.  I'm fairly
sure that early Dartmouth BASIC was all static allocated, no GC. -John]

[toc] | [next] | [standalone]

#1231

lpsantil@gmail.com <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?
+---------------

Not so much "history" per se, but you might be interested in Paul
Wilson's fairly comprehensive survey of GC techniques: circa 1992 [the
PDFs aren't from Wilson AFAIK, but seem to be accurate AFAICT]:

    ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps
      http://www.cs.rit.edu/~swm/cs800/gcsurvey.pdf
      http://www.maths.lse.ac.uk/Courses/MA407/gcsurvey.pdf

This is a very expanded version of the above circa 1994:

    ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps
      http://www.cs.rit.edu/~swm/cs800/bigsurv.pdf
      http://www.cs.rice.edu/~javaplt/311/Readings/bigsurv.pdf

-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

[toc] | [prev] | [next] | [standalone]

#1234

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

See "A Compiler Generator", McKeeman, Horning, and Wortman.
--
This email is full of viruses and malware because avast! Antivirus protection is overrated.
http://www.avast.com

[toc] | [prev] | [next] | [standalone]

#1237

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.

[toc] | [prev] | [next] | [standalone]

#1241

 "Kaz Kylheku" <kaz@kylheku.com>
> 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;

I mentioned it only only because John mentioned tags in one implementation
that he cited.

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

In the XPL implementation, multiple references [handles] to the same string can occur.
Furthermore, strings can overlap; that is, two or more handles can point to
different parts of the same string.

--
This email is longer than it should be because avast! Antivirus protection is active.
http://www.avast.com

[toc] | [prev] | [next] | [standalone]

#1242

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

>Why would there be tags; strings don't point to other strings.

Though unlikely to be found in an older system due to memory
constraints, there are string representations which can share
structure: e.g.,
https://en.wikipedia.org/wiki/Rope_%28data_structure%29

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

[toc] | [prev] | [next] | [standalone]

#1246

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

[toc] | [prev] | [next] | [standalone]

#1250

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.

[toc] | [prev] | [next] | [standalone]

#1251

Robin Vowels schrieb:
> From: "George Neuner" <gneuner2@comcast.net>

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

Just a note:

I found tree representations for strings in editors, implementing
unlimited Undo. Obviously such applications are not related to small
memory nor to garbage collection.

DoDi

[toc] | [prev] | [next] | [standalone]

#1244

By the 1970s (basic 6th edition) at Dartmouth, strings were garbage
collected, much ike XPL mentioned here. A form of subroutine supported
recursion with local variables, so the string pool was not static. instead
all string variables were marked ( possibly kept on a linked list). To GC,
the runtime marked and compacted all referenced string text.

String text was simple contiguous storage with no embedded pointers, so
this was straightforward - unlike some languages, where strings were linked
lists of fragments.

The runtime system borrowed the teletype (stdout) buffer for temporary
storage during GC. The same trick was used for Dartmouth XPL.
--
mac the naC/f

[toc] | [prev] | [next] | [standalone]

#1247

On 2014-05-06, mac <acolvin@efunct.com> wrote:
> The runtime system borrowed the teletype (stdout) buffer for temporary
> storage during GC. The same trick was used for Dartmouth XPL.

So if debug prints were needed out of the GC itself, the device
could be used unbuffered?
[If you needed to.  Things worked a lot better if you wrote in large chunks so you
didn't have to get swapped in for each character. -John]

[toc] | [prev] | [next] | [standalone]

#1240

<lpsantil@gmail.com> wrote in message news:14-05-001@comp.compilers...
> 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?
>
> [My LISP 1.5 manual says they used a straightforward mark and sweep
> GC.  The only complication was that list storage cells had a free bit
> they could use for marking, while cells used for strings didn't so
> it was a separate area and they used a separate bitmap.  I'm fairly
> sure that early Dartmouth BASIC was all static allocated, no GC. -John]

In the Microsoft BASIC used in the TRS-80, there is a bug in the string
garbage collection.  As far as I know, this was *never* corrected, but as
the string space fills... the GC fails way too soon.  This is sort of
historic, as the TRS-80 was using MS BASIC in the early 1980's.
--

numerist at aquaporin4 dot com

[toc] | [prev] | [next] | [standalone]

#1245

On Mon, 5 May 2014 08:28:48 -0500, "Charles Richmond"
<numerist@aquaporin4.com> wrote:

[snip]

>In the Microsoft BASIC used in the TRS-80, there is a bug in the string
>garbage collection.  As far as I know, this was *never* corrected, but as
>the string space fills... the GC fails way too soon.  This is sort of
>historic, as the TRS-80 was using MS BASIC in the early 1980's.

     I never heard of that, and I would appreciate details as I had a
TRS-80.  Microsoft made many of the BASICs of the time.  Was this bug
in all of them?  Most of them?  Just for the TRS-80?

Sincerely,

Gene Wirchenko

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web