ホイール欲しい ハンドル欲しい

スレッド間の同期を取る方法は複数あります。
OS のカーネルオブジェクト、ライブラリ関数、OS 依存の API など。
他にも CAS のような最低限の atomic 操作を使って Spinlock を作ることができます。
もちろんハードウエアスレッド環境に限ります。

C++11 対応に伴いコンパイラも新しい atomic 命令に移行しています。
例えば gcc の builtin 命令は __sync_ から __atomic_ となり、
clang にも同様に __c11_atomic_ があります。

Windows の場合は OS に Interlocked～ API がありますが、
VC++ が生成する同名の Intrinsic バージョンもあります。
こちらも C++11 に従いメモリバリアを指定できる命令が追加されているようです。

// CAS
gcc      __atomic_compare_exchange_*()
clang    __c11_atomic_compare_exchange_*()
Windows  _InterlockedCompareExchange_*()

・gcc 4.7.2 : Built-in functions for memory model aware atomic operations
・Clang 3.3 : Clang Language Extensions
・msdn : x86 Intrinsics List


↓各種 API による比較です。

(1) Windows             Win8 x86   Win8 x64
-------------------------------------------------------
SpinLock(intrinsic)         5852       6353
CriticalSection            20894      22610
Win32 Mutex              2537901    3790403


(2) Linux              Linux x86   Linux x64   Linux ARM
-------------------------------------------------------
SpinLock(gcc atomic)      12712       10641       27977
pthread mutex             13693       11796       23807


(3) MacOS X         MacOS X x86  MacOS X x64
-------------------------------------------------------
SpinLock(OSAtomic)         9505        9070
pthread mutex            563013      467785

// 実行時間 単位=us

3つのスレッドで同じカウンタをそれぞれ 50000回カウントしています。
100% 競合する状態で、ロック手段による違いを測定しています。

走らせた PC のスペックが異なることと、数値の変動が大きいため
単純な比較ができないのでご注意ください。
同じ OS 内で API による違いだけ見てください。


(1) Windows (Windows 8 + VS2012 Express)

カーネルオブジェクトである Mutex は非常に遅くなっています。
CriticalSection の方が2桁高速ですが、_Interlocked 命令を使った
SpinLock の方が更に速い結果となっています。


(2) Linux (Ubuntu 12.10 / 13.04)

x86/x64 は VMware Player によるテストなのでご了承ください。
特筆すべき点は pthread_mutex が SpinLock と全く変わらないか、
むしろ速いということです。

SpinLock を作る場合に atomic API の使い方を間違えると、
pthread_mutex よりも遅くなったり、ロックに失敗したりするようです。

X86/x64 の場合 gcc (4.7.2) builtin の __atomic_ でメモリアクセス方法に
__ATOMIC_SEQ_CST を指定すると pthread_mutex よりも低速でした。
__ATOMIC_RELAXED で pthread と同等になります。
また Legacy API ですが __sync_ を使った場合も pthread と同等の
速度となりました。

ARM (Cortex-A9) では RELAXED の場合メモリアクセスが競合し
正しくブロックされません。
上記テストは ARM の場合のみ SEQ_CST を指定しています。
また __sync_ も RELAXED 相当なためかロックされませんでした。


(3) MacOS X (10.8)

OSAtomic と phtread_mutex で大きな隔たりがあります。
同じ pthread の mutex でも、Linux と違い Windows のように
カーネルオブジェクトとして実装されている可能性があります。


API が同一でも OS と CPU によって挙動が違うことがわかりました。
Linux では pthread_mutex が最もよい選択ですが、
MacOS X では逆に pthread_mutex を避けた方が良いようです。


テストプログラムは下記のとおり。

template<typename LockT>
class LockTest {
    LockT  lock;
    static int Counter;
    enum {
        MAX_LOOP= 50000
    };
public:
    void thread_func()
    {
        for( int i= 0 ; i< MAX_LOOP ; i++ ){
            lock.Lock();
            Counter++;
            lock.Unlock();
        }
    }
    void Run()
    {
        ClockTimer time;

        Counter= 0;
        Thread t0, t1, t2;

        t0.Run( this, &LockTest<LockT>::thread_func );
        t1.Run( this, &LockTest<LockT>::thread_func );
        t2.Run( this, &LockTest<LockT>::thread_func );

        t0.Join();
        t1.Join();
        t2.Join();

        time.Output();
        assert( Counter == MAX_LOOP * 3 );
    }
};

関連?エントリ
・C++11 Rvalue Reference 右辺値参照

C++11 の新機能を使うとオブジェクトの無駄なコピーを減らすことができます。

