2012年9月30日日曜日

YAPC::Asia Tokyo 2012 参加メモ

ブログ書くまでが YAPC::Asia らしいので。/.-j にしようか迷ったけど一応こちらで。

1日目、2日目で参加。1日目は新幹線が 80 分くらい遅れたため残念ながら Larry 氏のセッションは聞けず、その後から参加。YAPC 参加者は Web 界隈の人が多いんじゃないかと思っているが、そういう意味ではそもそも日常業務的に Perl どころがプログラミングも(基本)しないという点で特異な参加者な気もする(1日目は年休取得して参加)。ということで Web サービス寄りよりかは Perl 本体寄りのセッション選択、のはず。以降、各セッションの雑多なメモとか感想とか。

一日目

Acmeism, Pegex and CoffeeScript on CPAN

40 分の枠に収まらなかった感じ。もうちょいちゃんと聞きたかった。

リアルタイム通知システムの舞台裏

C++ Compiler Farm みたいなものを作っていて通知ではなくバックエンドのコンパイルサーバについてだがこの辺の管理(どのサーバに投げたか)とかどうしようというのと通ずるものがある気がした。メッセージキュー(RabitMQ)で解決したみたいだが、CCF では S3 がその位置に来そう。

Perl初心者が作ったサーバ運用ツール

英語での発表。運用ツールそのものについて自分に知見がないけど、テストがある、というのが重要なところか。ただこれ、テスト可能なように設定を綺麗に分離してやるというか、role と blueprint との関係が重要な気がする。

GitHubを使った開発とデプロイ

丁度 Perl モジュールの fork とかし始めたところだったのでそういう話なのかなと(勝手に)期待していたけどそうではなく普通にプロジェクトの中心リポジトリとして Github を使う感じだった。

Distributed Job System. Clutch

中央サーバを必要とせずクライアント側で振り分ける分散ジョブシステム、だろうか。多分構成次第? 多対多になるなら間に中央管理サーバを置いた方が楽になる気がするし、振り分け先が動的に変化するケースだと難しくなったりするんじゃないだろうか。

DBD::SQLite: Recipes, Issues, and Plans

正直一番実用的だったかもしれない。解析の仕方から考えなきゃならないデータに対してとりあえず DB に突っ込んで SQL で色々料理してみるというのはかなり強力なスキームだと思っているが、その上で SQLite は強い味方である。で、DB へのデータ投入とか SQL が苦手な処理をする時に一旦外でやろうとする場合などで DBD::SQLite はお世話になりまくりである。bulk insert は自分も prepare/分割commit/各種pragma on でやってたのでお墨付きをもらった感が。複数レコード insert は今度試してみたい。その他、DBD::SQLite ユーザーは一度軽く資料を眺めておくといいんじゃないかと思う。

Profiling memory usage of Perl applications

TreeMap によるメモリ使用量の視覚化デモが格好良かった。使われていたのは JavaScript InfoVis Toolkit だろうか。Interactive な視覚化をやるのに Javascript を使うというのは環境も(あまり)選ばないし便利な気がする。

平均レスポンスタイム50msをPerlで捌く中規模サービスの実装/運用

実際の内容についてはどうこう言えることはないのだが、前振りのアドテック業界について、が非常に分かりやすい導入だったと思う。

Perlアプリケーションのベンチマークとプロファイリング

↑のセッションでもそうだがとにかく計測すること、視覚化することがまず重要か。CCF なんかはとりあえず立ち上げてるだけなので試せるといいなぁ。

LT

相変わらずネタ満載。

二日目

「新しい」を生み出すためのWebアプリ開発とその周辺

今回のベストトーク賞受賞セッション。企画の部分は、Web アプリに限らず何か作ろうと思ってる万人に得るものがあるのではないかと。実装については枯れたものを使えば十分というあたり? 11月末~12月発売予定という「Webサービスのつくり方」は期待大。

Padre - The Perl IDE for Normal People

Emacs ユーザーと Vim ユーザーが聴取者の大半というのが印象的。自分も Emacs も Vim もプログラミングに使わないけど IDE も(ほとんど)使わないという点で Normal People からは外れてるわけだけど。Perl ユーザーが拡張とかしやすいのは Perl で書かれた IDE というのはそうかもしれないけど Perl のコアユーザー層が IDE 使ってないわけで。Eclipse なんかは企業からの後押しが大きかったわけだし、一般ユーザー層への拡大の需要というかそういうのがないと難しいかもしれない。

Perl 今昔物語

