Paradigm for (repeated) use of PDP-10 indirect bit

Question

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?

Answer 1

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.

Answer 2

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.