Recursive functions Vs Non-recursive functions - performance aspect

Discussion in 'C Programming' started by vamsi, Feb 27, 2009.

  1. vamsi

    vamsi Guest

    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
    vamsi, Feb 27, 2009
    #1
    1. Advertising

  2. vamsi

    Ian Collins Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    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
    Ian Collins, Feb 27, 2009
    #2
    1. Advertising

  3. vamsi

    user923005 Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On Feb 26, 8:04 pm, 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.
    > 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.
    user923005, Feb 27, 2009
    #3
  4. vamsi

    vamsi Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On Feb 27, 9:39 am, user923005 <> wrote:
    > On Feb 26, 8:04 pm, 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.
    > > 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
    vamsi, Feb 27, 2009
    #4
  5. vamsi

    user923005 Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On Feb 26, 10:26 pm, vamsi <> wrote:
    > On Feb 27, 9:39 am, user923005 <> wrote:
    >
    >
    >
    >
    >
    > > On Feb 26, 8:04 pm, 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.
    > > > 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?
    user923005, Feb 27, 2009
    #5
  6. vamsi

    Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On 27 Feb, 04:04, vamsi <> 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
    , Feb 27, 2009
    #6
  7. vamsi

    Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On 27 Feb, 08:38, Richard Heathfield <> wrote:
    > said:
    >
    >
    >
    >
    >
    > > On 27 Feb, 04:04, vamsi <> 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
    , Feb 27, 2009
    #7
  8. vamsi

    JosephKK Guest

    On Fri, 27 Feb 2009 17:24:33 +1300, Ian Collins <>
    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.
    JosephKK, Mar 6, 2009
    #8
  9. vamsi

    JosephKK Guest

    Re: Recursive functions Vs Non-recursive functions - performance aspect

    On Fri, 27 Feb 2009 01:36:35 -0800 (PST),
    wrote:

    >On 27 Feb, 08:38, Richard Heathfield <> wrote:
    >> said:
    >>
    >>
    >>
    >>
    >>
    >> > On 27 Feb, 04:04, vamsi <> 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.
    JosephKK, Mar 6, 2009
    #9
  10. vamsi

    user923005 Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On Mar 5, 10:00 pm, "JosephKK"<> wrote:
    > On Fri, 27 Feb 2009 17:24:33 +1300, Ian Collins <>
    > 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/pubs/techreps/TR-2001-2.pdf
    http://c2.com/cgi/wiki?TailRecursion
    http://portal.acm.org/citation.cfm?id=1185574

    [smip]
    user923005, Mar 6, 2009
    #10
  11. vamsi

    JosephKK Guest

    Re: Recursive functions Vs Non-recursive functions - performance aspect

    On Fri, 6 Mar 2009 02:05:19 -0800 (PST), user923005
    <> wrote:

    >On Mar 5, 10:00 pm, "JosephKK"<> wrote:
    >> On Fri, 27 Feb 2009 17:24:33 +1300, Ian Collins <>
    >> 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/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.
    JosephKK, Mar 6, 2009
    #11
  12. vamsi

    Phil Carmody Guest

    "JosephKK"<> writes:
    > On Fri, 27 Feb 2009 17:24:33 +1300, Ian Collins <>
    > 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?


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

    Phil
    --
    I tried the Vista speech recognition by running the tutorial. I was
    amazed, it was awesome, recognised every word I said. Then I said the
    wrong word ... and it typed the right one. It was actually just
    detecting a sound and printing the expected word! -- pbhj on /.
    Phil Carmody, Mar 6, 2009
    #12
  13. vamsi

    CBFalconer Guest

    Phil Carmody wrote:
    >

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

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Mar 6, 2009
    #13
  14. vamsi

    Walter Banks Guest

    Re: Recursive functions Vs Non-recursive functions - performance aspect

    JosephKK wrote:

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


    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,

    --
    Walter Banks
    Byte Craft Limited
    http://www.bytecraft.com
    Walter Banks, Mar 7, 2009
    #14
  15. vamsi

    Richard Bos Guest

    CBFalconer <> wrote:

    > Phil Carmody wrote:
    >
    > > 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.


    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
    Richard Bos, Mar 8, 2009
    #15
  16. vamsi

    Rui Maciel Guest

    user923005 wrote:

    > 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
    Rui Maciel, Mar 8, 2009
    #16
  17. vamsi

    CBFalconer Guest

    Rui Maciel wrote:
    > user923005 wrote:
    >
    >> 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.


    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.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Mar 8, 2009
    #17
  18. In article <4all.nl> writes:
    ....
    > 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.)
    --
    dik t. winter, cwi, science park 123, 1098 xg amsterdam, nederland, +31205924131
    home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
    Dik T. Winter, Mar 9, 2009
    #18
  19. vamsi

    Guest

    In article <>,
    Richard Heathfield <> wrote:
    > said:
    >
    > > On 27 Feb, 04:04, vamsi <> 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.


    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?

    --
    B. L. Massingill
    ObDisclaimer: I don't speak for my employers; they return the favor.
    , Mar 9, 2009
    #19
  20. vamsi

    user923005 Guest

    Re: Recursive functions Vs Non-recursive functions - performanceaspect

    On Mar 8, 6:20 am, Rui Maciel <> wrote:
    > user923005 wrote:
    > > 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.


    Conversion to iteration does not help here.
    In the conversion, you definitely have to maintain your own stack.
    user923005, Mar 9, 2009
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. New_aspect

    Aspect oriented Everything?

    New_aspect, Aug 22, 2003, in forum: Perl
    Replies:
    5
    Views:
    1,091
    Robert Will
    Aug 31, 2003
  2. =?Utf-8?B?RGF2aWQgV2hpdGNodXJjaC1CZW5uZXR0?=

    Newbie: Image button aspect ratio

    =?Utf-8?B?RGF2aWQgV2hpdGNodXJjaC1CZW5uZXR0?=, Nov 6, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    1,212
    Scott M.
    Nov 7, 2004
  3. Arthur Hsu
    Replies:
    5
    Views:
    5,926
    Steven Cheng[MSFT]
    Dec 8, 2004
  4. Amelyan
    Replies:
    6
    Views:
    504
    Amelyan
    Jun 27, 2005
  5. nielinjie

    How to model Aspect using uml

    nielinjie, Sep 30, 2003, in forum: Java
    Replies:
    0
    Views:
    315
    nielinjie
    Sep 30, 2003
Loading...

Share This Page