記述が簡単になるなど、C++11 にはいろいろ便利に使える追加機能があります。
Rvalue Reference の場合はむしろコードが増えるのですが、
うまく使うことでプログラムの動作を効率化することができます。
とりあえず適当に文字列型を作ってみます。

class MyString {
    char*   Name;
private:
    void Clear()
    {
        delete[] Name;
        Name= NULL;
    }
    void Copy( const char* str )
    {
        Clear();
        size_t  length= strlen(str)+1;
        Name= new char[length];
        memcpy( Name, str, sizeof(char)*length );
    }
    void DeepCopy( const MyString& src )
    {
        Copy( src.Name );
    }
public:
    MyString() : Name( NULL ) {}
    MyString( const MyString& src ) : Name( NULL )
    {
        DeepCopy( src );
    }
    MyString( const char* str ) : Name( NULL )
    {
        Copy( str );
    }
    ~MyString()
    {
        Clear();
    }
    MyString& operator=( const MyString& src )
    {
        DeepCopy( src );
        return  *this;
    }
};

copy 時に文字列バッファの複製が発生します。
例えばこんな感じ。

MyString  str1;
MyString  str2;
str1= "abcdefg";              // -- (1)
str2= MyString( "ABCDEF" );   // -- (2)
str1= str2;                   // -- (3)

C++11 の Rvalue Reference を使うと特定のケースで copy を move に変換出来ます。
対応コードを追加したのが下記の形。

#include    <string.h>
#include    <utility>

#ifndef IS_CPP11
# define    IS_CPP11    (__cplusplus > 199711L)
#endif

int  AllocCount;
int  FreeCount;

class MyString {
    char*   Name;
private:
    void Clear()
    {
        if( Name ){
            FreeCount++;
        }
        delete[] Name;
        Name= NULL;
    }
    void Copy( const char* str )
    {
        Clear();
        size_t  length= strlen(str)+1;
        Name= new char[length];
        memcpy( Name, str, sizeof(char)*length );
        AllocCount++;
    }
    void DeepCopy( const MyString& src )
    {
        Copy( src.Name );
    }
public:
    MyString() : Name( NULL ) {}
    MyString( const MyString& src ) : Name( NULL )
    {
        DeepCopy( src );
    }
    MyString( const char* str ) : Name( NULL )
    {
        Copy( str );
    }
    ~MyString()
    {
        Clear();
    }
    MyString& operator=( const MyString& src )
    {
        DeepCopy( src );
        return  *this;
    }
    //-- ↓ここから追加分
#if IS_CPP11
    MyString( MyString&& src )
    {
        Name= src.Name;
        src.Name= NULL;
    }
    MyString& operator=( MyString&& src )
    {
        char*   tmp= Name;
        Name= src.Name;
        src.Name= tmp;
        return  *this;
    }
#endif
};

これで転送元を捨てても構わない場合に copy ではなく破壊転送 (move) が行われます。
上の場合はメモリを確保し直す必要がないので効率が上がります。

転送元を捨てても構わないケースの代表が、
一時確保されたオブジェクトである rvalue 右辺値です。
また明示的に std::move() をつければ任意の値を破壊転送することができます。

これで C++11 の場合は (1),(2) において copy が消えます。
どちらも一時的な object が作られているからです。

さらに適当なベクターを作ってみます。

template<typename T>
class MyVector {
    T*      Buffer;
    T*      Ptr;
    size_t  BufferSize;
private:
    void Clear()
    {
        delete[] Buffer;
        Buffer= Ptr= NULL;
    }
public:
    MyVector() : Buffer( NULL ), Ptr( NULL ), BufferSize( 0 ) {};
    MyVector( size_t size ) : BufferSize( size )
    {
        Ptr= Buffer= new T[size];
    }
    ~MyVector()
    {
        Clear();
    }
    size_t Size() const
    {
        return  Ptr - Buffer;
    }
    T& operator[]( size_t index )
    {
        return  Buffer[index];
    }
    const T& operator[]( size_t index ) const
    {
        return  Buffer[index];
    }
    void PushBack( const T& src )
    {
        assert( Ptr < Buffer + BufferSize );
        *Ptr++= src;
    }
#if IS_CPP11
    void PushBack( T&& src )
    {
        assert( Ptr < Buffer + BufferSize );
        *Ptr++= std::forward<T>(src);
    }
#endif
};

ループさせてどの程度高速化されるか測ってみます。

