function calls

[Henry Spencer]

In article <2000 at l.cc.purdue.edu> cik at l.cc.purdue.edu (Herman Rubin) writes:
>> I was under the impression that C's function calls are, relative to other
>> high level languages, very inexpensive...
>
>Simple, yes.  Inexpensive, no.  I can conceive of a way in which hardware
>can be constructed which would make subroutine calls inexpensive, but I
>know of no machine which has it.  

Many people can conceive of such ways, and a good many of them have been
implemented, some quite successfully.  On the Mips machines, for example,
a C function call to a "leaf" function (one which calls no others) is
one instruction for the call and one for the return, total elapsed time
a small fraction of a microsecond.  Non-leaf functions have to do a little
bit more work at times.

However, as Steve Johnson said at the winter 1987 Usenix conference, talking
about the early days:  ``Dennis had a lot of credibility and lied very
convincingly... it was years before we found out the truth.''  On the early
Unix machines (pdp11 and VAX), function calls were not particularly cheap
(although it is true that C's calls are cheaper than those of many other
languages).  Machine designers have paid a lot more attention to the matter
in recent years, and the situation has improved greatly.

>A subroutine necessarily must find its arguments (or pointers to them, etc.)
>in standardized places.  It also must put its results in such places, or use
>pointers to know where to put them.  Occasionally one can put the arguments
>in those places or use the results that way, but not always...

Not always, no, but a lot of the time.  Many modern machines are organized
so that most function parameters simply get evaluated into a register
(usually necessary anyway) and left there for the callee to find.  There
is sometimes a small cost of having to save the previous value of that
register, depending on circumstances and architecture.

>...necessarily a context switch to some extent...

It can be a very small extent on a well-designed machine.  There *is* a
fundamental problem of instruction reference locality, which necessarily
slows things down a bit on machines with hardware optimized for sequential
fetches.
-- 
MSDOS, abbrev:  Maybe SomeDay |     Henry Spencer at U of Toronto Zoology
an Operating System.          | uunet!attcan!utzoo!henry henry at zoo.toronto.edu