News for hackers. Stuff that matters.
Re:Sorting in C++: 3 times faster than C by udp on Saturday March 17, 2012 @08:40AM (#3716935)
Or rather, "Sorting with std::sort: 3 times faster than qsort".
Re:Sorting in C++: 3 times faster than C by osolo on Saturday March 17, 2012 @09:26AM (#3717013)
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++.
Re:Sorting in C++: 3 times faster than C by albertzeyer on Saturday March 17, 2012 @09:54AM (#3717066)
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

Re:Sorting in C++: 3 times faster than C by cygx on Saturday March 17, 2012 @09:54AM (#3717067)
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.

Re:Sorting in C++: 3 times faster than C by archangel_one on Saturday March 17, 2012 @09:50AM (#3717054)
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.
Re:Sorting in C++: 3 times faster than C by steve-howard on Saturday March 17, 2012 @10:12AM (#3717103)
I believe said requirements were written to allow qsort.
Re:Sorting in C++: 3 times faster than C by thedigitalengel on Saturday March 17, 2012 @08:44AM (#3716943)
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.
Re:Sorting in C++: 3 times faster than C by cygx on Saturday March 17, 2012 @08:51AM (#3716955)
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.

Re:Sorting in C++: 3 times faster than C by simcop2387 on Saturday March 17, 2012 @10:17AM (#3717116)
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

Re:Sorting in C++: 3 times faster than C by cygx on Saturday March 17, 2012 @10:27AM (#3717138)
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.

Re:Sorting in C++: 3 times faster than C by simcop2387 on Saturday March 17, 2012 @03:57PM (#3718015)
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.
Re:Sorting in C++: 3 times faster than C by rmcclellan on Saturday March 17, 2012 @09:25AM (#3717010)
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.
Re:Sorting in C++: 3 times faster than C by cygx on Saturday March 17, 2012 @09:51AM (#3717058)
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.