Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Recursive functions Vs Non-recursive functions - performance aspect

Reply
Thread Tools

Recursive functions Vs Non-recursive functions - performance aspect

 
 
vamsi
Guest
Posts: n/a
 
      02-27-2009
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
 
Reply With Quote
 
 
 
 
Ian Collins
Guest
Posts: n/a
 
      02-27-2009
vamsi wrote:
> 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.

--
Ian Collins
 
Reply With Quote
 
 
 
 
user923005
Guest
Posts: n/a
 
      02-27-2009
On Feb 26, 8:04*pm, vamsi <(E-Mail Removed)> wrote:
> 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.
 
Reply With Quote
 
vamsi
Guest
Posts: n/a
 
      02-27-2009
On Feb 27, 9:39*am, user923005 <(E-Mail Removed)> wrote:
> On Feb 26, 8:04*pm, vamsi <(E-Mail Removed)> wrote:
>
> > 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.


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
 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      02-27-2009
On Feb 26, 10:26*pm, vamsi <(E-Mail Removed)> wrote:
> On Feb 27, 9:39*am, user923005 <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Feb 26, 8:04*pm, vamsi <(E-Mail Removed)> wrote:

>
> > > 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.

>
> 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?

 
Reply With Quote
 
nick_keighley_nospam@hotmail.com
Guest
Posts: n/a
 
      02-27-2009
On 27 Feb, 04:04, vamsi <(E-Mail Removed)> wrote:

> 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
 
Reply With Quote
 
nick_keighley_nospam@hotmail.com
Guest
Posts: n/a
 
      02-27-2009
On 27 Feb, 08:38, Richard Heathfield <(E-Mail Removed)> wrote:
> (E-Mail Removed) said:
>
>
>
>
>
> > On 27 Feb, 04:04, vamsi <(E-Mail Removed)> wrote:

>
> >> 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

>
> 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
 
Reply With Quote
 
JosephKK
Guest
Posts: n/a
 
      03-06-2009
On Fri, 27 Feb 2009 17:24:33 +1300, Ian Collins <(E-Mail Removed)>
wrote:

>vamsi wrote:
>> 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.


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?
>
>> 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.


 
Reply With Quote
 
JosephKK
Guest
Posts: n/a
 
      03-06-2009
On Fri, 27 Feb 2009 01:36:35 -0800 (PST),
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

>On 27 Feb, 08:38, Richard Heathfield <(E-Mail Removed)> wrote:
>> (E-Mail Removed) said:
>>
>>
>>
>>
>>
>> > On 27 Feb, 04:04, vamsi <(E-Mail Removed)> wrote:

>>
>> >> 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

>>
>> 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


Reminds me of Ackerman functions.

 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      03-06-2009
On Mar 5, 10:00*pm, "JosephKK"<(E-Mail Removed)> wrote:
> On Fri, 27 Feb 2009 17:24:33 +1300, Ian Collins <(E-Mail Removed)>
> wrote:
>
> >vamsi wrote:
> >> 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.

>
> 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?


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

[smip]
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
performance of recursive generator aurora Python 7 08-11-2005 11:49 PM
Synthesis of VHDL RTL including recursive functions gpi5 VHDL 1 11-09-2004 02:44 PM
Recursive Functions dmattis C Programming 64 11-02-2003 01:39 PM
[Comparative performance] str-functions vs. mem-functions Alex Vinokur C Programming 6 08-30-2003 09:20 AM



Advertisments