Mail Archives: djgpp/2001/05/10/10:32:00
On 10 May 2001, Hans-Bernhard Broeker wrote:
> You really should rethink your strategy all the way since you started
> at square one. What you're doing here, actually, is to avoid the usual
> overhead involved in recursive function calling --- but you're doing
> it the wrong way. To avoid having more than absolutely necessary
> pushed to the stack in recursive calls, use the following recipe,
> instead:
>
> 1) Remove as many as possible of the arguments of the recursive function
> 2) Remove as many as possible of the recursive function's local variables
> in scope at the time of the resursion call(s). Block-scope variables
> of blocks without a recursion call in them can stay as they are.
> 3) Replace them by a manually implemented stack of 'status structs', where
> the status struct holds *exactly* those variables that have to be
> preserved across a recursion call.
> 4) Compile the whole stuff with -save-temps -fverbose-asm -O6 and see if
> you can really beat GCC in assembly hacking :-)
And I would like to point out, again, that all this complicated procedure
and the additional complexity it imposes on the code (meaning more bugs
and more slow-down) might be _totally_ unnecessary!
There's a popular belief that recursive code is terribly slow, but
experience shows that this is mostly a myth. Recursive code _might_ be
slow, but in many cases it isn't. Because recursive code is usually
smaller, it fits better into the CPU caches. It is also simpler, so you
have less probability for bugs, and it lends itself better to compiler
optimizations.
In other words, I _strongly_ recommend to write a recursive implementation
in a high-level language such as C or C++, compile it with optimizations,
and _profile_ it, before you decide to go to such lengths. There are good
chances that the code will run fast enough to make any of this completely
unnecessary.
- Raw text -