Re: When/why did function calls get cheap?

Short answer from one who watched it happen: It was the stack.


The old IBM mainframes didn't have a stack pointer or other hardware
to support a call stack. They used register 14, as I recall, as a
dedicated register pointing to the return address. Sort of a
one-level stack. If your subroutine called another subroutine, it had
to save off register 14 in memory first, then restore it after
returning from the next level down.


The only way to pass parameters was to put them in static RAM
addresses. All the old IBM Fortran compilers had separate parameter
blocks for each subroutine called. There was code overhead to store
the parameters there before calling, and retrieve them from there
after.


AIR, minicomputers were the first to have stack pointers and
call/return mechanisms in hardware. But what really made it efficient
was the advent of the microprocessor.


I don't think many people appreciate what great strides Intel made
when they introduced the 8080. At the time, the notion of a computer
with built-in support for a 64k stack was unheard of. This made it
not only possible, but practical, to pass parameters by pushing them
onto the stack.


Granted, the 8080 instructions for manipulating data on the stack were
primitive by modern standards, but they were very advanced at the
time, even compared to minis and mainframes.


I guess it was Motorola that made the next big step, by making stack
access cheap in terms of clock cycles. The 8080 stack accesses, while
convenient, took a lot more clock cycles to execute. In the 68000, by
contrast, they executed almost as fast as register-register
operations. In the case of stack-relative addressing, accesses were
actually _FASTER_ than direct memory addressing (because the offset
was 16 bits, not 32).


For fun, one day in the dim past I programmed up the eight-queens
problem in Turbo Pascal. I did it in the classical fashion, using
recursion. Then I remembered the "procedure calls are expensive"
dictum you referred to, so I recoded the algorithm to avoid recursion.
I was more than a little astonished to discover that the recursive
version was _FASTER_!


In retrospect, it's not hard to see why. All I had done, in my new,
improved version, is to replace the hardware stack with a softare one,
implemented in Pascal. Borland's implementation of function calls made
max use of stack-based operations on the hardware stack. No way could
my integer indexing compete.


Jack


Peter Seibel wrote:
> My understanding is that in Olden Times, Real Programmers avoided
> using lots of small functions because the overhead of a function call
> was considered high. But then, somewhere along the way, the compiler
> writers got clever and made function calls cheap so now nobody worries
> about it. Is that more or less correct? And if so, what happened to
> make function calls cheap. It seems that there's a non-trivial amount
> of work to do to set up a stack frame, etc. compared to just
> continuing along in a straight line processing instructions that do
> the actual work--are there deep black-magic optimizations or did the
> relative costs of something change or something else entirely?
>
> -Peter
[Hardware stacks are very old. The DEC PDP-6, the predecessor to the
PDP-10 and DEC-20, had them in 1964. It was designed at the same time
as the IBM 360, but DEC expected the primary languages to be Fortran
and Lisp, while IBM expected them to be Fortran and Cobol. IBM knew
all about stacks but decided, correctly at the time, that it wasn't
worth the expense of putting stack hardware into the 360. It's not
hard to do stacks on the 360 since it has so many registers, although
OS/360 and its descendants don't make it as easy as they should. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.