最近の tar には a (--auto-compress) オプションなるものが追加されたために人類の生産性がおよそ1%程度(当社比)向上する.

$ mkdir test

$ tar cavf test.tar.gz test
test/

$ file test.tar.gz
test.tar.gz: gzip compressed data, from Unix, last modified: Thu Mar 29 10:46:53 2012

$ rmdir test/

$ tar xavf test.tar.gz
test/
$ mkdir test

$ tar cavf test.tar.bz2 test
test/

$ file test.tar.bz2
test.tar.bz2: bzip2 compressed data, block size = 900k

$ rmdir test/

$ tar xavf test.tar.bz2
test/

GNU coreutils の sort のバージョンが古いために -V (--version-sort) オプションが無いという悲しみの中で,それでも僕たちは前を向いて強く生きていかないといけない.

http://linux.die.net/man/1/sort に記述されている -V (--version-sort) オプションに縋って生きてきた僕たちは,ある日,別の環境でこのオプションが使えないことを知って絶望の奈落へと突き落とされる.
http://stackoverflow.com/questions/4493205/unix-sort-of-version-numbers

$ curl -s 'http://ftp.tsukuba.wide.ad.jp/software/binutils/' | grep -Eo 'binutils-[[:digit:]]+\.[[:digit:]]+\.[[:digit:]]+' | sort -u
binutils-2.10.1
binutils-2.11.2
binutils-2.12.1
binutils-2.13.1
binutils-2.13.2
binutils-2.16.1
binutils-2.19.1
binutils-2.20.1
binutils-2.21.1
binutils-2.8.1
binutils-2.9.1

$ curl -s 'http://ftp.tsukuba.wide.ad.jp/software/binutils/' | grep -Eo 'binutils-[[:digit:]]+\.[[:digit:]]+\.[[:digit:]]+' | sort -u -t . -k 1,1n -k 2,2n -k 3,3n
binutils-2.8.1
binutils-2.9.1
binutils-2.10.1
binutils-2.11.2
binutils-2.12.1
binutils-2.13.1
binutils-2.13.2
binutils-2.16.1
binutils-2.19.1
binutils-2.20.1
binutils-2.21.1

Defining Scoped Enumerations with Human-readable Outputs

出力がちょっとだけホモ・サピエンスに優しい scoped enumeration を定義するだけのカンタンなマクロを作ったような気がする. GCC 4.6.1 -std=c++0x で動いたような気もする.

#include <iostream>

// 第1引数に enumeration の identifier (enum-name) を
// 第2引数以下に enumerator-definition を指定すること.
// 指定できる enumerator-definition は可変長で最大255個(のはず).
CRYOLITE_DECL_ENUM(Color, red, yellow, green, blue, white, black)

int main()
{
  std::cout << Color::red << std::endl;    // => "red"
  std::cout << Color::yellow << std::endl; // => "yellow"
  std::cout << Color::green << std::endl;  // => "green"
  std::cout << Color::blue << std::endl;   // => "blue"
  std::cout << Color::white << std::endl;  // => "white"
  std::cout << Color::black << std::endl;  // => "black"
}

出力がちょっとだけホモ・サピエンスに優しい以外は scoped enumeration とほとんど同じ.「第2引数以下に enumerator-definition を指定すること」って書いてるんだから, enumerator-definition のうち constant-expression の部分も書けないといけませんがなぜか書けちゃうようにできてる.ふしぎふしぎ.

#include <iostream>

// usamimi は 178
CRYOLITE_DECL_ENUM(KemonoMimi, inumimi, nekomimi, usamimi = 178, kitsunemimi)

int main()
{
  std::cout << KemonoMimi::inumimi << std::endl;     // => "inumimi"
  std::cout << KemonoMimi::nekomimi << std::endl;    // => "nekomimi"
  std::cout << KemonoMimi::usamimi << std::endl;     // => "usamimi"
  std::cout << KemonoMimi::kitsunemimi << std::endl; // => "kitsunemimi"

  std::cout << static_cast<int>(KemonoMimi::usamimi) << std::endl; // => "178"
}

まー,所詮マクロだし, constant-expression の部分に parenthesized じゃないむき出しの comma があると死にますさようなら.ちなみに上の例と下の例とで enumerator-definition の数を変えて可変長な感じを強調しているつもりだけど微妙に強調できてないっぽいのが悲しいですね? 見た目にこだわって可変長マクロと闘うようなことさえしなければ,実装コードにあるような数字の羅列を書かなくて済むわ, __VA_ARGS__ の展開タイミングに悩まなくて済むわ,いろいろ楽できるものを…….

以下,上記の CRYOLITE_DECL_ENUM というマクロの機能を実現するための実装っぽい何か.これ, GCC 以外でマクロの展開順序という超じゃじゃ馬娘を御しきるのが大変じゃないでしょうか.知らんけど? あ, 'a'-'z', 'A'-'Z' の連続を仮定してるの誰かなんとかしといてください私もう寝ますんで.

続きを読む

Boost.Build @ Linux + GCC + GNU Linker

Boost.Build において,各ターゲットの種類に対してビルドプロパティの値が具体的にどのようなコマンドラインオプションに対応するかを, Linux + GCC + GNU Linker の環境において例示するという,私以外の誰も得をしないしそもそも他に理解できる人が居るのかすら怪しい表.(基本コマンド)に各ビルドプロパティに対応するオプションが付加されたものが実際に走るコマンドになる.

