5 ms·

> I have never seen qsort beat sort Well, here you go: https://gist.github.com/ridiculousfish/bb511993deba1d148317 https://gist.github.com/ridiculousfish/bb511

> I have never seen qsort beat sort Well, here you go: https://gist.github.com/ridiculousfish/bb511993deba1d148317 https://gist.github.com/ridiculousfish/bb511993deba1d148317 qsort: 674 ms std::sort: 1104 ms qsort only requires one invocation of the comparator to determine the order, while std::sort often requires two. So qsort ought to be faster when comparisons are expensive.

agwa 12y ago
Under what compiler? On GCC 4.9 they're neck-and-neck:: qsort: 6727 ms std::sort: 6718 ms (CPU is Core i7-950)
- ridiculous_fish 12y ago
  qsort wins by 2x with clang++ on OS X, 10x with g++-4.9 on OS X, and by about 14% with gcc 4.8 on Linux. This may be a pathological case for either implementation, since the array is already sorted. Still the point about std::sort requiring up to twice as many comparisons is valid.
  - btmorex 12y ago
    fwiw, on linux with g++-4.8.2: qsort: 4415 ms std::sort: 4413 ms Some comments: 1.) std::sort doesn't require twice as many comparisons 2.) You not only have a vector with equal items, you have a vector of the same item repeated. That removes all data cache issues which I think is generally unrealistic and unfair. 3.) An already sorted vector is not only pathological, it's something that you usually need to optimize for (probably both qsort and std::sort are bad choices)
  - GFK_of_xmaspast 12y ago
    " the array is already sorted" Oh come on.
gmfawcett 12y ago
Running your code, I get: qsort: 6112 ms std::sort: 4925 ms Compiled on x86_64 with gcc 4.7.2 at -O3. I'm sure there are many possible reasons for the difference in performance.
alexkcd 12y ago
Neat! That said, std::sort is a template function, so you can pull the source (e.g., take the one from libc++) and change the comparator to return an int. You will still get all the benefits of inlining and optimizations from lack of type erasure, while performing only one comparison :) Edit: Actually quicksort only needs a stable boolean comparator (e.g., < or >) to determine order. So the number of invocations to the comparator is the same for both qsort and std::sort. Source: http://en.wikipedia.org/wiki/Quicksort http://en.wikipedia.org/wiki/Quicksort
yongjik 12y ago
I'm not sure why std::sort should require two comparisons. It's not required to be stable (neither is qsort), so when comparing a and b gives (a >= b), std::sort can just assume (a > b) and the array will be sorted just fine.
- ridiculous_fish 12y ago
  Oops, you are correct and I was mistaken. std::sort does not need to determine the total order in order to sort. I would amend my top-level comment but I don't seem able to.
AlexeyBrin 12y ago
Let's try again, with a more C++14 like solution: sort(v.begin(),v.end(),[](const auto x, const auto y) { return *x > *y; }); instead of your line 39: sort(v.begin(),v.end(),[](const string *x, const string *y) { return *x > *y; }); Some results: • g++ 4.9.2 with O3 qsort 545ms, sort 7289ms • clang with O3 and libc++ qsort 551ms, sort 844ms I've used: clang++ -std=c++1y -stdlib=libc++ -O3 test.cpp and g++-4.9.2 -std=c++14 -O3 test.cpp
- pubby 12y ago
  The first is comparing pointers, not strings. I wouldn't call this a fair comparison.
  - AlexeyBrin 12y ago
    +1 I stand corrected. I've updated my tests and qsort seems to be faster than sort, for this particular test case.
frankzinger 12y ago
With unmodified code and the exact same compilation command, I get: qsort: 5818 ms std::sort: 4948 ms Ubuntu 12.04 x86-64; g++ and clang++ give the same results. EDIT: with clang and libc++, same compilation line otherwise: qsort: 5822 ms std::sort: 571 ms
pubby 12y ago
When I run a modified version: http://pastebin.com/raw.php?i=XJup4FsU http://pastebin.com/raw.php?i=XJup4FsU qsort: 10466 ms std::sort: 5137 ms
deleted 12y ago
[deleted]
detrino 12y ago
C++14 version that sorts random strings: https://gist.github.com/det/57c7f0e377e02ccc696f https://gist.github.com/det/57c7f0e377e02ccc696f
stinos 12y ago
Ran it about 10 times and using msvc the sort version is around 2.5 times faster. Maybe you just got lucky once? Or something went wrong with timing?

agwa 12y ago

Under what compiler? On GCC 4.9 they're neck-and-neck:: qsort: 6727 ms std::sort: 6718 ms (CPU is Core i7-950)

ridiculous_fish 12y ago
qsort wins by 2x with clang++ on OS X, 10x with g++-4.9 on OS X, and by about 14% with gcc 4.8 on Linux. This may be a pathological case for either implementation, since the array is already sorted. Still the point about std::sort requiring up to twice as many comparisons is valid.
- btmorex 12y ago
  fwiw, on linux with g++-4.8.2: qsort: 4415 ms std::sort: 4413 ms Some comments: 1.) std::sort doesn't require twice as many comparisons 2.) You not only have a vector with equal items, you have a vector of the same item repeated. That removes all data cache issues which I think is generally unrealistic and unfair. 3.) An already sorted vector is not only pathological, it's something that you usually need to optimize for (probably both qsort and std::sort are bad choices)
- GFK_of_xmaspast 12y ago
  " the array is already sorted" Oh come on.

gmfawcett 12y ago

Running your code, I get: qsort: 6112 ms std::sort: 4925 ms Compiled on x86_64 with gcc 4.7.2 at -O3. I'm sure there are many possible reasons for the difference in performance.

alexkcd 12y ago

Neat! That said, std::sort is a template function, so you can pull the source (e.g., take the one from libc++) and change the comparator to return an int. You will still get all the benefits of inlining and optimizations from lack of type erasure, while performing only one comparison :) Edit: Actually quicksort only needs a stable boolean comparator (e.g., < or >) to determine order. So the number of invocations to the comparator is the same for both qsort and std::sort. Source: http://en.wikipedia.org/wiki/Quicksort http://en.wikipedia.org/wiki/Quicksort

yongjik 12y ago

I'm not sure why std::sort should require two comparisons. It's not required to be stable (neither is qsort), so when comparing a and b gives (a >= b), std::sort can just assume (a > b) and the array will be sorted just fine.

ridiculous_fish 12y ago
Oops, you are correct and I was mistaken. std::sort does not need to determine the total order in order to sort. I would amend my top-level comment but I don't seem able to.

AlexeyBrin 12y ago

Let's try again, with a more C++14 like solution: sort(v.begin(),v.end(),[](const auto x, const auto y) { return *x > *y; }); instead of your line 39: sort(v.begin(),v.end(),[](const string *x, const string *y) { return *x > *y; }); Some results: • g++ 4.9.2 with O3 qsort 545ms, sort 7289ms • clang with O3 and libc++ qsort 551ms, sort 844ms I've used: clang++ -std=c++1y -stdlib=libc++ -O3 test.cpp and g++-4.9.2 -std=c++14 -O3 test.cpp

pubby 12y ago
The first is comparing pointers, not strings. I wouldn't call this a fair comparison.
- AlexeyBrin 12y ago
  +1 I stand corrected. I've updated my tests and qsort seems to be faster than sort, for this particular test case.

frankzinger 12y ago

With unmodified code and the exact same compilation command, I get: qsort: 5818 ms std::sort: 4948 ms Ubuntu 12.04 x86-64; g++ and clang++ give the same results. EDIT: with clang and libc++, same compilation line otherwise: qsort: 5822 ms std::sort: 571 ms

pubby 12y ago

When I run a modified version: http://pastebin.com/raw.php?i=XJup4FsU http://pastebin.com/raw.php?i=XJup4FsU qsort: 10466 ms std::sort: 5137 ms

deleted 12y ago

[deleted]

detrino 12y ago

C++14 version that sorts random strings: https://gist.github.com/det/57c7f0e377e02ccc696f https://gist.github.com/det/57c7f0e377e02ccc696f

stinos 12y ago

Ran it about 10 times and using msvc the sort version is around 2.5 times faster. Maybe you just got lucky once? Or something went wrong with timing?