2004-08-25

用事の無い急な休みはいらない!

独り言

暇だよ、暇。

急な休みだから空いてる友だちもいないし。とりあえず、Red Hat Linuxのbacklogについて実験してみた。backlogってのはBSDソケットでサーバ側がlisten呼ぶときの二つ目の引数のこと。

#include 
int listen(int s, int backlog);

man listenからbacklog関係の部分を引用しておく

backlog 引き数は、保留中の接続のキューが拡張することのできる最大長を指定する。
（中略）
注意
TCP ソケットでの backlog 引数の振る舞いは Linux 2.2 で変更された。現在ではこの引数は、受け付けられるのを待っている、完全に確立されたソケットのキューの長さを指定する。以前は不完全な接続要求の数であったが、これを置き換えた。

ここでいう不完全な接続要求というのは多分3-way-ハンドシェークのクライアントからのACK待ち状態の事だと思う（これをSYN_RCVDという）。で、確立されたソケットってのは3-way-ハンドシェークが完了したソケット（これをESTABLISHEDという）のことでしょう。

backlogの最大値はSOMAXCONNで分かる。俺の環境では128だった。一般的には（というかBSD的には）5に制限されているところを見ると十分過ぎる程の大きさだ。で、実際にいくつの接続がキューされるか調べたところ、backlogに3足して、131よりも大きいときは131にカットされ、131より小さいときはbacklog+3が用いられているようだ。

だからbacklogに0を指定しても3つはキューされる（これに頼るのはだめ）。

manから察するにlistenに与えるbacklogはESTABLISHEDな接続のキューなので、暗黙的に追加される3というのが（意味的には）SYN_RCVDな接続の為のスペースなのかな。

2004-08-23

　数式型カウンタ

その他はてな

はてなにPVモジュール（カウンタ）があることに今更気づいて、mimeTeXと組み合わせてかっこいい（ようなかっこ悪いような）カウンタにカスタマイズしようとしたけど、PVモジュールの仕様上出来ないみたい。やろうとしたのはこんなの。23408がカウンタの値で、そこにPVモジュールを投げ込もうと思ってたんだよね。

2004-08-23

fork VS vfork VS pthread

プログラム

なんとなくベンチマーク取ってみた。コードはどれも

子プロセス（別スレッド）を作成
親は子を待つ（waitpid/pthread_join）
子は何もせずにexit（pthread_exit）する。

これだけだけど、少しずつ違うパターンで測定してみた。１つはグローバル変数がまったく無い状態。もう１つはグローバル変数があるけど、使用されない状態。最後はグローバル変数があり、親も子（プロセス&スレッド）もそれに書き込む場合。グローバル変数というのは

#if defined DEC_GLOBAL_VAR || defined USE_GLOBAL_VAR
long long buf1[4098*2];
long long buf2[4098*2];
long long buf3[4098*2];
long long buf4[4098*2];
#endif

このようなもので、それを使用するというのは

buf1[0] = buf2[0] = buf3[0] = buf4[0] = 1;

というもの。forkに関して言えば下のような感じになる。

void
do_fork(void)
{
    pid_t pid;

    if ( (pid = fork()) > 0) {
#if defined USE_GLOBAL_VAR
        buf1[0] = buf2[0] = buf3[0] = buf4[0] = 1;
#endif
        if (waitpid(pid, NULL, 0) <= 0)
            syserr("waitpid");
    }
    else if (pid == 0) {
#if defined USE_GLOBAL_VAR
        buf1[0] = buf2[0] = buf3[0] = buf4[0] = 2;
#endif
        exit(EXIT_SUCCESS);
    }
    else {
        syserr("fork");
    }
}

結果は

	fork	vfork	pthread
グローバル変数無し	0.942	0.108	0.044
グローバル変数の宣言のみ	1.080	0.112	0.050
グローバル変数に書き込み	1.214	0.100	0.060

まぁ、大部分は予想通りでしょう。速度的にはpthread > vfork > forkです。vforkは普通は使わないですけど、ここぞという場面でforkのかわりに使えばかなり高速になるでしょう（ただし、man vforkは良く読まないとダメ、forkとは性質が違うし、そもそも推奨されてない）。

それよりもグローバル変数を定義したり、それを使用したときの違いのほうが興味深い。fork意外ではほとんどグローバル変数の影響を受けていないことが分かると思う。これはvforkとpthreadはプロセスのデータ空間をコピーしないので、基本的にいくらメモリを使用していても速度に影響しない（はず）。それに対してforkはこれをコピーするから遅くなる。そして最近のforkの実装ではcopy-on-write（後述）という手法を用いてデータ空間のコピーを行なうから、データに対して書き込みが無い限りはデータがコピーされない（はず）なので、グローバル変数を使用するかどうかかで速度に大きな違いがでるというわけ。

