Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Where are the calculations that go with a calculated risk?


devel / comp.compilers / Re: Looking for a garbage collection paper

SubjectAuthor
* Looking for a garbage collection paperSpiros Bousbouras
+* Re: Looking for a garbage collection paperRobert Prins
|`* Re: Looking for a garbage collection paperSpiros Bousbouras
| `* Re: Looking for a garbage collection papergah4
|  `* Re: Looking for a garbage collection paperThomas Koenig
|   `* Re: Looking for a garbage collection papergah4
|    `- Re: Looking for a garbage collection papergah4
`- Re: Looking for a garbage collection paperDennis Boone

1
Looking for a garbage collection paper

<22-09-011@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=546&group=comp.compilers#546

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: spi...@gmail.com (Spiros Bousbouras)
Newsgroups: comp.compilers
Subject: Looking for a garbage collection paper
Date: Tue, 20 Sep 2022 09:29:24 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 24
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-011@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="11018"; mail-complaints-to="abuse@iecc.com"
Keywords: GC
Posted-Date: 20 Sep 2022 11:21:19 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Spiros Bousbouras - Tue, 20 Sep 2022 09:29 UTC

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. So I
was wondering whether anyone has a copy. If the algorithm is not too long ,
perhaps they can post it here (as pseudocode) ; or , if they are willing to
scan the paper , contact Lamport and ask him if he would like a scanned
version which he can put on his website.

Re: Looking for a garbage collection paper

<22-09-012@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=547&group=comp.compilers#547

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: rob...@prino.org (Robert Prins)
Newsgroups: comp.compilers
Subject: Re: Looking for a garbage collection paper
Date: Wed, 21 Sep 2022 09:42:35 +0000
Organization: A noiseless patient Spider
Lines: 44
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-012@comp.compilers>
References: <22-09-011@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="95533"; mail-complaints-to="abuse@iecc.com"
Keywords: GC, comment
Posted-Date: 22 Sep 2022 18:44:48 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-09-011@comp.compilers>
Content-Language: en-US
 by: Robert Prins - Wed, 21 Sep 2022 09:42 UTC

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 @ <https://prino.neocities.org/zOS/zOS-Tools.html>

Robert
--
Robert AH Prins
robert(a)prino(d)org
The hitchhiking grandfather - https://prino.neocities.org/
[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]

Re: Looking for a garbage collection paper

<22-09-013@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=548&group=comp.compilers#548

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: spi...@gmail.com (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
 by: Spiros Bousbouras - Fri, 23 Sep 2022 16:38 UTC

On Wed, 21 Sep 2022 09:42:35 +0000
Robert Prins <robert@prino.org> 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 @ <https://prino.neocities.org/zOS/zOS-Tools.html>

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]

Re: Looking for a garbage collection paper

<22-09-014@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=549&group=comp.compilers#549

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: gah...@u.washington.edu (gah4)
Newsgroups: comp.compilers
Subject: Re: Looking for a garbage collection paper
Date: Fri, 23 Sep 2022 12:33:21 -0700 (PDT)
Organization: Compilers Central
Lines: 34
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-014@comp.compilers>
References: <22-09-011@comp.compilers> <22-09-012@comp.compilers> <22-09-013@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="17209"; mail-complaints-to="abuse@iecc.com"
Keywords: GC, history, comment
Posted-Date: 23 Sep 2022 15:52:28 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-09-013@comp.compilers>
 by: gah4 - Fri, 23 Sep 2022 19:33 UTC

On Friday, September 23, 2022 at 11:33:30 AM UTC-7, Spiros Bousbouras wrote:

> > and for the next colour: cur_col = (cur_col + 1) mod 3
> >
> > Sources available @ <https://prino.neocities.org/zOS/zOS-Tools.html>

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

(snip)

