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

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

2014-12-04追記：std::random_shuffle関数テンプレートはC++1z(C++17)にて削除(remove)される。https://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]

yohhoyの日記

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

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