Recursive functions Vs Non-recursive functions - performance aspect

V

vamsi

Hi,
I am doing a performance profiling of my 'C' application. I would like
to know, if replacing a recursive function with a non-recursive
version of it will save CPU cycles.
One reason why it could improve performance, could be it could save
all the stack pushes and pops, when the function call happens or
returns. Also, in one of my past applications, replacing a function
call with an inline code did improve performance, and so I derived the
same.

Changing the function to non-recursive version, will take some effort.
I would like to know this info before proceeding.
If anyone has any data/observation in the past or comments/
suggestions, please let me know.

Regards,
Vamsi
 
I

Ian Collins

vamsi said:
Hi,
I am doing a performance profiling of my 'C' application. I would like
to know, if replacing a recursive function with a non-recursive
version of it will save CPU cycles.

There is no simple answer to that question. Different compilers will
apply different optimisations depending on the size of the function.
Some (most?) will attempt to unroll a recursive function with inlining.
Changing the function to non-recursive version, will take some effort.
I would like to know this info before proceeding.
If anyone has any data/observation in the past or comments/
suggestions, please let me know.

You really will have to do some test measurements.
 
U

user923005

Hi,
I am doing a performance profiling of my 'C' application. I would like
to know, if replacing a recursive function with a non-recursive
version of it will save CPU cycles.
One reason why it could improve performance, could be it could save
all the stack pushes and pops, when the function call happens or
returns. Also, in one of my past applications, replacing a function
call with an inline code did improve performance, and so I derived the
same.

Changing the function to non-recursive version, will take some effort.
I would like to know this info before proceeding.
If anyone has any data/observation in the past or comments/
suggestions, please let me know.

First profile.
Then, if it is too slow, examine the profile to find the slow spots.
Where you find the slow spots, improve the algorithm. This is many,
many times more important than things like change from recursive to
iterative.
 
V

vamsi

First profile.
Then, if it is too slow, examine the profile to find the slow spots.
Where you find the slow spots, improve the algorithm.  This is many,
many times more important than things like change from recursive to
iterative.

I have used oprofile for measurement and(callgraph) compiled with -O1
and -O3 optimizations. It showed that, my function(function_1) is
getting called recursively frequently.

1963 40.2089 App.sct function_1
206 3.1736 App.sct function_1
1963 51.4953 App.sct function_1
 
U

user923005

I have used oprofile for measurement and(callgraph) compiled with -O1
and -O3 optimizations. It showed that, my function(function_1) is
getting called recursively frequently.

  1963     40.2089  App.sct function_1
206       3.1736  App.sct function_1
  1963     51.4953  App.sct function_1

If the performance is not up to specifications, then it is time to
consider improving the algorithm.
What does the function look like when profiled line by line?
 
G

Guest

I am doing a performance profiling of my 'C' application. I would like
to know, if replacing a recursive function with a non-recursive
version of it will save CPU cycles.

if you are profiling your program couldn't you just remove
the recursion and re-profile and see what happens?

In general you can't answer this. Some algorithms are naturally
recursive (eg. tree walking) and you don't gain much by fighting it.
Some simple algorithms implemented in a naive way (eg. factorial)
with
a compiler that doesn't do tail recursion optimisation are really
poor.

But note the weasel density of that sentence

One reason why it could improve performance, could be it could save
all the stack pushes and pops, when the function call happens or
returns.

yes but, if it's natuarally recursive you may have to store
this information somewhere anyway.
Also, in one of my past applications, replacing a function
call with an inline code did improve performance,

ok, but profiling is the way to go. And turn up the
optimisation level

and so I derived the same.
what?


Changing the function to non-recursive version, will take some effort.
I would like to know this info before proceeding.
If anyone has any data/observation in the past or comments/
suggestions, please let me know.

I've never actually gained much on the rare occasions I've tried
it. There is no simple answer to your question. If it's tail
recursive (the recursive call is at the end of the function)
then try removing it (that should be easy). If it's a tree
or some sort of mutual recursion then it probably isn't
worth it.

--
Nick Keighley

Quantum Boggum Sort:
Q1. use a source of quantum noise (eg. radioactive decay) to
randomly permutate an array.
Q2. if the array is not ordered, destroy the universe (*)
Q3. if you reached this step your universe has sorted the array
in O(n) time.
(*) [100] this is left as an exercise
 
G

Guest

(e-mail address removed) said:









Note, too, that factorials were a poor example, since they won't
execute long enough for you to notice any significant difference
(because you get real big numbers real fast, and then you have to
stop).

Fibonacci's blasted rabbits make for a much better illustration.

