Sorting in C++: 3 times faster than C(radiospiel.org)
radiospiel.org
Sorting in C++: 3 times faster than C
http://radiospiel.org/sorting-in-c-3-times-faster-than-c
44 comments
This example highlights the reasons to avoid function pointers when possible.
An apples to apples comparison would use a handwritten sort routine for C instead of using a library function: STD::sort is closer to writing your own sort and putting in the function calls than calling an external function.
An apples to apples comparison would use a handwritten sort routine for C instead of using a library function: STD::sort is closer to writing your own sort and putting in the function calls than calling an external function.
I don't agree with how you define "apples".
I would define an apples to apples comparison as "How would a typical C developer write this test? How would a typical C++ developer write this test?"
A typical C developer would use a library function. A typical C++ developer would use the stl.
This was a great article for me because I am actually about to write some very performance intensive data manipulation code that will use sorting and other similar algorithms. I was thinking about doing it in C because I always mentally associate C with performance.
This article is a reminder to me that although I could eventually laboriously hand-tweak the C to be performant, there are things in C++ that will perform better than C without my even having to do much optimization, if any.
I would define an apples to apples comparison as "How would a typical C developer write this test? How would a typical C++ developer write this test?"
A typical C developer would use a library function. A typical C++ developer would use the stl.
This was a great article for me because I am actually about to write some very performance intensive data manipulation code that will use sorting and other similar algorithms. I was thinking about doing it in C because I always mentally associate C with performance.
This article is a reminder to me that although I could eventually laboriously hand-tweak the C to be performant, there are things in C++ that will perform better than C without my even having to do much optimization, if any.
FTA:
I agree that the language provides convenience, but the statement that sorting as a concept is faster in C++ than in C seems to be a stretch.
By inlining C++ is able to run just the raw algorithm. On the opposite the C code has a number of indirections
I agree that the language provides convenience, but the statement that sorting as a concept is faster in C++ than in C seems to be a stretch.
>STD::sort is closer to writing your own sort and putting in the function calls than calling an external function
No it's not, that's like saying that using inline operators for vector addition is the same as manually inlineing the code or that manually unrolling a loop is the same as the compiler doing it - by that logic everything is expanded to assembly therefore you should write it in hand optimized assembly to get a "decent comparison" (or LLVM if you want portability) and conclude that assembly is "faster" than C/C++.
Of course there is a reason C++ is faster - it's not magic - it compiles and runs on same hardware - but the point is that it has better abstractions that deliver more for similar code - C provides weak abstractions that don't make this sort of optimization easy for the compiler, so unless you like manually rolling out a sort function every time you need to use it it's actually slower than C++. Same goes for collection libraries, small vectors (eg. 3d vectors), etc. And it's worth pointing out because a lot of people assume low level == fast.
No it's not, that's like saying that using inline operators for vector addition is the same as manually inlineing the code or that manually unrolling a loop is the same as the compiler doing it - by that logic everything is expanded to assembly therefore you should write it in hand optimized assembly to get a "decent comparison" (or LLVM if you want portability) and conclude that assembly is "faster" than C/C++.
Of course there is a reason C++ is faster - it's not magic - it compiles and runs on same hardware - but the point is that it has better abstractions that deliver more for similar code - C provides weak abstractions that don't make this sort of optimization easy for the compiler, so unless you like manually rolling out a sort function every time you need to use it it's actually slower than C++. Same goes for collection libraries, small vectors (eg. 3d vectors), etc. And it's worth pointing out because a lot of people assume low level == fast.
FTA:
If you want to argue that the C++ standard library has more utilities to simplify these optimizations, certainly I will agree. I think, however, that the statement that "sorting in C++ is 3 times faster than C" is an unsubstantiated leap.
By inlining C++ is able to run just the raw algorithm. On the opposite the C code has a number of indirections
If you want to argue that the C++ standard library has more utilities to simplify these optimizations, certainly I will agree. I think, however, that the statement that "sorting in C++ is 3 times faster than C" is an unsubstantiated leap.
By rolling your own I meant manually unroling a sort for each type instance you use it for. Sure you can use a macro but that's just nasty.
Anyway I don't think anyone thinks C++ is magic but I guess the title could be cleaner "sorting with standard libraries C++ 3 times faster".
Anyway I don't think anyone thinks C++ is magic but I guess the title could be cleaner "sorting with standard libraries C++ 3 times faster".
of course you can. the whole point is that you don't have to.
Or rather, "Sorting with std::sort: 3 times faster than qsort".
Exactly. std::sort does NOT use quick sort. So all he's doing is comparing two different algorithms. It has nothing to do with C vs C++.
That's not exactly true. `std::sort` can use quick sort. It depends on the implementation.
As well as `qsort`. It is also not guaranteed to use quick sort.
E.g., here is the BSD qsort: http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd...
Here is the glibc one: http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
As well as `qsort`. It is also not guaranteed to use quick sort.
E.g., here is the BSD qsort: http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd...
Here is the glibc one: http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
The more relevant difference here is probably compile-time generic code which can take advantage of inlining vs run-time generic code which can't.
However, C compilers are smart enough to transform the latter into the former, but only if you let them.
However, C compilers are smart enough to transform the latter into the former, but only if you let them.
std::sort isn't guaranteed to use any particular algorithm, but IIRC quicksort fits the requirements and hence has been used in the past, even if introsort might be more common now.
I believe said requirements were written to allow qsort.
The point is, unless you are using some macro magic in C, you'll almost always have to make such a compromise to get an abstracted out sort function.
Not really - optimizers are smart enough to get the same performance out of runtime-generic C code using void* and function pointers; after all, it's a simple matter of type inference and constant propagation.
However, that's only true if you let them do their job, ie use link-time optimizations or code inclusion (which is where most of the template performance comes from).
Including the source of qsort() instead of linking against a DLL blob might be enough to make the C code perform as well as the C++ code.
However, that's only true if you let them do their job, ie use link-time optimizations or code inclusion (which is where most of the template performance comes from).
Including the source of qsort() instead of linking against a DLL blob might be enough to make the C code perform as well as the C++ code.
Link time optimization doesn't seem to make too much of a difference for GCC. You'll find some anecdotal data below. [1] Now I did it by building a static binary and enabling -ftlo (did both dynamic and static, didn't seem to matter). Pulling the code in manually would be an interesting test to see how it does and if the optimizer just isn't able to do it well itself. I think though using -flto is likely how many C coders would first approach the problem thinking the same thing you were, but it would appear that gcc isn't up to the task yet.
I'll update the gist with clang results as I get them built and tested.
[1] https://gist.github.com/acb454957e7e6d86f968
I'll update the gist with clang results as I get them built and tested.
[1] https://gist.github.com/acb454957e7e6d86f968
LTO only works if you statically link against a LTO-enabled libc version.
Of course you won't see any performance improvements if you only build your executable with LTO, but still link dynamically or statically against a non-LTO capable libc.
Of course you won't see any performance improvements if you only build your executable with LTO, but still link dynamically or statically against a non-LTO capable libc.
Ok, that's something I was unaware of. Makes me tempted to get a system setup to do a real test of it then. I had assumed that since the static libc is a copy of the object files going in that it would be able to do the LTO even at that stage. I don't think I want to play with getting my system built for doing LTO like that and risking instability on my main machine.
While I agree that this is totally possible, are there any shipping, non-buggy optimizers that do this? Sometimes C/C++ seems purposely designed to make the compiler/optimizer's job difficult.
I didn't test it with qsort() specifically (my use case was merge-sorting a linked list), but both gcc and clang are able to perform such optimizations.
I would be surprised if other high-performance compilers were unable to do so.
I would be surprised if other high-performance compilers were unable to do so.
To level the playing field, I took the glibc quicksort implementation from http://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib... (which is actually a hybrid algorithm), modified it to use a comparison function with signature _Bool(const void* , const void* ) as we're only interested in whether an element is less than another, and included the source code verbatim (which is essentially what including <algorithm> does).
The C++ code still outperformed the C code, but the ratio dropped from ~2.8 to ~1.4.
40% performance gain is nothing to sneeze at, but it's far less impressive than the sensational 3x from the headline.
The remaining difference is probably due to the choice of algorithm: the GNU STL algorithm is introsort. While it's also a hybrid algorithm based on quicksort, it adds heapsort to the mix, which is known to outperform quicksort on random data.
The C++ code still outperformed the C code, but the ratio dropped from ~2.8 to ~1.4.
40% performance gain is nothing to sneeze at, but it's far less impressive than the sensational 3x from the headline.
The remaining difference is probably due to the choice of algorithm: the GNU STL algorithm is introsort. While it's also a hybrid algorithm based on quicksort, it adds heapsort to the mix, which is known to outperform quicksort on random data.
[deleted]
How can one "limit branching", and "optimize for the second level memory cache"?
One way to limit branching is to try to make applications of each operation as temporally contiguous as possible. That is, rather than take each data item and apply each operation to it, structure the operations so they can each be applied to the entire data set, one after the other. The branch predictor is happy because you're predictably looping over a simpler piece of code. The I-cache is happy because you're looping over a smaller piece of code.
Optimizing for the second level memory cache means making your data access patterns predictable (the above suggestion helps here, too) and keeping your data compact to get as much use out of each cache line as possible: Do you really need a 64-bit size_t to store an index into an array that will never be larger than a few thousand elements?
Optimizing for the second level memory cache means making your data access patterns predictable (the above suggestion helps here, too) and keeping your data compact to get as much use out of each cache line as possible: Do you really need a 64-bit size_t to store an index into an array that will never be larger than a few thousand elements?
I split the code in two binaries: "code" (qsort) and "code2" (std::sort()) and then I ran both under a profiler (based on intel's performance counters).
It seams that qsort simply executes an order of magnitude more instructions for the same result than std::sort. On the other hand std::sort() code, even if it's faster, it has more branch miss-predictions.
Here [1] are the results if you want to have a look.
[1] https://gist.github.com/b97a6395c9a20c3d4cea
It seams that qsort simply executes an order of magnitude more instructions for the same result than std::sort. On the other hand std::sort() code, even if it's faster, it has more branch miss-predictions.
Here [1] are the results if you want to have a look.
[1] https://gist.github.com/b97a6395c9a20c3d4cea
Thanks, that is quite interesting.
Limit branching: code like "a < b ? 1 : b < a ? -1 : 0" (yes, this is more or less my comparison function) is bad, because the CPU has to predict 2 comparisons, and CPU prediction os probably right at only ~50%. If prediction fails, then the queue of already "parsed" instructions gets flushed, and the CPUs processing unit has to wait for new instructions. Code which does not branch usually runs faster.
Therefore (a-b) would be a better comparison function, if you guarantee it does not overflow.
Therefore (a-b) would be a better comparison function, if you guarantee it does not overflow.
Loop unroll for limit branching.
You can sort what's in cache, then load a new chunk of data into cached and sort it ... then merge the sorted chunks.
Sometimes, you can also get rid of branches by using arithmetic. For example, see http://stackoverflow.com/questions/1610836/branchless-code-t... or google "Branchless coding".
every once in a while some one would come out with this kind of stupid study. please do not post these results any more, it is just a waste of time.
Well, every once in a while someone comes out with "C++ is slow because of vtables". Which is false. If those guys would stop posting this I would stop writing what is true (but probably not too relevant for most screnarios, yes.)
[deleted]
This was also explained in the book "Programming Pearls".
Shouldn't he be using getrusage() instead of gettimeofday() in his timer code (https://gist.github.com/2057981)?
When writing profiling code (https://github.com/vstefan/Instrum/), I use clock_gettime(CLOCK_MONOTONIC) as it measures elapsed time from an arbitrary reference point.
...which is still measuring real time, not the time spent by the current process, or am I wrong? (maybe the downvoter can explain)
Reading your blog's "About me" section makes me sad.
"I am working as a freelance software architect, IT consultant, ..."
"I am working as a freelance software architect, IT consultant, ..."
And what exactly makes you sad in this?
An IT consultant/software architect who thinks he can compare C and C++ by calling a random sort function makes me sad...
People that cannot even parse headlines make me more sad: I compare sorting in C++ and C.
OMG, you really don't get it, right?
For example, couldn't you just inline the relevant code manually in C? Sure it would be ugly, but it would be fast. Besides, in an absolute sense pretty much any C or C++ code is going to be ugly; if you want pretty code and a compiler that valiantly tries to optimize it, use something like Haskell :P.