> [Hm, you're right, x+1 mod 3 is not a likely instruction. -John]

Maybe not common hardware today, but 50 years ago?

It would seem more likely on a machine with a word size a
multiple of 3, with 36 bit words not so rare 50 years ago.

The PDP-10 byte addressing instructions allow bytes
between 1 and 36 bits. I never learned all the tricks with them,
but if you use 12 bit bytes, the bit offset will cycle 0, 12, 24.

That is, you can sequentially address thirds of
the 36 bit words.

I did do PDP-10 assembly programming, but not quite enough
to learn all the tricks.
[I did a lot of PDP-8 and PDP-10 programming and I am pretty sure
there was no way to do x+1 mod 3 in a single instruction, not even
with tricky IDIVI with an indexed immediate operand. -John]

Re: Looking for a garbage collection paper

<22-09-015@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=550&group=comp.compilers#550

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: drb...@ihatespam.msu.edu (Dennis Boone)
Newsgroups: comp.compilers
Subject: Re: Looking for a garbage collection paper
Date: Fri, 23 Sep 2022 19:39:17 +0000
Organization: Compilers Central
Lines: 10
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-015@comp.compilers>
References: <22-09-011@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="19848"; mail-complaints-to="abuse@iecc.com"
Keywords: history, GC
Posted-Date: 23 Sep 2022 16:00:02 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Dennis Boone - Fri, 23 Sep 2022 19:39 UTC

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

After a bit of digging, our library has these in paper form. I
requested them from off-site storage. We'll see what I get. There
was no apparent trace of the proceedings in IEEE Xplore or ACM DL.

De

Re: Looking for a garbage collection paper

<22-09-016@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=551&group=comp.compilers#551

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: tkoe...@netcologne.de (Thomas Koenig)
Newsgroups: comp.compilers
Subject: Re: Looking for a garbage collection paper
Date: Thu, 29 Sep 2022 13:15:45 -0400 (EDT)
Organization: news.netcologne.de
Lines: 45
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-016@comp.compilers>
References: <22-09-011@comp.compilers> <22-09-012@comp.compilers> <22-09-013@comp.compilers> <22-09-014@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="62738"; mail-complaints-to="abuse@iecc.com"
Keywords: GC, history, comment
Posted-Date: 29 Sep 2022 13:15:45 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Thomas Koenig - Thu, 29 Sep 2022 17:15 UTC

gah4 <gah4@u.washington.edu> schrieb:
> On Friday, September 23, 2022 at 11:33:30 AM UTC-7, Spiros Bousbouras wrote:
>
>> > and for the next colour: cur_col = (cur_col + 1) mod 3
>> >
>> > Sources available @ <https://prino.neocities.org/zOS/zOS-Tools.html>
>
>> 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.
>
> (snip)
>
>> [Hm, you're right, x+1 mod 3 is not a likely instruction. -John]
>
> Maybe not common hardware today, but 50 years ago?
>
> It would seem more likely on a machine with a word size a
> multiple of 3, with 36 bit words not so rare 50 years ago.
>
> The PDP-10 byte addressing instructions allow bytes
> between 1 and 36 bits. I never learned all the tricks with them,
> but if you use 12 bit bytes, the bit offset will cycle 0, 12, 24.
>
> That is, you can sequentially address thirds of
> the 36 bit words.
>
> I did do PDP-10 assembly programming, but not quite enough
> to learn all the tricks.
> [I did a lot of PDP-8 and PDP-10 programming and I am pretty sure
> there was no way to do x+1 mod 3 in a single instruction, not even
> with tricky IDIVI with an indexed immediate operand. -John]

What about

int a[] = {1, 2, 0};

cur_col = a[cur_col];

That would qualify as a single indexed load, provided cur_col
started out with a value between 0 and 2.
[Duh, of course that will work on any word addressed machine. -John]

Re: Looking for a garbage collection paper

<22-09-022@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=557&group=comp.compilers#557

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: gah...@u.washington.edu (gah4)
Newsgroups: comp.compilers
Subject: Re: Looking for a garbage collection paper
Date: Thu, 29 Sep 2022 21:10:30 -0700 (PDT)
Organization: Compilers Central
Lines: 38
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-022@comp.compilers>
References: <22-09-011@comp.compilers> <22-09-012@comp.compilers> <22-09-013@comp.compilers> <22-09-014@comp.compilers> <22-09-016@comp.compilers>
Mime-Version: 1.0
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="34306"; mail-complaints-to="abuse@iecc.com"
Keywords: parallel, comment
Posted-Date: 30 Sep 2022 00:40:56 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-09-016@comp.compilers>
 by: gah4 - Fri, 30 Sep 2022 04:10 UTC

On Thursday, September 29, 2022 at 10:15:49 AM UTC-7, Thomas Koenig wrote:

(snip)

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

(snip, I wrote)

> > It would seem more likely on a machine with a word size a
> > multiple of 3, with 36 bit words not so rare 50 years ago.

(snip)

> What about
>
> int a[] = {1, 2, 0};
>
> cur_col = a[cur_col];
>
> That would qualify as a single indexed load, provided cur_col
> started out with a value between 0 and 2.
> [Duh, of course that will work on any word addressed machine. -John]

A word addressed machine with an indexed load.

Or a machine with indexed load that scales for the size, like VAX.

Or a table of bytes, so the index unit is 1.

But not if index registers are different from other registers, like
(if I remember) they are on the 7090.
[Yes, the 704 series had separate index registers. It occurs to me that
another way to do this is to use the rotate instructions the 70x and PDP-6/10
had. Since the word is 36 bits, you rotate by 12 each time and you'll have
three bit patterns. -John]

Re: Looking for a garbage collection paper

<22-09-023@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=558&group=comp.compilers#558

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: gah...@u.washington.edu (gah4)
Newsgroups: comp.compilers
Subject: Re: Looking for a garbage collection paper
Date: Thu, 29 Sep 2022 23:56:42 -0700 (PDT)
Organization: Compilers Central
Lines: 21
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-09-023@comp.compilers>
References: <22-09-011@comp.compilers> <22-09-012@comp.compilers> <22-09-013@comp.compilers> <22-09-014@comp.compilers> <22-09-016@comp.compilers> <22-09-022@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="16871"; mail-complaints-to="abuse@iecc.com"
Keywords: architecture, history, comment
Posted-Date: 30 Sep 2022 21:31:52 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-09-022@comp.compilers>
 by: gah4 - Fri, 30 Sep 2022 06:56 UTC

On Thursday, September 29, 2022 at 9:40:59 PM UTC-7, gah4 wrote:

(snip)

> But not if index registers are different from other registers, like
> (if I remember) they are on the 7090.

> [Yes, the 704 series had separate index registers. It occurs to me that
> another way to do this is to use the rotate instructions the 70x and PDP-6/10
> had. Since the word is 36 bits, you rotate by 12 each time and you'll have
> three bit patterns. -John]

or a ROTC double word rotate on the PDP-10 by 24, with 18 bit addressing
and indexing.

I am not sure about rotate on the 709 or 7090.

Also, for those machines, I suspect a 12 bit shift or rotate takes 12 cycles.
They didn't have enough logic for a barrel shifter, like many machines now have.
Might be slower than more than one fast instruction.
[The 709x had a rotate instruction but this archaeology is a bit far from compilers. -John]

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor