Today's Question:  What's your opinion about Alibaba mooncake incident?        GIVE A SHOUT

Technical Article => Programming =>  C++

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

  radiospiel.org      2012-03-17 12:59:45      1,940    0    0

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;
}
view raw sortbench.cpp This Gist brought to you by GitHub.

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

C C++ EFFICIENCY FASTER SORTING

  SAVE AS PDF   MARK AS READ   MARK AS IMPORTANT

Share on Facebook  Share on Twitter  Share on Google+  Share on Weibo  Share on Reddit  Share on Digg  Share on Tumblr    Delicious

  RELATED


  0 COMMENT


No comment for this article.


  WRITE ARTICLE

What is VBA?

By sonic0002
This is a conversation on Google product forum. Google engineers really don't know what is VBA? Or they just refuse to acknowledge the existence of VBA? The full conversation can be found at https://productforums.google.com/forum/m/#!topic/chrome/zY-8vP1lIys