In Guy Steele’s famous paper Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, he 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 things were so bad. 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. Steele provides a few broad possible explanations, but 336 bytes is quite a lot for a supposedly “simple” call. What were all these bytes used for? And how many more bytes did OS/360 PL/I use for this procedure call relative to an equivalent in MacLISP?

  • 8
    $\begingroup$ This might be better asked on Retrocomputing. $\endgroup$ Jul 24, 2023 at 19:26
  • $\begingroup$ Looking at the IBM System/360 calling convention it seems each procedure allocates enough space for its callees to save all of the registers, so that’s 72 bytes (16 32-bit registers, plus the 64-bit program status word) but I don’t know where the rest comes from. $\endgroup$
    – Jon Purdy
    Jul 24, 2023 at 19:45
  • $\begingroup$ I was looking for the You75 reference and I found a very harsh review which reads like something some clinically online troll would write. google.com/… but it's from Dijkstra $\endgroup$
    – coredump
    Jul 24, 2023 at 20:28
  • 1
    $\begingroup$ I think that the answer will ultimately boil down to the fact that the IBM System/360 was designed back in 1964, when the very concept of "procedure calls" (especially recursive ones) was new, and neither hardware nor compiler designers really understood how to implement them efficiently. $\endgroup$
    – dan04
    Jul 25, 2023 at 21:35
  • 4
    $\begingroup$ @dan04 This may be true, but I’d still like to understand the specific way in which the compiler failed to do a good job. Also, it’s worth saying that MacLISP, presented as an alternative in the paper that does a much better job, dates back to 1966, so it’s not as though such things were unheard of back then. $\endgroup$
    – Alexis King
    Jul 25, 2023 at 22:01


You must log in to answer this question.

Browse other questions tagged .