日記をさらってみたところ自分は 2008 が初参加の模様。この手のイベント自体が初参加だった。2010 は 2 日目だけ参加、2011 はキャンセル(海外出張)。参加してない部分のタイムテーブルを見ると聞いときゃ良かったというのが結構ある。今後はもう少し参加に貪欲になってもいいかもしれない。内容としてはPerl で書く必然性が薄れてきた、みたいなことを言われていたのが印象的だった。他のセッションの内容にもその辺が出てきているような気がする。

Perl と SQL のいろいろ

DBI/DBD についての分かりやすいチュートリアル。周辺モジュールの簡単な紹介もあって参考になった。質問タイムでプレースホルダの強制ができないんで O/R マッパー使ってるみたいなコメントがあって、プレースホルダの使用くらいプログラマとして最低限度の常識じゃないのかと思ったけど現実はそうもいかないんだろうなぁというのが悲しいところ。

シリコンバレーと世界のPerlエンジニア

川崎さんがアクティブ過ぎて眩しい。「10年後に食える仕事 食えない仕事」から引用されてた「グローカル」「ジャパンプレミアム」「無国籍ジャングル」「重力の世界」っていうのは興味深い。元々の本だとプログラマは「重力の世界」みたいだけど日本の適当な開発要求とのブリッジングという位置では立ち位置はありそう。それはそれでしんどそうだけど。

Perlで始める!初めての機械学習の学習

メモ見たら PRML 同人誌とだけ書いてあったw。とりあえず手に入れたいと思う。perl-kinect は面白そうなので公開されないかなぁ。

Perl入学式をやってみた!

期待していなかったのだが(ごめんなさい)、熱い思いを感じられるいいセッションだったと思う。「ハードルを下げることを重視する」「継続して参加できる環境を作る」というのは他のイベント主催の人も参考にできるかもしれないが、このレベルまで頑張るのは相当大変なことだと思う。あと、Perl 入学式参加者の Perl のわかりにくかったところとして、リファレンス(-> が省略できる場合がある)、コンテキストの概念、ファイルハンドルの , の省略、辺りが挙がってたのはそうだよなぁ、と思わざるを得ない。慣れてくると大丈夫だし逆に楽に書ける要因になったりもするんだけど、場合に応じてうまい具合に挙動が変わる、は、むしろ初めての人にはわかりにくい、と。

Performance Profiling with Devel::NYTProf

他のセッションでも言われていたけど、まず計測しろ、と。あと、目標達成したらそれ以上余計な事しない。局所的な変更から積み上げる。

LT

相変わらずネタ満載。

How Perl Changed My Life & Closing

総括感想も含めて。なんだろう、所詮 Perl はプログラミング言語の一つな訳だけど、TMTOWTDI に代表されるその精神というかそういうのがコミュニティにも有ってそれだけ懐が深いというか、Closing で牧さんが the most welcoming conference みたいなこと書いてたけどそういうのが有るんじゃないかな、と。忘れていたけど自分としては初参加のイベントが YAPC::Asia 2008 だった訳で、そこから色々参加(だけは)するようになったのを考えるとそれなりに大きな転機だったのかもしれないとも思う。そういう意味で Perl ってのは自分の中で結構大きい割合を占めているかもしれない。実際「Perl は生活、C++ は趣味」という感じで技術ネタは C++ が多いけど実際書いてたり日常使ってるものは Perl の方が多かったりするし。今現時点で Perl を選ぶ理由ってのはそんなにないのかもしれないけど、でも自分は Perl が好きなんだなぁ、と思う。で、スピーカーの人にはせっかくの YAPC なので別に Perl べったりの内容にする必要はないと思うんだけどもう少し Perl 寄りの発表をして欲しいなぁという気持ちもあったり。まぁとにかく来年も参加したいと思う。

2012年9月8日土曜日

小ネタ: Perl の警告: Deep recursion on subroutine ...

Perl では再帰呼び出しのネストが深いと警告してくれる機能がある。定石的に use strict; use warnings; していれば有効になっている。

use warnings;
sub dfs {
    if($_[0] < 101) { dfs($_[0]+1); }
}
dfs(0);
Deep recursion on subroutine "main::dfs" at ... line 3.

perldiag には "unless you're writing strange benchmark programs, in which case it indicates something else." などと書いてあったりするのだが、閾値が 100 であるためちょっと大きめのグラフに対して再帰で DFS かけたりしたら余裕で突破したりするのである。警告を抑制したい場合、Perl の警告はカテゴリ分けされているため再帰に関する警告だけオフにしてやればいい。

