Hacker News Reader

Comment by udp | Hacker News Reader

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++.

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.

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

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.

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.

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.

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

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.

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.

Reply on news.ycombinator.com