XOR swap今昔物語: sequence pointからsequenced-beforeへの変遷

この記事は C++ Advent Calendar 2016 21日目（の事後穴埋め）としてエントリしています。2017/01/06投稿。

C/C++言語による XOR交換(XOR swap)アルゴリズム の実装と、計算の評価順序によって引き起こされるみんな大好き未定義動作(Undefined behavior)にまつわるお話です。

xorswap.cpp

int a = /*...*/;
int b = /*...*/;

// 変数a, bの値を交換
a ^= b;
b ^= a;
a ^= b;

この記事の1行まとめ：あのC/C++言語もプログラマ・フレンドリに変化しているよ。それでも自分の足を撃ち抜きたくなければ、小賢しいコードは書かないように。

おことわり

本記事は、はてなダイアリーの記事でも利用した draw.io サービスを使ってお絵かきしたい欲求（8割）と、同記事をまとめた後に気づいた内容の整理（1割）と、昨年(2016)のC++ Advent Calendar残り1枠を埋める目的（1割）で書かれました。

このように不純な動機にもとづくため、あまり丁寧な解説を行っていません。特に後半C++11以降の説明では、Cryoliteさんによる一連の連載記事を前提とします。もし未読であれば連載記事を一読してから、本記事に戻られることを強くお勧めします。

• C++0x Memory Model 第0回 - メモリモデルとは何か
• C++0x Memory Model 第1回 - 1.9 Program execution

非常に基礎的な部分からとても丁寧に解説されていますが、それでも理解するのは易しくありません。1回だけでは内容を把握できなくても大丈夫、数回も繰り返し読めば少なくとも雰囲気くらい掴めるハズです。

XOR交換アルゴリズム

ビット排他的論理和(XOR)との複合代入演算子 ^= を用いた下記ソースコードは、C/C++プログラマの期待通りに正常動作します。¹

xorswap.cpp（再掲）

// 変数a, bの値を交換
a ^= b;
b ^= a;
a ^= b;

めでたしめでたし…… で終わるなら本記事は不要なのですが、ここで手練れのC/C++プログラマが “気を利かせ” たとします。

C++03以前（C99以前）のお話

彼/彼女は(複合)代入演算の式がその計算結果を返すこと、つまり「式a ^= bがaに代入された値を返す」ことを利用し、たった1行でアルゴリズムを書けることに思い至るかもしれません。やったね！

xorswap_1liner.cpp

// スマートな実装??
a ^= b ^= a ^= b;

この一見スマートなXOR交換アルゴリズム実装は、残念ながらプログラマの期待通りに動作する保証がありません。C/C++言語の未定義動作(Undefined behavior)の世界にようこそ！もちろん偶然に動くこともありますが、本当に何が起きても誰も助けてくれませんよ？

でもご心配なく、C/C++プログラマならば誰しも一度は通る道です。古事記もといC言語 FAQにもそう書かれています。

Q: Here's a slick expression:

a ^= b ^= a ^= b

It swaps a and a without using a temporary.

A: Not portably, it doesn't. It attempts to modify the variable a twice between sequence points, so its behavior is undefined.

For example, it has been reported that when given the code

int a = 123, b = 7654;
a ^= b ^= a ^= b;

the SCO Optimizing C compiler (icc) sets b to 123 and a to 0.

副作用完了点(Sequence point)による説明

どうして3行の式では問題無かったのに、1行の式にまとめるとアウトなのでしょうか。C/C++言語をそれなりに利用してきた方であれば、既に「副作用完了点(Sequence point)」という単語を知っているかもしれません。

詳しい説明はC言語 FAQ, 3章.式を読んでもらった方が早いのですが、ここでは簡単にまとめます。²

• 式の末尾に付けるセミコロン(;) ＝ 副作用完了点
• 下記2つのルールに違反した場合、プログラムは未定義動作を引き起こす。
  • 同じ変数への変更アクセスを、2つの副作用完了点の間では最大1回までしか行ってはならない。
  • 同じ変数への変更アクセスと読込アクセスを、2つの副作用完了点の間で並行して行ってはならない。

オリジナルのXOR交換アルゴリズム実装では、代入操作が3行に分割されていました。各行の末尾セミコロン(;)＝副作用完了点の間では、それぞれ変数a, b, aを1回づつ変更しているだけです。前掲ルールをちゃんと守っていますね。

xorswap.cpp（再掲）

a ^= b;  // 変数aを1回変更
b ^= a;  // 変数bを1回変更
a ^= b;  // 変数aを1回変更

1行にまとめた実装では、セミコロン(;)＝副作用完了点に到達する前に変数aを2回変更しています。未定義動作の世界にようこそ！！（2回目）

xorswap_1liner.cpp（再掲）

a ^= b ^= a ^= b;  // 変数aを2回変更!! + 変数bを1回変更

C++11/14（C11）のお話

時代はくだってプログラミング言語C++の仕様も改訂され、2011年発行の「C++11」を経て2016年12月現在は「C++14」が最新仕様となります。同様にプログラミング言語Cも「C11」が最新仕様となっています。

C++11仕様およびC++14仕様では色々な新機能が盛り込まれましたが、本記事で直接関係するのは「C++03以前の副作用完了点が廃止され、全く新しい順序規定へと置き換わった」ことです。

従来（C++03以前）は副作用完了点という“ポイント”を幾つか定義し、その間で行われる変更／読込アクセスにのみ着目していました。C++11ではマルチスレッド処理がサポートされたことに伴ってシングルスレッド処理の定義も全面的に見直され、ある「2つの変数アクセス間で順序関係が成り立つか」という観点に変わりました。³

大雑把に言うならば、C++03以前は粗いチェックポイント（＝副作用完了点）を規定するだけでしたが、C++11以降はあらゆる変数アクセス間の順序関係をチェックするという非常に細かい定義になりました。

基本の用語

さっそくXOR交換アルゴリズム実装を新しい順序関係ルールで説明してみましょう。

……と続けたいところですが、一から厳密な説明を行うのはあまりにも大変なため、ここからは図を使った曖昧な解説を行っていきます。それでも、おおよその雰囲気はつかめると思います（と信じてこの記事を書きました）。

とはいえ、説明中に登場するいくつかの基本用語だけは説明しておきます。

• "Value Computation"（vcと略記）：変数が保持する値の読込アクセスを含む、値の計算のこと。
• "Side Effect"（seと略記）：変数が保持する値の更新、つまり変数への変更アクセスのこと。
• sequenced-before関係（→で表記）：2つの変数アクセス間における前後関係。「A sequenced-before B」ならば、アクセスAはアクセスBより前に行われることが保証される。
• unsequneced：2つの変数アクセス間に順序関係が存在しないこと。「AとBが unsequenced」のとき、アクセスAとアクセスBの間には順序関係は定義されず、どんな順序でも良いという意味。⁴
• full-expression：セミコロン(;)で終わる1つの式文。例)a = 1;など。

sequenced-before関係による説明(1)

まずは下記3行のコードに含まれる vc, se を全て列挙します。

xorswap.cpp（再掲）

a ^= b;  // 1行目
b ^= a;  // 2行目
a ^= b;  // 3行目

• 1)vc: a 1行目/左辺a読込
• 2)vc: b 1行目/右辺b読込とXOR計算
• 3)se: a ^= b 1行目/左辺a変更
• 4)vc: b 2行目/左辺b読込
• 5)vc: a 2行目/右辺a読込とXOR計算
• 6)se: b ^= a 2行目/左辺b変更
• 7)vc: a 3行目/左辺a読込
• 8)vc: b 3行目/右辺b読込とXOR計算
• 9)se: a ^= b 3行目/左辺a変更

次に、2つのルールを適用します：

• (複合)代入演算子の 左辺 と 右辺 それぞれの vc は、(複合)代入演算子による変数の更新 se よりも前に評価される。
  • 左辺のvc → (複合)代入演算子のse
  • 右辺のvc → (複合)代入演算子のse
• あるfull-expressionに含まれる全ての vc, se は、後続するfull-expressionに含まれる全ての vc, se よりも前に評価される。exp1; exp2;とあるとき
  • exp1のvc, se → exp2のvc, se

さすがに文字だけでは辛くなってきましたので、図に登場してもらいます。

図中の矢印はそのままsequenced-before関係に対応します。見やすさのため変数aアクセスを赤枠、変数bアクセスを青枠に色分けしておきました。

はい、以上です。なんとなーく正しく動きそうな雰囲気がありますよね？そう感じ取ってください。

sequenced-before関係による説明(2)

C++03以前は副作用完了点により未定義動作となっていた、あの1行実装はどうなるでしょう。

xorswap_1liner.cpp（再掲）

a ^= b ^= a ^= b;

xorswap_1liner.cpp（ラべリング版）

   a ^= (b ^= (a ^= b));
//            ~~~~~~~~  部分式X
//      ~~~~~~~~~~~~~~~ 部分式Y
// ~~~~~~~~~~~~~~~~~~~~ 式Z

説明の都合上、部分式にはラベルを振ります。さっそく vc, se を列挙しましょう。

• 1)vc: a 部分式X/左辺a読込
• 2)vc: b 部分式X/右辺b読込とXOR計算
• 3)se: a ^= b 部分式X/左辺a変更
• 4)vc: b 部分式Y/左辺b読込
• 5)vc: a 部分式Y/右辺 部分式Xの評価結果 とXOR計算
• 6)se: b ^= X 部分式Y/左辺b変更
• 7)vc: a 式Z/左辺a読込
• 8)vc: b 式Z/右辺 部分式Yの評価結果 とXOR計算
• 9)se: a ^= Y 式Z/左辺a変更

次に、2つのルールを適用します（1個目は再登場、2個目が新出ルールです）：

• (複合)代入演算子の 左辺 と 右辺 それぞれの vc は、同演算子による変数の更新 se よりも前に評価される。
  • 左辺のvc → (複合)代入演算子のse
  • 右辺のvc → (複合)代入演算子のse
• (複合)代入演算子による変数の更新 se は、同演算子の評価結果の計算 vc よりも前に評価される。
  • (複合)代入演算子のse → (複合)代入演算子のvc

文字だけでは何が何だか分かりませんね。そこで図です。

はい、以上です…… はさすがに無理がありました。図中に unsequenced と書いた破線が引いてある通り、同じ変数aに対する 変更3) と 読込7) の間には順序関係が定義されません。

単純に考えると “変更3) より後に 読込7) が評価” または “読込7) より後に 変更3) が評価” の2パターンしか存在しないようにも思えますが、それはプログラマの身勝手な妄想に過ぎません。C/C++言語仕様はこのような「同一変数に対して順序関係のない（unsequencedな） se と vc が存在する」ことは、明確に未定義動作であるとしています。

そして、C/C++コンパイラはプログラムが未定義動作を起こすはずがないと仮定してよい（C/C++言語仕様にそう明言されている）ため、いかなること起きようとも未定義動作を起こすソースコードを書いたC/C++プログラマの責任となります。なんて世知辛い。

C++1zのお話

哀れな迷えるC++プログラマに対して、次世代標準 C++1z に向けた提案「一部の演算子では評価順をより強く規定する」という改善案が採択されました。この提案は、多くのC++プログラマが意図せず未定義動作を踏んでいた一部の処理を、期待通り動くよう救済するのが主目的です。

全ての未定義動作が解消されるわけではありませんので、そこは誤解なきよう。

sequenced-before関係による説明(3)

文字による説明はもはや放棄し、さっそくの図です。C++1zではどう変わるか見てみましょう。

図には3つの矢印（つまりsequenced-before関係）が追加されました。たったこれだけですが、前の図に存在していた 3) ー 7) 間の unsequenced 破線が消えています。

xorswap_1liner.cpp（ラべリング版再掲）

   a ^= (b ^= (a ^= b));
//            ~~~~~~~~  部分式X
//      ~~~~~~~~~~~~~~~ 部分式Y
// ~~~~~~~~~~~~~~~~~~~~ 式Z

• 2)部分式X/右辺vc: b → 1)部分式X/左辺vc:a
• 5)部分式Y/右辺vc: a ^= b → 4)部分式Y/左辺vc:b
• 8)式Z/右辺vc: b ^= □ → 7)式Z/左辺vc:a

3番目 8) → 7) の追加によって 3) → 5) → 6) → 8) → 7) という経路が確立し、新たに「変更3) sequenced-before 読込7)」が保証されるようになりました。つまり未定義動作を引き起こす条件を回避できたのです。

xorswap_1liner.cpp（再掲）

// C++1z準拠ならば 変数a, bの値を交換
a ^= b ^= a ^= b;

つまり、1行で書いたスマートなXOR交換アルゴリズムは、C++1z仕様に従えばC++プログラマの期待通りに動くのです！ありがとうC++1z、C++1zありがとう！

ぁ？C言語？知らない子ですね。

まとめ

素直に3行で書いたXOR交換アルゴリズム実装は、古今東西C/C++言語仕様の下で正しく動作します。

xorswap.cpp（再掲）

a ^= b;
b ^= a;
a ^= b;

1行に詰め込んだコードは、現行のC/C++言語仕様では未定義動作を引き起こします。C++1z言語仕様が無事に発行（2017年の予定）され、C++コンパイラがそれを正しく実装していれば、正しく動作するようになります。たぶんね。

xorswap_1liner.cpp（再掲）

a ^= b ^= a ^= b;

最後になりましたがC++プログラム中で「値の交換」を行うなら、通常は下記コードを書くべきです。

swap.cpp

#include <algorithm>

using std::swap;
swap(a, b);

奇妙なXOR交換アルゴリズムなんか使わないでね。

---

---

1. 本記事ではXOR交換アルゴリズムがどうして期待通り動くかの説明を行いません。Wikipedia記事を参照ください。 ↩

2. リンク先はC言語向けのFAQですが、副作用完了点の議論はC++03以前のC++言語にもそのまま適用できます。 ↩

3. C++11以降の言語仕様では「副作用完了点(Sequence point)」の定義が完全に削除されていますが、C11の言語仕様には依然として残っているようです。つまりC11仕様はC99以前の副作用完了点による規定と、C++11以降のsequenced-before関係による規定の両者混在した記述になっています。正直な所、C11側がどうなっているかをあまり理解できていません… ↩

4. 形式的に書くならば ￢(A sequenced-before B) ∧ ￢(B sequenced-before A) ⇒ (A unsequenced B) となります。なお厳密にはunsequencedは2項関係の一種としてはでなく、"If A is not sequenced before B and B is not sequenced before A, then A and B are unsequenced." と定義されます。 ↩