Apacheのアクセスログを使い、ユーザアクセスの集計やパターン解析などというのは一般にどこでもやられていることだと思います。通常のアクセスログはテキストファイルなので、集計を行うためにスクリプト上で扱える変数・オブジェクト化が必要になりますね。1行ごとの各ログ項目を取り出すのに正規表現を使ったり、cutやawkなどを使い空白で分割するなど、色々工夫されていることと思います。

今回、MessagePack版のアクセスログ出力をやってみようと思い立ったのは、アクセスログをあらかじめ構造化済みの状態で保存しておければ、読み込みの際の解析する手間を省くことで解析処理の高速化が期待できるのではないか、そう考えたためです。MessagePackであれば、PythonやRubyはじめ様々なスクリプト言語でのバインディングを備えており、取り扱いも簡単ですから、ファイル読み込みからログデータの取り出しまでを速やかに行い、その分集計処理の実装に集中することができるわけです。また、時折イレギュラー的に長かったり、予期しない文字がリクエストに入る等したためにログ解析の正規表現がエラーになったりすることがありますが、構造化済みの形式で保存するのであれば、この問題も回避できます。

何より、元々構造化されたデータがアクセスログ上では一度文字列になり、これを解析する時に再 度解釈処理されるという二度手間になっているわけで、テキストデータ化せずデータ構造を保った バイナリとしておくのはこの手間を回避する目的も持っています。

ソースはこちらです。
→http://log.blog.klab.org/support/mod_log_msgpack/mod_log_msgpack-0.1.0.tar.gz

それでは、実際にどのような変更を加えたのでしょうか。モジュールの中身を見てみましょう。

mod_log_msgpackは、従来型のログ出力モジュールであるmod_log_configからその多くを受け継いでいます。mod_log_configの構造がそのまま、mod_log_msgpackにも当てはまるとお考えください。

mod_log_configは、起動直後にLogFormatで定義された書式文字列を読み込み、アクセスログに出力する一行分の内容を定義します。例えば、

LogFormat "%h %l %u %t \"%r\" %>s %b \"%{Referer}i\" \"%{User-agent}i\"" combined

このようなログ書式の指定があったとします。mod_log_configは、このディレクティブを解釈して下記のような内部的なデータ構造に分解して落とすのです。http: //httpd.apache.org/docs/2.2/ja/mod/mod_log_config.html#formats を参考にしながら、当てはめてみるとこうなります。

このように、%?の箇所とそれ以外(空白等、置き換えない文字列)とでそれぞれ区切り、小片に分けられます。%で始まる項目は対応するコールバック関数を通し、指定のリクエスト情報を文字列に変換します。つまり、リクエスト情報は一旦LogFormatの項目数分(今回18個)の部分文字列に変換され、最後にこれらをすべて連結してログ1行分として出力しています。

mod_log_msgpackではこの部分を利用、アクセスログ1行をMessagePackのarray1個として置き換えて下記の項目のみ保持することとしました。

つまり、用があるのは%?の項目のみということにして、それ以外の固定文字列に関しては無視して います。%rや%iについていた「"」での囲みも、項目の内容が空白を含みうることを想定して区切 りとしての空白と区別がつかなくなることを回避するためのものなので、arrayとして分割できて あれば、不要なものとなるわけです。

さらに、これらのコールバック関数はrequest_rec構造体(と、%{…}?となったときの{}の中身)を引数にとり、部分文字列を返値とするわけですが、msgpack_packer構造体を渡す引数を1つ追加、ここにログの内容を順次packしていく処理に切り替えています。

static const char *log_remote_host(request_rec *r, char *a)
{
    return ap_escape_logitem(r->pool, ap_get_remote_host(r->connection,
                                                         r->per_dir_config,
                                                         REMOTE_NAME, NULL));
}

こちらが元々のmod_log_config版。"%h"に対応するコールバックです。mod_log_msgpackになりま すと下のように変更になりました。

static int _strpack(const char* s, msgpack_packer* pk)
{
    if (s) {
        size_t n = strlen(s);
        msgpack_pack_raw(pk, n);
        msgpack_pack_raw_body(pk, s, n);
    } else {
        msgpack_pack_nil(pk);
    }
    return 0;
}

static int log_remote_host(request_rec *r, char *a, msgpack_packer* pk)
{
    const char* str = ap_escape_logitem(r->pool, ap_get_remote_host(r->connection,
                                        r->per_dir_config,
                                        REMOTE_NAME, NULL));
    return _strpack(str, pk);
}

log_remot_host()の第3引数が追加され、msgpack_pack_xxxの関数が呼び出されていることが確 認できると思います。

あとはここまでログ内容を集めたmsgpack_packer構造体を、ファイルに書き出す関数 apr_file_write()に渡して書き出しを行います。渡す際、mod_log_msgpackであれば行っている部分文字列の連結の箇所がありますが、mod_log_msgpackでは不要なので省略しています。

static apr_status_t ap_default_log_writer( request_rec *r,
                           void *handle,
                           const char **strs,
                           int *strl,
                           int nelts,
                           apr_size_t len)

