4 ms·

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

by udp 15y ago

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.

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

by udp 15y ago

Or rather, "Sorting with std::sort: 3 times faster than 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.

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.