yohhoyの日記

技術的メモをしていきたい日記

std::random_shuffle関数はスレッド安全?

C++標準ライブラリが提供するstd::random_shuffle関数テンプレートのスレッド安全性についてメモ。

2014-12-04追記:std::random_shuffle関数テンプレートはC++1z(C++17)にて削除(remove)される。http://isocpp.org/blog/2014/11/updates-to-my-trip-report参照。

2014-02-18追記:std::random_shuffle関数テンプレートはC++14にて非推奨(deprecated)となる。(PDF)N3924 Discouraging rand() in C++14, v2 参照。

2013-03-31追記:C++1y(C++14)に向けた(PDF)N3547 Three <random>-related Proposalsでは、rand関数とrandom_shuffle関数テンプレートを非推奨(deprecated)とし、URNG+shuffle関数テンプレートのみに一本化する提案が出されている。

2引数でイテレータペアのみを指定するrandom_shuffleオーバーロードの場合、下記コードがデータ競合(data race)を引き起こすか否かは、C++11においても処理系定義(implementation defined)となる。(C++03以前は処理系定義が自明)

コードの可搬性およびスレッド安全性の観点からは、乱数生成器を明示指定する “3引数版のstd::random_shuffle” またはstd::shuffle*1を用いるのが好ましい。

#include <algorithm>

// スレッドA上で実行される
void threadA()
{
  int a[100] = {/*...*/};
  std::random_shuffle(a, a + 100);  // 配列aをシャッフル
}

// スレッドB上で実行される
void threadB()
{
  int b[100] = {/*...*/};
  std::random_shuffle(b, b + 100);  // 配列bをシャッフル
}

この動作仕様は呼出元コードの見かけに反してC++11標準ライブラリの基本的なスレッド安全性レベル(→id:yohhoy:20120513)よりも弱くなり得ることに注意。

  • 異なるスレッド上で実行される呼出元コードthreadA, threadBでは、それぞれ異なるメモリ領域a[], b[]に対する変更操作を意図しており、ユーザコード上は相互に影響を与える(=データ競合を引き起こす)ようには見えない。
  • 処理系によっては “2引数版random_shuffle内部実装がrand関数を呼び出し”、かつ “rand関数がデータ競合を引き起しうる” ため、前述のコードはデータ競合を引き起こす可能性がある。*2

N3337 25.3.12/p4*3, 26.8/p5より引用(下線部は強調)。

template<class I>
 void random_shuffle(I first, I last);
template<class I, class RNG>
 void random_shuffle(I first, I last, RNG&& rand);
template<class I, class URNG>
 void shuffle(I first, I last, URNG&& g);
4 Remarks: To the extent that the implementation of these functions makes use of random numbers, the implementation shall use the following sources of randomness:
The underlying source of random numbers for the first form of the function is implementation-defined. An implementation may use the rand function from the standard C library.
In the second form of the function, the function object rand shall serve as the implementation's source of randomness.
In the third shuffle form of the function, the object g shall serve as the implementation's source of randomness.

5 The rand function has the semantics specified in the C standard, except that the implementation may specify that particular library functions may call rand. It is implementation-defined whether the rand function may introduce data races (17.6.5.9). [Note: The random number generation (26.5) facilities in this standard are often preferable to rand. -- end note]

関連URL

*1:std::shuffle 関数テンプレートはC++11にて追加されたシャッフル操作。

*2:C++標準規格の文言からの演繹的な結論のため、現実のコンパイラ/ライブラリで何が起こるのかについては言及しない/できない。

*3:読みやすさのため関数テンプレートのテンプレート仮引数名は短縮表記。