{
    char *str;
    char *s;
    int i;
    apr_status_t rv;

#if 0
    // ここから、部分文字列の連結になるので
    str = apr_palloc(r->pool, len + 1);

    for (i = 0, s = str; i < nelts; ++i) {
        memcpy(s, strs[i], strl[i]);
        s += strl[i];
    }
    // ここまでスキップ。
#else
    str = *strs;
#endif

    rv = apr_file_write((apr_file_t*)handle, str, &len);

    return rv;
}

おおよその変更の概要は以上です。あとは、mod_log_configとの併存を可能にするためにいくつか細かい変更を加えていますが、次回以降に続くということで^^;。

通常、Apacheのログは動作サーバ上のローカルファイルとして出力されるので、 Webサーバを同時に何台も稼働させて負荷分散を行うような環境では、それらすべ てのWebサーバのログファイルを集めなければなりません。ローカルファイルとし て出力されるということは、Webサーバの台数分だけログファイルがばらけること を意味します。考えるだけでめんどくさいですね。

KLabでは、このApacheログを2パターンを使い分けて集めています。ひとつは syslogによるリモート出力を使い、全Webサーバからのログ出力を一か所に集中さ せる方法です。これは、CustomLogディレクティブにloggerコマンドを使用するこ とで可能です。

    CustomLog "|/usr/bin/logger -p local6.info --" (書式文字列)

これにより、通常ファイル出力されるアクセスログをloggerコマンド経由でsyslog に渡すことができます。あとはsyslogの設定で、リモートのログ集積サーバに集め させるというわけです。

ただし、これには問題もあります。syslogのログ転送はUDPやバッファリングなど の関係で取りこぼしがどうしても発生してしまう点です。いくつか対策は考えられ ますが、私たちはこれに従来型のファイル出力のログを併用することで解決してい ます。これが2パターンの2つめで、すなわち従来のように各Webサーバ上で出力す るログファイルを日次バッチで集積するという方法です。詳細なログ解析などはこ の日次の集積バッチによるログファイルを使用し、その日その日の緊急のアクセス 確認などはsyslog出力の側を見る、という使い分けを行っているのです。

さて、このsyslog出力について、もう一度CustomLogを確認します。loggerコマン ドへのパイプを用いていますので、httpdの子プロセスとしてloggerプロセスが多 数立ち上がることになります。

しかしふと考えてみると、syslogに送るって言ってもやることはsyslog()関数を 呼ぶくらい(他にもopenlog()とかありますが)なので、わざわざ外部プロセスにし なくても、Apache本体から出力できたっていいよね、と考えたわけです。

ということで、Apacheから直接syslogにアクセスログを出力するためのApacheモ ジュールを一つ作ってみました。

mod_syslog-0.1.0.tar.gz

syslogに送る設定は、以下のようにCustomLogを変更して行います。

    CustomLog syslog:foo (書式文字列)

"syslog:"をプレフィックスとして付加することで、mod_syslogがsyslogへの出力 であることを判別して処理を行いますが、パイプやファイルパス形式、つまり "syslog:"が付かない場合は引き続き従来と同じ処理が行われます。

mod_syslogのやることは至ってシンプルです。Apacheは、ログ出力処理のための関 数2つを下に表わすように定義しています。

  static ap_log_writer_init* ap_log_set_writer_init(ap_log_writer_init *handle);
  static ap_log_writer* ap_log_set_writer(ap_log_writer *handle);

ap_log_set_writer_init()は、ログ出力のための初期化処理(ファイルのオープン など)を行うための関数、またap_log_set_writer()は、実際のログ出力を行う際に 呼ばれる関数をそれぞれコールバック登録します。あとは、Apacheがそれらのコー ルバック関数を必要なタイミングで呼び出してくれます。

さらに上記の関数2つは返値を持ち、それぞれのコールバック関数の事前の値を表し ます。mod_syslogは"syslog:"のプレフィックス以外のログ出力先、すなわちパイプ やファイル出力については従来の処理に任せますので、mod_syslog自身のコールバッ ク関数登録と同時に従来のコールバック関数へのポインタを、この返値によって取得、保持します。

#define PREFIX_SYSLOG   "syslog:"
#define PREFIX_SYSLOG_LENGTH    7

static void *
ap_syslog_writer_init(apr_pool_t *p, server_rec *s,
                      const char* name)
{
    syslog(LOG_DEBUG, "%s: prev_log_writer_init = %p, name = %s", __func__, prev_log_writer_init, name);

    if (strncasecmp(PREFIX_SYSLOG, name, PREFIX_SYSLOG_LENGTH) == 0) {
        return &dummy[0];
        // NULL以外を返す。
        // 同じ値(&dummy[0])かどうかをap_syslog_writer()関数で判別できればよい。
    }

    if (prev_log_writer_init) {
        return prev_log_writer_init(p, s, name);
    }

    return NULL;
}

// ap_hook_pre_config()でフック登録
static int
syslog_pre_config(apr_pool_t *p, apr_pool_t *plog, apr_pool_t *ptemp)
{
    ...

    if (!prev_log_writer_init) {
        void* f;

        f = ap_log_set_writer_init(ap_syslog_writer_init);
        if (f != ap_syslog_writer_init) {
            prev_log_writer_init = f;
        }
        f = ap_log_set_writer(ap_syslog_writer); // ap_syslog_writerの内容については省略
        if (f != ap_syslog_writer) {
            prev_log_writer = f;
        }
    }

    return OK;
}

