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

Groups > comp.compilers > #3163 > unrolled thread

Looking for a garbage collection paper

Back to article view | Back to comp.compilers

Contents

  Looking for a garbage collection paper Spiros Bousbouras <spibou@gmail.com> - 2022-09-20 09:29 +0000
    Re: Looking for a garbage collection paper Robert Prins <robert@prino.org> - 2022-09-21 09:42 +0000
      Re: Looking for a garbage collection paper Spiros Bousbouras <spibou@gmail.com> - 2022-09-23 16:38 +0000
        Re: Looking for a garbage collection paper gah4 <gah4@u.washington.edu> - 2022-09-23 12:33 -0700
          Re: Looking for a garbage collection paper Thomas Koenig <tkoenig@netcologne.de> - 2022-09-29 13:15 -0400
            Re: Looking for a garbage collection paper gah4 <gah4@u.washington.edu> - 2022-09-29 21:10 -0700
              Re: Looking for a garbage collection paper gah4 <gah4@u.washington.edu> - 2022-09-29 23:56 -0700
    Re: Looking for a garbage collection paper drb@ihatespam.msu.edu (Dennis Boone) - 2022-09-23 19:39 +0000

#3163 — Looking for a garbage collection paper

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.

[toc] | [next] | [standalone]

#3164

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]

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

#3165

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]

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

#3166

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]

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

#3168

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]

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

#3174

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]

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

#3175

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]

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

#3167

 >     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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web