Hacker News Reader

Comment by ridiculous_fish | Hacker News Reader

> I have never seen qsort beat sort

Well, here you go: 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.

View on HN

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.

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

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

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?

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.

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.

When I run a modified version: http://pastebin.com/raw.php?i=XJup4FsU

    qsort: 10466 ms
    std::sort: 5137 ms

Under what compiler? On GCC 4.9 they're neck-and-neck::

  qsort: 6727 ms
  std::sort: 6718 ms

(CPU is Core i7-950)

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.

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)

" the array is already sorted"

Oh come on.

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

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

The first is comparing pointers, not strings. I wouldn't call this a fair comparison.

+1 I stand corrected.

I've updated my tests and qsort seems to be faster than sort, for this particular test case.

Reply on news.ycombinator.com