つまり、上記の例で言えばprev_log_writer_initとprev_log_writerに従来の処理 へのコールバック関数のポインタが入るわけです。 なお、この2関数が返値を返すようになったのはApache2.2以降なので、Apache2.0 系ではそのままでは使用できません。一応、同名の関数から旧い値を返させるだけ で動作するところまでは確認していますが、もしお試しの際はご注意ください。

このように、Apacheからアクセスログを出力するにあたり、モジュールの追加だけ でも結構な機能追加ができることが分かります。しかも、添付の例をご覧のように、 わずかなコード量で実現できています。あったらいいな、こんなことできたらうれ しいな、というちょっとした発想を柔軟に取り入れられるApacheの仕組みにはやは り目を見張るものがありますね。

ダウンロードはこちらから
イージスガード公式ページ（KLab サイトへ）

イージスガードには次の機能・特長があります。

• 所定のフォルダ・ファイルを保護対象として設定可能
• 許可しないプログラムからのアクセスを報告・記録する
• 許可しないプログラムからのアクセスを透過的にダミーフォルダへ誘導
• PC 環境に応じて保護設定を自動生成する
• 改変されたプログラムからのアクセスを抑制する
• 有効なデジタル署名つきのプログラムには自動的に許可を与える

イージスガードは、以前このブログでご紹介した「WinAmulet」を母体とする上位互換のソフトウェアです。WinAmulet ユーザ各位のご支援のおかげで、多くの機能を追加し大きく性能を改善したこの新しいソフトウェアが生まれました。もちろん、WinAmulet の保護設定をインポートすることも可能です。

イージスガードに使用制限はありません。多くの方に自由にご利用頂くことで、悲惨な情報流出被害発生の防止につながれば、と願っています。

正式なリリースノートは公式Webサイトを参照してもらうとして、この一年弱で改良された点を私の基準で紹介したいと思います。

TortoiseBZRが(たぶん)実用レベルになった

私はたいていコマンドラインから利用しているので、以前紹介したときはTortoiseBZRをあまり使い込んでいませんでした。

その後、TortoiseBZRを使い込んでみたところ、pushができない、addもできないなど最低限の機能がそろっていなかったり、ステータスの表示が重くてストレスになったりしたので結局アンインストールしてしまいました。

その後今年に入ってからTortoiseBZRの開発が停滞してしまい、このままじゃいけないと思って6月後半からTortoiseBZRの開発に参加しました。この2ヶ月で以下のような問題を解決しました。

• シェル拡張の致命的なバグ(「新しいフォルダを作成」などのボタンが動作しなくなる、Windows Vistaでコンテキストメニューのレイアウトが崩れるなど)が修正されました。
• ステータスの取得が速くなりました。また、まだステータスを取得していないファイルの場合 '?' マークのステータスアイコンを表示してバックグラウンドでステータスを取得することで、エクスプローラの応答速度の低下を抑えました。(この方法はTortoiseHGの開発者にTwitterで教えてもらって開発しました。感謝感謝)
• add, push, send といった機能をコンテキストメニューに追加しました。

まだTortoiseSVNの完成度には到達していませんが、とりあえずユーザーを邪魔をする挙動が無くなって基本的な操作の大半がコンテキストメニューから呼び出せるようになったので、人に試してみてと言える状態になっています。

新しいリポジトリフォーマットが標準になった

Bazaar 2.0 からは 2a といわれる新らしいリポジトリフォーマットが標準になりました。 Bazaarではデータの格納方式が変わる以外にも、新機能のために新しいメタデータを追加した時にも古いバージョンのBazaarからそのメタデータがないリビジョンをコミットされてしまわないようにとリポジトリフォーマットを変更しています。その結果としてBazaarには大量のリポジトリフォーマットができてしまい、「○○のフォーマットでは△△の機能が使えない」といった問題が発生していました。

新しいフォーマットが標準になることで、リポジトリフォーマットをオプションから選ばなくても新しい機能が全部使える、リポジトリサイズが小さくなったりいくつかの操作が速くなっていたりするという利点があります。

WindowsでのUnicodeファイル名への対応が改良された

PythonではUnicode APIを利用することで、Unicodeファイル名でファイルを扱うことができるのですが、 sys.argv で取れるコマンドライン引数は非Unicodeです。(Python3ではUnicodeになります) Bazaarも sys.argv を利用していたため、せっかくUnicodeでファイル名を扱うのにコマンドライン引数からはコードページでしかファイル名を取得できないという問題がありました。

最近のバージョンではこの部分が GetCommandlineW() APIを利用するようになり、bzr本体だけでなくQBzr等のGUIを含めてUnicodeへの対応が進んでいるので、Unicodeファイル名に関する問題はほとんどなくなりました。

日本語ユーザーグループができた

日本語で議論ができる環境が欲しいと思い、Bazaar 2.0 のリリースをきっかけにユーザーグループを作ることにしました。 http://groups.google.co.jp/group/bazaar-ja

Launchpad上にドキュメント翻訳プロジェクトも作成し、ゆっくりですが翻訳作業も開始しています。TortoiseBZRのバグ報告や要望なんかも、英語でLaunchpadに登録するよりも手軽にできるはずです。Bazaarに関心のある方はぜひ参加してみてください。

『Gainerでアイデアをフィジカルにスケッチする』
  ～ Gainerでアイデアをフィジカルにスケッチする

• 発表資料 (PDF, 5.5 MB)

『おしゃべりコーヒーボット』
  ～ 宇夫 陽次朗 (株式会社IIJイノベーションインスティチュート)

• 発表資料 (PDF, 2.1 MB)

『hwhack: USB解析のいろいろ』
  ～ 宇夫 陽次朗 (株式会社IIJイノベーションインスティチュート)

• 発表資料 (PDF, 6.8 MB)

『3DCADやRPによるハードウェア開発』
  ～ 松村 礼央(株式会社国際電気通信基礎技術研究所（ATR）知能ロボティクス研究所（IRC）環境知能研究室 研修研究員)

• 発表資料 (PDF, 849 KB)

先日の勉強会はちょうど台風の最中でしたが、お越しいただいたきありがとうございました。
みなさんのおかげで懇親会も楽しく過すことができました。

勉強会の様子は、動画のほうを準備していますので今暫くお待ちください。

旧バージョンをご利用中の方も、初めての方も、ぜひ最新の WinAmulet をお試し下さい。

■ このプログラムの概要

「WinAmulet」は、所定のフォルダに対しアクセス可能なプログラムを制限するソフトウェアです。対象フォルダ下の大切なファイルにユーザの許可しないプログラムがアクセスすることを防ぎます。

■ 主な更新内容

• キャッシュ機構の実装により処理効率を改善しました
• リダイレクト処理の精度を改善しました
• ファイルオープン要求中の各プロセス名を確認できるようにしました

ハードウェアと一口にいっても様々な分野があります。 今回は外部から宇夫陽次朗氏(株式会社IIJイノベーションインスティチュート) と松村礼央氏(株式会社国際電気通信基礎技術研究所)をお招きする予定です。

　宇夫氏からはUSBデバイスの解析方法について、また松村氏からは近い将来 身近な存在になるロボットの開発についてお話を頂きます。

併せて弊社から、USBデバイスを経由し手軽に工作ができるGainer(ゲイナー)の導入編から事例も交えお話しさせていただきます。

開催要項

日時

2009/8/31 (月) 19:00-21:10 (18:30受付開始)

場所

KLab株式会社 第3会議室
東京都港区六本木6-10-1 六本木ヒルズ森タワー20F
(アクセス方法)

参加費

無料

人数

30名程度
(定員になり次第、参加登録を締め切らせていただきます。)

※終了後に懇親会(会費制)を予定しています。

セッション

1. タイトル

   『Gainerでアイデアをフィジカルにスケッチする』

   講師

   竹井 英行(KLab株式会社)

   概要

   フィジカル・コンピューティングのための入門的なツールキットGainer(ゲイナー)を使って、LEDやアクチュエータなどのハードウェアを簡単なプログラムで動かす方法を説明する。またその中で、Gainerを使いこなすために必要な電気回路の基礎も説明する。その後、応用として、Zigbee+Gainerによるデモンストレーションを 紹介する。

2. タイトル

   『hwhack: USB解析とかいろいろ』

   講師

   宇夫 陽次朗 (株式会社IIJイノベーションインスティチュート)

   概要

   　コンピュータと周辺機器をつなげるためのインターフェイスとしてUSBが広く普及した。PCから組み込み機器といったホスト側や、様々な周辺機器群がUSBインターフェイスを装備し、多くのOSはUSBサポートの機能を標準的に提供している。
   　今回はUSBの概略を説明し、USBデバイスの挙動を解析する手法を紹介する。またBSD系OSでのデバイスドライバとの関係も扱っていきたい。

3. タイトル

   『3DCADやRPによるハードウェア開発』

   講師

   松村 礼央(株式会社国際電気通信基礎技術研究所（ATR）知能ロボティクス研究所（IRC）環境知能研究室 研修研究員)

   概要

   　近年、フィジカルコンピューティングをはじめ、インタラクティブな製品の開発が盛んに行われています。そこで今回は，人とコミュニケーションをとるロボットの開発を例に 3DCADやラピッド・プロトタイピング（RP）によるハードウェアの開発方法について概説します。

参加方法

register-study-20090831@klab.jp 宛に件名を「参加登録」として、以下の内容のメールを送ってください。

氏名　　　　：
所属　　　　：（会社名・学校名等）
懇親会　　　：（参加する・しない）
URL 　　　　：ご自身のブログなどがあればそのURLを。（任意）
コメント　　：勉強会についての希望や参加の意気込みなど、
　　　　　　　なんでも結構ですので、よろしければ一言コメ
　　　　　　　ントいただけるとうれしいです。（任意）

※当日は、受付にて名刺を一枚頂戴いたしますので、予めご用意下さい。