use warnings;
no warnings 'recursion';
sub dfs {
    if($_[0] < 101) { dfs($_[0]+1); }
}
dfs(0);

が、これだと全体で警告がオフになってしまう。Perl の警告制御は lexical scope である。これは限定した部分で警告をオン・オフできるということだが、

use warnings;
sub dfs {
    if($_[0] < 101) {
        no warnings 'recursion';
        dfs($_[0]+1);
    } # End of the effect of no warnings
}
dfs(0);

もう一つ、dynamic scope ではない、ということも意味している。つまり、以下では警告は抑制されない。

use warnings;
sub dfs {
    if($_[0] < 101) {
        dfs($_[0]+1);
    }
}
no warnings 'recursion';
dfs(0);

実際に deep recursion が発生するのは dfs(0); の実行中じゃないかと思ってしまうのだが、字面上(lexical)は 4 行目の dfs 呼び出しで発生するからだ。

2012年9月4日火曜日

Variadic Template にまつわる Workaround

C++11 は確かに便利、なのだが現状はまだ実装が十分と言えず回避手段(workaround)を取らざるを得ない場合がある。の割には余りそういう説明を見ない、ということでせっかく書いたのでメモってみる。まぁ Boost のソースコードの中にたくさん埋まっているのだろうし、ひょっとしたら C++er は息をするように workaround が書ける人種なのかもしれないが、そこはそれ。

sorry, unimplemented: use of ‘type_pack_expansion’ in template

#include <utility>
struct B { int operator()(int n) const { return n; } };

template<typename C>
struct A {

#if __GNUC__ == 4 && (__GNUC_MINOR__ <= 5 || __GNUC_MINOR__ == 6 && __GNUC_PATCHLEVEL__ == 0)

  template<typename ... Args>
  struct deduce {
      typedef decltype(C()(std::declval<Args&&>()...)) type;
  };
  template<typename ... Args>
  typename deduce<Args...>::type operator()(Args && ... args) const
  { return C()(std::forward<Args>(args)...); }

#else

  template<typename ... Args>
// sorry, unimplemented: use of ‘type_pack_expansion’ in template
// http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48292
  auto operator()(Args && ... args) const -> decltype(C()(std::forward<Args>(args)...))
  { return C()(std::forward<Args>(args)...); }

#endif
};

このエラーメッセージが出るのは恐らくこの場合には限らないと思うのだが、type pack (Args ... みたいな展開)を tailing return type 中で使った場合。GCC bugzilla にも書いてある通り、別のクラスに切り出すことで回避できる。@iorate さんの記事([C++][Boost] C++ で一般化された on を書く)にも workaround の方法を含め書かれている。後は、GCC 4.6.1 から直っている、という情報くらいだろうか。

sorry, unimplemented: cannot expand ‘Args ...’ into a fixed-length argument list

#include <boost/fusion/include/vector.hpp>

#include <boost/fusion/adapted/mpl.hpp>
#include <boost/fusion/include/as_vector.hpp>
#include "variadic_bridge.hpp"

template<typename ... Args>
struct C {

#if __GNUC__ == 4 && __GNUC_MINOR__ <= 6

  typename boost::fusion::result_of::as_vector<
    typename yak::util::variadic_to_vector<Args...>::type
  >::type v;

#else

// sorry, unimplemented: cannot expand ‘Args ...’ into a fixed-length argument list
// http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39653
  boost::fusion::vector<Args...> v;

#endif
};

こっちはエラーメッセージを日本語対象でググっても合っているものは tweet 1件しかヒットしない。……みんな困ってそうなものなのだが。variadic な template parameter を非 variadic な template に渡せない、というものだ。自作ヘルパ variadic_bridge.hpp を使って variadic な template parameter を MPL vector に変換して、さらに boost::fusion::vector に変換している。まぁ MPL vector まで持って来られれば後はどうとでもなるとは思うが、一応、固定長引数として Metafunction Class に渡す variadic_to_fixed も用意はしてある。こっちは GCC 4.7.0 から修正。

まとめ?

そもそも VC は 2012 でも variadic template 対応してねーよ、という時点で PP するしかないという話なのが悲しいところ。

しかし、CSS はブラウザバグとその対処、みたいなものが結構見つかるのだが C++ についてはそういうまとめみたいなものはないのだろうか。

2012年9月2日日曜日

(今更) C++ で拡張メソッド

Transactional Memory について予告をしておきながら別ネタ。何で実装しようと思ったのかそのきっかけを忘れてしまっているが、今更 C++ で拡張メソッドである。func(a, x) のようにメンバ関数外のものが a.func(x) で呼べるというやつである。まぁ、「今更」というくらいであって既にやってる方は色々いるわけだが。@cpp_akira (faith_and_brave) さん (2008年)、じくよろさん(でいいのだろうか?)(2009年)、@gim_kondo さん(2011年)などが作られているわけである。

もちろん C++ 自体には拡張メソッドは存在しないのでそれっぽいものを実現する仕組みを自前で作ることになるのだが、基本的に C++ で拡張メソッド風なものを実装しようとした場合、拡張するメソッド(関数)以外に大体 3 つの構成要素が必要だと思われる。

  1. 対象のオブジェクト、あるいは、引数を保持するオブジェクト(以下ラッパと表記)
  2. 上記ラッパを作成、値を紐付けする仕組み(以下ラッパ束縛と表記)
  3. 紐付けされなかった方と結びつけて実際の呼び出しを行う仕組み(以下ラッパ呼び出しと表記)

これで先の方の実装について整理するとこんな感じだろうか。じくよろさんの実装は最終的にフリー関数へ転送しているが「func(a, x) を」という形式に拘らなければ関数オブジェクト内でそのまま拡張メソッドの内容を実装してしまえばいいのでそのように実装した場合として記述している。

実装ラッパラッパ束縛ラッパ呼び出し
@cpp_akira さん拡張メソッドの内容を表す関数オブジェクト内に引数も保持コンストラクタoperator| のオーバーロード(任意の1引数関数オブジェクトを受ける)
じくよろさん拡張メソッドの内容を表す関数オブジェクト内に引数も保持コンストラクタoperator, のオーバーロード(関数オブジェクト限定)
@gim_kondo さん拡張メソッドの内容を表す関数オブジェクト内に対象オブジェクトへの this ポインタを保持対象オブジェクトへのメンバテンプレート埋め込みとマクロ置換によるコンストラクタ呼び出し関数オブジェクトの呼び出し

@gim_kondo さんの実装は . (ドット演算子)で呼び出せるようになっているが拡張メソッド呼び出し側でのマクロ置換発生は代償としてちょっと evil だと思われる。この判断をした時点で基本的に演算子オーバーロードで実装ということになるのだが、今回選んだ演算子は ->* である。ほとんどの C++er は使ったことがないだろうと思われる、というかひょっとしたら存在を知ってる人すら少ないかもしれない。通常の使い方は以下のような形である。

struct A { void func(void) {} };

int main(void)
{
 void (A::*mp)(void) = &A::func;
 A a, *pa = &a;
 (pa->*mp)();
 return 0;
}

つまりメンバないしメンバ関数へのポインタを参照するためのものである。とりあえず括弧の付け方に注意。知らないとまず間違えると思う。とりあえずこれがなくて困るとは普通ならない(そもそも普通の使い方ならポインタに対して使う)し、メンバアクセスのための演算子なので拡張メソッドとしては意味は近いはず、ということから選定。

で、拡張メソッド的なものが作れるというのは分かっている上でなぜまた(特に需要もないのに)別に作るのか。↑で書いたとおり、C++ で拡張メソッドを作ろうとすると本来の拡張メソッドだけでなく他の仕組みも必要になるわけでそれが面倒い。できるだけ拡張メソッド本体以外の余計な部分は勝手に作成させたい。で作ってみたのがこんな感じ。内部実装は https://github.com/yak1ex/cpp_stuff/blob/master/extender.hpp にある。

#include <iostream>
#include "extender.hpp"

namespace test { struct A { int n; }; }

namespace ext {

DEFINE_EXTENDER1(test::A, func1, {
 typedef test::A& result_type; // MUST follow result_of protocol

 result_type operator()(test::A& a, int &n) const {
  std::cout << "int&" << std::endl;
  return a;
 }
 result_type operator()(test::A& a, const int &n) const {
  std::cout << "const int&" << std::endl;
  return a;
 }
});

DEFINE_EXTENDER2(test::A, func2, {
 typedef test::A& result_type; // MUST follow result_of protocol

 result_type operator()(test::A& a, int &n) const {
  std::cout << "int&" << std::endl;
  return a;
 }
 result_type operator()(test::A& a, const int &n) const {
  std::cout << "const int&" << std::endl;
  return a;
 }
});

}

int main(void) {
 using ext::func1;
 using ext::func2;

 test::A a = { 0 }; int n = 0;

 ((a->*func1)(1)->*func1)(n); // Cascading but unintuitive

// NOTE: different from ordinary operator semantics/precedence
 a->*func2(1)->*func2(n);

 return 0;
}

実行結果

const int&
int&
const int&
int&

g++ 4.[5678] それぞれで -std=c++0x 有無両方で動作を確認している(いくつか workaround も入っている)。通常の演算子の優先順位の意味論に従ったのが EXTENDER1 の方、使いやすさを優先したのが EXTENDER2。まぁ普通は EXTENDER2 の方だと思う。使う側としてはほぼ書きたい拡張メソッドの内容部分のみだけで実現できている、と言っていいと思う。マクロにしてあるが↓なので直書きでもそんなに変わらない。なお、上記の例では 1 引数同士で const の違いだけでオーバーロードしているが、任意の型で引数の数が違っている場合でもそのまま operator() を書けばオーバーロード可能である。

#define DEFINE_EXTENDER1(target, name, ...) \
struct BOOST_PP_CAT(name, _functor) : public yak::util::extender1<BOOST_PP_CAT(name, _functor), target> \
__VA_ARGS__ name
#define DEFINE_EXTENDER2(target, name, ...) \
struct BOOST_PP_CAT(name, _functor) : public yak::util::extender2<BOOST_PP_CAT(name, _functor), target> \
{ \
 struct _ __VA_ARGS__; \
} name

内部実装について簡単に説明すると、CRTP + Barton Nackman trick を使ってラッパと演算子を定義している形。上表と同じ形で書くと次のようになる。

実装ラッパラッパ束縛ラッパ呼び出し
EXTENDER1拡張メソッドの内容を表す関数オブジェクト内に対象オブジェクトも保持operator->* のオーバーロードで関数オブジェクトを返す関数オブジェクトの呼び出し
EXTENDER2引数を保持するオブジェクトを関数オブジェクトと別に用意operator() のオーバーロードでラッパを返すoperator->* のオーバーロード(ラッパ限定)

2012年8月4日土曜日

LL Decade 「君ならどう書く Online」 で書いたコード

