2004-10-11

Singleton速度比較 (1)

C++

2chのマルチスレッドスレッドで興味深い議論があった。見ていただければわかるが、「C++でdouble checked locking(DCL)は安全か」という話題を、CPU毎に検討している。各CPUのmemory modelの話に立ち入った、楽しい議論だ。特に、リンクされている

Double-Checked Locking, Threads, Compiler Optimizations, and More
http://www.nwcpp.org/Downloads/2004/DCLP_notes.pdf

なるScott Mayersさんのペーパーがイケてると思う。最近書かれたばっかり。ここを読んでいなかったら当分知ることはなかっただろうな。ラッキー。

というわけで本題も興味深いのだが、とりあえずスレッドの中でいくつか示された「DCLに代わる高速なシングルトンの実装方法」が実際どの程度高速か興味がわいたので計測してみた。次の5種類を試した。

SynchronizedSingleton:
インスタンス取得メソッド全体をmutexで囲み、完全同期化を行ったシングルトン。

DCLSingleton:
インスタンス取得メソッドに Double Checked Locking Pattern を用いたシングルトン。

OnceSingleton:
インスタンス取得メソッド中でのインスタンスのnew処理を、pthread_onceで一度
だけ行うようにしたシングルトン。

> もしくは、pthread_once(3)のようなシステムが用意してくれてるAPIを使うとか。
> DCLが有効なアーキテクチャではpthread_once()の内部でDCLを使ってるかもしれ
> んが、使う側からはそういう内部実装を一切気にしなくて良い。

GccTSDSingleton:
インスタンス取得メソッドはSynchronizedSingletonと同一だが、それをTSDでキャッ
シュするように細工したシングルトン。

TSDは、__thread というGCC拡張のキーワードを用いて確保する。

> 正確に言うと、某CPUが数発のマシンでDCLを(バリアなしで）使ってる人に、バリア
> 使うか858のように書き直せと言いたいんです。そのための調査をしていまして。
> 自分はどちらかというと858派ですと付け加えておきます。基本的にはパフォーマンス
> より安全・確実な方を選びたいですね。
> # 完全synchronizeのペナルティがイヤならTLSにでもポインタいれとけばぁ？と思う。

TSDSingleton:
インスタンス取得メソッドはSynchronizedSingletonと同一だが、それをTSDでキャッ
シュするように細工したシングルトン。

TSDは、POSIXのAPIを用いて確保する。

なお、DCLの実装はx86向けのもの*1である。各CPU向けにどのようなメモリバリアを記述すればよいのかは、glibc(LinuxThreads)のpthread_onceの実装*2を参考にした。より正確には、各アーキテクチャ向けに linuxthreads/sysdeps/アーキテクチャ/pt-machine.h や linuxthread/internals.h で定義される、MEMORY_BARRIER(), READ_MEMORY_BARRIER(), WRITE_MEMORY_BARRIER() マクロを参考にした。参考までに、このマクロのx86の場合の#define内容は次の通りである。

[internals.h]

/* If MEMORY_BARRIER isn't defined in pt-machine.h, assume the
   architecture doesn't need a memory barrier instruction (e.g. Intel
   x86).  Still we need the compiler to respect the barrier and emit
   all outstanding operations which modify memory.  Some architectures
   distinguish between full, read and write barriers.  */

#ifndef MEMORY_BARRIER
#define MEMORY_BARRIER() asm ("" : : : "memory")
#endif
#ifndef READ_MEMORY_BARRIER
#define READ_MEMORY_BARRIER() MEMORY_BARRIER()
#endif
#ifndef WRITE_MEMORY_BARRIER
#define WRITE_MEMORY_BARRIER() MEMORY_BARRIER()
#endif

また、TSDSingletoがOnceSingletonよりも低速になるのは下のほうに貼ったソースコードを見れば自明だが、一応実験しておいた。

測定環境は、Linux 2.6.8(FC3test2), glibc-2.3.3(NPTL), g++-3.4.2, boost-1.13.0, Pentium4-2.8GHz(HT) である。

→　続き

*1:コンパイラによるreorderだけを防止している

*2:glibc-2.3.3-200405070341/linuxthreads/mutex.c

2004-10-11

Singleton速度比較 (2) 結果

C++

結果は次の通り。

$ ./a.out
DCLSingleton: 0.27 [s]
GccTSDSingleton: 0.62 [s]
OnceSingleton: 17.08 [s]
TSDSingleton: 22.83 [s]
SynchronizedSingleton: 52.95 [s]

手法	処理時間(1/Sync比)	処理時間(DCL比)
DCLSingleton	196.1	1.0
GccTSDSingleton	85.4	2.3
OnceSingleton	3.0	65.9
TSDSingleton	2.3	84.6
SynchronizedSingleton	1.0	196.1

...というわけで、結果を要約すると次の通りになるだろう(左にいくほど高速)：

DCLSingleton > GccTSDSingleton >> OnceSingleton > TSDSingleton >> SynchronizedSingleton

H/Wに特に詳しくない場合、DCLPを使うのには勇気が要るわけだが、そういう向きは__threadやpthread_onceを使ったシングルトンを作成すれば、充分な速度(完全同期化バージョンに比べてそれぞれ85倍、3倍)のパフォーマンスが得られることがわかる。少なくとも私と似たような環境の方は :-)

なお、ポータビリティは次の通り(左がポータブル)：

(SynchronizedSingleton == OnceSingleton == TSDSingleton) > GccTSDSingleton > DCLSingleton

→続き

2004-10-11

Singleton速度比較 (3) ソースコード

C++

