merge sort: recursive is fasfter 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,

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

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,

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.

Quote:

---

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

Quote:

---

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

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

---

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.

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.

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.