関数ポインタと関数オブジェクトと仮想関数の速度比較

趣旨

アルゴリズム内の処理の一部を指定させる一般的な方法には以下がある．

• 関数ポインタを使う (qsort 等)
• 関数オブジェクトを使う (std::sort 等)
• 仮想関数を使う

これらで性能がどう変化するかを測定した．

結果概要

wandbox にて実験した：http://melpon.org/wandbox/permlink/H7VjfOqgiEh4XWCP

pointer: 5.036541 sec
template: 3.373498 sec
virtual: 4.716775 sec
inline: 3.322171 sec

• pointer とは関数ポインタで指定した場合
• template とは関数オブジェクトで指定した場合
• virtual とは仮想関数を使って指定した場合
• inline とは指定なしでベタ書きした場合，一番最適化が効くはず

結果は template が inline とほぼ同等の速度で他より有意に高速であった．予想通りですね．これは，最適化の対象となるコードがベタ書きにかなり近くなり，インライン化等を含む最適化が効果的に働くから．

ソースコード

#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <sys/time.h>
#include <unistd.h>
#include <stdarg.h>

const int N = 500000000;

struct __bench__ {
  double start;
  char msg[100];
  __bench__(const char* format, ...)
  __attribute__((format(printf, 2, 3)))
  {
    va_list args;
    va_start(args, format);
    vsnprintf(msg, sizeof(msg), format, args);
    va_end(args);

    start = sec();        
  }
  ~__bench__() {
    fprintf(stderr, "%s: %.6f sec\n", msg, sec() - start);
  }
  double sec() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec * 1e-6;
  }
  operator bool() { return false; }
};

#define benchmark(...) if(__bench__ __b__ = __bench__(__VA_ARGS__));else

uint64_t x;

inline uint64_t xorshift() {
  x ^= x >> 12;
  x ^= x << 25;
  x ^= x >> 27;
  return x * 2685821657736338717LL;
}

uint64_t test_inline() {
  uint64_t s = 0;
  for (int i = 0; i < N; ++i) s += xorshift();
  return s;
}

uint64_t test_pointer(uint64_t (*f)()) {
  uint64_t s = 0;
  for (int i = 0; i < N; ++i) s += f();
  return s;
}

struct A {
  inline uint64_t operator()() const {
    return xorshift();
  }
};

template<typename T>
uint64_t test_template(T t) {
  uint64_t s = 0;
  for (int i = 0; i < N; ++i) s += t();
  return s;
}

struct B {
  virtual uint64_t f() = 0;
};

struct C : public B {
  virtual uint64_t f() {
    return xorshift();
  }
};

uint64_t test_virtual(B *b) {
  uint64_t s = 0;
  for (int i = 0; i < N; ++i) s += b->f();
  return s;
}

int main() {
  uint64_t seed, dummy;
  scanf("%lu%lu", &seed, &dummy);

  x = seed;
  benchmark("pointer") {
    printf("%lu\n", test_pointer(xorshift + dummy));
  }
    
  x = seed;
  benchmark("template") {
    printf("%lu\n", test_template(A()));
  }

  x = seed;
  benchmark("virtual") {
    C c;
    printf("%lu\n", test_virtual(&c));
  }

  x = seed;
  benchmark("inline") {
    printf("%lu\n", test_inline());
  }
    
  return 0;
}