nevin1@ihlpf.ATT.COM (00704a-Liber) (03/12/88)
In article <704@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:
.There are two problems with this. While using stacks may be easy to program,
.it involves lots of loads and stores. I know of at least one machine on which
.the normal subroutine call and return do not use stacks. Furthermore, if the
.called routine may make additional calls, it may be necessary to use a
.separate return stack, and this may require each such subroutine to maintain
.its own return stack. In some cases this should be the way to do things,
.but not always.
I would not be so worried about the efficiency of passing values to and
from functions on non stack-based machines and be more worried about how
you are going to implement efficiently a language which allows recursion
(C, Pascal, etc.) on a non stack-based machine. I do know that machines
like this exist (yea, I have programmed on a PDP-8), but I haven't seen an
efficient implementation of Pascal or C on any of these machines. The only
model that I know of that supports recursion is a stack. BTW, what I mean
by recursion is that if you graph out the functions in the order that they
are called and you find a cycle in it, it's recursive.
.Another problem comes with inline functions. I believe that many function
.calls, if not most, should be inline. In this case, I think the result should
.go to its destination at the time produced. If the destinations involve
.registers or register indirects, the expression of the algorithm must take
.the busy set of registers into account. This admittedly makes coding
.difficult, and is one reason why I believe DNA can optimize better than
.silicon. (The two should be used together, but I do not know of any compiler
.which allows the programmer to even give it a hint as to how to optimize,
.let alone improve the resulting product.)
As I have told you before, NOT ALL FUNCTIONS ARE INLINEABLE!! Any function
that can be called recursively (see my above definition of recursive) an
unknown (at compile/link time) number of times cannot be inlined!!
Also, another reason that you may not want to inline functions is that on a
smaller machine (such as a PC), you may have to move to a larger memory
module because your activation record is much bigger (it might no longer
fit into a segment, etc.).
Thirdly, if you are calling shareable routines you cannot inline them,
since their code is never actually put into the text segment.
BTW, I am not against inlining per se (I like it much more than macros),
but I do not feel that it should be done if it might break the code (any
function that might be recursive shouldn't be inlined). 'inline' should
be a hint in much the same way that 'register' is a hint (and NOT the way
'noalias' is a hint in the C draft standard).
Here is another proposition for the 'D' language: the keyword 'unroll'
(see Jon Bentley's "Programming Pearls" for reference) should be allowed
in front of any *simple* for loop. What this would do is, for example,
is change:
unroll for (i=1; i <= 4; i++)
printf("String number %d is: %s\n", i, string[i]);
to:
printf("String number 1 is %s\n", string[1]);
printf("String number 2 is %s\n", string[2]);
printf("String number 3 is %s\n", string[3]);
printf("String number 4 is %s\n", string[4]);
i=5;
since the latter is more efficient with respect to speed. Of course, the
comments I made above about potentially breaking code apply here is well
('unrolling' would only be a hint). Comments??
--
_ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194
' ) ) "The secret compartment of my ring I fill
/ / _ , __o ____ with an Underdog super-energy pill."
/ (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blahpardo@june.cs.washington.edu (David Keppel) (03/12/88)
In article <3980@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: >The only model that I know of that supports recursion is a stack. Recursion can also be supported with heaps. Many versions of Lisp and all versions of Smalltalk allow spaghetti stacks (usually, but not always obeys stack discipline). Spaghetti stacks are implemented using heaps, or at least they (transparently) copy frames from the stack into to heap-allocated space when they are going to live after their parents' destruction. Heaps are usually less efficient and more general than stacks. Followups to comp.lang.misc ;-D on (Gimme a *heap* o' them stacks!) Pardo
gore@eecs.nwu.edu (Jacob Gore) (03/14/88)
/ comp.lang.misc / nevin1@ihlpf.ATT.COM (00704a-Liber) / Mar 11, 1988 / I agree with Nevin's sentiment about inlining routines: There are situations in which to want them, and situations in which to avoid them. But I think there are some misconceptions in both his posting and in the one he was replying to: >.[...] if the >.called routine may make additional calls, it may be necessary to use a >.separate return stack, and this may require each such subroutine to maintain >.its own return stack. Why would you need separate stacks for each routine? >[...] NOT ALL FUNCTIONS ARE INLINEABLE!! Any function >that can be called recursively (see my above definition of recursive) an >unknown (at compile/link time) number of times cannot be inlined!! It can, if it can be converted to iteration, and a stack is maintained for its scope. (There is no reason to expect local objects and return addresses to be on the same stack, is there?) Another reason you may not want to use inline functions is that they make code maintenance harder. If a function is used inline, and I change its guts (without changing its interface or semantics), I have to recompile all code that invokes it. If I leave it as a separate routine, I can simply re-link it (or even just reload it, depending on whether or not my environment supports run-time linking). Jacob Jacob Gore Gore@EECS.NWU.Edu Northwestern Univ., EECS Dept. {oddjob,gargoyle,ihnp4}!nucsrl!gore
nevin1@ihlpf.ATT.COM (00704a-Liber) (03/19/88)
In article <4000013@eecs.nwu.edu> gore@eecs.nwu.edu (Jacob Gore) writes:
./ comp.lang.misc / nevin1@ihlpf.ATT.COM (00704a-Liber) / Mar 11, 1988 /
..
..[...] NOT ALL FUNCTIONS ARE INLINEABLE!! Any function
..that can be called recursively (see my above definition of recursive) an
..unknown (at compile/link time) number of times cannot be inlined!!
.
.It can, if it can be converted to iteration, and a stack is maintained for its
.scope. (There is no reason to expect local objects and return addresses to be
.on the same stack, is there?)
For the circumstances where you must keep a stack around for local objects,
what efficiency do you get for inlining vs. calling?? It seems to me that
all you are doing is replacing a push and a pop with a jump. For this
reason, I do not believe that converting to iteration (such as optimizing
tail recursive functions) is true inlining. In this case, we are not
eliminating the calling mechanism, we are just changing its' name.
--
_ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194
' ) ) "The secret compartment of my ring I fill
/ / _ , __o ____ with an Underdog super-energy pill."
/ (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blahnevin1@ihlpf.ATT.COM (00704a-Liber) (03/19/88)
In article <4443@june.cs.washington.edu> pardo@uw-june.UUCP (David Keppel) writes: .In article <3980@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: ..The only model that I know of that supports recursion is a stack. . .Recursion can also be supported with heaps. Many versions of Lisp and .all versions of Smalltalk allow spaghetti stacks (usually, but not always .obeys stack discipline). Spaghetti stacks are implemented using heaps, or .at least they (transparently) copy frames from the stack into to .heap-allocated space when they are going to live after their parents' .destruction. . .Heaps are usually less efficient and more general than stacks. The key word in the my first sentence (from article <3980@ihlpf.ATT.COM>) is *model*. You haven't eliminated the stack model, you've simply stated a way of implementing it. I still feel that the only *model* that supports recursion is a stack. -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) "The secret compartment of my ring I fill / / _ , __o ____ with an Underdog super-energy pill." / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah