Boost.勉強会 #14に参加しました

2014/3/1に開催されたイベント Boost.勉強会 #14 東京 にて、“新しい並列for構文のご提案”というタイトルで30分ほど話す機会をいただきました。（1年7ヶ月ぶり2回目）

スライド資料

新しい並列for構文のご提案 from yohhoy

感想とか

今回作ったスライド資料では、現行の並列化技術10種類とC++1y ParallelTSを広く浅く紹介というテーマで、前回よりも枚数を増やし進行テンポを速くしてみました。また前回の反省点として、概念と仕様のみ紹介だと理解されにくいかなと思ったこともあり、今回は導入部をシナリオ的にし(1/3)＋“今日から使える”技術の紹介(1/3)＋将来のC++1y動向の紹介(1/3)という構成にしています。Twitterでの皆様の反応を後から眺めてみると、思ったよりC++1y ParallelTSが注目されていたようでした（並列処理はTransactional Memoryよりも身近で分かり易いという側面はあるでしょうけど）。当日は少しぼやけてしまった感がありますが、「並列処理の"仕組み"を自分で書こうとしないで！*1」「並列化技術はいろいろあるから、適材適所で選んでね！*2」という主張でした。

並列処理は目に見える効果が大きく面白く感じられる反面、正しく動作するコード記述や適切な速度性能を引き出すのは一筋縄ではいきません。また昨今のハードウェア進化の方向性を鑑みるに、ソフトウェア側での並行処理・並列処理への対応は避けられそうもありません。今回紹介した並列化技術は“処理を並列実行する枠組み”部分を提供するため、この点ではプログラマのコーディング負担を下げてくれるはずです。ぜひ並列処理プログラミングの世界に足を踏み入れてみてください。

P.S. 勉強会の終了後に行われたじゃんけん大会で幸運にも勝ち残り、書籍版プログラミングの魔導書 〜Programmers' Grimoire〜 Vol.3 "Parallel, Concurrent, and Distributed Programming"を頂いてしまいました（もうおひと方と私の2冊）。@cpp_akiraさん、ありがとうございます！

*1:安易に、スレッドを自前で作り制御するような並列処理コードを書くべきでないと考えます。特殊な事情がある場合はこの限りではありませんが、安定性／スケーラビリティ／拡張性／保守性などの観点から、適切な実装手段を選択すべきです。（よくある標準ライブラリvs自前コードの比較ですね。）

*2:今回の文脈では 並列化＝実行速度の高速化(最適化) のため、良い結果が得られなければ特定技術にこだわるのは無意味です。また、単一の並列化技術だけでは十分でないケースも多々ありますので、複数の並列化技術を組み合わせることも検討してみてください。

gistにソースコードを放っておいたらOSSプロジェクトで活用されていた件

タイトル通り。

プログラミング言語Cの最新規格C11で採用されたスレッドサポートのエミュレーションライブラリをgistに放置していたら、汎用OpenGL実装The Mesa 3D Graphics Libraryに取り込まれました（2014年2月現在のGit版として）。

2014-05-07追記：MesaLib-10.1.0からinclude/c11以下にとりこまれたようです。

対応プラットフォームが多岐にわたるMesa 3Dでは、その差異を吸収するスレッドサポート実装をもっていましたが、4つのサブモジュールでそれぞれ独立に行われていたそうです。つまり、4種類のエミュレーション用コードがばらばらに存在する状態でした。そこで、C11標準ライブラリのAPI仕様に則りかつWindows／POSIX環境に対応していたgistのコードが拾われて、プロジェクト内の重複実装を整理する目的で採用されたようです。

• 2012/03/29, https://twitter.com/yohhoy/status/185290667604443136
• 2013/03/14, [Mesa-dev] RFC: C11 threads.h
• 2014/01/23, Mesa Starting To Use C11 Threads, Boost

ライブラリ内部実装としては、Pthreadの薄っぺらいラッパとBoost.Interprocessライブラリ（C++言語）からC言語への移植です。作成動機はC11標準スレッドサポート機能の調査と、条件変数プリミティブの実装調査でした。

（コードをBoostライセンスで公開していたのもあってか、Phoronix記事ではBoostライブラリの一部と勘違いされている？）

ま、そういうOSS貢献(？)の形もあったという事で一つ。

スレッドセーフという幻想と現実

この記事はC++ Advent Calendar 2013の15日目にエントリしています。
内容はC++標準ライブラリとスレッドセーフに関する解説になります。

flickr / rennasverden
もくじ

1. What's スレッドセーフ？
   1. スレッドセーフという幻想
   2. 基本型とデータ競合
   3. C++標準ライブラリとデータ競合
   4. C++標準ライブラリ：シーケンスコンテナ編
   5. C++標準ライブラリ：連想コンテナ編
2. スレッドセーフ RELOADED
   1. 基本的なスレッドセーフ保証
   2. std::shared_ptr<T>
   3. std::rand()
   4. std::cout

（本文のみ約9000字）

はじめに

マルチスレッド対応の点では他言語に遅れを取っていたプログラミング言語C++ですが、C++11ではようやく標準ライブラリにスレッドサポートが追加されました。C++11スレッドサポートではスレッドクラスstd::threadをはじめとし、ミューテックスstd::mutexや条件変数std::condition_variableなどの基本的な同期機構、Future／Promiseパターンを実現するstd::future, std::promise、少しマニアックなところではアトミック変数std::atomicなどがC++標準ライブラリに追加されました。Happy Multithreading Programming!

という風に、C++11スレッドサポートの文脈では新規クラス追加ばかりが注目されています。このような華やかな表舞台の裏側では、以前からあるstd::stringやstd::vectorといったクラス群に対して、スレッドサポートに関連する重要なルールが明確化されたことは知っていますか？マルチスレッドプログラム中でC++標準ライブラリを利用するとき、それらのスレッドセーフ性(thread safety)*1について理解し、適切に使えているでしょうか？

本記事では、プログラミング言語C++におけるスレッドセーフの観点から、C++11スレッドサポート追加クラス以外のC++標準ライブラリをいくつか紹介したいと思います。その中でも、たまに論争ネタになっているstd::shared_ptrやstd::coutのスレッドセーフ性についても説明を加えていきたいと思います。

1. What's スレッドセーフ？

複数スレッドを扱うプログラミングについて学び始めると、必ず「スレッドセーフ(thread safe)」という概念が出てくると思います。曰く、

• △△ライブラリはスレッドセーフだから、マルチスレッドプログラム中でも安全に使える。
• クラス○○はスレッドセーフじゃないから、スレッドと一緒には使えない。

どうやら“スレッドセーフなC++ライブラリ＝マルチスレッド対応”という雰囲気のようです。スレッドセーフなんて簡単ですね！

…でも、本当にそんなに単純な話でしょうか。次の「スレッドセーフ」に関する質問に答えられますか？（Q＆Aサイトでよく見かける質問の変形です）

• Q1. std::map<K,V>クラスはスレッドセーフですか？
• Q2. std::vector<T>クラスはスレッドセーフですか？
• Q3. std::stringクラスはスレッドセーフですか？
• Q4. 基本型intはスレッドセーフですか？
• Q5. そもそもC++言語での「スレッドセーフ」は何を意味しますか？

これらに回答できるなら、プログラミング言語C++の文脈での「スレッドセーフ」という概念について、ちゃんと理解していると言っても差し支えないでしょう。本記事の前半では、逆順にてそれぞれの質問に答えていきたいと思います。

1.1. スレッドセーフという幻想

Q5. そもそもC++言語での「スレッドセーフ」は何を意味しますか？

いきなり出鼻をくじくようですが、プログラミング言語C++の言語仕様としては「スレッドセーフ」という用語は直接定義されていません。ただし、スレッドセーフを考える上で重要な用語「データ競合(data race)」は、C++言語仕様の一部として厳密に定義されます。C++11におけるデータ競合とは、次の3条件を全て満たすときに発生します。*2

• (1) 同一メモリ位置に対するアクセスにおいて、
• (2) 少なくとも一方が変更(modify)操作であり、
• (3) 異なるスレッド上から同時に行われるとき。

そして、C++言語仕様では「プログラム中で何らかのデータ競合が発生した場合には、未定義の動作(undefined behavior)を引き起こす」と明言しています。つまり、ひとつでもデータ競合を含むマルチスレッドプログラムの動作結果について、C++言語仕様としては何も保証しないことを意味します。ここでの“何も保証しない”とは、本当に何も保証されていことに注意してください。例えば、データ競合を含むプログラムは偶然正しく動くかもしれないし、運悪く期待する結果とならないかもしれないし、はたまたプログラム実行中に突然異常終了するかもしれないという意味です。*3

残念ながら原典をあたっても「スレッドセーフ」についての明確な答えは得られませんでしたが、少なくともデータ競合を含まないプログラムとなっていればよい事は分かりました。

Q5. そもそもC++言語での「スレッドセーフ」は何を意味しますか？
A5. 厳密には「スレッドセーフ」は定義されない。一方、妥当なC++プログラムはデータ競合を一切含まないことが求められる。

と、このままでは話が終わってしまいますので、厳密なC++言語仕様から少し離れてみたいと思います。ある対象の「スレッドセーフ」について言及するときは、その利用者視点から議論するのが一般的と考えられます。本記事でもそれにならい“利用側コードからどのように扱えばデータ競合が生じないか”、より具体的には“いつ排他制御すれば良いのか”という観点から、基本型やクラスの「スレッドセーフ」の議論を続けていきます。

1.2. 基本型とデータ競合

Q4. 基本型intはスレッドセーフですか？

charやintなどの基本型*4は、C++プログラムを構成する最も原始的なデータ構造です。このような基本型変数は、一定サイズのメモリ領域にマッピングされます（例：sizeof(int) == 4な環境ではint型変数は連続した4バイトメモリ位置を占める）。つまり、基本型に関するスレッドセーフの議論は、前述「データ競合」の定義から単純に読み替えが可能です。

ところで「データ競合」は3つの発生要因から構成されますが、逆に言うと、これらの要因のうち1つでも排除できれば回避できます。

• (1') 異なる変数に対する同時アクセスは、データ競合とはなりません。
• (2') 同一変数に対して同時読み込み(read)操作のみならば、データ競合とはなりません。
• (3') 同一変数に対するアクセスが同時でなければ、データ競合とはなりません。

(1')はアクセスする変数自体が別々となるため、最も直感的に理解できるかと思います。（以降のコード例では、関数th1(), th2()等は異なるスレッドからそれぞれ同時に呼び出されるとします。）

// 異なる変数に対する同時アクセス
int x, y;
void th1() {
  x = 1;  // OK
}
void th2() {
  y = 2;  // OK
}

また(3')はマルチスレッドプログラムの定番、ミューテックスstd::mutexなどを用いた排他制御により同一変数へのアクセスが同時に生じないよう制御します。これも、マルチスレッドプログラミングの基本ですね。

// 同一変数に対するアクセスが同時でない
std::mutex mtx;
int x;
void th1() {
  std::lock_guard<decltype(mtx)> lk(mtx);
  x = 1;  // OK
}
void th2() {
  std::lock_guard<decltype(mtx)> lk(mtx);
  x = 2;  // OK
}

一番馴染みが薄いのは(2')でしょうか？C++における「データ競合」の定義に従うと、同一変数に対する読み込み操作のみであれば安全に同時アクセスが可能なのです（変数x）。ただし、1つでも変更操作が発生するケース（変数y）では、データ競合を回避するために排他制御が必要となることに注意してください。

// 同一変数に対して同時読み込み操作のみ
int x = 0;
void th1() {
  int r1 = x; // OK
}
void th2() {
  int r2 = x; // OK
}

// 同一変数に対して片方が変更操作
int y = 2;
void th1() {
  int r2 = y; // NG: データ競合
}
void th2() {
  y = 42;     // NG: データ競合
}

利用者視点で考えると、上記ルール“全てが読み込み操作ならば排他制御は不要である”というのが、C++基本型が提供するスレッドセーフ保証と解釈できます。

Q4. 基本型intはスレッドセーフですか？
A4. 「同時アクセスが全て読み込み操作であれば安全」というスレッドセーフ性レベルが保証される。

1.3. C++標準ライブラリとデータ競合

Q3. std::stringクラスはスレッドセーフですか？

さて基本型のスレッドセーフ保証は分かりましたが、C++標準ライブラリ提供のクラスではどうでしょう。例えば文字列型std::stringクラスでは、明らかにprivateなメンバ変数として複数の基本型（文字列ポインタやバッファ長など）を内包しているはずです。一方でC++11以前のプログラム動作との互換性を考慮すると、クラス内部実装にミューテックスなど排他制御の仕組みがこっそり追加されたとは考えにくいですね。そうなると、マルチスレッドプログラムからこれらのクラスを安全に利用するには、利用者側にて全てのメンバ関数呼び出しを排他制御しないとダメなのでしょうか…？

std::string s = "hello";
void th1()
{
  // ここに排他制御は必要？
  bool b = s.empty();
}
void th2()
{
  // ここに排他制御は必要？
  char& c = s.at(0);
}

実は、C++11における重要な（そして地味な）スレッドサポートとして、C++標準ライブラリ提供クラスのデータ競合に関する基本ルールが明確化されました。

• クラスオブジェクトのconstメンバ関数呼び出しは、オブジェクトに対する読み込み操作とみなす。
• クラスオブジェクトの非constメンバ関数呼び出しは、オブジェクトに対する変更操作とみなす。（一部例外事項あり）

このルールはC++標準ライブラリ提供のクラスに対して適用される、最低限かつ基本的なスレッドセーフ保証となっています。また追加的な例外事項として、begin, endやatなどの一部の非constメンバ関数ではオブジェクト自身の内部状態を変更しないため、これらもデータ競合に関してはconstメンバ関数相当（＝読み込み操作）とみなします。

std::string s = "hello";
void th1()
{
  if ( !s.empty() )             // OK: constメンバ関数呼び出し
    printf("%s\n", s.c_str());  // OK: constメンバ関数呼び出し
}
void th2()
{
  size_t n = s.length();  // OK: constメンバ関数呼び出し
  char& c = s.at(0);      // OK: constメンバ関数相当呼び出し
}

つまり、データ競合を回避する3つの方法は次のように拡張できます。

• (1') 異なるオブジェクトに対する同時アクセス／メンバ関数呼び出しは、データ競合とはなりません。
• (2') 同一オブジェクトに対して同時読み込み操作＝constメンバ関数相当呼び出しのみならば、データ競合とはなりません。
• (3') 同一オブジェクトに対するアクセス／メンバ関数呼び出しが同時でなければ、データ競合とはなりません。

こちらも利用者視点の表現では、上記ルール“全てconstメンバ関数相当呼び出しならば排他制御は不要である”というのが、C++標準ライブラリが提供するスレッドセーフ保証と解釈できます。

Q3. std::stringクラスはスレッドセーフですか？
Q3. 「同時アクセスが全て読み込み操作（constメンバ関数相当呼び出し）であれば安全」というスレッドセーフ性レベルが保証される。

1.4. C++標準ライブラリ：シーケンスコンテナ編

Q2. std::vector<T>クラスはスレッドセーフですか？

他の型を内包するシーケンスコンテナ(sequence containers)クラスはどうでしょうか（説明のためT=intとする）。コンテナクラスのデータ競合を考える場合、コンテナオブジェクト(vector<int>)と格納された各要素(int)は異なるオブジェクトであると認識することが重要です。

コンテナ要素へアクセスする最も一般的な方式はvector<T>::operator[]メンバ関数呼び出しでしょう。このoperator[]にはconst・非constメンバ関数の2つが存在しますが、前掲の「基本的なスレッドセーフ保証」により両者ともconstメンバ関数（相当）として扱われます。このため、コンテナオブジェクトの他constメンバ関数と同時に呼び出してもデータ競合とはなりません。

std::vector<int> v = { 1, 2, 3, 4, 5 };
void th1()
{
  size_t n = v.size();  // OK: v.size()は、vに対する読み込み操作
}
void th2()
{
  v[1] *= 2;  // OK: v[1]つまりv.operator[](1)は、vに対する読み込み操作
  // v[1] *= 2は、vの2番目要素に対する変更操作
}

operator[]や他メンバ関数（イテレータ経由やatなど）を介して得られた各コンテナ要素オブジェクトへのアクセスについては、既に説明してきたデータ競合の考え方と同じになります。つまり、異なるコンテナ要素オブジェクトへのアクセスであれば、同時に変更操作を行ってもデータ競合とはなりません。((このコンテナ要素アクセスに関するデータ競合に関して、1つだけ例外ケースが存在します。特殊化されたstd::vector<bool>だけは、異なる要素へのアクセスであってもデータ競合が発生する可能性があります。同テンプレート特殊化版の仕様が要請するメモリ空間最適化のために、異なるboolオブジェクトが“同一メモリ位置（バイト）”の異なるビットとして配置される可能性があるためです。))

std::vector<int> v = { 1, 2, 3, 4, 5 };
void th1()
{
  // v[1]つまりv.operator[](1)は、vに対する読み込み操作
  ++v[1];    // OK: vの2番目要素に対する変更操作
}
void th2()
{
  // v[3]つまりv.operator[](3)は、vに対する読み込み操作
  v[3] = 0;  // OK: vの4番目要素に対する変更操作
}

Q2. std::vector<T>クラスはスレッドセーフですか？
A2. コンテナ自身std::vector<T>および各要素Tに対して、個別に「同時アクセスが全て読み込み操作（constメンバ関数相当呼び出し）であれば安全」というスレッドセーフ性レベルが保証される。

1.5. C++標準ライブラリ：連想コンテナ編

Q1. std::map<K,V>クラスはスレッドセーフですか？

最後に、より複雑な連想コンテナ(associative containers)クラスをみていきましょう（説明のためK=int, V=std::stringとする）。既に説明してきた通り、コンテナオブジェクト(map<int,string>)と格納されるキー(int)－値(string)をそれぞれ異なるオブジェクトと考える必要があります。これらのクラス／型はそれぞれで基本的なスレッドセーフ保証を提供しますから、もう説明しなくても分かりますよね。

std::map<int,std::string> m = { {1,"a"}, {2,"b"} };
void th1()
{
  size_t n = m.size();  // OK: m.size()は、mに対する読み込み操作
}
void th2()
{
  m.at(2) += "x";  // OK: m.at(2)は、mに対する読み込み操作
  // m.at(2) += "x"は、mの要素{2,"b"}の値に対する変更操作
}

ところで、上記コードでは意図的にmap<int,string>::operator[]の利用を避けました。実は“連想コンテナクラスのoperator[]メンバ関数は変更操作”と解釈するため、下記コードへ単純に置き換えるとデータ競合を引き起こしてしまうのです((連想コンテナstd::map, std::unordered_mapでは非const版operator[]メンバ関数のみが提供され、そもそもconst版operator[]メンバ関数は存在しません。))。少々不便に見えるかもしれませんが、このメンバ関数は“与えられたキー値が存在しなければ新要素を追加する”という動作仕様となっており、これはコンテナ自身の内部状態を変更しないことには実現できないからです。

std::map<int,std::string> m = { {1,"a"}, {2,"b"} };
void th1()
{
  size_t n = m.size();  // NG: データ競合
}
void th2()
{
  m[2] += "x";  // NG: データ競合
  // m[2]つまりm.operator[](2)は、mに対する変更操作
}

つまりmap<int,string>::operator[]を安全に使うには、ミューテックスによる排他制御が必要となるのです。

std::mutex mtx;
std::map<int,std::string> m = { {1,"a"}, {2,"b"} };
void th1()
{
  std::lock_guard<decltype(mtx)> lk(mtx);
  size_t n = m.size();  // OK
}
void th2()
{
  std::lock_guard<decltype(mtx)> lk(mtx);
  m[2] += "x";  // OK
}

C++標準ライブラリでは、連想コンテナstd::map<K,V>, std::unordered_map<K,V>の2つで本ルールが当てはまります。

Q1. std::map<K,V>クラスはスレッドセーフですか？
A1. コンテナ自身std::map<K,V>および各要素キーKと値Vに対して、別個に「同時アクセスが全て読み込み操作（constメンバ関数相当呼び出し）であれば安全」というスレッドセーフ性レベルが保証される。ただしoperator[]はコンテナに対する変更操作であることに注意。

2. スレッドセーフ RELOADED

いかがでしょう。5つの質問には答えられましたか？ここでは、改めてC++標準ライブラリの基本的なスレッドセーフ保証について整理し、またこの考え方が特段目新しいものでないことを紹介します。さらに、しばしばスレッドセーフ論争を引き起こすクラスや関数をいくつか挙げて、追加的な解説を行いたいと思います。

2.1. 基本的なスレッドセーフ保証

前節の繰り返しとなりますが、C++言語仕様およびC++標準ライブラリでは次の「基本的なスレッドセーフ保証」を提供します。これは、C++標準ライブラリ提供のクラス／関数が提供する、最低限のスレッドセーフ性の保証となっています。ちなみに、ここで“最低限の”と表現しているのは、C++標準ライブラリの一部クラスではもっと強いスレッドセーフ保証（＝同時に変更操作を行っても安全）を提供するためです。

• 同一オブジェクトにする同時アクセスが全て読み込み操作であれば、排他制御なしでもデータ競合を引き起こさない。
• C++標準ライブラリ提供のクラスでは、constメンバ関数（およびオブジェクトを変更しない非constメンバ関数）呼び出しは読み込み操作とみなす。
• これ以外のケース（少なくとも片方が変更操作）の場合、同一オブジェクトへの同時アクセスを排他制御する必要がある。

さて、この「基本的なスレッドセーフ保証」ですが、実はC++11で新たに作られた考え方ではありません。C++98以前から存在しており、また現C++標準ライブラリの源流でもあるSGI STLライブラリでも、同等のスレッドセーフ保証を提供すると明言していました。*5

The SGI implementation of STL is thread-safe only in the sense that simultaneous accesses to distinct containers are safe, and simultaneous read accesses to to shared containers are safe. If multiple threads access a single container, and at least one thread may potentially write, then the user is responsible for ensuring mutual exclusion between the threads during the container accesses.

Standard Template Library Programmer's Guide, Thread-safety for SGI STL

さらにC言語の時代にまでさかのぼると、POSIXシステムにおいても同等のスレッドセーフ保証が明言されていました。（こちらは対象がC言語のためconstメンバ関数は存在しません。）

（略）They usually cannot determine when memory operation order is important and generate the special ordering instructions. Instead, they rely on the programmer to use synchronization primitives correctly to ensure that modifications to a location in memory are ordered with respect to modifications and/or access to the same location in other threads. Access to read-only data need not be synchronized. The resulting program is said to be data race-free.

The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition

2.2. std::shared_ptr<T>

C++11では所有権共有スマートポインタstd::shared_ptr<T>がC++標準ライブラリ入りしました。ここでは同一intオブジェクトを参照する2つのスマートポインタが存在し、同時にp1, p2を操作するケースを考えてみます（説明のためT=intとする）。各スレッド上での操作により参照カウント更新が同時に行われるため、これまでの延長線上で考えると排他制御が必要に思えます。

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  // ここに排他制御は必要？
  p1.reset();   // 参照カウントを-1
}
void th2() {
  // ここに排他制御は必要？
  auto q = p2;  // 参照カウントを+1
}

一方で、局所的な観点ではp1とp2はあくまで“異なるstd::shared_ptr<int>オブジェクト”です。仮に両スマートポインタが異なるintオブジェクト／異なる参照カウントを参照するなら、C++標準ライブラリの基本的なスレッドセーフ保証より明らかに排他制御は不要です。とはいえ、その参照先が同一か否かで必要有無が変わるようでは、結局は保守的に排他制御をせざるを得なくなります。

std::shared_ptr<int> p1 = /* ??? */;
std::shared_ptr<int> p2 = /* ??? */;
// p1とp2は同一オブジェクトor異なるオブジェクトを参照
void th1() {
  // ここに排他制御は必要？
  p1.reset();   // 参照カウントを-1
}
void th2() {
  // ここに排他制御は必要？
  auto q = p2;  // 参照カウントを+1
}

この問題に対して、C++標準ライブラリでは「異なるstd::shared_ptrオブジェクトに対するメンバ関数呼び出しは、その参照先に関わらずデータ競合を引き起こさない」と明確に保証しています。つまり、利用者からは見えないオブジェクト内部状態を気にすることなく、基本的なスレッドセーフ保証の通り“異なるオブジェクトへの同時アクセスは安全”と扱ってして良いのです。これは裏を返すと、スマートポインタstd::shared_ptrの内部実装では、参照カウント更新はatomic変数操作（または排他制御あり変数更新）にて行われることを意味します。

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  p1.reset();   // OK: 参照カウント-1は安全に行われる
}
void th2() {
  auto q = p2;  // OK: 参照カウント+1は安全に行われる
}

ただし、両スマートポインタp1, p2が同一オブジェクトを参照している状況で、shared_ptr<int>::operator*メンバ関数を介して得られた参照先intオブジェクトにアクセスする時には、intに対する基本的なスレッドセーフ保証に留意する必要があります。

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  *p1 += 1;     // NG: 参照先においてデータ競合
  // 参照先オブジェクトに対する変更操作
}
void th2() {
  int r = *p2;  // NG: 参照先においてデータ競合
  // 参照先オブジェクトに対する読み込み操作
}

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  int r = *p1;  // OK: 参照先オブジェクトに対する読み込み操作
}
void th2() {
  int r = *p2;  // OK: 参照先オブジェクトに対する読み込み操作
}

2.3. std::rand()

続いて、C言語時代の標準ライブラリから引きついだ乱数生成関数std::rand()を取り上げてみましょう((例示コードでは整数0～9を得るために剰余演算(%)を利用していますが、この実装では望ましい一様分布とはなりません。定数RAND_MAXを利用すればもう少しまともな一様分布が得られますが、C++11以降では後述の乱数ライブラリ<random>を利用すべきです。))。C++11では、この関数を複数スレッドから同時に呼び出した場合、データ競合を引き起こすか否かは処理系定義(implementation-defined)と定めています。つまり、コンパイラやライブラリに任せるとしか言っていないのです。

void th1() {
  // 処理系によっては排他制御が必要
  int r1 = std::rand() % 10;
}
void th2() {
  // 処理系によっては排他制御が必要
  int r2 = std::rand() % 10;
}

（スレッドセーフの議論に関わらず）C++11以降では、C++標準ライブラリに追加された乱数ライブラリを用いるべきでしょう。この新しい乱数ライブラリ<random>であれば乱数生成器をスレッド別に持つことができるため、データ競合について悩む必要が無くなります。((例示コードでは乱数生成エンジンstd::mt19937を引数なしで構築しているため、常に同一の疑似乱数列が得られることに注意してください。実行のたびに異なる乱数列が必要な場合、std::random_deviceなどで適当なシード値を与える必要があります。))

void th1() {
  std::mt19937 rng;
  std::uniform_int_distribution<int> dist(0, 9);
  int r1 = dist(rng);  // OK
}
void th2() {
  std::mt19937 rng;
  std::uniform_int_distribution<int> dist(0, 9);
  int r2 = dist(rng);  // OK
}

もちろん、下記コードのように単一の乱数生成器を複数スレッド間で共有し、アクセス時には排他制御を行うという実装でもOKです。ただし、この設計では“(a)高頻度で乱数生成を行う状況で、排他制御により他スレッドが停止するためプログラム処理速度に悪影響を与える”、“(b)各スレッドで取得する乱数列は実行時(OS)スレッドスケジューリングに依存するため、再現性のある乱数列を生成できない”という問題が生じます。最終的にはアプリケーションの目的によりますが、一般にはスレッド別に乱数生成器を保持する設計の方が好ましいと思います。

std::mutex mtx;
std::mt19937 rng;
std::uniform_int_distribution<int> dist(0, 9);
// 単一の乱数生成器を排他制御ありで利用
int next_rand() {
  std::lock_guard<decltype(mtx)> lk(mtx);
  return dist(rng);
}

void th1() {
  int r1 = next_rand();  // OK
}
void th2() {
  int r2 = next_rand();  // OK
}

今回はrand()関数をとりあげましたが、C++標準ライブラリに取り込まれたC標準ライブラリの関数のうち、strtok(), localtime(), setlocale()などの一部関数は複数スレッドから同時に呼び出すとデータ競合となる可能性があります。できるだけC++標準ライブラリを使いましょう！

2.4. std::cout

最後に、おそらく一番論争を引き起こすであろう、標準出力ストリームstd::coutのスレッドセーフ保証について整理します。C++標準ライブラリの基本的なスレッドセーフ保証に照らして考えると、各スレッドから同時にstd::coutへ出力するとき排他制御は必要でしょうか？

void th1() {
  // ここに排他制御は必要？
  std::cout << "I'm #1 thread." << std::endl;
}
void th2() {
  // ここに排他制御は必要？
  std::cout << "Hello, Multithreading World!" << std::endl;
}

この質問に対する回答は、2段階で考える必要があるでしょう。まず、C++11の標準ライブラリ仕様では「標準入出力ストリームオブジェクトに対する入力／出力操作は、排他制御を行わなくてもデータ競合を引き起こさない」と定めています。という訳で、上記コードはデータ競合なしに正常動作することが保証されています。つまり、標準入出力ストリームオブジェクトstd::cin, std::cout, std::cerr, std::clog（と対応するwide文字版）では、C++標準ライブラリの基本的なスレッドセーフ保証よりも強いスレッドセーフ性を提供しています。((このような強いスレッドセーフ保証が行われるのは、あくまで標準入出力ストリームオブジェクトのみです。std::fstreamやstd::stringstreamでは、基本的なスレッドセーフ保証しか提供しないのでご注意を。))

ただし、C++標準ライブラリでは「データ競合は起こさないが、複数スレッドからの出力が混ざる(interleave)可能性がある」とも言及しています。例えば標準出力には次のような文字列が出力されるかもしれませんが、これもプログラムが正常動作した結果なのです。

I'm #1
Hello,thread Multit
hreading World!

一般的には前掲コードを書いたプログラマが期待するのは、下記いずれかのように“行単位で出力されること”と考えられます。結局のところ標準出力ストリームstd::coutであっても、実用上は排他制御を行わない限りはまともな出力結果が得られないのです。

I'm #1 thread.
Hello, Multithreading World!

Hello, Multithreading World!
I'm #1 thread.

まとめ

これで今回の解説はおしまいです。最後にもう一度、本記事での要点をまとめてみましょう。

• C++11における基本型とC++標準ライブラリ提供クラスでは、少なくとも下記「基本的なスレッドセーフ保証」を提供します。
• 単一オブジェクトに対する同時アクセスが、全て“読み込み操作”＝“const関数相当呼び出し”のみであれば、複数スレッド間での排他制御は不要です。
• このルールは、複数オブジェクト間で内部共有されるデータがあったとしても維持されます。（例：std::shared_ptr）
• std::cout等の標準入出力ストリームを使う場合も、複数スレッド間での排他制御が必要になります。

I Hope You Have A Nice Multithreading C++ Programming Life!!

C++ Advent Calendar 2013 は 16日目 disktnk さんの記事へと続きます。

flickr / applebymatt

参考記事

本文中では次の記事をもとにした解説を行いました。より詳細についてはそれぞれの記事もご参考にください。

• vector要素アクセスとスレッド安全性
• C++11のcoutとスレッド安全性
• C++11標準ライブラリのスレッド安全性
• shared_ptrとスレッド安全性
• std::random_shuffle関数はスレッド安全?
• 「pthreadサポート」の意味するところ
• const, mutableキーワードとスレッド安全性

はしがき：本文中でゆるふわ手書き画像を使っていますが、当初はInkscapeで描こうと思いつつ心が折れた結果です。字が汚いことを横に置けば、手書きも悪くないですね！

*1:本記事中では thread safe＝スレッドセーフ との対比から thread safety＝スレッドセーフ性 と記述します。なお、後者の対訳語としては「スレッド安全性」の方が一般的かと思います。

*2:厳密にはもう1つの条件“(0) 対象がatomic変数でないとき”が追加されます。これを裏返すと、atomic変数に対するアクセスはデータ競合を引き起こさないことを意味します。本文中ではatomicでない通常の変数のみを対象とするため、この条件については言及していません。

*3:「データ競合」によるプログラム異常終了というのは直感に反するかもしれませんが、これは「未定義の動作」の結果としてあり得る動作の一つです。ちなみに、マルチスレッド分野でC++言語に大きな影響を与えたJava言語では、もう少し穏やかな定義「データ競合が生じると何らかの状態になる（が異常停止はしない）」となっています。

*4:組込み型やプリミティブ型と呼ばれることもあります。なお、C++言語仕様での正式名称はスカラ型(scalar type)です。

*5:id:y-hamigakiさんのHamigaki C++ライブラリでは、SGI STLより明快にスレッドセーフ保証について記載しています。

volatile教、あるいはvolatile狂

かつてのMicrosoft Visual Studio .NET 2003のC/C++コンパイラ(MSVC7.1)には、「volatile変数にオレオレ定義の意味を与えて最適化を行う」というアグレッシブすぎるオプションが存在したという昔話。

どんなもの？

このオプションでは、volatileキーワードにC/C++標準規格とは全く異なる独自の意味を与えて、コード生成時の最適化処理に利用します。つまり、コンパイル時に下記を前提としたコード生成を行うのです。

• 通常の変数＝変数実体にアクセスする手段は1通りだけ（aliasingが無い）
• volatile変数＝上記制約の範囲外（aliasingが有る）

これは「volatile＝aliasingが有りえる」というMSVC7.1だけの独自拡張です。*1

このaliasing（エイリアシング; 別名）という単語、少々耳慣れないかもしれません。aliasingが無いとは、“ある変数が指す実体にアクセス”するとき、その実体への“別の変数経由でのアクセス”が存在しないことを意味します。具体例を挙げると、int a = 0;に対してint *p = &a;を定義したとき、aと*pは“同一の実体（メモリ）”を指します。その後の処理でa = 42;とint b = *p;のように異なる変数を介してアクセスするとき、この実体に対してはaliasingが有ると言えます。*2

実はこのaliasingの有無は、コンパイラの最適化処理にとって非常に厄介なものです。通常はaliasingが有ると仮定を置いたコード生成を行わざるをえず、積極的な最適化ができないというケースが多々あります。*3

具体的には何をするの？

この最適化オプションの働きについて、マニュアル(MSDN)を引いてみましょう。

/Oa または /Ow を使用する場合は、次の規則に従う必要があります。次の規則は、volatileとして宣言されていないすべての変数に適用されます。

• 直接使われている変数をポインタで参照しません。変数が代入式の左辺または右辺で使われているか、あるいは関数の引数として使われていると、その変数が参照されます。
• 変数へのポインタが使われている場合は、その変数を直接使用できません。
• 変数のアドレスを関数で取る場合は、その変数を直接使用できません。
• ポインタによってメモリ位置が変更された場合は、別のポインタでそのメモリ位置にアクセスできません。

上記の規則に従わないと、データが破損する可能性があります。

/Oa、/Ow (エイリアスを使わないと仮定、関数呼び出しでエイリアスを使うと仮定)

…上記のMSDN日本語訳では意味が取りづらい気がしますので、素直に英語版MSDNを参照すべきかもしれません。

If you use /Oa or /Ow, you must follow these rules. The following rules apply for any variable not declared as volatile:

• No pointer can reference a variable that is used directly (a variable is referenced if it is on either side of an assignment or if a function uses it in an argument).
• No variable can be used directly if a pointer to the variable is being used.
• No variable can be used directly if its address is taken within a function.
• No pointer can be used to access a memory location if another pointer modifies the same memory location.

Failing to follow these rules can cause corrupted data.

/Oa, /Ow (Assume No Aliasing, Assume Aliasing Across Function Calls)

ちょっと何言ってるか分からない

MSDNに掲げられた4つのルールに従うと、下記ソースコードを/Oaオプションありでコンパイルした場合、実行時にデータが壊れて悲惨な結果が得られるのことです（おそらく、予期しない値を読み込んだように見えるでしょう）。いずれもC/C++言語ではごくありふれた処理ですし、このようなソースコードが正しく実行できないとなると、もはや普通のプログラムを書ける気がしません。

int x = 0;
int *p;
void rule1()
{
  x = 42;  // 直接xを使うとき...
  p = &x;  // NG: ポインタが参照してはダメ！
}

int x = 0, y;
int *p = &x;
void rule2()
{
  *p = 42;  // ポインタ経由で使うとき...
  y = x;    // NG: 直接xを使ってはダメ！
}

int x = 0;
void rule3()
{
  int *p = &x;  // 関数内でアドレスをとると...
  x = 42;       // NG: 直接xを使ってはダメ！
}

int x = 0, y;
int *p1 = &x;
int *p2 = &x;
void rule4()
{
  *p1 = 42;  // あるポインタ経由で使うと...
  y = *p2;   // NG: 別ポインタ経由で使ってはダメ！
}

volatile教のすゝめ

MSVC7.1曰く、/Oaオプションありでも正常動作させるならば、volatileキーワードを利用せよと。ここまで来ると、もはやvolatile教信者というよりvolatile狂信者の様相を呈しています。

volatile int x = 0;
volatile int *p;
void rule1()
{
  x = 42;  // 直接xを使うとき...
  p = &x;  // ポインタが参照してもOK！
}

volatile int x = 0, y;
volatile int *p = &x;
void rule2()
{
  *p = 42;  // ポインタ経由で使うとき...
  y = x;    // 直接xを使ってもOK！
}

volatile int x = 0;
void rule3()
{
  volatile int *p = &x;  // 関数内でアドレスをとると...
  x = 42;       // 直接xを使ってもOK！
}

volatile int x = 0, y;
volatile int *p1 = &x;
volatile int *p2 = &x;
void rule4()
{
  *p1 = 42;  // あるポインタ経由で使うと...
  y = *p2;   // 別ポインタ経由で使ってもOK！
}

Don't Try This At Home, I'm A Professional Volatileian.

その後…

結局のところ、実プロダクトでこの最適化オプションを活用できる場面が無かったのでしょう。次バージョンMicrosoft Visual Studio .NET 2005(MSVC8.0)ではあっさり削除されましたとさ。

• /Oaコンパイラオプションが削除されましたが、エラーなしで無視されます。（後略）
• /Owコンパイラオプションが削除されましたが、エラーなしで無視されます。（後略）

Visual Studio 2005 - コンパイラの新機能

R.I.P to /Oa, /Ow options.

*1:C/C++標準規格では（主として）「volatile＝C/C++実行環境の“外”にリンクしている」を意味し、代表的な例ではメモリマップドI/Oなどでvolatile変数が利用されます。よく「volatile＝最適化の抑止」のような表現がされますが、これは「volatile変数アクセス⇒C/C++言語仕様の“外”への干渉／未知の“何か”を操作する⇒コンパイラが直接知りえない操作は勝手に最適化できない」から帰結される一側面に過ぎません。

*2:本記事中では言及しませんが、C言語（C99以降）にはrestrictキーワードが導入されており、この最適化オプションが目指していた事をより安全に達成できます。つまり、プログラマ自身が「aliasingが無い」と分かっている箇所のみを明示し、普通の変数アクセスでは従来通り「aliasingが有る」という仮定が置かれます。詳細はrestrictキーワードや続 restrictキーワードなどを参照ください。

*3:C/C++言語の文脈では“Strict Aliasing Rule”という規則があり、これにより一定の条件下ではaliasingが無いと仮定した積極的な最適化処理ができます。詳細は翻訳記事“C/C++のStrict Aliasingを理解する”あたりをどうぞ。

FizzBuzz化ストリーム

インターネット上で定期的に話題にのぼる「FizzBuzz問題」を、C++言語で変な風に解いてみたというお話。

今ではすっかり有名になったFizzBuzz問題ですが、元々はJeff Atwood氏による2007年の記事Why Can't Programmers.. Program?（青木靖氏による日本語訳）が初出のようです。ルールをおさらいしておくと、次の仕様を満たすプログラムを作れという問題ですね。

1から100までの数をプリントするプログラムを書け。ただし3の倍数のときは数の代わりに「Fizz」と、5の倍数のときは「Buzz」とプリントし、3と5両方の倍数の場合には「FizzBuzz」とプリントすること。

困ったときのおまじない

FizzBuzz問題はあまりにも有名なため、Web検索すればいくらでも実装コード例が見つかります。いまさら普通に解いてもしょうがない（？）ので、C++標準ライブラリI/Oストリームを利用して非侵襲的(nonintrusive)な解法をとりたいと思います。

つまり、オリジナルのこんなコードに対して：

#include <iostream>
const int N = 16;

// 1...Nまでの数字を出力
template <class OutputStream>
void countup(OutputStream& os)
{
  for (int i = 1; i <= N; ++i)
    os << i << os.widen(' ');
  os << std::endl;
}
 
int main()
{
  // countup()関数を呼ぶ
  countup(std::cout);
}
// 出力結果：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

標準出力ストリームstd::coutに小細工をすると…

int main()
{
  fizzbuzznizer fb(std::cout);  // おまじない

  // 先ほどと同じcountup()関数を呼ぶだけ
  countup(std::cout);
}
// 出力結果：
// 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16

元の出力処理(countup関数)には一切手を加えずに（＝非侵襲的）、ちゃんとFizzBuzz問題が解けました。

ちなみにこの“おまじない”、出力処理側のコードには依存しないので：

fizzbuzznizer fb(std::cout);  // おまじない

// 出力が文字列でもOK
std::cout << "seq={1 2 3 4 5 6...}";
  // 出力結果：seq={1 2 Fizz 4 Buzz Fizz...}

// Boost.Formatとの組み合わせもOK
#include <boost/format.hpp>
std::cout << boost::format("%1% and %2%, %3%") % 1 % 42 % 105;
  // 出力結果：1 and Fizz, FizzBuzz

また出力ストリーム（std::ostream派生クラス）を対象として、こんなことも：

#include <sstream>
std::ostringstream oss;
fizzbuzznizer fb(oss);  // おまじないをossにふりかける

// ostringstreamでもいけるよ
oss << 6 << "/10";
assert(oss.str() == "Fizz/Buzz");

C++万歳！I/Oストリーム万歳！

タネ明かし

先ほど使った怪しい“おまじない”は、下記コードで実現されます。
実装の概略：

• basic_fizzbuzznizer：対象出力ストリームオブジェクトのストリームバッファを、下記basic_fizzbuzz_streambufに差し替える。
• basic_fizzbuzz_streambuf：対象ストリームオブジェクトから渡されてくる文字に対してFizzBuzz化を行い、結果を元ストリームバッファに転送する。
• ジェネリックな記述によりwchar_t等にも（無駄に）対応。

basic_fizzbuzznizerクラステンプレート

同オブジェクトの変数スコープにあわせて、対象出力ストリームオブジェクト（std::coutなど）のストリームバッファを置換／復元するヘルパクラスです。

通常は「std::cout → {coutのストリームバッファ}」のようになっている関連付けを、コンストラクタにて「std::cout → basic_fizzbuzz_streambuf → {coutのストリームバッファ}」のように差し替え、またデストラクタでは関連付けを元に戻しています。

basic_fizzbuzz_streambufクラステンプレート

実際にFizzBuzz化処理を行う、std::basic_streambufから派生するストリームバッファクラスです。basic_fizzbuzz_streambufは一般的なストリームバッファと異なり、ストリームクラスから渡されてくる文字を変換（FizzBuzz化）するだけで、本当の“出力”処理は元のストリームバッファへ委譲します。

さて、FizzBuzz問題における倍数判定は「数値」に対して行う必要がありますが、残念ながらストリームバッファで受け取れるデータは「文字」シーケンスだけです。これは前段のストリームオブジェクトで整形(format)された結果であり、I/Oストリームライブラリ設計に起因しています。

ただ幸いなことに必要な倍数判定は3と5のため、次の代替判定アルゴリズムを利用できます。また、与えられた「文字」シーケンスに対して、“数字で構成される部分シーケンス”を「数値」として解釈することにします。

• 3の倍数＝各桁の数値の合計値が3の倍数
• 5の倍数＝最下位桁が0または5

以上をもとに、basic_fizzbuzz_streambuf各メンバ関数では次の処理を行います。

コンストラクタ

元ストリームバッファを保持し(sb_)、自身の出力領域(put area)サイズを0に設定する(setp(0, 0))。これにより、1文字受け取るたびにoverflow()が呼び出されるようになる。

overflowオーバーライド

出力領域があふれる＝ストリームバッファへ1文字入力された時に呼び出される。入力が“数字”であれば一時バッファ(tb_)で追加保持し、3の倍数判定準備(acc3_)と5の倍数判定(mul5_)を行う。数字以外の場合はそのまま元ストリームバッファへ転送する(sb_.sputc(c))。

syncオーバーライド

フラッシュ要求がなされた時に呼び出される。倍数判定結果に応じて出力文字列を決定し、putn()ヘルパ関数を経由して元ストリームバッファへ流し込む(sb_.sputc(...))。

fizzbuzznizer

仕上げに、C++標準ライブラリ風のchar／wchar_t用typedefを準備して完成です。

typedef basic_fizzbuzznizer<char> fizzbuzznizer;
typedef basic_fizzbuzznizer<wchar_t> wfizzbuzznizer;