Re: Historical Implementations to Garbage Collectors

X-Received	by 10.182.105.1 with SMTP id gi1mr6742923obb.6.1399679621681; Fri, 09 May 2014 16:53:41 -0700 (PDT)
Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!c1no3894521igq.0!news-out.google.com!dz10ni37437qab.1!nntp.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From	George Neuner <gneuner2@comcast.net>
Newsgroups	comp.compilers
Subject	Re: Historical Implementations to Garbage Collectors
Date	Wed, 07 May 2014 00:12:15 -0400
Organization	A noiseless patient Spider
Lines	40
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<14-05-021@comp.compilers> (permalink)
References	<14-05-001@comp.compilers> <14-05-009@comp.compilers> <14-05-012@comp.compilers> <14-05-017@comp.compilers>
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
X-Trace	miucha.iecc.com 1399679620 39850 2001:470:1f07:1126:0:676f:7373:6970 (9 May 2014 23:53:40 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Fri, 9 May 2014 23:53:40 +0000 (UTC)
Keywords	GC, history
Posted-Date	09 May 2014 19:53:40 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Xref	csiph.com comp.compilers:1246

Show key headers only | View raw

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

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