copy-on-writeってのは検索してもらえば分かると思うけど、要はプロセス空間のコピーを最初に全部やるんじゃなくて、必要なとき（空間に書きこむとき）にコピーするということ。遅延効果ってやつだね。

あぁ、clone()も実験すれば良かったかなぁ。多分pthreadと同じような結果になると思うんだけど（スレッドの内部は普通clone()で実装される）。急にpthreadのソースが見たくなったな。ちょっと見て来るか。

2004-08-22

C++によるCGIフレームワーク

ソフトウェア

C++の練習も兼ねてCGIのフレームワークを作ってみた。

WebLabor

JavaのServletとかを知っている人には馴染みやすい仕組みだと思う。このフレームワークを使えばCGIを作るときにmain関数を作る必要が無くて、指定されたクラスのサブクラスを作るだけで良いのでだいぶ作業は楽になると思う。。

日本語周りがひじょーーーーに微妙な状況です。

【追記】

string::clear()が無い環境ではコンパイル出来ない。それに加えてBSD系の環境では警告がでることが判明。どちらもすぐに修正できますが、疲れているので後ほど。ってかstring::clear()が無い環境があるのにびっくりした。とりあえず、機械的にstring::erase()に書き換えればOK。

2004-08-19

C++のコンストラクタ

プログラム

const string&を引数にとるコンストラクタがあるとき、、機械的にcosnt char *を引数にとるコンストラクタを作ると良い。例えば下のようなクラスがあるとき

class Message
{
    string msg;
public:
    Message(const string& msg_) : msg(msg_) {}
}

次のようにした方が速いことがある

class Message
{
    string msg;
public:
    Message(const string& msg_) : msg(msg_) {}
    Message(const char *msg_) : msg(msg_) {}
}

これが速くなるのは下のように初期化したときだ。

Message msg("Hello");

stringの生成される回数が１回少くなる。const char *を取らない場合は"Hello"はstring(const char *)というコンストラクタでstring型に変換され、再度msg(msg_)でstringが生成されるのに対して、const char *があるとmsgの構築のみで終わる。

生成と破棄を繰り返してベンチマーク取った。ベンチマークを取ったコードの一部はこんな感じ

for (i=0; i<COUNT; i++) {
    Message msg("Sample Message");
}

ループ回数	const char *を引数に取らないとき	const char *を引数に取るとき
1,000,000回	0.75sec	0.49sec
5,000,000回	3.66sec	2.42sec
10,000,000回	7.29sec	4.83sec

C++を使うときはいろんな暗黙の動作を知ってないといけないなぁ。

2004-08-16

桁数を求める（2）

プログラム

昨日の日記（id:kt-blackout:20040815#p1）で桁数を求める関数のベンチマークの比較を取ってみた。結果としてtype_D（昨日の日記参照）がもっとも速かったわけだけど、同日のid:PaiNさんのコメントを見て気付いたことがある。

それはベンチマークの取り方だ。昨日は0からCOUNT_MAXまでのすべての数字の桁を求めることでベンチマークとした。それも１つのやり方として間違ってはいないだろうけど、これはアルゴリズムの１つの側面でしかない。そこで、別の２通りの計測を行なってみた。それぞれの疑似ソースを見て頂きたい（COUNT_MAX=2,000,000,000）。

＜ベンチマークタイプ1＞ 0 - 10桁の全体を対象とする

for (int i=0; i

＜ベンチマークタイプ2＞ 8桁以上の数のみを対象

for (int i=0; i

＜ベンチマークタイプ3＞ 6桁未満の数のみを対象

for (int i=0; i

そして、ベンチマークを取ったのは以下の二つの関数

#define FIG_10 1000000000
#define FIG_9 100000000
#define FIG_8 10000000
#define FIG_7 1000000
#define FIG_6 100000
#define FIG_5 10000
#define FIG_4 1000
#define FIG_3 100
#define FIG_2 10
#define FIG_1 1

int type_D(int n)
{
    n = (n>=0)?n:-n;
    if      (n >= FIG_10)   return 10;
    else if (n >= FIG_9)    return 9;
    else if (n >= FIG_8)    return 8;
    else if (n >= FIG_7)    return 7;
    else if (n >= FIG_6)    return 6;
    else if (n >= FIG_5)    return 5;
    else if (n >= FIG_4)    return 4;
    else if (n >= FIG_3)    return 3;
    else if (n >= FIG_2)    return 2;
    else                    return 1;
}

int type_E(int n)
{
    n = (n>=0)?n:-n;

    if (n >= FIG_6) {
        if (n >= FIG_8) {
            if (n >= FIG_10)        return 10;
            else if (n >= FIG_9)    return 9;
            else                    return 8;
        }
        else {
            if (n >= FIG_7)         return 7;
            else                    return 6;
        }
    }
    else { /* n < FIG_6 */
        if (n >= FIG_3) {
            if (n >= FIG_5)         return 5;
            else if (n >= FIG_4)    return 4;
            else                    return 3;
        }
        else {
            if (n >= FIG_2)         return 2;
            else                    return 1;
        }
    }
}

type_D()は問題無いと思う。type_E()は桁数を二分探索で絞りこむようになっている。こうすることでどんなときも比較の回数を3,4回で求めることを可能にしている。type_Eでは見ての通り比較回数は1-9回となっているので性質が違うことが分かると思う。

# 余談。PaiNさんが言おうとしてたのはtype_Eのことでしょうか？ PaiNさんのコメントを見て「あぁ、二分探索すれば良いのか」と思ったものの、何か比較の手順が違う…。

そして結果は以下の通り。

	Bench 1（全域）	Bench 2（高域）	Bench 3（低域）
type_D	8.14000	23.65000	35.14000
type_E	10.28000	30.51000	24.81000

おし、想像通りの結果。一言で言えば、type_Eは大きな数の桁数を求めるのが遅い。極端な話10桁の数字を対象とするとtype_Dでは1回の比較ですむのが、type_Eでは3回かかるのだから当然だ。しかも皮肉なことに全域を平均的に走査すると大きな数の方が多いから、ベンチマーク1でtype_Dのほうが優勢なわけだ。同様に高域のみを対象とするベンチマーク2でもtype_Dのほうが速い。そして、低域のみを対象とするベンチマーク3ではtype_Eがダントツに速くなる。

つまりtype_Eはたしかに平均的には速いが、数字の桁数の分布というのは大きな数ほど多いので全域を対象とすると負ける。ただ一般的には極端に大きな数を扱うことは少ないので、type_Eが良いように思う。type_Dだとバランスが悪いし、得意とする桁数が6桁以上なのは別に嬉しくない。

と、今日もまた、そんなに凄くないことを、さも凄いかのように熱く書いてみた。

2004-08-15

たまに余計な事に興味を持つんですよ。

プログラム

数字の桁数を調べる方法はどんなのが良いのだろう、と。

とりあえず、誰でも思いつくであろう4種類を簡単に計測してみた。ソースは次の通り（include等は省略）

#define COUNT_MAX 20000000

int type_A(int n)
{
    int fig = 1;
    while ( (n /= 10) != 0) fig++;
    return fig;
}

int type_B(int n)
{
    n = (n>=0)?n:-n;
    if (n == 0) return 1;
    return log10(n) + 1;
}

int type_C(int n)
{
    char buf[11]; /* INT32_MAXの桁数が10なので11で十分 */
    n = (n>=0)?n:-n;
#if 0
    /* この方が速いけど、glibc 2.0.6までのものでは動かないよ */
    return snprintf(NULL, 0, "%d", n);
#endif
    snprintf(buf, 11, "%d", n); 
    return strlen(buf);
}

int type_D(int n)
{ /*intが4byteであることを決めうちしているので注意*/
    n = (n>=0)?n:-n;
    if      (n >= 1000000000)   return 10;
    else if (n >= 100000000)    return 9;
    else if (n >= 10000000)     return 8;
    else if (n >= 1000000)      return 7;
    else if (n >= 100000)       return 6;
    else if (n >= 10000)        return 5;
    else if (n >= 1000)         return 4;
    else if (n >= 100)          return 3;
    else if (n >= 10)           return 2;
    else                        return 1;
}

double bench(int (*func)(int))
{
    double start, end;
    int i;
    start = clock();
    for (i=0; i

そして結果は（恐らく想像通り）

Bench(A): 3.69000
Bench(B): 6.41000
Bench(C): 17.84000
Bench(D): 0.50000

type_A()とかtype_B()は見た目は知的に見えるけど、所詮type_D()には歯が立たない。if-elseの羅列も悪くないってことね。それだけ。