sorting in C++: 3 times faster than C.

If you don't know C++ well, you might be surprised how fast C++ can be sometimes. This is especially true when code involved is small, because then inlining - which is what C++ is very good at - and templating, which makes excessive inlining possible in the first place - has the most effect.

The following code compares C and C++ sorting: 

#include <iostream>
#include <algorithm>
#include <vector>
#include "stop_watch.inl" // see https://gist.github.com/2057981

#ifndef COUNT
#define COUNT 100000000
#endif

int compare_int(const void* p1, const void* p2)
{
  int i1 = *(int*)p1;
  int i2 = *(int*)p2;
  return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
}

int main()
{
  srand(12345);
  
  int* data1 = new int[COUNT];
  int* data2 = new int[COUNT];

  for(int i=0; i<COUNT; i++) {
    data1[i] = data2[i] = ((rand() << 16) | rand());
  }
  
  {
    StopWatch stopWatch("std::sort: ");
    std::sort(data1, data1+COUNT);
  }

  {
    StopWatch stopWatch("qsort:    ");
    qsort(data2, COUNT, sizeof(int), compare_int);
  }
  
  return 0;
}

And here are some actual numbers, taken on a Macbook Air (gcc -DCOUNT=100000 -O3 -Wall sort.cpp -lstdc++):

count        c++         c    c/c++ ratio
    30000       1769      4949    2.80
   100000       6604     17665    2.67
   300000      22721     59713    2.63
  1000000      79107    231982    2.93
  3000000     266550    711608    2.67
 10000000     920159   2530939    2.75
 30000000    2909369   8259053    2.84
100000000   10016849  28173682    2.81

So, C++ is up to 3 times faster than C. How is this possible?

Well: By inlining C++ is able to run just the raw algorithm. On the opposite the C code has a number of indirections: a) the comparison  function will be called indirectly, via a pointer, and b) the values to compare are passed through to the comparison function can be accessed only via pointers. This - as measured - costs some overhead. 

Funny that the C code does explicitely, what many people wrongly assume C++ would be doing, namely calling a function via a pointer. 

My experience, when going for top level performance:

- limit branching

- optimize for the second level memory cache

- consider C++ templating

Source:http://radiospiel.org/sorting-in-c-3-times-faster-than-c