5 ms·

Sorting in C++: 3 times faster than C

21 points by radiospiel 15y ago

udp 15y ago
Or rather, "Sorting with std::sort: 3 times faster than qsort".
- thedigitalengel 15y ago
  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.
  - cygx 15y ago
    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.
    - rmcclellan 15y ago
      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.
      - cygx 15y ago
        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.
    - simcop2387 15y ago
      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 https://gist.github.com/acb454957e7e6d86f968
      - cygx 15y ago
        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.
        simcop2387 15y ago
        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.
- osolo 15y ago
  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++.
  - archangel_one 15y ago
    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.
    - steve-howard 15y ago
      I believe said requirements were written to allow qsort.
  - albertzeyer 15y ago
    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/kern/qsort.c 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 http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
  - cygx 15y ago
    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.
VMG 15y ago
Shouldn't he be using getrusage() instead of gettimeofday() in his timer code (https://gist.github.com/2057981 https://gist.github.com/2057981)?
- psyren 15y ago
  When writing profiling code (https://github.com/vstefan/Instrum/ https://github.com/vstefan/Instrum/), I use clock_gettime(CLOCK_MONOTONIC) as it measures elapsed time from an arbitrary reference point.
  - VMG 15y ago
    ...which is still measuring real time, not the time spent by the current process, or am I wrong? (maybe the downvoter can explain)
livebeef 15y ago
This was also explained in the book "Programming Pearls".
lzm 15y ago
How can one "limit branching", and "optimize for the second level memory cache"?
- infiniteburp 15y ago
  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.
  - Someone 15y ago
    Sometimes, you can also get rid of branches by using arithmetic. For example, see http://stackoverflow.com/questions/1610836/branchless-code-that-maps-zero-negative-and-positive-to-0-1-2 http://stackoverflow.com/questions/1610836/branchless-code-t... or google "Branchless coding".
- twoodfin 15y ago
  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?
- hanbam 15y ago
  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 https://gist.github.com/b97a6395c9a20c3d4cea
tikhonj 15y ago
Couldn't you replicate most of C++'s optimizations by hand in C? Because that's what I always took to be the real reason C is fast--not because pretty code is fast, but because you can make the code as ugly as you want (hello instrinsics!) to optimize it. 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.
- baq 15y ago
  of course you can. the whole point is that you don't have to.
- veyron 15y ago
  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.
  - moonchrome 15y ago
    >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.
deleted 15y ago
[deleted]
chj 15y ago
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.
- radiospiel 15y ago
  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 15y ago
[deleted]
KonradKlause 15y ago
Reading your blog's "About me" section makes me sad. "I am working as a freelance software architect, IT consultant, ..."
- radiospiel 15y ago
  And what exactly makes you sad in this?
  - KonradKlause 15y ago
    An IT consultant/software architect who thinks he can compare C and C++ by calling a random sort function makes me sad...
    - radiospiel 15y ago
      People that cannot even parse headlines make me more sad: I compare sorting in C++ and C.
      - KonradKlause 15y ago
        OMG, you really don't get it, right?
        dkersten 15y ago
        I don't get it either - whats the problem?
        cygx 15y ago
        The headline implies that C++ as a language is superior to C as far as performance is concerned, whereas all that was shown is that the STL is superior to the libc from a batteries-included point of view.
cygx 15y ago
To level the playing field, I took the glibc quicksort implementation from http://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/qsort.c;hb=HEAD 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.

21 points by radiospiel 15y ago

udp 15y ago

Or rather, "Sorting with std::sort: 3 times faster than qsort".

thedigitalengel 15y ago
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.
- cygx 15y ago
  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.
  - rmcclellan 15y ago
    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.
    - cygx 15y ago
      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.
  - simcop2387 15y ago
    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 https://gist.github.com/acb454957e7e6d86f968
    - cygx 15y ago
      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.
      - simcop2387 15y ago
        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.
osolo 15y ago
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++.
- archangel_one 15y ago
  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.
  - steve-howard 15y ago
    I believe said requirements were written to allow qsort.
- albertzeyer 15y ago
  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/kern/qsort.c 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 http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
- cygx 15y ago
  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.

VMG 15y ago

Shouldn't he be using getrusage() instead of gettimeofday() in his timer code (https://gist.github.com/2057981 https://gist.github.com/2057981)?

psyren 15y ago
When writing profiling code (https://github.com/vstefan/Instrum/ https://github.com/vstefan/Instrum/), I use clock_gettime(CLOCK_MONOTONIC) as it measures elapsed time from an arbitrary reference point.
- VMG 15y ago
  ...which is still measuring real time, not the time spent by the current process, or am I wrong? (maybe the downvoter can explain)

livebeef 15y ago

This was also explained in the book "Programming Pearls".

lzm 15y ago

How can one "limit branching", and "optimize for the second level memory cache"?

infiniteburp 15y ago
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.
- Someone 15y ago
  Sometimes, you can also get rid of branches by using arithmetic. For example, see http://stackoverflow.com/questions/1610836/branchless-code-that-maps-zero-negative-and-positive-to-0-1-2 http://stackoverflow.com/questions/1610836/branchless-code-t... or google "Branchless coding".
twoodfin 15y ago
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?
hanbam 15y ago
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 https://gist.github.com/b97a6395c9a20c3d4cea

tikhonj 15y ago

Couldn't you replicate most of C++'s optimizations by hand in C? Because that's what I always took to be the real reason C is fast--not because pretty code is fast, but because you can make the code as ugly as you want (hello instrinsics!) to optimize it. 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.

baq 15y ago
of course you can. the whole point is that you don't have to.
veyron 15y ago
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.
- moonchrome 15y ago
  >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.

deleted 15y ago

[deleted]

chj 15y ago

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.

radiospiel 15y ago
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 15y ago

[deleted]

KonradKlause 15y ago

Reading your blog's "About me" section makes me sad. "I am working as a freelance software architect, IT consultant, ..."

radiospiel 15y ago
And what exactly makes you sad in this?
- KonradKlause 15y ago
  An IT consultant/software architect who thinks he can compare C and C++ by calling a random sort function makes me sad...
  - radiospiel 15y ago
    People that cannot even parse headlines make me more sad: I compare sorting in C++ and C.
    - KonradKlause 15y ago
      OMG, you really don't get it, right?
      - dkersten 15y ago
        I don't get it either - whats the problem?
        cygx 15y ago
        The headline implies that C++ as a language is superior to C as far as performance is concerned, whereas all that was shown is that the STL is superior to the libc from a batteries-included point of view.

cygx 15y ago

To level the playing field, I took the glibc quicksort implementation from http://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/qsort.c;hb=HEAD 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.