9

Answers to question PDP-10 effective address calculation explain how PDP-10 effective address calculation works, including potentially infinite indirections.

However the answers don't address how this feature would be typically used, and to what extremes. Was it common to use more than, say, two indirections for some particular programming paradigm or data structure (or design pattern as one might say these days).

One kind of application I could imagine is a garbage collector which moves allocated memory blocks around, without the users of that memory being aware of it. To hide this fact, it fiddles with pointers to the memory by adding another step of indirection ("any problem can be solved by adding another layer of indirection"). Were there such memory management schemes?

What other clever uses are there of multiple-to-infinite levels of indirection?

Improve this question
4
  • 2
    The obvious usage is to store pointers with I set, and then de-reference them in a single instruction, instead of using two instructions. But I am very curious, too, if other clever ways of using this were invented.
    – dirkt
    Aug 30, 2020 at 11:35
  • 2
    I wrote a garbage collector for MDL, a Lisp like language, in 1971-1972. My recollection is kind of dim, but I don't recall making use of multiple level indirection. Instead, we had a pointer update phase. en.wikipedia.org/wiki/MDL_(programming_language)
    – Walter Mitty
    Aug 30, 2020 at 13:45
  • As an enthusiastic PDP-10 dilettante that has spent years staring at PDP-10 code, I can honestly say I can't remember having seen even two levels of indirection. Contrived examples can be thought up, but in real life? Not so likely.
    – Lars Brinkhoff
    Aug 31, 2020 at 13:47
  • 1
    I only ever saw two. But I did see a very interesting use where you would XCT with the indirect bit on to a word with the indirect bit on to finally get to the instruction to execute. I'm wracking my brain to remember the context - was it some kind of threaded interpreter as @another-dave suggests in his answer or something else? This will keep me preoccupied the rest of the day ..
    – davidbak
    Sep 1, 2020 at 16:08

2 Answers 2

Reset to default
5

It might be useful in indirect threaded code. This is a contrived example based on my brief 45-years-ago acquaintance with a Snobol4 implementation (Macro Spitbol - Dewar and McCann).

Consider that each statement is compiled into a sequence of 'code objects', each of which contains some standard attributes and also a pointer to the (fixed per type of code object) body of code that implements the operation -- such as a pattern match -- required by the code object.

The whole program is a list of addresses of code objects. Execution proceeds as a sequence of jumps to the actual code. We start by jumping to the first piece of actual code, which does its thing and then jumps to the successor.

This can be handled by multilevel indirection. In pseudocode:

; compiled user program

codeobj1: 
   @actualCode1
   blah
   blah

codeobj2:
   @actualCode2
   mumble
   mumble

userprog:
   @codeobj1
   @codeobj2
    :
    :

; standard stuff

start:
   movei ptr,userprog
   jump @ptr

actualcode1:
   ...
   increment ptr ; or set it, for 'goto'
   jump @ptr 

actualcode2:
   ...
   increment ptr 
   jump @ptr

Having made all that up, I don't know if the TOPS-10 version actually made use of multiple-level indirection. The compiler was written in MINIMAL, a machine-independent macro assembly language designed for SPITBOL implementation, which was then translated into a target assembly language. The translator from MINIMAL to MACRO-10 would have to recognize the possibility of using indirect chains.

Improve this answer
1

I can think of a potential use of multiple level indirect addressing.

It has to do with accessing a single cell in a multidimensional array. If we have a three dimensional array A, and we want to access cell A(7, 3, 8). We have to figure out what address that's located at, relative to some base address called, say, ABASE.

The classical way you go about doing this is by doing some address arithmetic. You take the first index, 7 subtract 1 from it (assuming indexes begin at 1 as in Fortran), multiply by the size of the second dimension, now add 3 (maybe minus 1) to that, multiply by the size of the third dimension, and add 8 (maybe minus 1) to that. Finally multiply by the cell size if the cell size is larger than 1 word. Now you have the offset of the desired address from the base address ABASE of the array. (Unless I've made a mistake in the above).

Anyway, it's a whole lot of work, and it takes a considerable amount of time. If you start doing millions of references to a large array, we're talking hours of compute time here.

There is a faster way, using multiple level indirection, and referencing an accumulator in the index field. This requires auxiliary data structures to be set up when the array is constructed. These auxiliary data structures have the indirect bit set (except for the lowest level), and reference some accumulator in the index field.

The top level auxiliary has one entry per possible value of the first index, let's say 20, It has the form:

@ABASE2+x(B).

where ABASE2 is the base address for the second level auxiliary structure, B is one of the accumulators used as an index register and X is some offset that I'm too lazy to figure out.

The second layer of auxiliary structure might have the form:

@ABASE3+y(C)

And the third level auxiliary points to one the cells as follows:

 ABASE+ z

Where Z is some multiple of the cell size.

Now, if you do:

 MOVEI A, 6
 MOVEI B, 2
 MOVEI C, 7
 MOVEI D, @ABASE1(A)

what happens is that A selects the seventh entry in ABASE1, which selects the third entry in ABASE2, which selects the eighth entry in ABASE3, which points to the desired address somewhere in ABASE, the array itself.

It's awfully complicated sounding, and I would hate to implement it with my tired old brain, but it runs faster than doing all the address arithmetic at run time.

It also requires extra memory to hold the auxiliaries. This is similar to the way a B-TREE index to a table requires extra space in a database.

What I do not know is whether any of the third generation languages, like Fortran or Algol, ever employed this technique on the PDP-10.

Improve this answer
2
  • The disadvantage of that approach of course is that if you have an array with k dimensions, you need k-1 tables of pointers, which waste a lot of space. If each dimension has n entries, you need ca. n^(k-1) space for the pointers, compared to n^k space for the data itself.
    – dirkt
    Aug 31, 2020 at 12:32
  • That is indeed a disadvantage. A second disadvantage is that it takes longer to construct an array, because all these pointer tables have to be constructed and populated. Whether the benefits outweigh the disadvantages depends on how you use the data.
    – Walter Mitty
    Aug 31, 2020 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .