Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Spiros Bousbouras Newsgroups: comp.compilers Subject: Re: Looking for a garbage collection paper Date: Fri, 23 Sep 2022 16:38:26 -0000 (UTC) Organization: Aioe.org NNTP Server Lines: 60 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-09-013@comp.compilers> References: <22-09-011@comp.compilers> <22-09-012@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="96613"; mail-complaints-to="abuse@iecc.com" Keywords: GC, comment Posted-Date: 23 Sep 2022 14:33:26 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com X-Organisation: Weyland-Yutani Xref: csiph.com comp.compilers:3165 On Wed, 21 Sep 2022 09:42:35 +0000 Robert Prins wrote: > On 2022-09-20 09:29, Spiros Bousbouras wrote: > > The book "Garbage collection: algorithms for automatic dynamic memory > > management" by Jones and Lins starts describing on page 197 a concurrent > > garbage collection algorithm by Leslie Lamport and concludes on page 198 with > > : "This colour change is done in a single instruction by an ingenious > > reinterpretation of colour values by incrementing the value of a base colour > > modulo 3: interested readers should consult [Lamport, 1976] for more > > details." > > > > Ok ; if it's ingenious , I want to read it. The reference is > > > > Leslie Lamport > > Garbage Collection with Multiple Processes: an Exercise in Parallelism > > Proceedings of the 1976 International Conference on Parallel Processing, > > T. Feng, ed., 50-54. > > > > I did a bit of googling , arrived at > > http://lamport.azurewebsites.net/pubs/pubs.html and it says "No electronic > > version available". The entry on the page for the above paper references > > "On-the-fly Garbage Collection: an Exercise in Cooperation" and I have > > downloaded that but ideally I would also like to see the above paper. ... > Looks nothing more than what I'm doing in my various tools to convert legacy > languages source to html to colour nested parentheses, in essence: > > colour[0] = 'red' > colour[1] = 'blue' > colour[2] = 'green' > > cur_col = 0 > > and for the next colour: cur_col = (cur_col + 1) mod 3 > > Sources available @ If it were nothing more than that , the book would not have called it ingenious. Obviously it will have to fit with the rest of the algorithm without breaking the invariants which guarantee correctness. It also says "a single instruction". I don't think that cur_col = (cur_col + 1) mod 3 can be implemented in a single instruction in common hardware. > [Sounds right. Keep in mind that this paper is from almost 50 years > ago, and the comments on the web site said it was trivial, written for > a conference where you needed to submit a paper to go, then he went > and decided it wasn't worth it. -John] If the algorithm had been superseded , the Jones/Lins book would have mentioned it. But there is a 2nd edition of the book which I don't have. Lamport doesn't say on his paper that it was trivial but it was a "minor extension". He doesn't say that you needed to submit a paper to go but "To justify my attendance at Sagamore, I always submitted a paper". I don't know to whom he was supposed to justify his attendance , perhaps to himself or some body who was paying his expenses. Finally I don't see what his decision not to bother with the conference any longer has to do with the content of the paper. [Hm, you're right, x+1 mod 3 is not a likely instruction. -John]