epoll と kqueue について思ったことの垂れ流し

programming

C10K Problem では、epoll/kqueue は速く、select/poll などは遅い、というのをよく見かける。実際ベンチマーク結果を見ると、そのように見える。計算量的には、epoll/kqueue は O(log2N)、select/poll は O(N) のように見える。ベンチマーク結果は libevent のページに掲載されているものなどが参考になる。epoll に関してはおそらく epoll_wait() のみで、epoll_ctl() は入っていないと思われる。


計算量から考えると、select/poll は線形な実装で、epoll/kqueue は何かしら木を使った実装なのかな、と予想できる。木構造を使っていれば、要素の追加・削除も大抵は O(log2N) で済むだろう。イベントが発生したときに通知する処理は、配列に対して行われるので O(N) になるだろう。ただ、select/poll は変化がないものも返すので遅いらしい。


この辺を考えていてふと思ったんだけど、epoll/kqueue はファイル記述子をキーにしたハッシュを使えばもう少し速くなるんじゃないかな。ハッシュは基本的に計算量が O(1) で済むし。よく分かってないが、Linux や BSD などでは、ファイル記述子は 0 が標準入力、1 が標準出力、2 が標準エラー出力となっていて、プロセスでファイル記述子を使うと 3 以降が使われる。これは使うたびに 4、5、6・・・となっていって、5 を閉じて新たにファイル記述子を使うと、7 ではなく 5 が再び利用出来る。この挙動については open() の manpage に記載されている。POSIX の仕様？


なので、キーの範囲は正の整数かつ小さい値から順に使われるというとてもナイスな特性を持つ。最大接続数を制限してやれば、単純にファイル記述子をキーにしたテーブルを作ってしまえばいい。65536 個の接続を捌くにしても、64K x N バイト程度で済むので大した問題ではないように思える。コードもすごくシンプルになる。このままだと使用されているファイル記述子をたどるのが面倒なので、逆引きできるようにしておく。


epoll も kqueue もそうだが、結果を配列に入れて返すというのがイマイチだと思う。コールバック指定するからそれを呼び出してよ、と思う。そっちの方が効率いい気がする。つうことは、I/O 多重化よりも 非同期 I/O の方が効率いいのかな。この辺は、KLab さんの資料も参考になる。

そういう意味では、Windows の I/O 完了ポートが最強なのかな。