Like Tree5Likes
  • 1 Post By Adak
  • 1 Post By laserlight
  • 1 Post By iMalc
  • 1 Post By Click_here
  • 1 Post By laserlight

Function calls and performance

This is a discussion on Function calls and performance within the C Programming forums, part of the General Programming Boards category; Hello there, So I was reading about inline functions and I came up with a doubt. If function calls tends ...

  1. #1
    Registered User
    Join Date
    May 2012
    Location
    Brazil
    Posts
    52

    Function calls and performance

    Hello there,

    So I was reading about inline functions and I came up with a doubt.

    If function calls tends to be slower than loops in C, what are the advantages of using recursive functions? I mean, if I have the option to choose between using a recursive function and loops, shouldn't I always prefer loops?

    Also, what is your criteria when deciding to split a function? Is it just a question of keeping different things in different functions or are there some "rules"? Or is it just "this function is too big, let me split it"?

    I really appreciate any advice.

    Regards,
    koplersky

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Inline functions are not slower than loops - they become part and parcel of the calling function. The advantages of recursive functions is the stack that keeps track of just where you are at any time - going deeper with another call, or popping back out with a return.

    Quicksort is a great example - it can be done iteratively of course, but it's a mess to code it up, and not so pretty, if I do say so. Recursively, it's VERY clean - and some recursive versions of it are even faster than the iterative version. Which is better, depends on exactly what you are doing. I'm not a big fan of recursive functions, but for Quicksort, it's a winner.

    I like to keep the functions doing one thing - say, getting input. Normally, that would include parsing it - but if the input is complex, and the parsing is too, then making another function just for parsing, seems right. Size is one factor, complexity is another. I want to finish whatever the function was supposed to do, (encapsulating it in that one function), but if I can't easily grasp all the logic in the function readily, then it's time to think about splitting it up.
    koplersky likes this.

  3. #3
    Registered User
    Join Date
    May 2012
    Location
    Brazil
    Posts
    52
    Thanks for the answer, Adak.

    Quote Originally Posted by Adak View Post
    Inline functions are not slower than loops - they become part and parcel of the calling function.
    Yes, what I read was this:
    The point of making a function inline is to hint to the compiler that it is worth making some form of extra effort to call the function faster than it would otherwise - generally by substituting the code of the function into its caller. As well as eliminating the need for a call and return sequence, it might allow the compiler to perform certain optimizations between the bodies of both functions.
    That's what got me confused. I mean, inline functions eliminate the need of this call and return sequence, so keep calling functions might be in some case slower than using loops, right? So why would one prefer to use recursion? Except that it might improve code readability, isn't there a case where this way of thinking (always improve code readability and thus using recursive function) might make the program run slower?

    Quote Originally Posted by Adak View Post
    and some recursive versions of it are even faster than the iterative version.
    Could you please provide me an example?

    Quote Originally Posted by Adak View Post
    I like to keep the functions doing one thing - say, getting input. Normally, that would include parsing it - but if the input is complex, and the parsing is too, then making another function just for parsing, seems right. Size is one factor, complexity is another. I want to finish whatever the function was supposed to do, (encapsulating it in that one function), but if I can't easily grasp all the logic in the function readily, then it's time to think about splitting it up.
    So there is no rule to when split a function? We could say that it's a matter of taste, always aiming at improve code readability and letting each function doing one job?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,170
    Quote Originally Posted by koplersky
    So why would one prefer to use recursion? Except that it might improve code readability, isn't there a case where this way of thinking (always improve code readability and thus using recursive function) might make the program run slower?
    If the difference to the efficiency is negligible and the other pitfalls of recursion do not apply (e.g., limited stack space), whereas the improvement to readability and/or the reduced time needed to code and debug is significant, then why not use a recursive solution?

    On the other hand, if the problem lends itself well to iteration, why not use an iterative solution?

    Quote Originally Posted by koplersky
    So there is no rule to when split a function? We could say that it's a matter of taste, always aiming at improve code readability and letting each function doing one job?
    Yes, there is always some kind of judgment call to be made.
    koplersky likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2012
    Location
    Brazil
    Posts
    52
    Thank you laserlight, straight to the point as always.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    In general a lot of people will suggest to perfer the recursive version because it is cleaner, and many will tell you to prefer the iterative version because it may be faster and cant suffer from stack overflow issues, and really they are both right. My take on it is that you should probably start by writing the recursive version, but also try to write the iterative version if for no reason other than to learn how to translate from one to the other. Being able to convert between them is a good skill to have!


    The best, and perhaps most surprising example of the performance of iterative vs recursive that I ever came across, was for Bitonic Sort.
    Basically it can cleverly be done entirely iteratively with no need to maintain an explicit stack, which amounts to nested loops performing the sort in a breadth-first manner,
    Or it can be done recursively, with a doubly-recursive function that calls another function which may also be doubly-recrursive. This then causes the sort to be performed in a totally depth-first manner.
    Or finally, one can create various hybrid approaches with differing amounts of recursion and iteration, where the recursive parts can either be swapped out for the iterative counterparts that perform the sort in a different order, or they can be translated into an iterative form directly, possibly using an explicit stack.
    It turned out in my case that one of the hybrids I created consistently beat both the fully iterative and fully recursive methods. It's not strictly about iteration vs recursion because the order it progresses for each part is different, but it was very interesting nevertheless.
    koplersky likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,500
    It really depends on what you are doing.

    A good example of where recursion may look easier, but not be ideal (given in "C Unleashed") is the Fibonacci Sequence.

    Code:
    int fib(int x)
    {
      if((x == 1) || (x == 2))
      {
        return 1;
      }
      
      return fib(x-2) + fib(x-1);
    
    }
    For this to work on on fib(9), it first calls fib(7), which calls fib(6), and then fib(5)... After that it then calls fib(8), which goes through each calculation again. This can cost a lot of time with larger numbers.

    Another way of approaching this problem would be to not use recursion -
    Code:
    int fib(int x)
    {
      int i, a[3];
    
      if(x<3) return 1;
    
      a[1] = a[0] = 1;
      for(i=2; i<x; ++i)
      {
        a[2] = a[0] + a[1];
        a[0] = a[1];
        a[1] = a[2];
      }
    
      return a[2];
    }
    The performance changed from geometric to linear.

    There are other things, like a binary search - Using recursion to create a VERY efficient search algorithm.

    I suppose that the message that I got from that section of the book was to not use recursion for recursion's sake.

    [edit]
    PS - Thanks for recommending that book to me Salem, it's been great. It covers advanced techniques in C programming, which I couldn't recommend more.

    For others
    Heathfield, R., Kirby, L., et al. (2000), "C Unleashed", Sams Publishing, Dallas. TX
    http://www.amazon.com/C-Unleashed-Ri.../dp/0672318962
    [/edit]
    Last edited by Click_here; 12-11-2012 at 01:55 AM.
    koplersky likes this.
    Fact - Beethoven wrote his first symphony in C

  8. #8
    Registered User
    Join Date
    May 2012
    Location
    Brazil
    Posts
    52
    The way I understood it was that calling functions would make the program run slower, that's why recursion came to my mind.

    Click_here this example is indeed interesting, because when I first learned recursion teachers used a recursive version of the Fibonacci Sequence to explain why it's good. So it's just easier and cleaner.

    Thank you all for the answers.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,170
    Quote Originally Posted by koplersky
    Click_here this example is indeed interesting, because when I first learned recursion teachers used a recursive version of the Fibonacci Sequence to explain why it's good. So it's just easier and cleaner.
    It also happens to be the first problem to which I saw memoization applied
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    May 2012
    Location
    Brazil
    Posts
    52
    Quote Originally Posted by laserlight View Post
    It also happens to be the first problem to which I saw memoization applied
    And from this casual comment I learned a new technique, or at least the concept of something I had already done.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The sorting times for the iterative Quicksort version are due to it's silly choice of the first element of the array/sub-array, as the pivot, and should be ignored.

    The difficultly of handling the stack explicitly is clear, however.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    
    #define INSERT 64
    #define SIZE   100000
    
    void binaryInsertion(void);
    void bubbleSort(void);
    int checkIt(void);
    void insertionSort(int lo, int hi); 
    void middle1(int lo, int hi);
    void quicksortOpt(int lo, int hi);
    void quicksortIter(void);
    void quicksortRecursive(int lo, int hi);
    void fillArray(void);
    void shellSort(void);
    void selectionSort(void);
    void swap(int i, int j);   
    
    int A[SIZE]={0};
    unsigned long long int SWAPS=0;
    int TYPE=0; 
    
    int main(void) {
       int i,j;
       char type[3][11]={{"random"},{"ascending"},{"descending"}};
       clock_t start,stop;
    
       srand(time(NULL));
       for(j=0;j<3;j++) {
          TYPE=j;
          fillArray();
          printf("\nSorting %d integers, initially in %s order. The first 10 numbers:\n\n",SIZE,type[TYPE]);
          for(i=0;i<10;i++)  printf("%6d  ",A[i]); 
          printf("\n");
    /*
          SWAPS=0;
          start=clock();
          binaryInsertion();
          stop=clock();
          printf("    Binary Insertion: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    */   
    /*
          SWAPS=0;
          start=clock();
          bubbleSort();
          stop=clock();
          printf("         Bubble sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    
          SWAPS=0;
          fillArray();
          start=clock();
          middle1(0,SIZE);
          stop=clock();
          printf("        Middle1 sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    
          SWAPS=0;
          fillArray();
          start=clock();
          insertionSort(0,SIZE);
          stop=clock();
          printf("      Insertion sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    */
          SWAPS=0;
          fillArray();
          start=clock();
          quicksortIter();
          stop=clock();
          printf(" Iterative Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    
    
          SWAPS=0;
          fillArray();
          start=clock();
          quicksortOpt(0,SIZE-1);
          stop=clock();
          printf(" Optimized Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    
          SWAPS=0;
          fillArray();
          start=clock();
          quicksortRecursive(0,SIZE-1);
          stop=clock();
          printf(" Recursive Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt());
    
    /*
          SWAPS=0;
          fillArray();
          start=clock(); 
          selectionSort();
          stop=clock();
          printf("      Selection sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt()); 
    */      
          
          SWAPS=0;
          fillArray();
          start=clock(); 
          shellSort();
          stop=clock();
          printf("          Shell sort: %15llu swaps in %10.4f seconds\n\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
          if(checkIt()); 
       } 
    
       for(i=0;i<10;i++)
          printf("%6d  ",A[i]);
       
       
       printf("\n");
       return 0;
    }
    //Binary Insertion Sort  Has a subtle error in it - sorts correctly
    //but overwrites SWAPS++ for Bubble sort. 
    void binaryInsertion(void)
    {
        register int i, m;
        int n=SIZE,hi, lo, tmp;
    
        for (i = 1; i < n; i++) {
            lo = 0, hi = i;
            m = i / 2;
    
            do {
                if (A[i] > A[m]) {
                    lo = m + 1;
                } else if (A[i] < A[m]) {
                    hi = m;
                } else
                    break;
    
                m = lo + ((hi - lo) / 2);
            } while (lo < hi);
     
            if (m < i) {
                tmp = A[i];
                memmove (A + m + 1, A + m, sizeof (int) * (i - m));
                A[m] = tmp;
                SWAPS++;
            }
        }
    }
    void bubbleSort() {   
       int i, n, swapped;
       n = SIZE-1;
       do {
          swapped = 0;
          for(i =0; i < n; i++) {  
             if(A[i] > A[i + 1 ]) {
                swap(i, i + 1);
                ++SWAPS; 
                swapped = 1;
             }
          }
          --n;
       }while(swapped);
    }
    void middle1(int lo, int hi) {
       int i,j,temp;
       for(i=hi-1;i>-1;i--) {      
          for(j=0;j<i;j++) {
             if(A[j] > A[i]) {
                temp=A[j];
                A[j]=A[i];
                A[i]=temp;
                ++SWAPS;
             }
          }
       }
    }
    void insertionSort(int lo, int hi) {
       int i, j, val; 
       for(i=lo+1;i<hi;i++) {  
          val = A[i];
          j = i-1;
          while(A[j]>val) {
             A[j + 1] = A[j];
             ++SWAPS;
             --j;
             if(j<0) 
                break;
          }   
          A[j+1] = val;
       }
    }
      //Quicksort, Iterative
    void quicksortIter(void) {
      int I, J, left, right, stack, pivot,maxStack=0;  
      int ST[64] = { 0 }; //uses ~20 with N=25,000 and range of 0-999
      left = stack = 0; right = SIZE-1; 
                                                    
      while(1) {
        while(left >= right) {         //better with the >=
          if(stack != 0) {             
              right = ST[stack];         
              left = ST[stack - 1]; 
              stack -= 2;
            }
            else { //if T0 == 0, we're done sorting
              printf("maxstack: %d \n",maxStack); 
              return;    //not break 
            }
          }
          pivot = A[left]; 
          I = left+1;    //forward loop counter 
          J = right+1;   //backward loop counter 
         
        
          /* these iterators are touchy */                 
          do {
            while(A[--J] > pivot);      
            while(A[I] < pivot) ++I;  
    
            if(J > I) {
              swap(I, J);
              ++SWAPS;
            }
          }while(J > I);
    
          A[left] = A[J];
          A[J] = pivot;
                                        
          if((J - left) < (right - J))  //take the smallest sub array first
            ST[stack + 1] = J + 1;
                                              
          if(ST[stack + 1] == J + 1) { 
            ST[stack + 2] = right; 
            right = J - 1; 
          }
          else {
            ST[stack + 1] = left; 
            ST[stack + 2] = J - 1; 
            left = J + 1;
          }
          stack = stack + 2;                      //push onto ST[]
          if(stack > maxStack) maxStack = stack;  //debug aid 
                                              
        }
        
    }
    //Optimized Quicksort
    void quicksortOpt(int lo, int hi) {
       int i, j, pivot;
       if(lo == hi) return; 
    
      if(hi - lo < INSERT) {  //The optimizer. Value of
        insertionSort(lo, hi+1);           //INSERT will vary 
        return;
      }
    
       i=lo; 
       j=hi;
       pivot= A[(lo+hi)/2]; 
    
      /* Split the array into two parts */
       do {    
          while (A[i] < pivot) i++; 
          while (A[j] > pivot) j--;
          if (i<=j) {  
             swap(i, j);   //this line works fine.
             SWAPS++;
             i++;
             j--;
          }
       } while(i<=j);
      
       if (lo < j) quicksortOpt(lo, j);
       if (i < hi) quicksortOpt(i, hi);
    }
    
    //Good but unoptimized, Quicksort
    void quicksortRecursive(int lo, int hi) {
       int i, j, pivot;
       if(lo == hi) return; 
       i=lo; 
       j=hi;
       pivot= A[(lo+hi)/2]; 
    
      /* Split the array into two parts */
       do {    
          while (A[i] < pivot) i++; 
          while (A[j] > pivot) j--;
          if (i<=j) {  
             swap(i, j);   //this line works fine.
             SWAPS++;
             i++;
             j--;
          }
       } while(i<=j);
      
       if (lo < j) quicksortOpt(lo, j);
       if (i < hi) quicksortOpt(i, hi);
    }
    void selectionSort()
    {
       int i,j,n=SIZE,min;
        
       for(i = 0; i < n-1; i++) {
          min = i;                 //set min to the firt index  
          for(j = i+1; j < n; j++) {
             if (A[j] < A[min]) {
                min = j;
             }
          }
     
          if( min != i ) {
             swap(i, min);
             SWAPS++;
          }
       }
    }
    
    //Shell sort
    void shellSort(void) {
      int i, j, gap, temp;
      for(gap = SIZE/2; gap > 0; gap /= 2) {
        for(i = gap; i < SIZE; i++) {
          for(j = i - gap; j >= 0 && A[j] > A[j + gap]; j -= gap) {
    	      ++SWAPS;
             temp = A[j];
    	      A[j] = A[j + gap];
            A[j + gap] = temp;
          }
        }
      }
    }
    void swap(int i, int j) {    
       int temp;
       temp = A[i];
       A[i] = A[j];
       A[j] = temp;
    }
    void fillArray(void) {
       int i,j;
       if(TYPE==0) {         //random order
          for(i = 0; i < SIZE; i++)
             A[i] = (rand() % 10000)+1;
       }else if(TYPE==1) {   //ascending order
          for(i=0;i<SIZE;i++)
              A[i]=i;
       }else if(TYPE==2) {   //descending order
          for(j=0,i=SIZE-1;i>=0;i--,j++)
             A[j]=i;
       }
    }
    int checkIt(void) {
       int i;
       for(i=0;i<SIZE-1;i++) {
          if(A[i]>A[i+1]) {
             printf("Error! Not sorted in ascending order.\n");
             return 1;
          }
       }
       return 0;
    }

  12. #12
    Registered User
    Join Date
    Nov 2012
    Posts
    1,220
    Personally, I prefer the iterative version of the fibonacci function, because it exactly matches the mathematical definition.

    If you're really concerned with speed, though, you should focus on algorithms rather than "optimizations". Even with the best optimizations, for example even if writing something with a for loop as opposed to recursive calls turns out to be 10 times faster, all this ever does is give you (slightly) scaled-up performance. What does this mean in terms of the algorithm? It means if your algorithm takes n operations to complete, then even the fastest, heavily-optimized version will still take c * n operations, where c < 1. Notice how this is true for both versions of fibonacci, above. It doesn't matter if you do it recursively or with for loops. And it still doesn't matter even if you apply memoization.

    If you find a better algorithm to solve the problem at hand this is much more meaningful for performance. For example, there is a closed form expression for the fibonacci numbers. What does this mean? It means you can calculate any fibo(n) in only c operations, where c is a constant number of operations to apply the specific formula involved, some of which are exponentiations (which one might think are more expensive than a bunch of additions). Given this approach, the fibo function will now take only c steps to complete, no matter if you do something like fibo(100000) or fibo(7). And then if you're STILL worried that fibo(n) is doing wasteful exponentiations for small n, then just use memoization for the smallest or most commonly requested fibonacci numbers - i.e. just return a pre-computed fibo(n) for, say, the first 100 fibonacci numbers.

  13. #13
    Registered User
    Join Date
    May 2012
    Location
    Brazil
    Posts
    52
    I see, so the difference in performance is not that much.

    Thank you for the answers, and specially Adak for the fine sample code.

  14. #14
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    993
    I see, so the difference in performance is not that much.
    If you mean the difference between iterative and recursive, the performance difference probably isn't an issue. However, the fact that the stack on many systems is rather limited, combined with the fact that C does not mandate tail-call elimination, means that recursion is usually a bad idea unless you know the function will recurse a limited number of times.

    Functional languages (e.g. Erlang, Haskell, etc.), which do not have looping constructs, require recursion, but do tend to require tail-call elimination where possible, so recursion can be safe.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,170
    Quote Originally Posted by c99tutorial
    Personally, I prefer the iterative version of the fibonacci function, because it exactly matches the mathematical definition.
    Eh, the recursive version exactly matches the mathematical definition since expressing it as a recurrence relation is err... mathematical.

    Quote Originally Posted by c99tutorial
    Notice how this is true for both versions of fibonacci, above. It doesn't matter if you do it recursively or with for loops. And it still doesn't matter even if you apply memoization.
    It is not true for both versions of Fibonacci presented above: the iterative version and the recursive version with memoization both run in linear time, but Click_here's point was that that is not the case for the recursive version without memoization. The thing is, applying memoization changes the algorithm: you're doing table lookups instead of continually re-computing.

    Quote Originally Posted by c99tutorial
    For example, there is a closed form expression for the fibonacci numbers. What does this mean? It means you can calculate any fibo(n) in only c operations, where c is a constant number of operations to apply the specific formula involved, some of which are exponentiations (which one might think are more expensive than a bunch of additions). Given this approach, the fibo function will now take only c steps to complete, no matter if you do something like fibo(100000) or fibo(7).
    Heh, I once asserted the same thing to a prof of mine, who then pointed out that the exponentation/square root calculations run in logarithmic time (if I remember correctly). So, it is not really c steps to complete (i.e., constant time), but it certainly is asymptotically faster than linear time.
    Click_here likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pointers and function calls inside a function
    By lexitron in forum C Programming
    Replies: 1
    Last Post: 12-03-2011, 05:43 PM
  2. Replies: 19
    Last Post: 09-08-2011, 08:56 AM
  3. Performance and footprint of virtual function
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-31-2008, 07:34 PM
  4. Performance Timing Function
    By rosicky2005 in forum C++ Programming
    Replies: 11
    Last Post: 05-31-2007, 04:09 PM
  5. Function calls
    By cpluspluser in forum C++ Programming
    Replies: 1
    Last Post: 04-09-2003, 07:20 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21