TL;DR: Code is Law -or- Never Trust Citations, RTFSM
(Read the Fine Source Material)
Auslander and Strong [Aus76] report that one simple procedure call, compiled by the OS/360 PL/I optimizing compiler, pushes 336 bytes onto the stack!
Sounds like a clear find, doesn't it? So a look at the 1968 PL/1 or 1971 manual for the /360 shows that the minimum DSA (Dynamic Storage Area *1)) consists of 20 words (80 bytes) for register storage and linkage. This is a fixed size not at least for compatibility with other languages. The DSA frame of a procedure needs to hold all variables and work areas (intermediate values) of that procedure. That may include otherwise not visible parts like areas for parameter lists for further calls (*2) and so on.
Obviously PL/1 calling conventions per se can't be a reason.
Now, one could assume that the local variables and parameter lists of that recursive procedure could fill up the missing 256 bytes (BTW, interesting value, isn't it? *3). Looking at the code presented in that [Aus76] paper (*4) shows that neither of the two recursive procedures holds a real lot of local storage.
But wait, there are two? Yes, two, one (CIRCUIT) that is called from main (C_FIND), which calls itself (CIRCUIT) recursive and does as well call the second (UNBLOCK), which in turn also calls itself (UNBLOCK) as well. Nicely shown by a picture:
(P.129 of [Aus76])
So, which is the 'simple procedure call' are they talking about and where does that number originate?
The original paper does as well not offer more insight. It states in Section IV. Results (p.134):
The implementation of the recursive stack costs PL/I 336 bytes per level of recursive call, with the maximum depth call being the number of vertices of the graph.
Without telling which of those recursive routines it is about or if it's about both or at a certain level. Without a clarification what the mentioned 336 bytes are related to, no clear answer can be given.
But the paragraph continues (still p.134):
The transformed program requires 9 bytes of storage per level of call. The total storage used was about 55000 bytes for both versions.
This seems like a great hook to attach some plausible conclusions:
So with both needing about the same amount of total storage, no real memory overhead of the stack based solution can be seen.
The 336 bytes do seem to be a value averaged over the iterated graphs divided by call depth.
Not the total number of all iteration in both procedures was used as divisor, but only the times the higher (CIRCUIT) was called.
Thus the number represents the memory required by one call of CIRCUIT plus the average of all included UNBLOCK DSA frames.
Conclusiones 3 and 4 are as well supported by the authors focusing on the CIRCUIT procedure for all explanation.
They continue (still p.134):
Thus the size differences we report support our theoretical expectation but are unimportant in practice.
Which further underlines that space reduction was neither goal nor result of that research.
Reading the original paper can outwight any assumption done by browsing some citation.
This is especially important when it's about ancient technology and papers, written at a time before today's canon was settled and with different intention.
Further background information related to pints in the question:
The /360 is a stackless machine. That means each and every stack operation is at least two machine instructions per allocation plus one per item stored/taken.
Except, I would expect that the code generated follows the standard scheme IBM uses, which means at least a dozend or two instructions filling up various values, do bookkeeping (like noteing the procedure number/name).
The /360-50 is quite at the low end of that time and incredible slow by today's standards.
The fastest instruction possible (32 bit register register OP) takes about 3 µs.
Regular memory based operation anywhere between 10 and 100 µs.
Its memory bandwidth is ~2 MB/s. (4 byte every 2 µs). This includes code fetch which is 2,4 or 6 byte per instruction (1..3 µs)
Saving all 16 registers is a single instruction (well two with calling convention) and will need at least 2 reads (4µs) and 16 stores. Same for reloading, which gives a lower boundary of 72 µs just for register save.
Looking at the Prolog/Epilog code shown on p.32..36 of the 1985 Optimizing Compiler Execution Logic Manual, one can see a need of ~38 memory transactions (read or write) to execute that code. Together with above 36 this adds up to 74 or 148 µs just for the memory access. With that base a call overhead of 198 µs does seem a good mach. Hard to optimize that any further (*5).
There is no cache or other means of access optimization (beside basic word size buffers)
Now looking at the mentioned papers gives better perspective:
Filling 336 byte into a new stack entry might alone take 168 µs,not considering fetch of code or data.
As mentioned that stack holds a full register set, which alone is 64 bytes (and >32 µs).
198 µs might sound a lot by today, but for that machine it's just a few instructions. Considering that creating a standard 80 byte DSA frame already explaind a good part thereof
At this point it may be worth to note that one of the goals for PL/1 was to be easy translated into efficient machine code. Most of its statements can be directly translated in a few, often not more than 1-4 /360 instructions.
Of course all of that becomes moot when noting that the original paper [Aus74] states (p.133 right side):
This experiment was done using the PL/I optimizing compiler run under OS/360 MVT on an S/360 Model 91.
The Model 91 was the fastest /360 there was in 1968, only beaten by CDC's 6600 (and only in FP). It performed anywhere between 20 and 50 times faster than a Model 50 (*6).
Now for the software side one item may be obvious
- Looking at the [Aus76] paper it seems to me that their 'trick' is to eliminate recursion at all and replace the stack by several arrays.
I would assume as common knowledge that recursion is, in real life terms, always the worst way to iterate. Eliminating recursion will bring considerable speedup almost independent of ISA type and machine generation.
*1 - A DSA is not just IBM lingo for a stack but a linked list. It is in no way handled by some CPU provided management. Also linking does work a bit different than one would build it today, but that's a different story.
*2 - (IBM) PL/1 works by default by building a parameter list and handing over a single address pointer. Thus any call parameter must be build in memory, usually in the DSA of the caller (a must for recursion).
*3 - Usually a value that should call immediate attention - but in this case it may be more of an artefact due the size of certain variables that add up to beautiful multiples of 2.
*4 - Always look at the paper itself, not just some abstract.
*5 - I'm a long time /370 Assembly programmer and I may have a hard time to cut that down much.
*6 - It is a very interesting machine when looking back as it features many details that only became common with micros more than 30 years later, like multiple parallel units for integer, FP and other instructions, or multiple independent memory controllers, each again working 16 times interleaved, delivering a memory bandwidth of up to 133 MB/s. It was so advanced that it took about 10 years until similar performance was average for large mainframes.