C10K Problem では、epoll/kqueue は速く、select/poll などは遅い、というのをよく見かける。実際ベンチマーク結果を見ると、そのように見える。計算量的には、epoll/kqueue は O(log2N)、select/poll は O(N) のように見える。ベンチマーク結果は libevent のページに掲載されているものなどが参考になる。epoll に関してはおそらく epoll_wait() のみで、epoll_ctl() は入っていないと思われる。 libevent http://monkey.org/~provos/libevent/ 計算量から考えると、select/poll は線形な実装で、epoll/kqueue は何かしら木を使った実装なのかな、と予想できる。木構造を使っていれば、要素の追加・削除も大抵は O(log2N) で済むだろう。イベ