開発
社内コードコンペ - お題：最速なCIDRブロックマッチ判定 〜 稲田の場合: hamanoが倒せない 〜
|
|
おさらい
- #1 ひろせの場合 - IP::CountryとAPRを使ってみた
- #2 安井の場合: バイナリサーチのあれとこれ
- #3 hamanoの場合: あ ありのまま 今 起こった事を話すぜ!『コードコンペだと思ったらゴルフコンペだった』な(ry
- #4 稲田の場合: hamanoが倒せない ← 今回
このコードのウリ
安井さんが２分探索で実装しているという話を聞いて、「それ、TRIE(トライ)で書いた方が速いしシンプルに 書けるんじゃね？」と思って、コードコンペに参加しました。
TRIEそのもの解説は、先日の濱野さんの物と同じなので省略します。
２分探索等だとO(log n) (nは登録されているcidrの数)の計算量になりますが、TRIEを使うと計算量はO(m) (mはアドレスの長さ) となり、登録するcidrの数が増えてもほとんど遅くなりません。 また、２分探索に比べると、探索部分のコードが非常にシンプルになるのもTRIEの魅力です。
基本的に濱野さんと比じ処理なのですが、性能で若干負ける代わりに、可読性や柔軟性はこちらの方が 高いと自負しています。
コード解説
まず、最初のバージョンはこんな感じになっていました。この頃は「アドレス帯がかぶっている時は 狭いアドレス帯を優先する」という要求がなかったこともあり、非常にシンプルです。
/* データ構造 */
typedef struct ADR_TRIE {
const char *type;
struct ADR_TRIE *child[TABLE_SIZE];
ADR_TRIE;
/* 葉からはchildを削ってメモリ節約する. */
typedef struct ADR_TRIE_LEAF {
const char *type;
} ADR_TRIE_LEAF;
...
/* 探索部分 */
ADR_TRIE *pt = &trie_root;
while (pt && (!pt->type)) {
int b = addr >> 24; /* このころはアドレスはuint32_tだった */
pt = pt->child[b];
addr <<= 8;
}
if (pt) return pt->type;
このコードを実装している間、IRCでは濱野さんが同じアイデアを提案していました。
hamano``> 256 分木つくって 1オクテットずつ読んで分木すれば、最低4回の遷移で判別出来る hamano``> メモリ空間が大きくなるかもしれませんが、この程度のデータ量ならそれほど大きくならないと思います hamano``> 僅か数命令で判別出来るのでこれ以上の最適化は無いかも YasuiML> やってみて★ hamano``> あんまり、差が出ないのでイマイチ乗れないなぁ hamano``> 問題を国判別に拡張しません?^^;
そして、上の実装ができて、コードを安井さんに渡しました。
YasuiML> こみったす katsumiD> 2段のテーブル引きにしたらどだろう katsumiD> 上位16bit と 下位16bit にわけて YasuiML> うほ YasuiML> yasui-m@sag15:~$ ./cidrlookup 5000000 210.153.84.128 210.169.176.128 222.7.56.128 209.85.238.120 60.32.85.216 YasuiML> loop : 5000000 YasuiML> elapse: 6.8481210 YasuiML> avg : 0.0000003 YasuiML> 稲田さんのはやいすね！！ YasuiML> 一秒以上差がつきましたかあ
と褒められて、良い気になっていました。（この時点では、ベンチマークの内容が違い、経過時間がまったく異なります）
しかし、次の日、濱野さんがより高速なコードをコミットしました。その中身を読んでコードを読んで衝撃が走りました。
return type[tab[addr[3]][tab[addr[2]][tab[addr[1]][tab[addr[0]][1]]]]];
なんだこの[]だらけのコードは！分岐なしか！テーブル参照回数が同じである以上、 分岐を消さないと絶対勝てない！と思い、慌てて対抗して分岐を削除してみました。
pt = pt->child[*addr++]; /* addrは、ネットワークバイトオーダーで格納されたアドレスの先頭アドレス */ pt = pt->child[*addr++]; pt = pt->child[*addr++]; pt = pt->child[*addr++]; return pt->type;
分岐を削除するためのhackとして、葉の形を変えました。分岐削除前は、pt->childを持たないようにしてメモリ消費を 抑えていたのですが、葉もpt->childを持ち、pt->child[n] == ptとしておくことで、短いサブネットアドレスでも4回の テーブルルックアップを実行するようにしました。分岐が減る代わりに、サブネットアドレスが短い場合はテーブルルック アップが増えるのですが、今回はマイクロベンチだからテーブルはほぼ確実にキャッシュに載っていますし、テストに使った アドレスもサブネットアドレスが長い物ばかりだったので、分岐を削除することでかなり速度を稼げました。
おわりに
ここに載せている以外にもいろいろと寄り道したのですが、最終的に、これ以上にできそうなアイデアは全て等価なものが 濱野さんのコードで実現済みという状況になってしまい、負けを認めました。 でも、メモリの確保の仕方が柔軟に対応できる点や、コードを読んで構造を把握しやすいかなどの面で、本採用を狙っています。
ベンチマーク
5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。
ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。_8が、1テーブルでアドレス1byte分処理するバージョンで、 _16が1テーブルでアドレス2byte分処理するバージョンになります。16の方がテーブル参照が２回で済むので高速ですが、 メモリ使用量がバカみたいに増えるので、普通に使うなら8の方になります。
x64環境に置いてはかなり善戦していますが、hamanoさんにはあと一歩届きませんorz
x86
時間name elapsed[sec] average[usec] ======================================== apr 59.379924 2.375197 ip-country 3.739187 0.149567 yasui-a 2.727045 0.109082 # インラインアセンブラ yasui-c 0.975544 0.039022 # C言語 hamano-1 0.234664 0.009386 hamano-2 0.142496 0.005700 inada-n_16 0.175591 0.007023 inada-n_8 0.208570 0.008342
x86_64
name elapsed[sec] average[usec] ======================================== apr 52.340651 2.093626 ip-country 0.664034 0.026561 yasui-c 0.706095 0.028244 hamano-2 0.107557 0.004302 inada-n_16 0.116348 0.004653 inada-n_8 0.137042 0.005481続きを読む
社内コードコンペ - お題：最速なCIDRブロックマッチ判定〜 hamanoの場合: あ ありのまま 今 起こった事を話すぜ!『コードコンペだと思ったらゴルフコンペだった』な(ry 〜
|
|
おさらい
- #1 ひろせの場合 - IP::CountryとAPRを使ってみた
- #2 安井の場合: バイナリサーチのあれとこれ
- #3 hamanoの場合: あ ありのまま 今 起こった事を話すぜ!『コードコンペだと思ったらゴルフコンペだった』な(ry ←今回
- #4
はじめに
社内 irc で盛り上りを見せている、IPv4 アドレスの判定問題に取り組んでみました。
まず既にある実装としては、CPAN モジュールの IP::Country という実装がある様で、この実装は、判定データから2分木を構築し 1ビットずつ遷移して行くという実装のようです。
IPv4 に限定すると 1 bit ずつの判定でも高々 32回の参照になるのでこの時点ですでに O(1) なのですが、メモリをたくさん使用する代わりにもっと早い実装を考えてみると IPv4 であれば 4G のテーブルを用意しておけば、たった 1度の参照で判定出来ます。
このことから早さとメモリ空間のトレードオフとなる、この2つのアルゴリズムの間で今回のデータ量に適したところを探っていくことにしました。
実装1:このコードのウリ
まず実装が簡単そうな 1オクテットずつ遷移する実装を行ってみました。データ構造は以下のような感じで、この図では 192.168.1.2 を sakanaya の ネットワーク範囲として判定するケースを表しています。
この様なテーブルを構築しておく事で 4回の lookup で判定することが出来ます。メモリの使用量は short * 256 のテーブルが300 個程度ですので 150k でした。
実装1:コード解説
判定のコードはこんな感じになりました。
const char *cidr_lookup(unsigned char *addr, int len)
{
return type[tab[tab[tab[tab[1][addr[0]]][addr[1]]][addr[2]]][addr[3]]];
}
そう、実はこのコードコンペ。アルゴリズムは最初から O(1) なので、アルゴリズムではなくコード(命令数)の短さが速さを決定する、ゴルフコンペだったのです。
実装1:ベンチマーク
x86
name elapsed[sec] average[usec] ======================================== apr 59.379924 2.375197 ip-country 3.739187 0.149567 yasui-a 2.727045 0.109082 # インラインアセンブラ yasui-c 0.975544 0.039022 # C言語 hamano-1 0.234664 0.009386560
実装2:このコードのウリ
最初の実装で十分早かったのですが、この頃には細部までチューニングされたもっと早い実装が登場してきていたので、こちらも負けずとチューニングを行ってみることにしました。
次の実装はもう少しメモリを使用して大きなテーブルを使うことにしました。
この実装は、最初の bigtable でメモリを 32M 使用しますが、lookup が 2 回で済むの以前の実装より早くなりました。
実装2:コード解説
判定のコードはこんな感じです。ネットワークオーダーでの下位 24bit と残りの1オクテットが使いたかったので。union を定義しています。
typedef union{
uint32_t all;
unsigned char o[4];
}addr_t;
const char *cidr_lookup(addr_t *addr, int len)
{
return type[tab[bigtab[addr->all & 0xffffff]][addr->o[3]]];
}
実装2:ベンチマーク
x86
name elapsed[sec] average[usec] ======================================== apr 59.379924 2.375197 ip-country 3.739187 0.149567 yasui-a 2.727045 0.109082 # インラインアセンブラ yasui-c 0.975544 0.039022 # C言語 hamano-1 0.234664 0.009386 hamano-2 0.142496 0.005700
x86_64
name elapsed[sec] average[usec] ======================================== apr 52.340651 2.093626 ip-country 0.664034 0.026561 yasui-c 0.706095 0.028244 hamano-2 0.107557 0.004302
とうとうマシン語にして 10 ステップ程度となり、これ以上の最適化は大変そうなので、ここで断念することにしました。
最後に、この実験で使用したコードを載せておきます。探索以外の部分のコードはあまりキレイに書けていませんがご了承くださいm(--)m
続きを読む社内コードコンペ - お題：最速なCIDRブロックマッチ判定 〜 安井の場合: バイナリサーチのあれとこれ〜
|
|
おさらい
- #1 ひろせの場合 - IP::CountryとAPRを使ってみた
- #2 安井の場合: バイナリサーチのあれとこれ ←今回
- #3
- #4
前回に引き続きコードコンペのお話で、今回は安井の出番です。 前回は導入だったせいもあり、あまり速いコードはできてきませんでしたが、さてさて今回はどうでしょうか。
このコードのウリ
「IPアドレスのマッチング」とは、言い替えれば「32ビット値の検索」です。そこで私の中で真っ先に頭をよぎったのは、バイナリサーチ（二分探索）という手法でした。今回のネタはデータ数が300個弱ということなので、 IP::Country のようにビット単位で二分木検索するよりも、ソート済みのリストからバイナリサーチしたほうが計算量は少なくて済むだろうと考えました。
コード解説
泥臭い処理（ファイルからCIDRブロックを読み込んでソート済みの配列を生成する部分）は末尾に掲載します。
ここでは、ソート済みのCIDRブロックリストから、IPアドレスを検索する関数を紹介します。（とはいってもある種お決まりのコードですけどね(^^;
cide_lookup()
char *cidr_lookup(void *ipaddr, int len)
{
int half;
int cmin = 0;
int cmax = listcount;
uint32_t addr;
if(len != 4)
return(NULL);
addr = ntohl(*(uint32_t *)ipaddr);
/* バイナリサーチで範囲を絞りこむ */
while(cmax - cmin > 7){
half = (cmin + cmax)>>1;
if(addr < cidrlist[half]){
cmax = half;
}else{
cmin = half;
}
}
/* 絞りこんだ結果((最大7個)の中からマッチするものを探す */
while(cmin<(cmax--)){
if((addr & masklist[cmax]) == cidrlist[cmax]){
return(typelist[cmax]);
}
}
return(NULL);
}
通常のバイナリサーチの実装では、検索終了条件を以下のようにすると思います。
- 目的の値が見付かったとき
- (cmin == cmax)になっても目的の値が見付からなかったとき
- 配列に格納されているのはCIDRブロックのネットワークアドレスなので
- 検索対象のIPアドレスとの同値データは存在しない
- ネットマスクとのANDをとらなければマッチしているか判定できない
- ネットワークアドレスが同じでネットマスク長が異なるケースが考えられる
- 192.168.0.0/16
- 192.168.0.0/17
- 192.168.0.0/18
- このような場合、192.168.0.1は(3)にマッチしなければいけない
アセンブラでも書いてみた
もう、だいぶ昔の話になりますが、アセンブラ（6502,Z80,68000)で遊んでいた時期がありました。ちょうどそのころ、バイナリサーチ、バブルソート、クイックソートなどの「アルゴリズム」と呼ばれるものにはじめて遭遇し、「これはすごい！」と純粋に感動していたことを覚えています。
その記憶が甦ったのか、なにを血迷ったのかわかりませんが、なぜかふと、「cidr_lookupをアセンブラで書き直せばもっと速くなるんでね？」と思い、インラインアセンブラで書き直してみたのがこちらのコードです。処理の内容は上記のものとまったく同じです。
そして、それぞれでベンチマークをとってみたところ、このような結果になりました。
※gccの最適化オプションは-O3を指定しました。
結果をみてびっくりしました。Cで書いた方が圧倒的に速かったのです。 アセンブラで書いたコードは、そのままでは64bit環境で動かないですし、メンテナンス性もわるいですし、コーディングにも時間がかかります。それでも高速に動作すれば使いどころはあるかなあと思っていましたが、今回は少し残念な結果に終わってしまいました。コンパイラの最適化ってすごいです！さすがです。
おわりに
今回の件で、単純にアセンブラで書き直しただけでは速くならないことを体感しました。しかし、このアセンブラのコードも、まだまだ高速化できる余地がいっぱい残っています。（というか、ツッコミどころ満載かもしれません(^^;;
どれだけコンパイラに近付くことができるかわかりませんが、もっと速くなるようにもう少しいじってみたいと思います。「この辺をこうしたら速くなるぞ」みたいなアドバイスをいただけると、大変ありがたいです。
ベンチマーク
5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。
ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。
x86
name elapsed[sec] average[usec] ======================================== apr 59.379924 2.375197 ip-country 3.739187 0.149567 yasui-a 2.727045 0.109082 # インラインアセンブラ yasui-c 0.975544 0.039022 # C言語
x86_64
name elapsed[sec] average[usec] ======================================== apr 52.340651 2.093626 ip-country 0.664034 0.026561 yasui-c 0.706095 0.028244続きを読む
社内コードコンペ - お題：最速なCIDRブロックマッチ判定 〜 ひろせの場合 - IP::CountryとAPRを使ってみた 〜
|
|
突然始まった社内コードコンペ
ある晴れた日のことです。 「とあるIPアドレスが、 予め与えられている複数のCIDRブロックのどれかに含まれるかどうか」、 を判定するロジックを書こうとしていました。
どうせならばと、いくつか違った方法で実装してみてベンチマークをとって最良のものを採用しようと思い、いく通りかの実装方法を考えてみました。この方法は速そうだけどメモリ消費が多そうとか、この方法は明らかに遅いけど一応実装してみるかーなどなど。
ってなことを社内IRCであーでもないこーでもないとひとりつぶやきながらコードを書いていたところ、案の定、興味を持った何人かが釣れました。フフフ。
そんな流れで釣れたエンジニアを巻き込んで、お題についてコードを書いて競う社内コードコンペがはじまりました(ちなみに、優勝賞品はカレーです)。
お題自体はそれほど複雑なものではないのですが、書く人によって意外と趣向が違ったりしておもしろかったので、 本エントリも含めこれから何回かにわけて、参加者自らが自分のコードの解説や自慢をするエントリをお届けしたいなと思います。
お題
まず、お題についてまとめておきます。
- 『グループ』は複数のCIDRブロックから成り立っています
- 『グループ』は複数あります
- とあるIPアドレスが、どの『グループ』に所属するかを、当該グループのいずれかのCIDRブロックに含まれるかどうかで判断する、というのがお題です。
- もし、グループを越えて含まれるCIDRブロックが複数ある場合は、よりネットマスクが長いものを採用します。
- ベンチマークでは、CIDRマッチ処理の部分のみを計測対象とし、初期化処理は測定対象には入れません
具体例はこんな感じです。
2つのファイル、yaoyaとsakanayaがあり中身はこうだとします。
$ cat yaoya 172.16.0.0/16 $ cat sakanaya 10.0.1.0/24 10.1.1.0/24 10.2.1.0/24
そして、検査対象のIPアドレスが10.1.1.1だとします。
このIPアドレスは、sakanayaの2つめのCIDRの10.1.1.0/24に含まれるので、グループsakanayaに属している、ということになります。
本データでは、グループ数が20個程度、総CIDRブロック数が270個程度です。つまり、それほど大きなデータではありません。
このコードのウリ
というわけで、第1回はひろせのコードです。こんにちは。
モットーはいかにコードを書かないで済ますかｗで、既存の実装の流用やライブラリを使って書いてみました。
最初にお伝えしておくと、わたしのコードがいちばん遅かったです。壊滅的に遅かったです。次回以降はびゅんびゅんに速いコードが出てきますので、今回は導入程度と思っていただき、おもしろげなコードは次回以降にご期待ください。
コード解説
今回は2種類紹介します。APRを使ったものと、IP::Countryのコードを流用したものです。
共通部分
まずは共通部分のコードを。次回以降もこの部分は共通です。
cidr_initialize()で初期化処理をして、cidr_lookup()でマッチ判定をやります。 cidr_loopupには、コマンドの引数で指定されたIPアドレスをstruct in_addrに変換して渡しています。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
void cidr_initialize();
char *cidr_lookup(void *ipaddr, int len);
int main(int argc, char *argv[]) {
int i, j;
int nipaddr = argc - 1;
char *label;
struct in_addr addrs[nipaddr];
if (argc < 2) {
fprintf(stderr, "missing argument\n");
return -1;
}
nipaddr = argc - 1;
for (i=0; i<nipaddr; i++) {
int ret = inet_aton(argv[i+1], addrs+i);
if (!ret) {
fprintf(stderr, "bad address: %s", argv[i+1]);
return -2;
}
}
cidr_initialize();
for (j=0; j<nipaddr; j++) {
label = cidr_lookup((void *)&addrs[j].s_addr, 4);
printf("result: %s = %s\n", argv[j+1], label);
}
return 0;
}
その1 APRのapr_ipsubnet_test
長いわりには見るところが少ないので、コードは末尾に掲載します。
初期化関数のcidr_initialize()では、CIDRのデータファイル群を読んで、APRの関数apr_ipsubnet_create()でcidrlist[]を用意しています。
判定関数のcidr_loopup()では、cidrlist[]のそれぞれについて、マッチするかどうかapr_ipsubnet_test()を使って判定しています。
このあたりの処理は、実はApacheのAllowやDenyディレクティブで、CIDRブロックが指定された場合のと同じです。
さてさて、このコードはかなり遅いです。
APRのAPIを使う以上、初期化処理などが必要なのは仕方ないのですが、それよりなにより判定処理がリニアなので、CIDRブロックの数が多くなればなるほど遅くなるのは火を見るより明らかです。
なのでこのコードは、最速を目指しているのではなく、比較用にApacheのAllow, Denyと同じ実装のものを用意してみた、といった位置づけと思ってください。
参考：
その2 IP::Country
お次は、PerlのモジュールであるIP::Countryからロジックを拝借したものです。
IP::Countryは、IPアドレス帯と国名の対応データベースを元に、とあるIPアドレスがどの国に割り当てられているかという情報を返すものなのですが、これのデータを差し換えて、今回のお題に使っちゃおうというのが魂胆です。
さて、IP::CountryにはIP::Country::Fastというものが含まれていて、これはどんな処理をするかというと、CIDRを(最大で)32bitのビットの並びとしてみて、0と1で二分木を構築しておきます。で、判定処理をするときは、この二分木を辿ってリーフから国名を取り出します。
末尾にベンチマークの結果を掲載しますが、APRのに比べると段違いで速いです。 採用するのはこのコードでいいかなーと思っていたのですが、コンペ参加者によりこの記録はあっさりと抜かれることとなります...
参考：
おわりに
今回のコードはなんのヒネリもなく、面白味という点ではちょっと物足りなかったのではないかと思います。が、今回は導入ということでご容赦いただき、次回以降にご期待いただければ！と思います。
ベンチマーク
5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。
ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。
x86
name elapsed[sec] average[usec] ======================================== ip-country 3.739187 0.149567 apr 59.379924 2.375197
x86_64
name elapsed[sec] average[usec] ======================================== ip-country 0.664034 0.026561 apr 52.340651 2.093626続きを読む
サタデーにコードをフィーバーしてきました！
|
|
そんなわけで、気分をかえてウノウで趣味の開発してみませんか？ のエントリを見た瞬間、迷わずメールを出していました。
続きを読む
オープンソースを楽しむエンジニア達のこだわり 〜 デバッグ情報を得る
|
|
前回、ftrace で引数を表示するためにスタックフレームの位置を得る方法を 紹介しましたが、実際に引数の値を得るためにはプロトタイプ情報(引数の数 や型情報)が必要になることが解りました。
通常通りコンパイルした実行バイナリファイルには変数の型情報は含まれてい ませんが gcc のコンパイルオプションに -g を付けるとオブジェクトファイ ルに型情報を含め、様々なデバック情報を含めることが出来ます。今回はこのデバッグ情 報の詳細と利用する方法について紹介してみたいと思います。
続きを読む
PHP Extension を作ろう第１回 - まずは Hello World
|
|
ひとつは PEAR のように PHP でクラスライブラリを作る方法、もう一つが今回紹介する PECL の様に PHP 自体を拡張するモジュールを書く方法です。
ひとつは、過去に C で書かれた既存のライブラリを流用したい場合に PHP Extension を作成すれば自然に PHP のコードに結合することが出来ます。また、PEAR の様に PHP で書いたコードと比べると若干高速になります。
続きを読む
ディレクティブの処理と設定値の利用 (apache module 開発事初め その3)
|
|
今回は前回の記事で予告した通り，Apache の(いくつかのタイプの)モジュールが動作するべきか否かをどうやって判断するか，というお話です．タイトルは「ディレクティブの処理」となっていますが，モジュールがディレクティブを処理することと今回のテーマは密接に結びついています．
続きを読むアクセス制御モジュールを作ってみる (apache module 開発事初め その2)
|
|
前回の記事では，apxs が生成したテンプレートをそのまま動かしてみましたが，今度は少しコードを書いてみましょう．同じ handler を作っても面白くないので，アクセス制御をするモジュールにしてみます．Apache のアクセス制御は2種類あって，一つはユーザ認証を目的としたもので，mod_auth の眷属がそれです．もう一つはリクエストの別の側面，例えばクライアントのアドレスによってアクセスを許可したり拒否したりするもので，標準モジュールでは mod_access がそれに当たります．あまり複雑なことをしても話が見えにくくなるので，今回作るモジュールではランダムにアクセスを許可したり拒否したりすることにします．
