2008年07月31日
社内コードコンペ - お題：最速な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
実装1:コード
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <dirent.h>
#include <string.h>
#include <fcntl.h>
#include <libgen.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#define DBDIR "../data"
#define MAX_TYPE 30
static char type[MAX_TYPE][PATH_MAX];
int type_index = 1;
#define MAX_TAB 1024
static unsigned short tab[MAX_TAB][256];
int tab_index = 1;
void add_tab(uint32_t addr, char type){
int i1, i2, i3;
if(tab_index + 3 > MAX_TAB){
fprintf(stderr, "error: few table\n");
return;
}
if(!(i1 = tab[1][addr >> 24 & 0xff])){
tab_index++;
i1 = tab[1][addr >> 24 & 0xff] = tab_index;
}
if(!(i2 = tab[i1][addr >> 16 & 0xff])){
tab_index++;
i2 = tab[i1][addr >> 16 & 0xff] = tab_index;
}
if(!(i3 = tab[i2][addr >> 8 & 0xff])){
tab_index++;
i3 = tab[i2][addr >> 8 & 0xff] = tab_index;
}
tab[i3][addr & 0xff] = type;
}
int getnetmask(int n, uint32_t *netmask)
{
uint32_t h = 1;
uint32_t m = 0xffffffff;
if(n>32)
return(0);
n = 32 - n;
while(n--){
m -= h;
h *= 2;
}
*netmask = m;
return(1);
}
int initread(int fd, char file)
{
int r;
int l;
char buff[256];
char *p = buff;
uint32_t ad;
uint32_t nm = 0;
char ip[64];
uint32_t max;
strcpy(type[0], "(null)");
while((r=read(fd,p,1)) != 0){
if(r == -1)
return(-1);
if(*p == '#')
*p = 0;
if(*p == '/')
*p = ' ';
if(*p == '\r')
*p = 0;
if(*p == '\n'){
*p = 0;
l = 32;
if(sscanf(buff,"%s%d", ip, &l) < 1){
/***** not ip addr ******/
if(buff[0]){
fprintf(stderr,"read error: %s(%s/%d)\n",buff,ip,l);
}
}else{
if(!inet_aton(ip, (struct in_addr *)&ad)){
fprintf(stderr,"ip addr error: %s\n", buff);
}
if(!getnetmask(l,&nm)){
fprintf(stderr,"netmask error: %s\n", buff);
}
ad = ntohl(ad);
ad &= nm;
max = (1 << (32 - l)) + ad - 1;
while(ad <= max) add_tab(ad++, file);
}
p = buff;
continue;
}
p++;
}
return(0);
}
char alloctype(char *name)
{
char path[PATH_MAX];
strcpy(path, name);
strcpy(type[type_index], basename(path));
return type_index++;
}
void cidr_initialize()
{
int f;
DIR *d;
char path[PATH_MAX];
struct dirent *e;
struct stat st;
if((d=opendir(DBDIR)) != 0){
while((e=readdir(d)) != 0){
sprintf(path,"%s/%s", DBDIR, e->d_name);
if(stat(path, &st) != 0)
continue;
if(!S_ISREG(st.st_mode))
continue;
f = open(path, O_RDONLY);
if(f == -1){
fprintf(stderr,"file open error %s\n", path);
}else{
initread(f,alloctype(path));
close(f);
}
}
}
}
static inline void inet_aton2(char *p, char *o) {
int i=0;
do{
while (*p != '.' && *p) {
o[i] *= 10;
o[i] += *p++ - '0';
}
i++;
}while(*p++);
}
const char *cidr_lookup(unsigned char *addr, int len)
{
return type[tab[tab[tab[tab[1][addr[0]]][addr[1]]][addr[2]]][addr[3]]];
}
実装2:コード
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <dirent.h>
#include <string.h>
#include <fcntl.h>
#include <libgen.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#define DBDIR "../data"
typedef union{
uint32_t all;
unsigned short half[2];
unsigned char o[4];
}addr_t;
typedef struct{
unsigned char type;
uint32_t addr;
size_t len;
}cidr_t;
#define MAX_TYPE 50
static char type[MAX_TYPE][PATH_MAX];
static char *typep[MAX_TYPE];
int type_index = 1;
#define MAX_TAB 1024
static unsigned short tab[MAX_TAB][256];
int tab_index = 1;
static unsigned short bigtab[0x1000000];
#define MAX_CIDR 1024
void add_tab(uint32_t addr, char type){
int i1, index;
if(tab_index + 3 > MAX_TAB){
fprintf(stderr, "error: few table\n");
return;
}
index = addr >> 24 | (addr >> 8 & 0xff00) | (addr << 8 & 0xff0000);
if(!(i1 = bigtab[index])){
tab_index++;
i1 = bigtab[index] = tab_index;
}
tab[i1][addr & 0xff] = type;
}
int getnetmask(int n, uint32_t *netmask)
{
uint32_t m;
if (n < 0 || 32 < n) return 0;
m = 1UL << (32 - n);
--m;
*netmask = ~m;
return 1;
}
int initread(int fd, unsigned char t, cidr_t *cidr, unsigned int *cidr_num)
{
int r;
int l;
char buff[256];
char *p = buff;
uint32_t ad;
uint32_t nm = 0;
char ip[64];
while((r=read(fd,p,1)) != 0){
if(r == -1)
return(-1);
if(*p == '#')
*p = 0;
if(*p == '/')
*p = ' ';
if(*p == '\r')
*p = 0;
if(*p == '\n'){
*p = 0;
l = 32;
if(sscanf(buff,"%s%d", ip, &l) < 1){
/***** not ip addr ******/
if(buff[0]){
fprintf(stderr,"read error: %s(%s/%d)\n",buff,ip,l);
}
}else{
if(!inet_aton(ip, (struct in_addr *)&ad)){
fprintf(stderr,"ip addr error: %s\n", buff);
}
if(!getnetmask(l,&nm)){
fprintf(stderr,"netmask error: %s\n", buff);
}
ad = ntohl(ad);
ad &= nm;
cidr[*cidr_num].addr = ad;
cidr[*cidr_num].len = l;
cidr[*cidr_num].type = t;
(*cidr_num)++;
}
p = buff;
continue;
}
p++;
}
return(0);
}
unsigned char alloctype(char *name)
{
char path[PATH_MAX];
strcpy(path, name);
strcpy(type[type_index], basename(path));
typep[type_index] = type[type_index];
return type_index++;
}
/* qsort compare function */
static int cmplen(const void *p1, const void *p2)
{
const cidr_t *c1 = p1;
const cidr_t *c2 = p2;
return c1->len > c2->len;
}
void cidr_initialize()
{
int f;
DIR *d;
char path[PATH_MAX];
struct dirent *e;
struct stat st;
int i;
uint32_t addr, max;
cidr_t cidr[MAX_CIDR];
unsigned int cidr_num = 0;
typep[0] = NULL;
if((d=opendir(DBDIR)) != 0){
while((e=readdir(d)) != 0){
sprintf(path,"%s/%s", DBDIR, e->d_name);
if(stat(path, &st) != 0)
continue;
if(!S_ISREG(st.st_mode))
continue;
f = open(path, O_RDONLY);
if(f == -1){
fprintf(stderr,"file open error %s\n", path);
}else{
initread(f, alloctype(path), cidr, &cidr_num);
close(f);
}
}
}
qsort(cidr, cidr_num, sizeof(cidr_t), cmplen);
for(i=0; i<cidr_num; i++){
addr = cidr[i].addr;
max = (1 << (32 - cidr[i].len)) + addr - 1;
while(addr <= max) add_tab(addr++, cidr[i].type);
}
}
const char *cidr_lookup(addr_t *addr, int len)
{
return typep[tab[bigtab[addr->all & 0xffffff]][addr->o[3]]];
}
