Why were OS/360 PL/I procedure calls so expensive in terms of stack space?

Question

In 1977, Guy Steele published a paper entitled Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO. The paper was the fourth in a now-famous series known as the Lambda the Ultimate papers, which discussed the design and implementation of the Scheme programming language. In the paper, Steele describes the poor performance of procedure calls on what was then a state-of-the-art optimizing compiler:

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! Yourdon [You75,98] reports that on a 360/50 a PL/I procedure call costs 198 microseconds. It is no wonder that programmers feel that procedure calls are slow — they are!

Following the citations does not provide much insight into why so much space was used. Aus76 points to Systematic recursion removal, which merely mentions the size of the stack frames in passing. You75 appears to be a textbook, which I could not find online, but it is unlikely to go into such details, either.

This leaves one wondering why precisely this system’s procedure calls were so expensive in stack space. Steele provides a few broad possible explanations, and broadly speaking, I understand the most likely factors at play: word sizes were large (for the time), I suspect the calling convention was not particularly efficient, and I imagine register allocation was unsophisticated and resulted in lots of unnecessary spilling. Still, even considering those factors, 336 bytes is quite a lot for a supposedly “simple” call. What were all those bytes actually used for? And how many more bytes did OS/360 PL/I use for this procedure call relative to an equivalent in contemporary MacLISP?

(Note: I have cross-posted this question from PLDI because it failed to attract answers there and people suggested this might be a better fit.)

Answer 1

There's a lot of information you can dig out of the IBM OS PL/I Optimizing Compiler: Execution Logic manual - this is a 1985 version (release 5) while the GLSteele papers were from 7-8 years earlier; still, the /360 didn't change though the compiler may have done.

The whole manual is impossibly informative, but I direct your attention to the section beginning at page 32: "Prolog And Epilog Code". It starts describing the dynamic save area ("DSA") - with a diagram of it on page 34.

There's a lot of stuff in there - most of it optional and only present if the procedure requires it.

I suspect that the "simple procedure call" actually had arguments and locals and that's where some of the 366 bytes went.

Also PL/I had richer variable scoping than more modern C-based languages. Like Pascal and Ada it needed both static and dynamic scope chains.

Elsewhere the document describes handling of variables, compiler-generated temporaries, and lots of other stuff.

And also there's "Chapter 4: Communication Between Routines" (starting on page 64), which is all about control blocks for descriptors and other data for describing the rich and dynamically sized data structures that PL/I supported and goes into great detail about argument and result passing.

All in all the document is fascinating. It's not a tutorial on /360 programming but you'll sure as hell learn a lot about how IBM's best compiler writers thought to use it.

(Of particular interest to me was page 27 where it describes how you address beyond the 4K limit (meaning the 12-bit displacement field in an instruction). They basically create a table, in the first 4K addressable by R6, which points to the dividing lines to all the other 4K chunks of addressable area you need.)

(This is interesting to me because when designing, at Rational, the run-time model for Ada for a bare /370 I had to deal with frames on a machine with no stack. Yet the Rational compiler - as did most compilers - kind of assumed you'd have a "frame pointer" register where you'd have negative offsets for arguments and positive for variables. The way I did it was to dedicate one of the registers, R0 as it happens, to hold -4096 at all times. Then with an index+displacement instruction I could access [-4096..-1] off the frame pointer - negative offsets! - nearly as easily as I could get to positive offsets.

(Another "advantage" of no stack hardware was that you could make lemonade out of that lemon when creating the run-time model for Ada threads ... as long as you had to create the stack yourself you could create a cactus stack as well ...)

Answer 2

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:

1. So with both needing about the same amount of total storage, no real memory overhead of the stack based solution can be seen.

2. The 336 bytes do seem to be a value averaged over the iterated graphs divided by call depth.

3. Not the total number of all iteration in both procedures was used as divisor, but only the times the higher (CIRCUIT) was called.

4. 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.

---

Bottom Line:

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.

Answer 3

I wrote assembler code for a 370 during a previous life, and I used a standard IBM macro (whose name I have forgotten) for every function call, and it's companion macro for return. As @raffzahn has already noted, there is no hardware stack, so the macro used a linked list to save all 16 registers, so there is a fair amount of overhead in each call, before you get around to doing any PL/1 stuff. I suppose I could have kept track of the registers that I was going to use, and done something more efficient, but the edit-compile-execute cycle was fairly slow, so I went for reliability rather than machine efficiency.