本日(8/4)開催された、LL Decade では「君ならどう書く Online」という企画がありました(問題の内容はリンク先参照)。14:00 までという短い時間と告知がそれほど強いものではなかったこともあってか参加者は 14 名(+締め切り以降10名)(間違ってるかも)だったそうですが、おかげで商品をゲットすることが出来ました。問題発表前は C++ Template Meta Programming で書いて「コンパイルの必要もない Lightweight です(キリッ」とかやろうかと思ったのですが、文字列の validation ということで断念しました。で、順当に Perl で書いた訳ですがせっかくこういう場で書くんだから多少のひねりが欲しいところです。という訳で書いたのが以下のコード。文字列処理ということで正規表現さんにお出まし願ったわけですが、普段使わない機能を使ってみました。

#!/usr/bin/perl

# regexp 内でそれなりに頑張る

use utf8;
use strict;
use warnings;

local $/; # slurp
my $t = <STDIN>;
$t =~ s/^(
   (?<ipv4>(?&ipv4_))|
   (?<ipv6>(?&ipv6_))|
   (?<mac>(?&mac_))|
   (?<any>.*)
  )$
  |(?<spc>\s+)
  (?(DEFINE)
   (?<ipv4_1>1[0-9]{2}|2([0-4][0-9]|5[0-5])|[1-9]?[0-9])
   (?<ipv4_>(?:(?&ipv4_1)\.){3}(?&ipv4_1))
   (?<ipv6_1>[1-9a-fA-F][0-9a-fA-F]{0,3}|0)
   (?<ipv6_>(?:(?&ipv6_1):){7}(?&ipv6_1))
   (?<mac_1>[0-9a-fA-F]{2})
   (?<mac_>(?:(?&mac_1):){5}(?&mac_1)|(?:(?&mac_1)-){5}(?&mac_1)) # 格好悪い。backreference でいける?
  )/@{{
   ipv4 => '01',
   ipv6 => '10',
   mac => '00',
   any => '11',
   spc => '',
  }}{keys %+}/mxge;

print pack('B*', $t);

9,10 行目は Perl5 だと悲しい slurp。以降の(一応一つの)正規表現で 0 と 1 の文字列に変換してから pack() で普通の文字列に復元という流れになっています。18行目からの (?(DEFINE) で始まっている部分は正規表現パターンに対して名前を付けている部分です。(?<name>pattern) で pattern に対して name という名前を付け、(?&name) で呼び出している訳です。hoge_1 になっているのがアドレス構成要素 1 要素分、hoge_ になっているのがアドレス全体に対するパターンです。これを (?<name>pattern) で hoge として名前付きキャプチャしています(12行目から)。名前付きキャプチャの結果はハッシュ %+ に設定されるので、keys を使って有効なキャプチャ名(hoge)を取得し、ハッシュで値を置き換えています(25行目)。keys をリストコンテキストで評価したいので(ハッシュリテラルに対する)ハッシュスライスを使っています。わざわざハッシュリテラルを使っているのはその方がなんか格好良さそうだからです。spc 関連は改行削除用のものです。正規表現のオプションとしては、複数行に ^$ をマッチさせるための m、空白等を入れるための x、全体を置き換えるための g、eval するための e を指定しています。こうして変換した後は pack を使って変換して出力するだけです。

perlre とか見ながら即席で書いたにしてはなかなか面白みのあるコードに仕上がったんじゃないかと思います。IP アドレス等にマッチする正規表現そのものがあんまりいけてない感じなのがちょっと残念なところですが。もっと格好良い書き方がある気がします。

ちなみにもらった商品は、iOS プログラミング第2版(ISBN978-4-86401-049-8) なのですが、Mac 持ってないんですよね。iPad も会社支給(貸与)された今、MBP とかを買うべきと言うお告げだったりするのでしょうか。

2012年8月1日水曜日

A bit inside of Transactional Language Constructs for C++ - part.2 Intel TM ABI

前回 Part.1 では、Transactional Language Constructs for C++ (以下 TM 提案)について Atomic transaction の記述「他のスレッドが transaction の中間結果を観測しない」が、どのようなからくりになっているかを説明しました。Part.2 では、TM 提案と対とも言える文書、Intel TM ABI specification を元にコンパイラがどのように C++ TM を実現しようとするかについて覗いてみたいと思います。

TM 提案を実装しているコンパイラはいくつかありますが Intel によるプロトタイプ実装 Intel C++ STM Compiler, Prototype Edition というものがあります。Intel TM ABI とはこの実装で使用されている ABI です。元々 TM 提案は何が実現されるか(what)についてだけ規定しておりどのように実装するか(how)については規定していません。これはソフトウェア、ハードウェア、ハイブリッドといった区分を含め様々な TM 実装を利用できるようにするためです。コンパイラの実装としてもこの方針に則っており、Tntel TM ABI に則ったライブラリ(libitm)を差し替えることで実装を切り替えられるようになっています。GCC 4.7 以降も TM 提案を試験的に実装していますが、同様に Intel TM ABI に則ったライブラリ(正確には特に例外周りで変更があるみたいですが)への呼び出しに変換されて実現されます。

さて、では TM 提案 に則ったコードをコンパイラがどのように libitm への呼び出しに変換するのかを見てみましょう。以下は TM ABI の例を一部改変しています。

int s;
[[transaction_safe]] int f(int);
void foo(void)
{
  int i;
  for (i=0;i<10;i++)
  {
    __transaction_atomic {
      s += f(i);
      if (s > 1000) __transaction_cancel;
    }
  }
}

このコードは(例外関係を無視し効率を考えないとして)例えば次のようなコードに変換されます。

int s;
int f(int);
static _ITM_srcLocation start_outer_loc = {…};
static _ITM_srcLocation commit_outer_loc = {…};
static _ITM_srcLocation abort_loc = {…};
void foo(void)
{
  _ITM_transaction * td = _ITM_getTransaction();
  for (i=0;i<10;i++) {
    int doWhat = _ITM_beginTransaction (td,pr_instrumentedCode | &start_outer_loc);
    if (doWhat & a_restoreLiveVariables) {
      /* TM 化していない有効なローカル変数を復元する */
    }
    if (doWhat & a_abortTransaction) goto txn1_abort_label;
    if ((doWhat & a_saveLiveVariables)) {
      /* TM 化しない有効なローカル変数を保存する */
    }
    int sval = (int)_ITM_RU4 (td, (uint32 *)&s);
    sval += f_@TXN(i); // TM 化された関数 f の呼び出し
    _ITM_WaRU4 (td, (uint32 *)&s, (unit32_t)sval);
    if (sval > 1000)
      _ITM_abortTransaction(td,userAbort,&abort_loc);
    _ITM_commitTransaction(td,commit_outer_loc);
    txn1_abort_label:
  }
  return;
}

以下では _ITM_ を省略して記述します。srcLocation 関連はデバッグ情報みたいなもので無視して構いません。"instrumented" という表現は TM 対応化された、くらいの意味に取ればいいと思われます。では、簡単に流れに沿って説明してみましょう。

  • まず最初に getTransaction() で transaction descriptor を取得しています。以下の libitm 関数呼び出しで共通して渡されている情報です。内部に libitm で必要な情報が格納されているわけですが、結局は実質スレッドに紐付け可能なわけで libitm 側で管理すればいいんじゃね?という話はあります。この辺りも簡単に ABI spec 3.8 節に触れられており、また、実際 GCC の場合は td が存在しないコードになります。特に本筋に大きな影響はないので spec の記載通りで書いています。
  • beginTransaction() によって transaction を開始します。これは内部的に setjmp() と同じような処理を含んでおり、commit に失敗した場合や abort された場合に(longjmpと同様の処理が行われ)再びこの関数から戻ってきます。戻り値は次にどのような処理を行うべきか、です。前述の通り abort した場合などもこの関数から戻ってくるためどのような処理をするか戻り値から判別しなければなりません。下表で再実行となっているのは commit に失敗した場合の transaction 再実行です。取り消し不可能云々は本稿では説明しません。さしあたって無視してもらっても大筋は成立します。
    transaction 開始時
    状況戻り値
    直列で取り消し不可能な transaction (serial irrevocable transaction)を開始
    a_runUninstrumentedCode
    transaction 開始a_saveLiveVariables | a_runInstrumentedCode
    transaction 再実行a_restoreLiveVariables | a_runInstrumentedCode
    直列で取り消し不可能な transaction として transaction 再実行(モード変更)a_restoreLiveVariables | a_runUninstrumentedCode
    取り消し不可能な transaction として transaction を開始a_runInstrumentedCode
    transaction 終了時
    状況戻り値
    transaction が aborta_restoreLiveVariables | a_abortTransaction
  • a_restoreLiveVariables と a_saveLiveVariables はローカル変数に対するものです。libitm に渡して TM 化する場合オーバーヘッドがかかるため TM 化する変数アクセスは当然出来るだけ絞りたいわけです。transaction 中であればローカル変数は自分のスレッドからしか有効にアクセスできません。ということでローカル変数について保存・復帰によって対処しようというものがこれらのフラグとそれに対応する処理となります。
  • abort された場合は、a_abortTransaction が返ってくるので(a_restoreLiveVariables によってローカル変数の復帰済み)、以降の transaction 関連コードをスキップします。
  • RU4() だとか WaRU4() が実際に TM 化するためのメモリアクセスの置き換えです。最初の R or W が読み書きの区別、最後が型です(この場合は U4)。途中の aR 等は読み込みの後(after Read)等の意味を持ち、状況に応じて不要な処理を省くといったことを実現するために分けられています。
  • f_@TXN は関数 f() の TM 化バージョンという表記です。実際にはコンパイラによって変わってくるでしょう。transaction 中であるかを判別する inTransaction() という関数もあるのでそれを使って関数内で切り替えることも可能だと思いますが、恐らくはゼロオーバーヘッドを考慮して 2 バージョン用意する形を想定して書かれているのだと思います。
  • abortTransaction() はそのまま transaction の abort で前述のように beginTransaction() の場所に戻ります。
  • commitTransaction() もそのまま transaction の commit です。commit に失敗した場合、前述のように beginTransaction() に戻って transaction が再実行されます。

さて、どうでしょうか? まだ libitm の中まで見ていませんが、begin, abort, commit があって変数アクセスが置き換えられているということから(単一グローバルロックでなくとも)、Transactional Memory が実現できそうかなという感じがするんじゃないでしょうか? part.3 では libitm 実装の一つである RSTM を参考にして TM がどのように実現されているかを簡単に見てみたいと思います。

2012年7月31日火曜日

A bit inside of Transactional Language Constructs for C++ - part.1 Atomic transaction

Boost.勉強会 #10 にて @yohhoy さんが Transactional Language Constructs for C++ (C++ における Transactional Memory 拡張)について発表 されました。丁度自分も提案文書を読んでいるところであり Transactional Memory (以下 TM)というか並列プログラミング全般について知識がないので勉強会駆動の発表ネタになるかなと思っていたところだったので非常にタイムリーでした。発表内容としては現在提案されている TM 拡張の syntax と semantics についての説明で、実装については対象外だったわけですが(もともと提案文書には実装については含まれていない)、その発表の中で

  • (Atomic Transaction で、他の transaction だけでなく)他のスレッドに途中状態を見せないってどう実現するのか分からない

というコメントがありました(多分)。その時は、ピンと来なかったのですが色々調べたりするうちにその感覚が分かってきました。その心は

  • ゼロオーバーヘッドか?(TM 有効にしても実際に TM を使用しなければオーバーヘッドはないか?)

という質問にも通じます。私は TM 拡張は基本的に transaction 内部のコードだけ変更すればいいと考えていたので実行時にはほぼゼロオーバーヘッドだと思っていたのですが、(transaction 外の)他のスレッドにも途中状態を見せないということは transaction 外のコードに対しても何かガードなりを設ける必要があるのではないか?という懸念があった訳です。

が、なんというか「確かに嘘は書いてないんだけどさぁ」という解釈が可能であることに気付きましたので、本稿ではそのことについて書いてみます。

さて、提案文書では Atomic transaction について以下のように書かれています。

In a data-race-free program, an atomic transaction appears to execute atomically; that is, the compound statement appears to execute as a single indivisible operation whose operations do not interleave with the operations of other threads.
データ競合がないプログラムでは、atomic transaction はアトミックに実行される。(atomic transaction として指定された)複文は他のスレッドの操作とインターリーブされない単一の分割不可能な操作として実行される。

さて、ここでどうしても後半に意識がいってしまうわけですが、この文章で最も重要なのは最初の部分 "In a data-race-free program" です(appear であることも多分重要)。

data-race-free とは何かについては TM 提案の最初の方にも簡単に触れられています。C++11 では 1 スレッド内の実行順序について "sequenced before" という関係で順序が定められているものがあります。またスレッド間の実行順序について "synchronized with" という関係で順序が定められているものがあります。これらをもとに "happens before" という関係が定められています(厳密にはもうちょっと複雑)。

  • A is sequenced before B → A happens before B
  • A synchronizes with B → A happens before B
  • A happens before B ∧ B happens before C → A happens before C

そして、あるメモリ領域に対する書き込み操作と、別の読み込み操作あるいは書き込み操作が同じメモリ領域に対して行われている時、これらを conflict と称します。以上を元に data race (データ競合) は、次のように規定されています。

The execution of a program contains a data race if it contains two conflicting 2 operations in different threads, at least one of which is not an atomic operation, and neither happens before the other.
異なるスレッドの 2 つの操作が conflict しており、"happens before" の関係になく、かつ、少なくとも一方は atomic ではない場合、data race が発生している。

要するに、「同一メモリ領域に対する書き込みと、読み込みないし書き込み」(=conflict)について順番が定められていないケースを data-race と呼んでいる訳です。

さて、transaction 間については、ある transaction の終了と別の transaction の開始には "synchronized with" の関係があるとされ、実行がインターリーブしません。従って、transaction 間では data-race は発生しません。では、transaction と transaction 外ではどうなるでしょうか?

atomic transaction はロックや atomic など他の同期機構を含むことができません。このため、transaction 内のコードと transaction 外のコードについて "synchronized with" 関係が発生しません。この状況下で data-race-free、つまり順序不定な conflict が存在しないためには、

  1. 同一スレッド内で sequenced before 関係にあるか、
  2. そもそも conflict が存在しないか、
  3. 別の transaction 内に存在しているか、

のいずれかである必要があります。結果として別スレッドの transaction 外のコードは transaction の途中状態を見ることがありません。この場合、2 しか有り得ず、そもそも transaction が変更するメモリ領域に対するアクセス、conflict が存在しない訳ですから。

つまり、atomic transaction において他のスレッドが transaction の途中状態を見ないというのは atomic transaction によって保証されているというよりは、その前提、data-race-free なプログラムである、というところに依るところが大きいと言えます。data-race-free であることはプログラマが保証してやらねばなりません。一番簡単なのは conflict があるところを transaction で囲むことでしょう。この場合、atomic transaction である必要はありません(transaction 間であれば relaxed transaction でも順序が規定されるので)。

本記事では A bit inside of Transactional Language Constructs for C++ part.1 として TM 提案 での atomic transaction の記述の解釈について書いてみました。心づもりとしては part.2 では TM 提案の対とも言える文書、Intel TM ABI を元にコンパイラがどのように C++ TM を実現しようとするかについての概要、part.3 では Intel TM ABI を実装しているライブラリ RSTM の実装を簡単に覗いてみたいと思っています。