C
C++
sort

C++ の方が C よりも速い例

だいたい、同じ趣旨のコードを書いたら C++ の方が速いと私は思っている。

例えば。std::sortqsort よりも速いことが多い。

たくさんの整数を 1の位の値で整列するというコードを例に。

C言語のソースコード

まずは C99 で。

C99
// clang -std=c99 -O2 qsort.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double get_tick()
{
  struct timespec t;
  clock_gettime(CLOCK_REALTIME, &t);
  return t.tv_sec + t.tv_nsec*1e-9;
}

typedef int target_type;

void prepare( target_type * data, size_t len )
{
  for( size_t i=0 ; i<len ; ++i ){
    data[i] = (target_type)i;
  }
}

int compare( void const * a, void const * b )
{
  return (*(target_type*)a)%10 - (*(target_type*)b)%10;
}

int main(void)
{
  const size_t N = 1024 * 1024 * M;
  target_type * data = malloc(N * sizeof(target_type));
  prepare( data, N );
  double tick = - get_tick();
  qsort( data, N, sizeof(target_type), compare );
  tick += get_tick();
  printf( "%.6f\n", tick );
  free( data );
  return 1;
}

C++ のソースコード

続いて同じ趣旨の計算を C++11 で。

C++11
// clang++ -std=c++11 -O2 stdsort.cpp
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <memory>

double get_tick()
{
  timespec t;
  clock_gettime(CLOCK_REALTIME, &t);
  return t.tv_sec + t.tv_nsec*1e-9;
}

using target_type = int;

void prepare( target_type * data, size_t len )
{
  for( size_t i=0 ; i<len ; ++i ){
    data[i] = static_cast<target_type>(i);
  }
}

int main()
{
  const size_t N = 1024 * 1024 * M;
  std::unique_ptr<target_type[]> data( new target_type[N] );
  prepare( data.get(), N );
  double tick = - get_tick();
  std::sort( data.get(), data.get()+N, 
             [](target_type a, target_type b)->bool{ return a%10<b%10; } );
  tick += get_tick();
  std::printf( "%.6f\n", tick );
  return 1;
}

これを、M の値を変えながら手元のマシンで実行すると、下表のようになった:

M C言語(qsort) C++(std::sort)
1 0.014700 0.007676
2 0.034709 0.015732
4 0.061273 0.031011
8 0.127590 0.061935
16 0.242823 0.126991
32 0.451090 0.260800
64 1.077482 0.550410

ご覧のとおり、 std::sort の方が倍ぐらい速い。
たぶん、比較関数が inline 展開されるかどうかの違いだと思う。