featurevalueobj (C++ ソースの場合)obj (C ソースの場合)lib (built shared) *1lib (built static) *2lib (prebuilt shared) *3lib (prebuilt static) *4exerun
(基本コマンド) "g++" -c -o "target" "source""g++" -x c -c -o "target" "source"*5"ar" rc "target" "sources"*6*7*8
"ranlib" "target"
linkshared-fPIC-fPICN/AN/A
staticN/AN/A
runtime-linkshared
staticN/A (ビルドエラー)-static
runtime-debuggingon
off
optimizationoff-O0-O0
speed-O3-O3
space-Os-Os
profilingoff
on-pg-pg-pg-pg
inliningoff-fno-inline-fno-inline
on-Wno-inline-Wno-inline
full-finline-functions-finline-functions
-Wno-inline -Wno-inline
threadingsingle
multi-pthread-pthread-Wl,-Bdynamic -lrt-Wl,-Bdynamic -lrt
-pthread-pthread
rttion
off-fno-rtti-fno-rtti
exception-handlingon
off
asynch-exceptionsoff
on
extern-c-nothrowoff
on
debug-symbolson-g-g-g-g
off
stripoff
on-Wl,--strip-all-Wl,--strip-all
definevalue-Dvalue-Dvalue
undefvalue
includepath-I"path"-I"path"
cflagsvaluevaluevalue
cxxflagsvaluevalue
fflagsvalue
asmflagsvalue
linkflagsvaluevalue *9value
archiveflagsvaluevalue *10
versionvalue
flagsvalue
location-prefixvalue調査中調査中調査中調査中調査中調査中
usetarget参照
dependencytarget参照
implicit-dependencytarget調査中調査中調査中調査中調査中調査中調査中調査中
warningson-Wall-Wall
all-Wall-Wall
-pedantic-pedantic
off-w-w
warnings-as-errorsoff
on-Werror-Werror
c++-template-depthn-ftemplate-depth-n *11
sourcetarget(参照)(参照)(参照)*12挙動不明挙動不明(参照)(参照)
librarytarget*13※ (同左)挙動不明挙動不明*14
filetargetN/AN/A*15※ (同左)
find-shared-libraryvalue-Wl,-Bdynamic -lvalue-Wl,-Bdynamic -lvalue
find-static-libraryvalue-Wl,-Bstatic -lvalue-Wl,-Bstatic -lvalue
library-pathpath-L"path"-L"path"
namevalueN/AN/A*16*17
tagvalue(参照)(参照)(参照)(参照)調査中調査中(参照)(参照)
searchpathN/AN/A*18*19
locationpath*20※(同左)※(同左)※(同左)※(同左)※(同左)
dll-pathpath-Wl,-R -Wl,"path"-Wl,-R -Wl,"path"LD_LIBRARY_PATH 環境変数path を追加
hardcode-dll-pathstrue*21
false
xdll-pathpath-Wl,-R -Wl,"path" *22LD_LIBRARY_PATH 環境変数path を追加
-Wl,-rpath-link -Wl,"path"
def-filetarget
suppress-import-libfalse
true
allowvalue
address-model(無指定)
32-m32-m32-m32-m32
64-m64-m64-m64-m64
c++abi(無指定)
conditionalvalue参照
buildyes参照
no
user-interfaceconsole
gui
wince
native
auto

特記事項

まー,各バイナリフォーマットの話やリンカ・ローダのお仕事をほとんど把握してないのであれだけど,

  • 実行ファイルリンク時の -rpath-link と実行ファイルを走らせるときの LD_LIBRARY_PATH を設定するために, DLL がビルドチェインに取り込まれたらそのパスを依存先に取回している.
  • アーカイブファイル (静的ライブラリ) の扱いが非常に特殊.共有ライブラリやアーカイブファイルを他のアーカイブファイルのソースとして指定すると,アーカイブ内に追加せずに依存先に取回して,最後の最後,実行ファイルのリンク時にようやくリンク対象として列挙される.一見すると意味不明だけれど,こうしないと実態が重複して取り込まれたアーカイブができてまずいっぽい.リンカの探索が one-path なせいかしてこの環境だとそんな状況でも一応通る.ただし MSVC だとそういうアーカイブファイルのリンクはおそらく通らない.
  • あと, PE との可搬性を考慮するなら,共有ライブラリはシンボル全部解決しておいたほうが良いはず.知らんけど?
  • --no-allow-shlib-undefined なんてオプションあったのね.これを <linkflags> に設定しておきましょうそうしましょう.

*1:<link>shared が指定されていて,かつ, <name>value<search>path<file>value も指定されていない場合.

*2:<link>static が指定されていて,かつ, <name>value<search>path<file>value も指定されていない場合.

*3:<link>shared が指定されていて,かつ, <name>value<search>path<file>value かのどれか少なくとも一つが指定されている場合.

*4:<link>static が指定されていて,かつ, <name>value<search>path<file>value かのどれか少なくとも一つが指定されている場合.

*5:"g++" -o "target" -Wl,-h -Wl,target -shared -Wl,--start-group "sources" -Wl,--end-group

*6:実際の効果に関しては <name>, <search>, <file> の記述を参照すること.

*7:実際の効果に関しては <name>, <search>, <file> の記述を参照すること.

*8:"g++" -o "target" -Wl,--start-group "sources" -Wl,--end-group

*9:リンク時のフロントエンドとして g++ が使われるため,指定されたフラグは g++コマンドラインオプションとして渡される.フラグをリンカに直接渡したい場合は -Wl, を併用すること.

*10:arコマンドラインオプションとして渡される.

*11:1024 までの 32 の倍数,または 1000 までの 10 の倍数が設定できる.

*12:指定されたターゲットのうち, obj (および他の種類のターゲットから暗黙に生成された obj ターゲット) をアーカイブファイルに含める.それ以外の各々のターゲットについては usage-requirements<library>target として追加されるのと同等.さらにすべてのソースに対する <use>requirements に指定されるのと同等.

*13:ソースが空でない場合は target をソースに追加する.ソースが空の場合は挙動不明.

*14:ソースが空でない場合は target をソースに追加する.ソースが空の場合は挙動不明.

*15:ライブラリファイルへのフルパスを指定する. <name> と同時に使われることは想定されていない.効果としては usage-requirements<library>"value" および <xdll-path>"dir" が指定されるのと同等.ここで dir<file> で指定されたライブラリファイルが存在するディレクトリへのフルパス. Boost.Build のドキュメントも参照すること.

*16:ライブラリ名 (g++ld-l コマンドラインオプションに与えるのと同じ名前規則による名前) を指定する. <file> と同時に使われることは想定されていない.効果としては usage-requirements<linkflags>"-Wl,-Bdynamic -lvalue" が指定されるのと同等. <search>path と同時に指定された場合は usage-requirements<xdll-path>"path" も指定されるのと同等. Boost.Build のドキュメントも参照すること.

*17:ライブラリ名 (g++ld-l コマンドラインオプションに与えるのと同じ名前規則による名前) を指定する. <file> と同時に使われることは想定されていない.効果としては usage-requirements<linkflags>"-Wl,-Bstatic -lvalue" が指定されるのと同等. <search>path と同時に指定された場合は usage-requirements<xdll-path>"path" も指定されるのと同等. Boost.Build のドキュメントも参照すること.

*18:<name> の記述を参照すること.

*19:<name> の記述を参照すること.

*20:ターゲットの出力先パスが path に強制される.

*21:<hardcode-dll-paths> の効果を変化させる.詳細は <hardcode-dll-paths> の項を参照のこと.

*22:<hardcode-dll-paths>true が指定されている場合のみ.

C++0x の std::unique_lock - std::defer_lock と std::adopt_lock でちょっと高度なロック管理

http://cpplover.blogspot.com/2011/07/mutex.html
C++ソースコード中に「途中のreturnや例外に気をつけること」などといったコメントはあってはならないため,補足.

// 排他的にアクセスするリソース
class exclusive_resource
{
public :
    std::vector<int> v ;
private :
    std::mutex m ;
public :
    void lock() { m.lock() ; }
    void try_lock() { m.try_lock() ; }
    void unlock() { m.unlock() ; }
} ;

exclusive_resource res1, res2 ;

void thread1()
{// res1のみを操作
    std::lock_guard< exclusive_resource > guard( res1 ) ;
    res1.v.push_back(0) ;
}

void thread2()
{// res2のみを操作
    std::lock_guard< exclusive_resource > guard( res2 ) ;
    res2.v.push_back(0) ;
}

void thread3()
{// res1, res2両方を操作
    std::unique_lock<exclusive_resource> lk1(res1, std::defer_lock);
    std::unique_lock<exclusive_resource> lk2(res2, std::defer_lock);
    std::lock( lk1, lk2 ) ; // デッドロックを回避するためstd::lockを使用すること
    // res1, res2両方を操作
    // このスコープをどのように抜けようが res1.unlock() と res2.unlock() が確実に実行される.
}

void thread4()
{// thread3と同じく、res1, res2の両方を操作、thread3とは異なる処理
    std::lock( res1, res2 ) ; // デッドロックを回避するためstd::lockを使用すること
    std::unique_lock<exclusive_resource> lk1(res1, std::adopt_lock);
    std::unique_lock<exclusive_resource> lk2(res2, std::adopt_lock);
    // res1, res2両方を操作
    // このスコープをどのように抜けようが res1.unlock() と res2.unlock() が確実に実行される.
}

std::unique_lock クラステンプレートの基本的な役割,つまりどのような形でスコープを抜けようともロックの解除を確実に行うという RAII のお手本のような役割についてはすでに理解しているものとします.

まず最初に補足しておくと, unique_lock が操作の対象とする型は std::mutex だけではありません.一般に, lockunlock という名前のメンバ関数を持った型――BasicLockable コンセプトのモデル――ならなんでも操作の対象にできます.上のソースコードの例で言えば exclusive_resource クラスはこの要件を満たしているので unique_lock で扱うことができます. exclusive_resource クラスを対象にした場合も,当然, unique_lock が果たす基本的な機能は「デストラクタで exclusive_resource クラスのオブジェクトの unlock メンバ関数を呼び出す」になります.

さて, unique_lock には BasicLockable コンセプトのモデルのオブジェクトを取るだけの基本的なコンストラクタ以外に,やや特殊なコンストラクタがあります.以下の2つのシグネチャを持つ特殊なコンストラクタが今回説明するものです.

namespace std {
template <class Mutex>
class unique_lock {
public:
typedef Mutex mutex_type;
.....
unique_lock(mutex_type& m, defer_lock_t) noexcept;
unique_lock(mutex_type& m, adopt_lock_t);
.....
}
}

これら2つのコンストラクタの2つ目の引数は機能が異なるコンストラクタを呼び分けるための「タグ」を渡すためだけにあります.これらのタグ, std::defer_lock_t のオブジェクト,および std::adopt_lock_t のオブジェクトが 標準ヘッダで次のように宣言されているため

namespace std {
constexpr defer_lock_t defer_lock { };
constexpr adopt_lock_t adopt_lock { };
}

これらのコンストラクタは最初に掲げたソースコード中で示したように std::defer_lock オブジェクトおよび std::adopt_lock オブジェクトを用いて呼びだすことができます(これらのタグは, new に対する std::nothrow_t, std::nothrow と同様の機能を果たすものだと説明すれば理解される方もいらっしゃるかもしれません).

1つ目の defer_lock を渡して呼び出す方のコンストラクタですが,これは「unique_lock に対象のオブジェクトを管理させるが,コンストラクタの段階ではロックを行わない」というものです. "defer" は「保留する」とか「(実行などを)引き延ばす」などといった意味ですね.作成された unique_lock オブジェクトに対して,後に lock メンバ関数が呼ばれてロックされた状態になることでしょう.従って,最初に掲げたソースコード中のように,複数の unique_lockロックを実行せずに作成しておいて最後に std::lock でそれらすべてをデッドロックしないアルゴリズムで安全かつ一斉にロックする,という使い方が可能になります.

2つ目の adopt_lock を渡して呼び出す方のコンストラクタですが,これは「すでにロックされた何らかのリソースについて,ロック解放の管理を unique_lock へ引き継ぐ」という機能を有します.つまり,このコンストラクタはすでにロックされたlock メンバ関数が呼び出されていて,かつ, unlock メンバ関数が呼び出されていない)オブジェクトを第1引数に取り,コンストラクタの呼び出し時にはロックせず(すでにロックされているオブジェクトが渡されることを前提にしているので当然ですね),以降,ロック解放の管理が unique_lock に移譲されることになります.このコンストラクタで作成された unique_lock オブジェクトは当然ながらすでにロックされた状態となります.従って,最初に掲げたソースコード中のように, std::lock で複数のリソースをロックした後に各々のリソースのロック解放の管理を行う unique_lock を作成する,という使い方が可能になります.

このような unique_lock の使い方によって, std::lock を使ってもきちんと RAII を活かしたロック管理が可能になり,ソースコード中に「途中のreturnや例外に気をつけること」などといったコメントを書く必要がなくなります.

C++0x Memory Model 第1回 - 1.9 Program execution

前回の記事:C++0x Memory Model 第0回 - メモリモデルとは何か

以下では, C++0x プログラミング言語の標準規格として一貫して N3225 を参照しています.文中で (1.9/12) などという表現が出てきた場合は N3225 における条項を指しています. 太字かつ斜字体の言葉 は N3225 で C++0x で定義される用語, 太字の言葉 は本ブログエントリ中で特別な意味を持たせた用語として定義しているものです.

第1回目のこの記事では,まず,ただ1つの 実行スレッド thread of execution だけを考慮した場合のメモリモデルに関わる基本的な事項を説明していきます.複数スレッドが存在する状況下でのメモリモデルに関する説明する上で,単一の実行スレッド内に限定した場合の状況を把握しておくことは必要不可欠なのです.

第0回において,プログラム中にただ1つの実行スレッドしか存在しない場合には,プログラマがほとんどの状況で無意識に置いている仮定がメモリの読み書きに対して成り立つと言いました.この無意識の仮定をちょっと言葉にしてみましょう.

単一の実行スレッドにおいてはプログラムは記述された順に動作する.

一見すると至極当然のことを言い表した一文で,もちろんこの一文は真です……と言いたいところです.しかし,当然に成り立つと思われるこの一文にメスを入れていくことは非常に重要なのです.この一文のいくつかの部分に細かくツッコミを入れていくとすぐにいくつかの疑問点が出てきます.

  • 「実行スレッド」とは何か?
  • 「記述された順」とは何か?
  • 「記述された順」というのが何か分かったとして「その順に動作する」とはどういうことか?
  • 「単一の実行スレッドにおいては」ということは複数の実行スレッドがある場合には「記述された順に動作しない」のか? 仮に「記述された順に動作しない」とするならばそれはどういった理由からか?
  • プログラムが「最適化」の対象となる場合にはどうなるのか? そもそも「最適化」とは何か?

ただ1つの実行スレッドのみを考慮した場合におけるこれらの疑問点に C++0x の言葉で真摯に答えていくことは極めて重要です.なぜなら,これらの疑問点に答えていくことで,複数の実行スレッドがある場合のメモリの読み書きにおいて重要な用語や概念が自然に導入されていくからです.

C++0x における「プログラム順 program order」 - sequenced-before

いくらか話を簡単にするために,以下,登場人物を少し限定しましょう.以下では スカラー型 scalar type のオブジェクトのみに限定して話を進めます.スカラー型とは, charint など, C++0x において最も単純で基礎的な型のグループを指す言葉です.どれほど複雑で巨大なユーザ定義型のオブジェクトに対する操作を実行するにしても,どれほど複雑で長大な関数を実行するにしても, C++0x の範疇では,これらの操作は最終的にすべからく,スカラー型に対する操作か,あるいは環境が用意する何らかの API (関数) 呼び出しか,からなる列に還元されます*1.したがって,ここでの説明をスカラー型に対するものに限定しても必要十分なものとなります.環境が用意する API 呼び出しに関しては通常の関数呼び出しに関する規則が適用されます.あとはその規則を正確に展開し積み重ねていくだけで, C++0x の標準規格の範疇で書かれたあらゆるプログラムに関する動作に関する規定を演繹することができます.

もう1つ,説明の便宜上,しばらくの間「最適化」についての話は脇に置いておくことにします.最初に,「最適化」について考慮しない前提で説明を進めた後,その説明に対して「最適化」についての話を加えていくことにします.

まず最初に 制御の流れ flow of control という言葉について定義しておきます. C++0x におけるある制御の流れとは,各々の条件分岐においてどの分岐を取るかの選択の集合である,と定義しておきます.ここで,「条件分岐においてどの分岐を取るか」とは,つまり if, switch, while, do 〜 while, for の各文の各実行,および各々の仮想関数呼び出しにおいてプログラムコード上のどこへ分岐するかの選択のことに他なりません.

制御の流れが1つ与えられ,全ての条件分岐における選択が定まっていれば,ある関数からどの関数が直接あるいは間接に呼び出されるかも定まります.いくつかの関数は複数回の呼び出しの対象となります.これら各々の関数の各々の呼び出し全てに関して,それらの関数の定義におけるオブジェクトの初期化および式の評価の集まりも一意に列挙することができます.したがって,制御の流れが1つ与えられれば,その制御の流れに含まれるオブジェクトの初期化と式の評価の集まりがただ1通りに定まります.なお,制御の流れに含まれるオブジェクトの初期化や式の評価の中にはコード上に陽には現れないものもあります.

ここで, 式 expression と式の 評価 evaluation という2つの言葉の使い分けに注意してください.式は C++0x に定められた構文上の要素であり,コード上の部分文字列を指します.一方で,制御の流れによっては,ある式に対して評価が存在しなかったり,ある式に対して複数の評価が存在することがあります.たとえば,複数回呼び出される関数の定義に含まれる式や繰り返し文のブロック中の式は複数回の評価の対象となります.

以上を踏まえて 実行スレッド thread of execution という言葉を定義します.実行スレッドとは,ある関数呼び出しを最上位とするある1つの制御の流れのことを指します.制御の流れが一意に定まったとき,そこに含まれるオブジェクトの初期化および式の評価の集まりがただ1通りに列挙することができると説明しました.したがって,1つの実行スレッドに対して,それに含まれるオブジェクトの初期化および式の評価の集まりもただ1通りに定まります.このようなオブジェクトの初期化や式の評価には,最上位の関数呼び出し以前に行われるものや,呼び出しの完了以降に行われるもの,コード上に陽には現れないオブジェクトの初期化や式の評価も含まれます.

通常の説明では,「糸」という意味を持つ「スレッド」という言葉通り,オブジェクトの初期化や式の評価の,つまり何らかの前後関係が定められた集まり,を含むものとして実行スレッドを説明する場合が多いです.しかし,ここではオブジェクトの初期化や式の評価の単なる集まりを含む,とだけしておきます.これら,オブジェクトの初期化や式の評価の集まりに関する「前後関係」は後で導入します.

例えば, C++0x の範疇で書かれたプログラムの実行に際しては,少なくとも1つの実行スレッド,俗に言う メインスレッド main thread ,が存在することになります.メインスレッドは,典型的には main という名前を持つ特別な関数の呼び出しを最上位とするある1つの制御の流れです.また,メインスレッドには,最上位の関数呼び出しから直接あるいは間接に呼び出される関数全てに関して,それらの関数の定義におけるオブジェクトの初期化と式の評価を全て列挙したものが含まれます.メインスレッドには,最上位の関数呼び出し以前における静的大域変数の初期化などや,最上位関数の呼び出しが完了して以降における静的大域変数のデストラクタ実行も含まれます.また,一時オブジェクトの構築や破壊,関数パラメタの初期化など,コード上に陽には現れないものも含まれます.(5/1)

しばらくの間,以下で示すコード片においてはただ1つの実行スレッドしか存在しないものとして説明を展開していくことにします.以下,式の評価などといった言葉を用いる際には,暗黙に想定しているただ1つの実行スレッドに関して言及していることを常に意識しておいてください.複数の実行スレッドについて考える場合には,たとえば式の評価などといった言葉は「どの実行スレッドに含まれる評価であるか」を明示する必要があります.

具体的なプログラムを例として説明を進めます.

int main() {
  int x = 2;    // (1)
  int y = 0;    // (2)
  y = (x == x); // (3)
  return 0;     // (4)
}

上のプログラムにおける x = 2, y = 0 はオブジェクトの初期化です.また, 2, 0, x, x == x, y = (x == x) はそれぞれ式です.上のプログラムを実行した際のオブジェクトの初期化と式の評価の集合は以下の通りです.

2            // (1) 
x = 2        // (1) x の初期化
0            // (2)
y = 2        // (2) y の初期化
x            // (3) における等号演算子の左辺
x            // (3) における等号演算子の右辺
x == x       // (3)
y = (x == x) // (3)
0            // (4)

オブジェクトの初期化や式の評価に関する「前後関係」についてはまだ何も説明していませんから上で列挙しているオブジェクトの初期化や式の評価の並び順は今のところは特に意味がないものと思ってください.これらが,先のプログラムがある1つの実行スレッド T によって実行された際の, T による式の評価の集合となります.

しつこいようですが,今の段階においては,オブジェクトの初期化や式の評価に関する「前後関係」のようなものをまだ一切定義していないことに注意してください.したがって,どのオブジェクトがどの順番で初期化されどの式がどの順番で評価されるかは今の段階では何も説明できません.「オブジェクトの初期化や式の評価はプログラムコードの上の行から下の行に向かって行われていく」などといったことはまだ一言たりとも述べていません.どのような順でオブジェクトが初期化され式が評価されるのかは以下に述べる規則が全てです.そして,オブジェクトの初期化や式の評価の順序を述べていないということは,必然的に式の評価によって値を読み込んだ際にどういった値が読み込まれるかもまだ一切説明できない段階だということです.

次に,オブジェクトの初期化と式の評価という言葉をより掘り下げていくことにします.一般に,オブジェクトの初期化と式の評価は「読み」と「書き」から成り立ちます.「読み」とは 値の計算 value computation のことであり,「書き」とは 副作用の開始 initiation of side effect のことです.式の評価における値の計算とは,その式が左辺値ならばそれがどのオブジェクトを指しているかを同定すること――平たく言えばオブジェクトのアドレスの算出――と,式が表している値を取り出すこと,を指します.また,オブジェクトの初期化や式の評価における副作用の開始とは,オブジェクトの初期化や式の評価の結果生じる 実行環境の状態 state of execution environment の変化――平たく言えば,たとえばメモリ上に記録されている値の変化など――が開始されることです.(1.9/12, 5/1)

再び,先ほどのプログラムを例として説明を進めます.たとえば (3) の代入式の右辺における式 x の値の計算には, x という式がどのオブジェクトを指しているのかの同定――平たく言いなおせばオブジェクト x のアドレスの計算――と, x に対して代入されている値の取出しが含まれます.この式 x の評価は副作用を開始しません.また,他の例として (4) の代入式 y = (x == x) の評価においては,左辺の式で同定されたオブジェクト y に対して,右辺の式 x == x で取り出された値が代入されるという副作用が開始されます.また,この代入式の値の計算として代入先のオブジェクト (つまり y) が再び同定され (代入式は代入先のオブジェクトの左辺値を返すことを思い出してください),式の値 (つまり代入後の y の値) が取り出されます (代入式の値は代入結果の値であることを思い出してください) .先ほどのプログラムにおける副作用の開始と値の計算を列挙すると以下のようになります.

2 の vc            // (1) の初期化子 initializer の評価
x = 2 の se        // (1) による初期化
0 の vc            // (2) の初期化子の評価
y = 2 の se        // (2) による初期化
x の vc            // (3) における等号演算子の左辺
x の vc            // (3) における等号演算子の右辺
x == x の vc       // (3)
y = (x == x) の se // (3)
y = (x == x) の vc // (3)
0 の vc            // (4)

ここで, vc は値の計算 (Value Computation) , se は副作用の開始 (initiation of Side Effect) の略であるとします.この略号は以下でも使用します.先と同様,やはりこの段階でも上の表における値の計算と副作用の開始の並び順には特に意味はありません.

以下,値の計算と副作用の開始の2種類をまとめて アクション action と呼ぶことにします.

ある1つの実行スレッドにおけるアクション間の「前後関係」に相当する用語を導入しましょう.ある1つの実行スレッドにおけるアクション A と B を考えます.あるアクション A が別のアクション B よりも先行することを アクション A がアクション B に対して sequenced-before である (an action A is sequenced before an action B) ということにします.どのアクションがどのアクションに対して sequenced-before であるかは,各アクションがどの構文要素に対応したものであるかを元に, C++0x の記述から正確に定めていくことができます.ただし,ある1つの実行スレッドにおけるすべてのアクションのペア A と B に対して,「A が B に対して sequenced-before である」か,「B が A に対して sequenced-before である」か,を常に定められるとは限りません. A が B に対して sequenced-before でもなく, B が A に対して sequenced-before でもないとき, A と B は unsequenced である,ということにします.

さて,アクションは値の計算と副作用の開始の2種類であると定義しました.この説明の最も重要な部分は,アクションには副作用の開始だけが関連付けられているということです.開始されたものはいつかは完了されなけれなりません.ある実行スレッドにおけるアクション A で開始された副作用がどの時点まで完了していることが保証されるかは, A を含む実行スレッド内に関して限定すると, sequenced-before という言葉を用いて明確にすることができます. A があるアクション B に対して sequenced-before であるとき, A で開始された副作用は B までに完了していることが保証されます.

sequenced-before についていくつか説明しておきます. sequenced-before は,2つのアクションからなる順序対 ( (A, B) と (B, A) とが区別されるペア) に対して真偽を与える関数と見なすことができます.このことを特に強調して, sequenced-before はアクション上の 2項関係 である,と言うこともできます.以下,特に注記することなく, sequenced-before を2項関係として,あるいは単に 関係 として言及することにします. sequenced-before 関係は同じ実行スレッドにおけるアクション間においてのみ真になりえます.2つのアクションが異なる実行スレッドにおけるものであるときにはそれら2つのアクションは常に unsequenced となります.定義から,任意のアクション A に関して, A は A 自身に対して sequenced-before ではありません.この性質を特に指して 非反射的 irreflexive であると言います.また,同じく定義から,任意の異なる2つのアクション A, B に関して, A が B に対して sequenced-before ならば B は A に対して sequenced-before ではありません.この性質を特に指して 非対称的 asymmetric, antisymmetric であると言います.また,同じく定義から,任意のアクション A, B, C に関して, A が B に対して sequenced-before であり, B が C に対して sequenced-before であるならば, A は C に対しても常に sequenced-before となります.この性質を特に指して 推移的 transitive であると言います.以上, sequenced-before 関係は,非反射的で,非対称的で,推移的で,いくつかのアクションのペアに対してどちらの方向にも成り立たない関係となります*2.このことを特に指して 厳密な半順序 strict partial order であるなどと表現します*3 *4

以下,メモリモデルに関する多くの事柄は,言葉で延々と書かれたものを読むよりも,図を用いた説明のほうがずっと分かりやすいものになります.アクション A が アクション B に対して sequenced-before であることを次のように図示することにします.

今,下図のような4つのアクションに対する sequenced-before 関係を考えます.

この図に表されている sequenced-before 関係がきちんと厳密な半順序になっていることを確認しておいてください.さて,このままだと多くのアクションが図中に登場したときに sb の矢印が多くなりすぎます.そこで一定のルールで sb の矢印を省略することにします. sequenced-before 関係の推移性を用いることで他のアクション間の sequenced-before 関係から導出できる sequenced-before 関係を全て省略することにします.たとえば,先ほどの4つのアクションが登場する図に対しては sb の矢印が次のように省略されます.

この省略を 推移簡約 transitive reduction と呼び,推移簡約の結果できるこのような図のことを特に ハッセ図 Hasse diagram と呼びます.逆に,ハッセ図から2つのアクション間に sequenced-before 関係があるかどうかも簡単に確認することができます.アクション A から sb の矢印を向きに従ってたどって行ってアクション B にたどり着けるならば A は B に対して sequenced-before である,ということが分かります.以下では, sequenced-before 関係を図示する際には常にハッセ図の形で描くことにします.

ここに至って,先ほどのプログラムを実行した場合の各式の各評価がどのような順序で行われるかの説明にようやく入ることにします.プログラムコードと対応するアクションの集合を以下に再掲します.

int main() {
  int x = 2;    // (1)
  int y = 0;    // (2)
  y = (x == x); // (3)
  return 0;     // (4)
}
a: 2 の vc            // (1) の初期化子の評価
b: x = 2 の se        // (1) による初期化
c: 0 の vc            // (2) の初期化子の評価
d: y = 2 の se        // (2) による初期化
e: y の vc            // (3)
f: x の vc            // (3) における等号演算子の左辺
g: x の vc            // (3) における等号演算子の右辺
h: x == x の vc       // (3)
i: y = (x == x) の se // (3)
j: y = (x == x) の vc // (3)
k: 0 の vc            // (4)

行頭のアルファベットは各々の値の計算や副作用の開始を本文や図中で言及できるようにするための名前付けです.このアクションの集合に対する sequenced-before 関係を図示したものが以下です.

図中の矢印はすべて sb ラベルを省略しています.また,図中の各矢印に付けているのは各 sequenced-before 関係の直接的な根拠となっている C++0x ドラフト N3225 の条項です.この例のようにして,ある1つの実行スレッドに含まれるアクションの集合に対して, C++0x が定める規則から sequenced-before 関係を付与していくことができます.1つの実行スレッド上のアクションの集合に対して,このようにして付与されたある sequenced-before 関係が C++0x における プログラム順 program order ということになります.

sequenced-before 関係の定義のところで述べましたが, C++0x においてはある1つの実行スレッド上の全てのアクションのペアに対して sequenced-before 関係が付与されるとは限りません.これを unsequenced と言いました.ある2つのアクション A と B とが unsequenced である場合, A は B に対して先行するか, B は A に対して先行するか,あるいは A と B の実行が一部または全部重なり合うかの,いずれかとなります.上のプログラムの例では,例えば e, f, g の3つのアクションの間には sequenced-before 関係が一切存在しません.したがってこの3つのアクションは,任意の順序で実行されることも,2つ以上のアクションの実行が一部または全部重なり合う形で実行されることも,いずれもが許されることになります.ここで,現在の説明の段階では「最適化」の話を脇に置いていることに注意してください.「最適化」が許されていない状況下でもこのようなことが許されるわけです.

上の例で見られるように, C++0x では,複数のアクションの実行順序が任意であったり,複数のアクションの実行が一部または全部重なり合っても許されます.この具体的な意味づけについて少しだけ説明しておきます.以下のコード片を例として説明します.

int x = 0;
int y = 1;
int z = 2;
y = x++ + y + ++z; // (A)

上のコード片における (A) に含まれるアクションに対する sequenced-before 関係は以下に図示する通りとなります.各矢印の sb ラベルは省略します.

上のコード片がある実行スレッドによって実行される際には, (A) 中の式 x++ の評価に対する副作用の開始 e は,式 y = x++ + y + ++z の評価に対する副作用の開始に対してさえ sequenced-before 関係を維持していれば良いことになります.したがって,式 x++ の評価に対する値の計算は式 y = x++ + y + ++z の評価に対する副作用が開始されるまでにさえ完了していれば良いことになります.結果,この式 x++ の評価に対する副作用の開始が, C++ のコードがある特定のコンパイラ実装によって機械語に翻訳される様子,およびその翻訳結果の機械語が実際のある特定のアーキテクチャ上で実行される様子は,その制限さえ充足していればどのようであっても構わないことになります.たとえば,式 x++ の評価に対する副作用の開始がコンパイラによって対応する機械語に翻訳される際に,式 y の評価に対する値の計算に対応する機械語の後ろに配置されることが許されるわけです.また,たとえば,式 x++ の評価に対する副作用の開始に対応する機械語の実行と,式 ++z の評価に対する副作用の開始に対応する機械語の実行が,アーキテクチャ上で並列に行われても構いません*5.ある式が複数回評価される場合に,各評価毎に異なる順序,異なる方法を取ることすら許されます.これによって,コンパイラによる翻訳の自由度,およびアーキテクチャ上の機械語の実行の自由度を非常に高い状態で維持できることになります.

最後に,現行の C++ プログラミング言語の標準規格である C++03 における表現との対応について簡単に触れておきます. C++03 では,上記で説明したような内容は 副作用完了点 sequence point と呼ばれる用語を用いて規定されていました.しかし, C++0x で厳格なメモリモデルの記述を導入するにあたって,副作用完了点という用語は廃止され,上記で説明した sequenced-before 関係を用いた記述に刷新されました.副作用完了点という用語が廃止された理由としては,

  • いくつかの状況におけるアクション間の順序に関して,これまで副作用完了点という用語による説明では不明瞭だったことが,上記の sequenced-before 関係による説明で明確になるから
  • 上記のような半順序関係による説明の方が,後の説明で明らかとなりますが,そのまま複数の実行スレッドがプログラム中に存在するときの記述に自然に拡張できるから

というのが挙げられます.これまで副作用完了点という用語で説明されてきたことはすべて, sequenced-before という用語による説明によって上位互換な形で置き換わっています.

単一スレッド上のデータ競合 - unsequenced race

先に述べたとおり,いくつかのアクションの実行は,その順序が任意であったり,一部または全部が重なり合っていることが許されます.このことは,先に述べたようにコンパイラによる機械語への翻訳の自由度やアーキテクチャ上の機械語の実行の自由度を確保します.一方で,世間一般によく知られたある種の 未定義の振る舞い undefined behavior を引き起こす直接的要因を生み出すことにもなります.

unsequenced な異なる2つのアクションが同じオブジェクトに対するアクションである場合を考えます.これら2つのアクションが「読み」「読み」である場合には特に問題はありません. unsequenced な2つのアクションが同じオブジェクトに対して値の計算を行うことは C++0x においては許されています.問題は少なくとも一方が「書き」の場合です.

あるオブジェクト M に対して,ある副作用 S が開始されて以降その完了が保証されないタイミングで, M に関する値の計算を行うこと,あるいは M に対して別の副作用を開始すると未定義動作を引き起こします. S の完了が保証されないタイミングにおいては, S はすでに完了しているか,まだ開始されていないか,あるいは最悪の場合は M は S の完了に向けた中途半端な状態にあるかであり,このどれであるかは,上述の通り,機械語への翻訳を行うコンパイラ,および機械語を実際に実行するアーキテクチャ,それらの完全な裁量に委ねられています. M に対する副作用が完了していることが保証されないタイミングで, M に関する値の計算を実行したり, M に対して別のさらなる副作用を開始すると非常に具合が悪いことは明らかでしょう.したがって, C++0x においてはこのような状況を一括して未定義動作を引き起こすものとして規定しています.

具体的な例として以下のコード片について詳しく見ていきます.*6

void g(int i, int *v) {
  i = v[i++]; // (A)
  /* ... */
}

(A) がある実行スレッドで実行されたときの,各アクション間の sequenced-before 関係を以下に図示します.各矢印の sb ラベルは省略します.

g と f の2つのアクションは unsequenced であり,両方ともに i に対して副作用を開始します.このような場合,例えば g による i に対する副作用が開始されるタイミングでは, i に対する f の副作用は,すでに完了しているか,まだ開始されていないか,もしくは f の副作用は開始されているがまだ完了しておらず i は中途半端な値を持つか,のいずれかです.逆に, f の副作用が開始されるタイミングの観点から見てもまったく同様の議論になります.これは先に述べたように非常に具合が悪く, C++0x ではこのような状況は未定義動作を引き起こすものとして規定されています.

未定義動作を引き起こすこの種の状況を,以下, unsequenced race と呼ぶことにします.

unsequenced race が引き起こされる条件を,先に定義した用語を用いて表現しておきましょう.2つのアクションの片側から見てもう一方が引き起こした副作用が完了していない状態というのは,結局のところ,これら2つのアクションの間に sequenced-before 関係がどちらの向きにも存在しない場合になります.したがって, unsequenced race が引き起こされる条件は,2つのアクション A と B が以下のすべての条件を満足するときとなります.

  • A と B とが unsequenced である
  • A と B 両方が同じオブジェクトに対するアクションである
  • A と B のどちらかが副作用の開始である

なお,現行の C++03 では 未指定の振る舞い unspecified behavior を起こすとされていたいくつかの状況が, unsequenced-before 関係による規定に変更されたことに伴い, C++0x では一括して未定義の振る舞いを起こすものとして規定が変更となっています.

「最適化」とは何か? - observable behavioras-if ルール

ここまでの説明は「最適化」の話を一切脇に置いて説明してきました.以下では,上記までの説明に「最適化」に関する説明を加えていくことにします.

C++0x におけるプログラムの 最適化 optimization とは, C++0x の範疇で書かれたあるプログラムコードに対して,上述の制約を満たした機械語への翻訳結果とアーキテクチャ上における機械語の実行方法――C++0x プログラミング言語の実装――が得られたとき,それに対してある観点からは見分けのつかない別の C++0x プログラミング言語の実装に変換する行為である,とここでは定義することにします*7.ここで,「2つの C++0x プログラミング言語の実装の見分けが付く・付かない」がどの観点から定義されるかが問題となります. C++0x では「プログラミング言語の実装の見分けが付く・付かない」についての観点は, 観測可能な振る舞い observable behavior という言葉で定義されます.

観測可能な振る舞いについて説明します.観測可能な振る舞いとは,プログラムを実行した際に,ユーザが観測することが前提となっている挙動です.たとえば,メモリのどの場所へどのような順序でどのような値が書き込まれたかは観測可能な振る舞いではありません*8C++0x で定義されている観測可能な振る舞いは以下の通りです.

  • volatile 修飾されたオブジェクトに対するアクセスの評価
  • プログラム終了時のファイルへの出力結果
  • interactive device の入出力の挙動において,入力を待つ前に入力を促すための出力をきちんと表示すること

今, C++0x の範疇で書かれたあるプログラムコードに対する C++0x プログラミング言語の実装が2つあるとして,観測可能な振る舞いだけ見てもそれら2つの違いが分からないとき,この2つの C++0x プログラミング言語の実装は「見分けが付かない」と呼ぶことにします. C++0x では,あるプログラムコードの C++0x プログラミング言語の実装は,「見分けが付かない」ものならばどれであっても構わないと規定されています.この規定を特に as-if ルール と呼びます.「最適化」とは, as-if ルールの範囲で許される C++0x プログラミング言語の実装の候補のうちの適当な1つを選択することだということができます.

複数の実行スレッド間の関係を説明するにあたって

以上の説明は,ただ1つの実行スレッドが存在する場合についてのものでした.ここでは,それらの説明が複数の実行スレッドが存在する場合の話へどうつながっていくかについて簡単に触れておきます.

sequenced-before 関係の説明においては, sequenced-before 関係はある1つの実行スレッドに含まれる異なる2つのアクションに関してのみ真になりえると説明しました.また, sequenced-before 関係は,あるアクションが開始した副作用がいつまでに完了するかについての保証をもたらすとも説明しました.ここから得られる1つの帰結として,異なる実行スレッドに含まれる2つのアクションの間においては,何か特別なことをしない限り副作用の完了に関する保証が一切得られない,ということが挙げられます.

unsequenced race の説明においては,あるオブジェクトに対する副作用が完了していることが保証されていないタイミングで,同じオブジェクトに関する値の計算や別の副作用の開始を行うことが未定義動作を引き起こすと説明しました.ところで,マルチスレッドプログラミングにおける データ競合 data race という用語をご存じの方も多いかと思います. C++0x では,この,あるオブジェクトに対する副作用が完了していることが保証されていないタイミングで,同じオブジェクトに関する値の計算や別の副作用の開始を行うことをまさにデータ競合と定義しています.したがって, unsequenced race は単一実行スレッド下におけるデータ競合の特殊形であると説明することができます.ということは,逆に, unsequenced race という概念・用語を理解すること,あるいは,その成立条件を構成する値の計算,副作用の開始・完了, sequenced-before 関係などの概念・用語を理解することはそのまま C++0x におけるデータ競合の概念を理解することにつながっていきます.

最適化の説明においては,コンパイラによってプログラムコードが機械語に翻訳された結果,そして翻訳結果の機械語が実際のアーキテクチャ上で実行される様子は,観測可能な振る舞いを変化しない範囲ならばどのようであっても完全に自由だと説明しました.ここで, C++0x で規定されている観測可能な振る舞いを思い出してください.何か特別なことをしない限り,ある実行スレッドにおけるアクションが他のある実行スレッドにおけるアクションに対してどのような影響を与えるかは観測可能な振る舞いの範疇には一切入りません.したがって,最適化は,何か特別なことをプログラム上でしていない限り,観測可能な振る舞いに影響のある sequenced-before 関係,つまりある実行スレッド上のプログラム順のみを考慮し,それ以外のあらゆる観点で複数の実行スレッド間の関係を一切考慮しないことが許されます.結果として,複数スレッド間の関係に関する特別な何かをプログラムコード上で明示しない限り,最適化は複数の実行スレッド間の関係に対して完全に予測不能な結果をもたらすことになります.ただし,このことは一方で,単一実行スレッドのためにこれまでに積み上げられてきた膨大な量の各種最適化実装の資産とノウハウを完全に継承することができるということも意味します.

複数の実行スレッドがある場合に volatile 修飾子がどのような効果をもたらすかについても説明しておきます.上に述べたとおり, volatile 修飾子によって対象のオブジェクトに対するアクションは観測可能な振る舞いとして扱わなければならなくなります.したがって, volatile 修飾子が付与されたオブジェクトに対するアクションは, as-if ルールの適用外となり, sequenced-before 関係に厳密に従う形態で実装されなければなりません.しかし,それだけです.前述のとおり, sequenced-before 関係は同一実行スレッドにおけるアクションだけにしか成り立ちません.したがって, volatile 修飾子は異なる実行スレッドにおけるアクション間の関係には一切寄与しません.結果, volatile 修飾子に複数の実行スレッド間の関係に関する何らかの効果を期待することは基本的にできない,という結論になります.

以上の説明を踏まえた上で,複数の実行スレッドが登場する場合について順次説明していくこととします.

(次の更新は多分1ヶ月以上後です.)

*1:厳密には ビットフィールド bit field についても説明する必要がありますがここでは省略します.

*2:非反射的で推移的であれば必ず非対称的であるため,非対称的であることを述べるために sequenced-before 関係の定義に言及することは必ずしも必要ではありません.

*3:「厳密な strict」という言葉は,非反射性のことを指しています.「厳密な」という言葉を入れずに,単に 半順序 partial order という言葉で同じ意味を指すこともあります.

*4:同じ内容を指す他の用語として 非反射的な半順序 irreflexive partial orderstrict preorder といったものがあります.

*5:筆者はハードウェアレベルの話にはあまり明るくないですが,単一の実行スレッド上でアクションが並列に実行されるというのは,例えばアーキテクチャ上の機械語の実行における instruction-level parallelism が想定されます. instruction-level parallelism に関しては,例えば "Computer Architecture, Fourth Edition: A Quantitative Approach" の2章などを参照してください.

*6:1.9/15 の example から引用.

*7:ある C++0x プログラミング言語の実装に対して,そのような変換は一般に無数に存在します.実際上は,「最適化」とはその変換の中から実行速度やプログラムサイズ等の観点から見て適当な1つを選ぶことを指す言葉になります.

*8:もちろん,実行環境によってはこれらの振る舞いもユーザの観測対象となる場合がありますが,依然として C++0x の観測可能な振る舞いではありません.