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 とかを買うべきと言うお告げだったりするのでしょうか。

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 が abort	a_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 がどのように実現されているかを簡単に見てみたいと思います。