PythonからMessagePackフォーマットでSerialize/DeserializeするためのPythonパッケージを作ったので、取得方法と使い方について簡単に紹介します。

$ easy_install msgpack

>>> import msgpack
>>> help(msgpack)  # docstring を読む

>>> msgpack.packb([1,2,3])
'\x93\x01\x02\x03'

>>> packer = msgpack.Packer()
>>> packer.pack([1,2,3])
'\x93\x01\x02\x03'
>>> packer.pack([4,5,6])
'\x93\x04\x05\x06'

>>> msgpack.unpackb(b'\x93\x01\x02\x03')
[1, 2, 3]

>>> unpacker = msgpack.Unpacker()
>>> buf = b'\x93\x01\x02\x03' * 5
>>> len(buf)
20
>>> unpacker.feed(buf[:9])
>>> for o in unpacker:
...     print o
...
[1, 2, 3]
[1, 2, 3]
>>> unpacker.feed(buf[9:])
>>> for o in unpacker:
...     print o
...
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]

#!/usr/bin/env python
# coding: utf-8

from msgpack import packs, unpacks
from cPickle import dumps, loads
import simplejson as json
from time import time

BENCH_NUM = 10

def bench(func, num=BENCH_NUM):
    start = time()
    for i in xrange(BENCH_NUM):
            func()
    end = time()
    print "%-12s  %4.3f[ms]" % (func.__name__, (end-start)*1000/BENCH_NUM)

def setup_int():
    global a, a_pickle, a_mpack, a_json
    a = range(1024) * 2**10
    a_pickle = dumps(a)
    a_json = json.dumps(a)
    a_mpack = packs(a)

def setup_str():
    global a, a_pickle, a_mpack, a_json
    a = ['a'*(i % 4096) for i in xrange(2**14)]
    a_pickle = dumps(a)
    a_json = json.dumps(a)
    a_mpack = packs(a)


def pickle_dump(): dumps(a)
def pickle_load(): loads(a_pickle)

def json_dump(): json.dumps(a)
def json_load(): json.loads(a_json)

def mpack_pack(): packs(a)
def mpack_unpack(): unpacks(a_mpack)


targets = [
        pickle_dump, pickle_load,
        json_dump, json_load,
        mpack_pack, mpack_unpack]
import gc
gc.disable()

bytes_suffix = "[bytes]"

print "== Integer =="
setup_int()

print "= Size ="
print "pickle:", len(a_pickle), bytes_suffix
print "json:  ", len(a_json), bytes_suffix
print "mpack: ", len(a_mpack), bytes_suffix

for t in targets:
    bench(t)

print "== String =="
setup_str()

print "= Size ="
print "pickle:", len(a_pickle), bytes_suffix
print "json:  ", len(a_json), bytes_suffix
print "mpack: ", len(a_mpack), bytes_suffix

for t in targets:
    bench(t)

== Integer ==
= Size =
pickle: 6203398 [bytes]
json:   5154816 [bytes]
mpack:  2752517 [bytes]
pickle_dump   248.640[ms]
pickle_load   360.288[ms]
json_dump     255.601[ms]
json_load     136.922[ms]
mpack_pack    51.383[ms]
mpack_unpack  26.851[ms]
== String ==
= Size =
pickle: 33731696 [bytes]
json:   33611776 [bytes]
mpack:  33595139 [bytes]
pickle_dump   182.324[ms]
pickle_load   141.639[ms]
json_dump     126.675[ms]
json_load     93.945[ms]
mpack_pack    66.833[ms]
mpack_unpack  34.953[ms]

【Ver1.1.3→Ver1.2.0】

• 応答速度と安定性の向上
• エラーログに"[error]"という文字列を追加
• メンバがタイムアウトしたときの状況を詳細に出力するようにした
• msync --statusで、実行中のコマンドを表示するようにした
• msyncを複数同時実行したときに挙動がおかしくなる不具合を修正
• ファイルクローズに失敗したときに異常終了する不具合を修正
• msyncにdeleteオプションを指定したときの結果表示がおかしくなる不具合を修正
• その他細かい不具合を修正

【ダウンロード】

• ダウンロードページ
• makuosan-1.2.0.tar.gz