ah yes, and it's quite astonishing how many recursions it can do
 
J

JosephKK

The quick answer is maybe, a better answer is "what is the metric
used?". Note that the result may be highly data dependent.
There is no simple answer to that question. Different compilers will
apply different optimisations depending on the size of the function.
Some (most?) will attempt to unroll a recursive function with inlining.

I have used loop unrolling many times, this is the first i have heard
of recursion unrolling. Can you explain how it is done?
 
U

user923005

J

JosephKK

The quick answer is maybe, a better answer is "what is the metric
used?".  Note that the result may be highly data dependent.




I have used loop unrolling many times, this is the first i have heard
of recursion unrolling.  Can you explain how it is done?

These may prove interesting reading:
http://www.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-2.pdf
http://c2.com/cgi/wiki?TailRecursion
http://portal.acm.org/citation.cfm?id=1185574

[smip]
^ ;=D

Yes i did find it interesting. Tail recursion transforms followed by
complete transformation into iteration, and iteration is regularly
unrolled.

That last one requires special access rights however. The description
sounds really interesting though.
 
P

Phil Carmody

JosephKK said:
The quick answer is maybe, a better answer is "what is the metric
used?". Note that the result may be highly data dependent.

I have used loop unrolling many times, this is the first i have heard
of recursion unrolling. Can you explain how it is done?

Ian is probably referring to 'tail recursion'. If he isn't,
he ought to be. It's easily googlable.

Phil
 
C

CBFalconer

Phil said:
.... snip ...

Ian is probably referring to 'tail recursion'. If he isn't,
he ought to be. It's easily googlable.

You can convert any recursive function into an iterative function.
The result may no longer be re-entrant. There is no limitation to
tail recursion, although that reduction is much simpler.
 
W

Walter Banks

JosephKK said:
^ ;=D

Yes i did find it interesting. Tail recursion transforms followed by
complete transformation into iteration, and iteration is regularly
unrolled.

That last one requires special access rights however. The description
sounds really interesting though.

Peiyi Tang's publications (most well worth reading) are on line at
http://titus.compsci.ualr.edu/~ptang/publications.html

This paper can be downloaded from .
http://titus.compsci.ualr.edu/~ptang/papers/acmse06-b.pdf


Regards,
 
R

Richard Bos

CBFalconer said:
You can convert any recursive function into an iterative function.
The result may no longer be re-entrant. There is no limitation to
tail recursion, although that reduction is much simpler.

You can convert any recursive function to a _technically_ iterative
function, but if this means having to build your own stack, the result
is still _semantically_ recursive, and you may as well leave it
recursive in the code, as well. For one thing, your compiler and/or OS
are much more likely to choose correctly which branch to unrecurse, if
any.

Richard
 
R

Rui Maciel

user923005 said:
This is many,
many times more important than things like change from recursive to
iterative.

That and the risk of your recursive function ending up overflowing the stack.


Rui Maciel
 
C

CBFalconer

Rui said:
That and the risk of your recursive function ending up
overflowing the stack.

Create the stack with malloc, as an appropriate array. Stack
pointers are indices to that array. When the stack overflows,
simply realloc, and tuck the result away.
 
D

Dik T. Winter

> You can convert any recursive function to a _technically_ iterative
> function, but if this means having to build your own stack, the result
> is still _semantically_ recursive, and you may as well leave it
> recursive in the code, as well. For one thing, your compiler and/or OS
> are much more likely to choose correctly which branch to unrecurse, if
> any.

I know of at least one study that did compare recursive formulations with
non-recursive formulations. It is long ago, done by (amongs others) Kees
Dekker at my institute. Not for C, C was not yet in the picture at that
time. But if I remember right, for Algol 68 programs, recursive formulation
almost always resulted in faster programs with the compiler of CDC. And
it did not unrecure any branch. On the other hand, for the Algol 60
compiler it was a dead heath. (The study was about numerical integration
where you split the interval over which to integrate in two halves and
repeated the process on those two halves if the result was not good enough.)
 
B

blmblm

(e-mail address removed) said:


Note, too, that factorials were a poor example, since they won't
execute long enough for you to notice any significant difference
(because you get real big numbers real fast, and then you have to
stop).

Fibonacci's blasted rabbits make for a much better illustration.

A rather belated two cents' worth ....

But the reason the rabbits make such a good illustration -- it's
not so much the recursion itself as the duplication involved, no?
 
U

user923005

That and the risk of your recursive function ending up overflowing the stack.

Conversion to iteration does not help here.
In the conversion, you definitely have to maintain your own stack.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top