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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, 21 Sep 2022 09:42:35 +0000
Robert Prins <[email protected]> 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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

gah4 <[email protected]> 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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)