「ところで、まくおさんってだれ？」という方は、こちらやこちらを見てやってください(^^;

php の VM のソースコードは、phpソースパッケージ中の Zend/ というディレクトリの中にあります。zend_vm_で始まる幾つかのファイルのうち、 zend_vm_execute.h というファイルが命令ディスパッチが実装されているファイルで、このファイルは zend_vm_gen.php というスクリプトで生成されています。そして、 zend_vm_gen.php のオプションで、命令ディスパッチの方法を選択できます。(phpのビルドにphpが必要です)

computed goto を使うビルド手順は以下の通りになります。

$ tar xzf php-5.2.x
$ cd xzf php-5.2.x/Zend
$ php zend_vm_gen.php --with-vm-kind=GOTO
$ cd ..
$ ./configure --with-zend-vm=GOTO [その他オプション]
$ make

Zend/ ディレクトリの中に bench.php というファイルがあったので、これを使って通常の関数ポインタ配列版とcomputed goto版の速度を比較してみました。

# 関数ポインタ配列版.
$ ~/local/stow/php-5.2.9-func/bin/php bench.php
simple             0.319
simplecall         0.412
simpleucall        0.639
simpleudcall       0.693
mandel             0.991
mandel2            1.311
ackermann(7)       0.767
ary(50000)         0.047
ary2(50000)        0.037
ary3(2000)         0.534
fibo(30)           1.739
hash1(50000)       0.087
hash2(500)         0.098
heapsort(20000)    0.312
matrix(20)         0.257
nestedloop(12)     0.539
sieve(30)          0.232
strcat(200000)     0.034
------------------------
Total              9.047

# computed goto版
$ ~/local/stow/php-5.2.9-goto/bin/php bench.php
simple             0.283
simplecall         0.360
simpleucall        0.584
simpleudcall       0.645
mandel             1.022
mandel2            1.213
ackermann(7)       0.788
ary(50000)         0.046
ary2(50000)        0.036
ary3(2000)         0.485
fibo(30)           1.716
hash1(50000)       0.079
hash2(500)         0.090
heapsort(20000)    0.276
matrix(20)         0.237
nestedloop(12)     0.479
sieve(30)          0.234
strcat(200000)     0.035
------------------------
Total              8.610

5%くらい速くなっていますね。 Python 3.1 だけじゃなくて php をビルドするときも computed goto を試してみて下さい。

Python3.1のパフォーマンス向上は、主に次の2点が影響しています。

• ioモジュールがC言語で書き直された
• computed goto の採用 (--with-computed-gotos というconfigureオプションで有効)

computed goto という名前を聞き慣れなかったのですが、調べてみると Ruby 1.9 の VM (YARV) や、 Perl6 の VM として開発されとうとうリリースされた Parrot にも採用されている手法でした。今回は簡単に computed goto の紹介をしてみます。

    goto label;
    puts("foo"); // 表示されない.
label: //ここにジャンプする.
    puts("bar");

    void *jump_target = &&label;
    goto *jump_target;
    puts("foo");
label:
    puts("bar");

for (;;) {
    code = *code_pc++;
    switch (code) {
    case CODE_ADD:
        // 足し算処理.
        break;
    case CODE_SUB:
        // 引き算処理.
        break;
    // ...
    case CODE_END:
        goto LOOP_END;
    }
}
LOOP_END;

    static const void *JUMPTABLE[] = {&&CODE_ADD, &&CODE_SUB, ... , &&CODE_END};

    code = *code_pc++;
    goto *JUMPTABLE[code];

CODE_ADD:
    //足し算処理.
    code = *code_pc++;
    goto *JUMPTABLE[code];

CODE_SUB:
    // 引き算処理
    code = *code_pc++;
    goto *JUMPTABLE[code];
    ...
CODE_END:

IPythonとは

IPythonとは、Pythonistaの中で絶大な人気を誇るインタラクティブシェルです。

Pythonはもともとインタラクティブシェルを内蔵しているのですが、 IPythonには内蔵のインタラクティブシェルと比べて多くの利点があります。いくつか挙げてみます。

• 動的補完

  変数名などを途中まで入力した状態でTABキーを押すと、残りを補完してくれます。 候補が複数ある時は候補一覧を表示してくれます。

• シンタックスハイライト

  プロンプトなどに色がつきます。ちょっとうれしいです。

• 通常のシェルとしても利用可能

  IPythonの中で、lsでファイル一覧を見たり、cdでカレントディレクトリを移動したりできます。 !vim のようにエクスクラメーションマークに続いてコマンド名を入力することで、コマンドの実行もできます。 さらに、コマンドの出力がPythonの変数に格納され、Pythonから利用可能になります。Unixの大量のコマンドを使いこなせなかったり、Windowsでコマンドが少ないことが不満だったりするときに重宝します。

• よく使う機能を省略形で記述可能

  help(o) の代わりに o? でそのオブジェクトのドキュメントが読めます。

  func(a, b) の代わりに func a b で関数呼び出しが可能です。

• エディタと連携可能

  ed foo.py のようにすることで、 foo.py を外部エディタで開いて編集できます。 そしてエディタを閉じると、自動的にそのファイルがevalされます。 この機能を使うと、エディタで関数を書く→IPython上で動作を確認する→エディタで関数を修正する、というサイクルでサクサク開発できます。 これに馴れてしまうと、IDEが欲しいと思わなくなります。

$ python
Python 2.5.2 (r252:60911, Oct  5 2008, 19:24:49)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> u"あ"
u'\u3042'
>>>
$ ipython
Python 2.5.2 (r252:60911, Oct  5 2008, 19:24:49)
Type "copyright", "credits" or "license" for more information.

IPython 0.9.1 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object'. ?object also works, ?? prints more.

In [1]: u"あ"
Out[1]: u'\xe3\x81\x82'

>>> c = compile("""u'あ'""", "foo.py", 'single')
>>> c.co_consts
(u'\xe3\x81\x82', None)
>>> c = compile(u"""u'あ'""", "foo.py", "single")
>>> c.co_consts
(u'\u3042', None)

--- iplib.py.old    2009-03-13 15:42:33.000000000 +0900
+++ iplib.py        2009-03-13 15:42:58.000000000 +0900
@@ -2019,9 +2019,9 @@
         # this allows execution of indented pasted code. It is tempting
         # to add '\n' at the end of source to run commands like ' a=1'
         # directly, but this fails for more complicated scenarios
-        source=source.encode(self.stdin_encoding)
-        if source[:1] in [' ', '\t']:
-            source = 'if 1:\n%s' % source
+        #source=source.encode(self.stdin_encoding)
+        if source[:1] in [u' ', u'\t']:
+            source = u'if 1:\n%s' % source

         try:
             code = self.compile(source,filename,symbol)

In [1]: u"あ"
Out[1]: u'\u3042'

In [2]: u"ソ"
Out[2]: u'\u30bd'

Hack the Cell '09 に参加して知った、Cellに限らず一般的に使えるビット演算の高速化手法について紹介します。

Bitslice と呼ばれる手法では、ビット順を90度回転します。言葉で説明するよりもコードを見たほうが早いので、回転させるコードの例を見てください

int   x[32], y[32]; // x が元のデータ、y が回転後のデータ.
for (int i = 0; i < 32; ++i) {
    int t = 0;
    for (int j = 0; j < 32; ++j)
        t |= ((x[j] >> i) & 1) << j; // x[j] の i ビット目を
    y[i] = t;                        // y[i] の j ビット目にする
}

この変換をすることで、y[0] には x[0] - x[31] の最下位ビットが、 y[1] には 2番目のビットが格納されることになります。

回転することでビット演算が高速になる様を見てみます。

//--
// and 演算

// 通常
for (int i = 0; i < 32; ++i) {
    x[i] &= 3; // load, and, store, 各32回
}

// bitslice
for (int i = 2; i < 32; ++i) {
    y[i] = 0; // store 30回
}

//--
// xor 演算

// 通常
for (int i = 0; i < 32; ++i) {
    x[i] ^= 0xff; // load, xor, store, 各32回
}

// bitslice
for (int i = 0; i < 8; ++i) {
    y[i] = ~y[i]; // load, not, store 各8回
}

//--
// シフト演算
for (int i = 0; i < 32; ++i) {
    x[i] >>= 16; // load, 右シフト, store, 各32回
}

// bitslice
for (int i = 0; i < 16; ++i) {
    y[i] = y[i+16]; // load, store, 各16回
}

bitslice はなぜ速いか

無駄なビットに対する演算を省略できる

たとえば、 x ^= 1 (xは32bit整数) という演算は、最下位ビットを反転させているだけで、最下位以外の31bitにはまったく影響がありません。せっかくの32bit演算なのに、実質は1bit演算になってしまっているわけです。

bitslice なら最下位ビットだけを集めた32bitに対して演算するので、32bit演算の能力を無駄にすることがありません。

マスクがいらない

マスクは操作したくないビットを保護するためのものです。操作したいビットが集まっていれば、マスクが不要です。

マスク付きの通常ビット演算とbitsliceでの演算の対応は次のようになります。

• and演算は、マスクビットが0の場所への 0 代入に
• or演算は、マスクビットが1の場所への 1 代入に
• xor演算は、マスクビットが1の場所への not 演算に

load が減る

普通の and や or 演算においてロードが必要なのは、操作しない(マスクされた)ビットを元の値にしておくためです。bitsliceでは全bitに1や0を代入できるので、不要な load を減らすことができます。

load が減るということは、単純に命令数が削減する以上の意味があります。一般的に言って、store命令は遅延して次の命令と並列に実行できるのに対して、load命令は完了するまでloadした値に依存する命令を実行できません。load命令が減ることで、パイプラインストールを減らすことができます。

工夫次第でさらに速く

先ほどの例では、通常のシフト演算を配列内での移動に置き換えていました。しかし、 y[i] = y[i+16] の代わりに y += 16 が許されるのであれば、シフト演算は完全に省略できることになります。

同じように or 演算でも、 y[i] = 0 をする代わりに、次に y[i] を参照する場所を 0 に置き換えることができるかもしれません。状況によって、いろいろな工夫が考えられます。

bitslice が苦手な計算

bitslice では各ビットがバラバラになっているので、ビット単位の演算は得意な代わりに、ビットをまたがる演算が苦手です。たとえば加算や減算は繰り上がりや繰り下がりがビットをまたぐので、bitsliceでは遅くなります。試しに加算を実装してみます

// 通常の演算
for (int i = 0; i < 32; ++i) {
    x[i] += z;
}

// bitslice
int carry = 0;
for (int i = 0; i < 32; ++i) {
    int c;
    c = (carry & y[i]) | (y[i] & z) | (z & carry);
    y[i] = carry ^ y[i] ^ z;
    carry = c;
}

ただし、特定の条件では通常の演算に近い速度が出せることもあります。次の例では、CPUに bitcnt() という bit が 1 になっている数を数える命令があると仮定して、配列の合計値を計算しています

// 通常の演算
int sum = x[0]; // load 1回
for (int i = 1; i < 32; ++i) {
    sum += x[i];  // load, add, 各31回
}

// bitslice
int sum = bitcnt(y[0]); // load, bitcnt, 各1回
for (int i = 1; i < 32; ++i) {
    sum += bitcnt(y[i]) << i; // load, bitcnt, shift, add 各31回
}

提出物とスコア

ソースコード (試行錯誤の跡が整理されていません)

スコア

ORIGNAL:         sum=3c927c56, 294030647 ticks
MINE:            sum=3c927c56, 4464381 ticks
ORIGNAL:         sum=2e987a4d, 424155603 ticks
MINE:            sum=2e987a4d, 6440068 ticks
ORIGNAL:         sum=ef1b6aef, 312102737 ticks
MINE:            sum=ef1b6aef, 4738888 ticks
ORIGNAL:         sum=eedd2516, 290055058 ticks
MINE:            sum=eedd2516, 4403913 ticks
ORIGNAL:         sum=f7e967a8, 14366822 ticks
MINE:            sum=f7e967a8, 218363 ticks
ORIGNAL:         sum=1f37a7db, 214216185 ticks
MINE:            sum=1f37a7db, 3252580 ticks
ORIGNAL:         sum=c7d41f36, 294964206 ticks
MINE:            sum=c7d41f36, 4478494 ticks
ORIGNAL:         sum=aa9d2e9f, 259565045 ticks
MINE:            sum=aa9d2e9f, 3941212 ticks
ORIGNAL:         sum=8abd398a, 250844221 ticks
MINE:            sum=8abd398a, 3808729 ticks
ORIGNAL:         sum=a374bd58, 6110290 ticks
MINE:            sum=a374bd58, 92978 ticks

倍率としては、約66倍といったところです。ただし、ORIGINALの速度が安定しない(プログラムのアライメントによって実行速度が変化する)ので、倍率は参考程度にとどめておいてください。

今回のコンテストの内容について

課題は、メルセンヌツイスターという乱数生成機の高速化でした。

最適化する対象となる関数はこちらです(一部省略)

#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfUL   /* constant vector a */
#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffUL /* least significant r bits */

static unsigned long mt[N]; /* the array for the state vector  */
static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */

/* ... */

unsigned long genrand_int32(void)
{
    unsigned long y;
    static unsigned long mag01[2]={0x0UL, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */

    if (mti >= N) { /* generate N words at one time */
        int kk;

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

        mti = 0;
    }

    y = mt[mti++];

    /* Tempering */
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

しかし、最適化したコードを実装する側のスケルトンとなる関数は次のような定義になっていました

unsigned int
genrand_mine(int num_rand)
{
  int r = 0;
  /* r = num_rand 個の乱数のチェックサム */
  return r;
}

この関数は戻り値として、 num_rand 個の生成された乱数のチェックサムを返す必要があります。

もともとの課題では、「※疑似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。」となっていたのですが、参加者によって以下のように異なった解釈がされていました。

• 同じ32bit整数としての乱数を求められている (私はこの解釈をしていました)
• 乱数のビット順がどうなっていても良い
• そもそも配布されているプログラムがチェックサムしか見ていないのだから、チェックサムだけ合ってれば何をしてもOK

この解釈の違いが問題になっていたのですが、最終的には現在課題のページにあるように、一番ゆるい「チェックサムが合っていれば何をしてもOK」というルールで優勝・準優勝を決め、きちんと乱数を生成していた人にはFixstars社の判断で「フィックススターズ賞」が送られることになりました。

結果として、今回のコンテストにおいて最適化の方針として3つが生まれました。

1. 元のコードをそのままSIMD化する

   基本は元のプログラムのまま、mt[] の要素を4つひとまとめに処理する。 その後、命令数を削減したりパイプラインを埋めて速度を稼いでいく。 この方法だと、60倍～70倍程度までを目指せます。

   元の乱数生成器と同じ32bit整数で乱数を生成するので、フィックススターズ賞ねらいになります。

2. ビット順を90度入れ替えた bitsliece と呼ばれる構造で乱数を計算する

   SPUの128bitレジスタを、32bit整数4つとしてではなくて、1bitが128個あると考えて最適化していきます。命令の組み合わせだけでなくデータ構造をどうするのかにも工夫が必要になります。この方法で100倍を超えた参加者もおられるようです。

   この方法では乱数が32bit整数の形では出現しないので、優勝・準優勝ねらいになります。

3. 乱数を生成しないで直接チェックサムを計算する

   mt[] の値は 32bit整数を乱数の種として初期化されるので、種と num_rand と組み合わせた 64bitの情報から結果のチェックサム32bitを求めるということが究極的な目標になります。 極端な例を言えば 32bit * 2^64 分のテーブルを用意すれば、O(1) でチェックサムの計算ができる事になります。

   私には全く思いつかなかったのですが、 この計算をメモリ制約の中で O(n) 未満で実行する方法が存在するかもしれません。

私は2月は忙しくて全く高速化できなかったので、ルール確定前までに書いていた 1 の方法のプログラムのまま提出しました。 提出締め切り後、同じ1の方法でもあと5%以上高速化する方法が他の参加者のブログで紹介されていて悔しい思いをしています。 次回があればまた参加したいと思います。