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 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> 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 Our esteemed moderator wrote: On Tue, 06 May 2014 10:55:03 -0400, George Neuner 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