webber@porthos.rutgers.edu (Bob Webber) (06/25/88)
In article <3347@tekchips.TEK.COM>, stevev@tekchips.TEK.COM (Steve Vegdahl) writes: > In article <Jun.22.22.48.57.1988.7380@aramis.rutgers.edu>, webber@aramis.rutgers.edu (Bob Webber) writes: > > In article <3061@rpp386.UUCP>, jfh@rpp386.UUCP (John F. Haugh II) writes: > > > ... [collapsed to the following for reference] > > > strlen (s) char *s; { return (*s) ? strlen(s+1) + 1 : 0; } > > > ... > > > not such a smart move. always consider the cost of your algorithm. > > > > A perfectly fine algorithm. Any decent compiler would remove the tail > > recursion. > > Unfortunately, the above program is not tail-recursive. The result of the > recursive "strlen" call is incremented before its value is returned. It > would take a pretty sophisticated compiler to transform this into an > iteration. Among other things, it would probably have to use the > associativity of "+". Over 10 years ago this stuff was being done on lisp compilers. The first step is the generation of a ``helping variable'' creating strlen2(s,n) char *s; int n; { return (*s) ? strlen2(s,1+n) : n ; } which is then recognized to be tail recursive. And yes, you are right that this presumes associativity of "+". While in general, ``plus'' even for integers is not associative, since this situation is also monotone increasing, it all works out. Note the special case of monotone integer arithmetic is actually very common due to the number of things that can be thought of as sequences to be manipulated in order. > BTW, does a typical C compiler perform tail-call optimization. On your home micro? Not likely. A modern major production C compiler I would expect to. The technology has been in the literature for at least 10 years and this is definitely the way people are encouraged to analyze problems. Of course, the original C compilers did practically no optimization assuming that you would hand massage the critical parts and the others it wasn't worth the effort (10% of the code executing 90% of the time and such) -- also, they didn't have alot of space to waste on such nicities. Now-a-days, there seems to be more of a willingness to relieve the programmer of making such trivial algorithm refinements. Being commercial products, not alot is known about the optimizations actually done by the standard compilers. However, my understanding is that the GNU CC compiler is at least as good as what the commerical people are cranking out, so to the extent that statistics of 1 case are better than statistics of 0 cases, I am cross posting this message over to gnu.gcc to see if any of the experts over there know how it would handle such code. ------ BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber) p.s., The above code was being discussed in the context of a student compiler project and I still maintain that even if it wasn't optimized, that such an implementation of strlen is not ``unreasonable.'' Most of those projects spend far more time being compiled themselves rather than compiling other things and the only real usage for such a function in a reasonably written compiler would be enforcing restrictions on the targe language material. [Note: it has already been mentioned that on a VAX, strlen can be so cheaply implemented in assembler that it can be used in lots of places where one wouldn't normally contemplate using it.]
stevev@tekchips.TEK.COM (Steve Vegdahl) (06/29/88)
[Discussion of tail-call optimization for the C program:
strlen (s) char *s; { return (*s) ? strlen(s+1) + 1 : 0; }]
In article <Jun.25.12.48.01.1988.11442@porthos.rutgers.edu>, webber@porthos.rutgers.edu (Bob Webber) writes:
> Over 10 years ago this stuff was being done on lisp compilers. The first
> step is the generation of a ``helping variable'' creating
> strlen2(s,n) char *s; int n; { return (*s) ? strlen2(s,1+n) : n ; }
> which is then recognized to be tail recursive. ...
There are lots of transformations that a compiler could conceivably perform,
including the one mentioned above. Each one will tend to decrease the speed
and increase both the size and expected number of compiler bugs. The issue
is then a tradeoff between the above issues and the expected gain in
efficiency for the "typical" (whatever that means) program. The tradeoffs
for a lisp compiler and a C compiler are likely to be quite different. Even
for a lisp compiler, the optimization mentioned not be near the top of the
list of transformations that I would expect.
> > BTW, does a typical C compiler perform tail-call optimization.
...
> Being commercial products, not alot is known about the optimizations actually
> done by the standard compilers. However, my understanding is that the GNU
> CC compiler is at least as good as what the commerical people are cranking out,
> so to the extent that statistics of 1 case are better than statistics
> of 0 cases, I am cross posting this message over to gnu.gcc to see if any
> of the experts over there know how it would handle such code.
Detecting whether a compiler does tail-call optimization should not be that
difficult: just construct a suitably large test case and see whether the
stack overflows. I tried the above program with the (VAX) UNIX C compiler.
With a string of length 100, it worked fine; when I upped the size to
100000, it generated a segmentation fault, presumably because it overflowed
the stack. I also transformed the program by adding the dummy argument,
thereby making it truly tail recursive: same result. Conclusion: the VAX
UNIX C compiler does not perform tail-call optimization even in the simple
cases.
I think that the statement that "any decent compiler would remove the tail
recursion" is a bit strong, especially considering that additional program
transformation is necessary to put it into tail-recursive form. How many
production Lisp or Scheme compilers perform this "two-step" optimization?
> p.s., The above code was being discussed in the context of a student compiler
> project and I still maintain that even if it wasn't optimized, that such
> an implementation of strlen is not ``unreasonable.''
I agree.
Steve Vegdahl
Computer Research Lab
Tektronix Labs
Beaverton, Oregon