Does anyone know if the standard C library function qsort is pre-optimized? I am assuming the object code was compiled using, say, gcc with a -O option.
The reason I am asking is because I have to compare processing times for my homegrown quicksort function to the built-in qsort (which may or may not actually use quicksort). If I don't optimize I run 2-3 times slower than qsort, if I optimize fully, I run ~.7 seconds faster.
The C library is probably optimized, but not aggressively.Originally Posted by MacNilly
Also, quoting sort time is kind of meaningless unless you specify the size of your data set. Make a graph of say, N = 10 to N = 10000 of the times for your sort vs. qsort(). That's a better way to see how you're doing.
EDIT: Furthermore, test the performance of your sort on various distributions of values. What happens if the input is already sorted? Reverse-sorted? Consists all of a single value? Etc.
Last edited by brewbuck; 11-01-2007 at 07:06 PM.
I'd expect the c-library to be compiled with -O2 or -Os [which is essentially -O2 but with less inlining and unrolling]. That is in Linux. I haven't seen the build scripts for MS Libraries, but I would expect that they have decent optimization enabled.
Is your own function using callbacks for compares, or are you comparing "inline"? If you are comparing inline, then that would help your function by a fair bit.
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
Since this is for a class assignment, I am required to use a callback for comparisons. Actually the parameters are exactly the same as qsort.
The assignment only asks for a test of 1000 cases each sorting 20000 randomly-generated numbers. Since I am not using median-of-three or some other algorithm to select my pivot I am fairly sure that I will get O(N^2) on a already sorted list. Reverse sorted, probably the same. Although median of three is not required for this assignment, I am still thinking of a way to find the median item using only pointer arithmetic.
That's pretty decent. I expect that if you use "fully optimized" as -O3, you'd get better results than the C library, since the latter has to compromise between "max" optimization and code-bloat, so it may not get quite as good optimization. Also, if you compile your function directly into the code, it may use more inlining than the C library can do - not sure about that. You could have a look at the generated code in your case, and compare it with the objdump of the C library function, of you really want to know where the difference is.
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
