Take the 2-minute tour ×

According Scott Meyers, in his Effective STL book - item 46. He claimed that std::sort is about 670% faster than std::qsort due to the fact of inline. I tested myself, and I saw that qsort is faster :( ! Could anyone help me to explain this strange behavior?

#include <iostream>
#include <vector>
#include <algorithm>

#include <cstdlib>
#include <ctime>
#include <cstdio>

const size_t LARGE_SIZE = 100000;

struct rnd {
    int operator()() {
        return rand() % LARGE_SIZE;

int comp( const void* a, const void* b ) {

int main() {
    int ary[LARGE_SIZE];
    int ary_copy[LARGE_SIZE];
    // generate random data
    std::generate( ary, ary + LARGE_SIZE, rnd() );
    std::copy( ary, ary + LARGE_SIZE, ary_copy );
    // get time
    // perform quick sort C using function pointer
    std::qsort( ary, LARGE_SIZE, sizeof( int ), comp );
    std::cout << "C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
    // get time again
    start = std::clock();
    // perform quick sort C++ using function object
    std::sort( ary_copy, ary_copy + LARGE_SIZE );
    std::cout << "C++ quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";

This is my result:

C quick-sort time elapsed: 0.061
C++ quick-sort time elapsed: 0.086
Press any key to continue . . .


Effective STL 3rd Edition ( 2001 )
Chapter 7 Programming with STL

Best regards,

share|improve this question
Did you let your compiler optimize? Debug/unoptimized builds won't take full advantage of things like inlining. –  Crazy Eddie Jan 16 '11 at 21:23
Understanding how quick sort works, would give you a better idea of how to test it, in short: 1. use a larger array, eg: 10^6 in size, then populate the array in descending order 999999... 4,3,2,1 - this will cause the sort to become O(n^2), doing this will effectively demonstrate why inlining comparators makes such a big difference in this particular algorithm. –  Matthieu N. Jan 16 '11 at 21:24
@Zenikoder- Almost no implementations of qsort or sort will use a quicksort implementation that breaks on reverse-sorted inputs. The most common STL sort implementation uses introsort, which introspects on the quicksort routine to ensure it never degrades to worse than O(n lg n), and I'm fairly confident that the C qsort routine uses something similar (or at least a heuristic like median-of-three) to prevent this. –  templatetypedef Jan 16 '11 at 21:26
@Noah: According to a 06 article on artima SM: "I’ll begin with what many of you will find an unredeemably damning confession: I have not written production software in over 20 years, and I have never written production software in C++." He calls himself an archeologist/anthropologist of the C++ language. –  Matthieu N. Jan 16 '11 at 21:30
@Chan: The Bentley and McIlroy paper can be found here: cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol23/issue11/… –  Matthieu N. Jan 16 '11 at 21:54

6 Answers 6

up vote 58 down vote accepted

std::clock() is not a viable timing clock. You should use a platform-specific higher resolution timer, like the Windows High Performance Timer. More than that, the way that you call clock() is that first, text is output to the console, which is included in the time. This definitely invalidates the test. In addition, make sure that you compiled with all optimizations.

Finally, I copied and pasted your code, and got 0.016 for qsort and 0.008 for std::sort.

share|improve this answer
+1 for actually benchmarking. –  Billy ONeal Jan 16 '11 at 21:25
@DeadMG: Thanks! I changed to release mode, and I got the similar result. I really love Scott Meyers, and I trust his word ;) –  Chan Jan 16 '11 at 21:27
Text seems to be is output on both cases so it can not exactly make the outcome invalid. –  Öö Tiib Jan 16 '11 at 21:29
@Oo Tiib: Text being output doesn't mean that it doesn't output in the same time. What if the buffer is somewhat bigger than the first but less than the second? Now it has to flush before the second call- but it didn't in the first call. Oh dear. I'm not very happy though because I fixed all the above problems and qsort is now a lot faster. :( –  Puppy Jan 16 '11 at 21:33
@DeadMG: std::qsort requires "The return value of this function should represent whether elem1 is considered less than, equal to, or greater than elem2 by returning, respectively, a negative value, zero or a positive value." operator< does not meet that requirement (specifically it returns only 0 or 1). Check to make sure that std::sort and std::qsort produce the same results in your testing :) (Just changing - to < results in qsort returning the wrong answer for me) –  Billy ONeal Jan 17 '11 at 0:04

I am surprised that no one mentions caches.

In your code, you start by touching ary and *ary_copy* so they are resident in the cache at the time of qsort. During qsort, *ary_copy* might get evicted. At the time of std::sort, the elements would have to be fetched from memory or a larger (read slower) cache level. This will of course depend on your cache sizes.

Try to reverse the test, i.e., start by running std::sort.

As some people have pointed out; making the array larger will make the test more fair. The reason is that a large array is less likely to fit in cache.

share|improve this answer
I am surprised no one mentioned any strategies to measure the actual effectiveness of the code. You can write a tiny program that sorts a few hundred elements, get everything loaded into your L1 cache, and rip through that in record time, but that is in no way going to reflect your actual program running on a system with a few hundred other active processes, doing context switches because you're compute-bound and the scheduler hates you, while sorting a dataset the size of New Jersey. Make your benchmark look much like the real application. –  Wexxor Jul 12 '13 at 22:37

std::clock is not accurate enough for benchmarking. You would need to use the high resolution performance timers available for your platform (QueryPerformanceCounter on Windows, not sure on POSIX) in order to get meaningful results here.

The other issue with std::clock, is that even if it was 100% accurate, if your process is no longer active on the machine (i.e. there has been a context switch), that is not accounted for in testing.

Scott Meyers' measurements are only valid for the one implementation he tested on which performed that poorly. He says that he tested on several implementations, and it's entirely possible the difference for your particular implementation is less than 600 some percent.

Finally, as @templatetypedef stated, meaningful benchmarks can only be done with release (optimizations on) builds.

EDIT: Using the following code:

#define _SCL_SECURE 0
#include <stdlib.h>
#include <ctime>
#include <algorithm>
#include <vector>
#include <iostream>
#include <windows.h>

//Shamelessly using Windows specific stuff here because we're benchmarking.

static const unsigned __int64 numInts = 100000000ull;

int qCmp(const void * a, const void * b)
    return *static_cast<const int *>(a) - *static_cast<const int *>(b);

int main()
    LARGE_INTEGER start, afterSort;
    std::vector<int> arrayToSort(numInts);
    std::srand(static_cast<unsigned int>(std::time(0)));
    std::generate_n(arrayToSort.begin(), numInts, std::rand);
    std::vector<int> arrayToQSort(arrayToSort);
    std::qsort(&arrayToQSort[0], numInts, sizeof(int), qCmp);
    std::cout << "Qsort took     " << afterSort.QuadPart - 
        start.QuadPart << " ticks." << std::endl;
    std::sort(arrayToSort.begin(), arrayToSort.end());
    std::cout << "std::sort took " << afterSort.QuadPart -

I get (on an AMD Athlon II "Regor" overclocked to 3.5GHZ running Windows 7 Ultimate):

c:\Users\Billy\Documents\Visual Studio 2010\Projects\Test\x64\Release>Test.exe
Qsort took     28849379 ticks.
std::sort took 21859763 ticks.

a win for std::sort, but nowhere near the stipulated 600 some percent.

This of course is without even discussing the other advantages of std::sort over qsort, such as the ability to reliably sort non POD types, the automatic selection of a user defined operator< overload, and type safety.

EDIT2: In response to @DeadMG:

int qCmp2(const void * a, const void * b)
    //This is what you'd have to do if you wanted to do it in terms of `operator<` --
    //qsort is almost half as fast as `std::sort` with this comparison function.
    int ac = *static_cast<const int *>(a);
    int bc = *static_cast<const int *>(b);
    if (ac < bc)
        return -1;
    else if (bc < ac)
        return 1;
        return 0;
share|improve this answer
Thanks! I got the idea. –  Chan Jan 16 '11 at 21:25
Apparently QueryPerformanceCounter is sort of a "wall clock" and not per process: drdobbs.com/184416651 –  6502 Jan 17 '11 at 7:17
@6502: What exactly in that article indicates that it's a wall clock? I don't see anything there to that effect. Why then does NT have a specific LARGE_INTEGER field for the performance timer use in the TEB (Thread Environment Block) if it's a wall clock? –  Billy ONeal Jan 17 '11 at 16:16
Here is the quote "GetTickCount(), timeGetTime(), GetSystemTime()/GetSystemTimeAsFileTime(), and QueryPerformanceCounter() all yield values on a systemwide basis. In other words, they measure absolute times on the system, so if the system has other busy processes, the measured values will reflect that activity". May be the article is wrong of course... I'm not an expert about win32 APIs (I like more writing portable code unless forced). –  6502 Jan 17 '11 at 22:47

On my machine adding some meat (making the array 10 million elements and moving it in the data section) and compiling with

g++ -Wall -O2 -osortspeed sortspeed.cpp

I get as result

C quick-sort time elapsed: 3.48
C++ quick-sort time elapsed: 1.26

Be also careful about modern "green" CPUs that may be configured to run at a variable speed depending on the load of the system. When benchmarking this kind of behavior can drive you crazy (on my machine I've setup two small script normal and fast that I can use when making speed tests).

share|improve this answer
"Green" CPUs don't matter if you're using performance counters (as you should be doing for meaningful benchmark results) –  Billy ONeal Jan 16 '11 at 21:50
Performance counters are great, but clock is not that bad if you're not trying to measure small stuff. Also clock() is per-process, perf counters are global. –  6502 Jan 16 '11 at 21:59
@6502: You have that reversed. Perf counters are per process, clock is global. –  Billy ONeal Jan 16 '11 at 23:49
@Billy ONeal: I thought you meant RDTSC and that's very nice but global. And no, clock() is a per-process counter. See cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_19.html –  6502 Jan 17 '11 at 0:29
@6502: glibc != standard c. Usually I believe these things are implemented in terms of rdtsc, but the OS keeps track of what the timestamps are when it performs a context switch, and restores these values when the context is given back to the process being measured. –  Billy ONeal Jan 17 '11 at 0:35

Another reason that qsort may perform much better than expected is that newer compilers can inline and optimize through the function pointer.

If the C header defines an inline implementation of qsort instead of implementing it inside of a library and the compiler supports indirect function inlining, then qsort can be just as fast as std::sort.

share|improve this answer

The two sorting algorithms, without optimizations enabled, should have comparable performance. The reason that the C++ sort tends to appreciably beat qsort is that the compiler can inline the comparisons being made, since the compiler has type information about what function is being used to perform the comparison. Did you run these tests with optimization enabled? If not, try turning it on and running this test again.

share|improve this answer
Thanks! I'm using Visual Studio, and I really don't know how to turn optimization on. –  Chan Jan 16 '11 at 21:24
@Chan: Switch to using the "Release" build. Also make sure you don't run the program from whithin visual studio for your benchmarks -- things like debuggers will change the time characteristics of your program. –  Billy ONeal Jan 16 '11 at 21:24
@Billy ONeal: I switched to Release, and I got the expected result. Happy ^_^ ! –  Chan Jan 16 '11 at 21:28

Your Answer