// main.cpp
int main()
{
    AllocCount= 0;
    FreeCount= 0;
    {
        const int   LOOP_MAX= 100000;
        MyVector<MyString>  string_list( LOOP_MAX );

        for( int i= 0 ; i< LOOP_MAX ; i++ ){
            string_list.PushBack( "12345" );
        }
    }
    printf( "alloc=%d  free=%d\n", AllocCount, FreeCount );
    return  0;
}

差が出るように作ったので C++11 でコンパイルした方が速いのは当然なのですが、
実際にメモリ確保の回数が半減していることがわかります。

Prog  time         output
c03   0m0.015s     alloc=200000  free=200000
c11   0m0.009s     alloc=100000  free=100000

# Makefile
mac:
	clang++ -std=c++11 -stdlib=libc++  -O4 main.cpp  -o c11
	clang++ -std=c++03 -stdlib=libc++  -O4 main.cpp  -o c03

linux:
	g++ -std=c++11   -O4 main.cpp  -o g11
	g++ -std=c++03   -O4 main.cpp  -o g03
	clang++ -std=c++11 -O3 main.cpp  -o c11
	clang++ -std=c++03 -O3 main.cpp  -o c03

win:
	cl /O2 main.cpp /Fev11.exe -DIS_CPP11=1
	cl /O2 main.cpp /Fev03.exe -DIS_CPP11=0

特定のケースで明らかな無駄を省いているだけなので、通常はここまで差がでません。
例えば (3) の場合何もせずに copy を減らすことはできません。

move の場合は結局 move 用に別の API を設けていることになります。
またオブジェクトだけでなく、copy が発生する API を経由する場合も
copy の他に move 用の別のルートを追加する必要があります。
途中で move() や forward() を付け忘れると、オブジェクトまで到達しないで
途切れてしまいます。

上の MyVector 自体も複製できるようにしてみます。

template<typename T>
class MyVector {
    T*      Buffer;
    T*      Ptr;
    size_t  BufferSize;
private:
    void Clear()
    {
        delete[] Buffer;
        Buffer= Ptr= NULL;
    }
#if IS_CPP11
    void Move( MyVector&& src )
    {
        Clear();
        BufferSize= src.BufferSize;
        Ptr= Buffer= new T[BufferSize];
        for( int i= 0 ; i< BufferSize ; i++ ){
            *Ptr++= std::move(src[i]);  //-- (4)
        }
    }
#endif
    void DeepCopy( const MyVector& src )
    {
        Clear();
        BufferSize= src.BufferSize;
        Ptr= Buffer= new T[BufferSize];
        for( int i= 0 ; i< BufferSize ; i++ ){
            *Ptr++= src[i];
        }
    }
public:
    MyVector() : Buffer( NULL ), Ptr( NULL ), BufferSize( 0 ) {};
    MyVector( size_t size ) : BufferSize( size )
    {
        Ptr= Buffer= new T[size];
    }
    ~MyVector()
    {
        Clear();
    }
    size_t Size() const
    {
        return  Ptr - Buffer;
    }
    void PushBack( const T& src )
    {
        assert( Ptr < Buffer + BufferSize );
        *Ptr++= src;
    }
#if IS_CPP11
    void PushBack( T&& src )
    {
        assert( Ptr < Buffer + BufferSize );
        *Ptr++= std::forward<T>(src);
    }
#endif
    T& operator[]( size_t index )
    {
        return  Buffer[index];
    }
    const T& operator[]( size_t index ) const
    {
        return  Buffer[index];
    }


    MyVector& operator=( const MyVector& src )
    {
        DeepCopy( src );
        return  *this;
    }
#if IS_CPP11
    MyVector& operator=( MyVector&& src )
    {
        Move( std::move(src) );
        return  *this;
    }
#endif
};

下記のように MyVector を代入できるようになりました。
この (5) のケースでは完全な move となり string のメモリ確保が発生しません。

int main()
{
    AllocCount= 0;
    FreeCount= 0;
    {
        const int   LOOP_MAX= 100000;
        MyVector<MyString>  string_list( LOOP_MAX );

        for( int i= 0 ; i< LOOP_MAX ; i++ ){
            string_list.PushBack( "12345" );
        }

        MyVector<MyString>  string_list2( LOOP_MAX );
        string_list2= std::move(string_list);    // -- (5)
    }
    printf( "alloc=%d  free=%d\n", AllocCount, FreeCount );
    return  0;
}

ですが std::move() を付け忘れると move でなく MyString の copy になります。
下記のように alloc/free が増えます。(5) でも同じです。

c03    alloc=300000  free=300000
c11    alloc=200000  free=200000   ( (5) or (6) の move 無し )
c11    alloc=100000  free=100000