(1) SynchronizedSingleton: 完全同期型Singleton

特に説明は不要でしょう。non-PODでstaticなオブジェクトを使用するのは好きじゃありませんが(メンバ変数m)、今回は目を瞑ります。

template<typename T>
class SynchronizedSingleton : private boost::noncopyable
{
public:
  static T& getInstance(void) {
    boost::mutex::scoped_lock lk(m);
    if (!instance) {
      instance = new T;
    }
    return *instance;
  }
private:
  static T* instance;
  static boost::mutex m;
};

template<typename T>
T* SynchronizedSingleton<T>::instance = 0;

template<typename T>
boost::mutex SynchronizedSingleton<T>::m;

(2) DCLSingleton

先に述べた方法で、x86用のメモリバリアを挿入し、安全なdouble checked lockingを実現したバージョンです。結果として、メモリバリアとして余計なインストラクションは挿入されず、g++の最適化を抑制するだけ("memory")になっているので速そうですね。

template<typename T>
class DCLSingleton : private boost::noncopyable
{
public:
  static T& getInstance(void) {
    T* tmp = instance;
    __asm__ __volatile__ ( "" ::: "memory" ); // read memory barrier for x86
    if (!instance) {
      boost::mutex::scoped_lock lk(m);
      if (!instance) {
        tmp = new T;
        __asm__ __volatile__ ( "" ::: "memory" ); // write memory barrier for x86
        instance = tmp;
      }
    }
    return *instance;
  }
private:
  static T* instance;
  static boost::mutex m;
};

template<typename T>
T* DCLSingleton<T>::instance = 0;

template<typename T>
boost::mutex DCLSingleton<T>::m;

(3) OnceSingleton

pthread_once()で実装したシングルトンです。それ自体はちょっと使い方がインタフェースが煩雑なので、内部でpthread_once()を使っているboost::call_once()で実装しました。少々手抜きですね。

// Once
template<typename T>
class OnceSingleton : private boost::noncopyable
{
public:
  static T& getInstance(void) {
    static boost::once_flag flg = BOOST_ONCE_INIT;
    boost::call_once(init, flg);
    return *instance;
  }
private:
  static void init(void) {
    instance = new T;
  }
  static T* instance;
};

template<typename T>
T* OnceSingleton<T>::instance = 0;

(4) GccTSDSingleton

最近のGCCの__thread拡張を使ったシングルトンです。

// TSD (gcc拡張)
template<typename T>
class GccTSDSingleton : private boost::noncopyable
{
public:
  static T& getInstance(void) {
    static __thread T* tsd_instance = 0;
    if (!tsd_instance) {
      tsd_instance = getInstance_();
    }
    return *tsd_instance;
  }
private:
  static T* getInstance_(void) {
    boost::mutex::scoped_lock lk(m);
    if (!instance) {
      instance = new T;
    }
    return instance;
  }
  static T* instance;
  static boost::mutex m;
};

template<typename T>
T* GccTSDSingleton<T>::instance = 0;

template<typename T>
boost::mutex GccTSDSingleton<T>::m;

(5) TSDSingleton

POSIXで標準化されている、スレッド固有データを用いたシングルトンです。
こちらもboostで手抜きしたいところですが、Boost.ThreadにはTSD/TLSのAPIは(まだ)ないので、直接pthread APIを叩いています。。

// TSD (POSIX)
template<typename T>
class TSDSingleton : private boost::noncopyable
{
public:
  static T& getInstance(void) {
    static boost::once_flag flg = BOOST_ONCE_INIT;
    boost::call_once(init, flg);

    T* tsd_instance = static_cast<T*>(pthread_getspecific(key));
    if (!tsd_instance) {
      tsd_instance = getInstance_();
      pthread_setspecific(key, tsd_instance);
    }
    return *tsd_instance;
  }
private:
  static void init(void) {
    pthread_key_create(&key, 0);
  }
  static T* getInstance_(void) {
    boost::mutex::scoped_lock lk(m);
    if (!instance) {
      instance = new T;
    }
    return instance;
  }
  static T* instance;
  static pthread_key_t key;
  static boost::mutex m;
};

template<typename T>
T* TSDSingleton<T>::instance = 0;

template<typename T>
pthread_key_t TSDSingleton<T>::key;

template<typename T>
boost::mutex TSDSingleton<T>::m;

次のコードでテストしました。

int main(void) {
  static const int TIMES = 500000000; // 5億回
  double s;
  boost::timer t;

  t.restart();
  for(int i = 0; i < TIMES; ++i) {}
  const double r = t.elapsed();

  t.restart();
  for(int i = 0; i < TIMES; ++i) {
    volatile X& x __attribute__((__unused__)) = DCLSingleton<X>::getInstance();
  }
  s = t.elapsed() - r;
  std::cout << "DCLSingleton: " << s << " [s]" << std::endl;

  (略)

→続き

2004-10-11

Singleton速度比較 (4) 感想

C++

500,000,000回まわしてこの程度の処理時間ですから、どれも高速だと思う。差なんてないようなものではなかろうか。むしろ、Singleton(=グローバル変数)なんて殆ど使わなくて済むような設計を心がけるべきで、完全同期バージョンのSingletonを使ってパフォーマンスに問題が出るようなソフトウェアは問題(を抱えている事が多い)と思う。

私はテスト駆動開発入門の Kent Beck氏のお言葉が好きです。少しだけ引用します：

Sinleton:

グローバル変数のない言語でグローバル変数をどのように提供するのか？

      そのようなことを考えてはならない。そのようなことを考える時間
      を設計に費やせば、プログラムがよりよくなる。