Thread: merge sort: recursive is fasfter than non-recursive

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    6

    merge sort: recursive is faster than non-recursive

    greeting all:

    i'm making merge sort function for arrays as a project in my computer science class and found a very interesting phenomina. i implemented both recursive and non-recursive versions and non-recursive version is much slower than recursive version. ( OS: Windows XP Pro. compiler: Microsoft Visual Studio 2005 Pro. Ed. )

    excuse me for my messy source code but you can find my recursive version as MergeSort and non-recursive version as MergeSort2.

    does anyone know why recursive version is faster than non-recursive version? i suspect that somehow compiler optimized well so that CPU cached function's return address and other information in register rather than in main memory but i'm not really familier with that kinda hardware related topics so... any help please.

    sincerely,
    Last edited by rio_cat; 11-24-2006 at 10:45 PM.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    You shouldn't cast malloc().

    It could be that your compiler optimises recursive functions very well. Test it with simpler recursive functions, and see if you get the same results . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    6

    simpler recursive functions?

    Quote Originally Posted by dwks
    You shouldn't cast malloc().

    It could be that your compiler optimises recursive functions very well. Test it with simpler recursive functions, and see if you get the same results . . .
    Thank you for replying me. I wasn't "casting" malloc at the first place but when I tried g++, he errored out all casting between void* and unsinged char* that's why I had to change it. However, clock() returns time in seconds in linux so couldn't measure time... do you know any alternative ways to do it in linux? Or could you compile my source code in your environment and see if you can get a same result?

    Though what do you mean by simpler recursive function though? You mean something like this:

    Code:
    exp( double base , int x ) {
    if (x == 0) return 1;
    else return exp(base,x-1);
    }
    
    exp2( double base , int x ) {
    double exp=1.0;
    
    while (exp--) {exp*=base;}
    
    return base;
    }
    Thanks a lot,

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by rio_cat
    I wasn't "casting" malloc at the first place but when I tried g++, he errored out all casting between void* and unsinged char* that's why I had to change it.
    The real fix is to use a C compiler to compile C code.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I wasn't "casting" malloc at the first place but when I tried g++, he errored out all casting between void* and unsinged char* that's why I had to change it.
    There's your problem right there. C++ compilers do complain about casting from void* pointers to other pointers, but C compilers don't. You only need to cast malloc() if you're using a C++ compiler, in which case you should be using a C compiler. Use gcc in your case instead of g++.

    However, clock() returns time in seconds in linux so couldn't measure time... do you know any alternative ways to do it in linux? Or could you compile my source code in your environment and see if you can get a same result?
    No, I know how to get millisecond accuracy in Windows, but not Linux. I've heard of gettimeofday(), though, and I'm sure you can find an answer on this board by searching.

    I can't compile on this computer, but I will ASAP if I remember. You could try another Windows compiler yourself, such as Dev-C++, or turn on/off optimisations and see what happens.

    That's exactly what I meant by a simpler recursive/iterative function. Do you get the same results (recursive faster)?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Nov 2006
    Posts
    6
    I executed the following code and turned out that recursive version is slower.
    Code:
    int main() {
    	time_t	start;
    
    	start=clock();
    	exp(2.7,100000);
    	printf("recursive:%d\n",clock()-start);
    
    	start=clock();
    	exp2(2.7,100000);
    	printf("non-recursive:%d\n",clock()-start);
    
    	return 0;
    }

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    6
    Quote Originally Posted by Dave_Sinkula
    The real fix is to use a C compiler to compile C code.
    Quote Originally Posted by dwks
    Use gcc in your case instead of g++.
    Thank you. I didn't know that g++ was a C++ compiler. Even though C is my primary language, as you can see, my knowledge about Linux/UNIX is really limited.
    Last edited by rio_cat; 11-25-2006 at 10:14 PM.

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Quote Originally Posted by rio_cat
    I executed the following code and turned out that recursive version is slower.
    Code:
    int main() {
    	time_t	start;
    
    	start=clock();
    	exp(2.7,100000);
    	printf("recursive:%d\n",clock()-start);
    
    	start=clock();
    	exp2(2.7,100000);
    	printf("non-recursive:%d\n",clock()-start);
    
    	return 0;
    }
    So if not all recursive functions on your machine are slower, then it must be the way the compiler optimised your merge sorting functions. I don't know why this is, though.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    6

    Thank you everyone

    Thank you everyone. It's still interesting that recursive version is faster but I had to give up because I'm pretty much ran out of time. For future reference, I'll post the data sheet I obtained and source code of all of my merge sort functions.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 09:47 PM
  2. Merge Sort
    By blindman858 in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2005, 11:14 AM
  3. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  4. Recursive Array Sort
    By Nakeerb in forum C++ Programming
    Replies: 3
    Last Post: 12-13-2002, 08:27 PM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM