1/2/2023 0 Comments Cache xsort and qsort sort.cc![]() ![]() This is just another article reinforcing that std::sort is in fact quite superior to the old workhorse qsort. Of course Scott Meyers already discussed this in length in his book Effective STL. Then the programmers are less frustrated and more eager to tackle the runtime performance problems and maybe comes up with a better algorithm that doesn't require as much sorting, thus speeding up the game in the end more than the guys who went with the std::sort method. Going with a solution that causes you to use the possibly slower qsort, but having faster compile times (maybe 1 minute faster) does add up over the course of a project. Don't underestimate the gain from having rapid turnaround times for the programmers. The term "death by a thousand cuts" comes to mind. ![]() (yepp, just declare the prototype locally, it's not as it will actually change).Ĭompile times are important, it's something that is usually not covered until it's way too late. The C version uses such amazing things as prototypes and prebuilt libraries (fancy such advanced features), which if you are careful can induce zero inclusion cost. It also includes, which usually is on par with windows.h. ![]() Ok, so why are not everybody doing this? Hm, well, there are some drawbacks to std::sort as well, which are nicely swept under the rug. But something is going on here definitely and the function call to do the compare for qsort and the fact that it can be inlined by std::sort looks like a win. Cache xsort and qsort sort.cc Pc#Now I would take these results with a grain of salt, the arrays were different, the algorithms might be different and I'm running on my non deterministic PC (and it runs Vista, thus all bets are off). Turning around and preventing std::sort from inlining the comparison shows that the times goes up and is now comparable to the regular qsort. Even though std::sort actually expands out to a lot more code, it's faster. Listing 3: Output from the sample program showing some timings.įrom the output we can see that using std::sort and giving the function a chance to inline the whole thing is faster than the regular qsort. But for the special case when you do have a large-ish array of linear (small) things that you need to sort with a simple short comparison function (ok, I've probably lost most of you here?) this could be somewhat true. At most they can show some indication on what can happen, but as Christer Ericson mentions, simple tests like these are not always so good, or just downright bad. We're going to do some fairly quick and dirty tests, not particularly good actually. The compiler has no chance to actually rearrange the calling convention, since the function signature actually defines that the callback needs to be a standard C function. The function call will in worst case cause a stack reference to store the return address. The function callback is pretty bad though, it will cause an indirection for each compare. ![]() Cache xsort and qsort sort.cc plus#On the plus side, the function does not know about the data at compile time and can be put in a library. You send in the stride and the range to the function. If we look at qsort, it takes a function callback to do the actual compare between two items since it the library function itself doesn't know anything about the data. You might think that they both perform about the same? Not really. You might even go, hey there is a library function for this, why reinvent the wheel? Turns out that there are two different functions, the old trusty qsort from the standard C library and the new std::sort from the C++ library (STL). This article is not going to go into any of that. There are numerous texts on sorting and the different algorithms, their complexities and their merits. So while I'm happily downloading The Orange Box on Steam, I'm writing this very quick and dirty post. In fact, it's even involving templates, my old archenemy (Bowser is nothing compared to them). I'm going to do something different today, instead of bashing on C++ as I usually do, I'm going to point at some good things about it. We should forget about small efficiencies, say about 97% of the time. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |