Home > Unix > epoll(2)とselect(2)の計算量

epoll(2)とselect(2)の計算量

研究室でid:yama6がepollとか言っていて、mixi Engineers’ Blog さんの「Linux Programming、epollの話」を思い出した。

パフォーマンスの方はselect(2)とpoll(2)のtime complexityがO(n)に対しepollはO(1)と無視のできない性能の差を実現しています。

これこれ、書こうとして忘れてた。僕の理解だとepoll(2)はO(n)でselect(2)がO(n^2)です。この差はsignificantですよ！

例えば1万個のソケットを管理しているとします。で、ソケットが１個づつ順番に読み込み可能になるという最悪のシチュエーションを考えて見ます。select(2)だと10000 * 10000のループが回ります。epoll(2)だと10000 * 1回のループが回ります。

そういう上手いペースで接続をする方法を思いつかないので、実データで示せないのが申し訳ないですが。libeventのグラフもO(n ^ 2)の曲線になってませんな…。

Comments:2

しろきゃぴたん 07-11-21 (Wed) 11:55: いや、それはたぶん同じことを言っていて、リンク先のほうは「ひとつのコネクションを裁くのにかかる時間」なのではー
kzk 07-11-21 (Wed) 17:18: いや、そりゃまぁそうなんですが、元記事だと1万コネクションになっても対した問題にならなさそうな言い方だと思ったんですね。
1万回程度loopしても対した問題にならないんじゃ？という反論が来てもまぁそうかとなってしまう説明の仕方だなぁと。でもO(n ^ 2)だと話は違いますよね。
というエントリでした。舌足らずで申し訳ないですが。

Trackback URL for this entry: http://kzk9.net/blog/2007/11/epoll2.html/trackback
Listed below are links to weblogs that reference: epoll(2)とselect(2)の計算量 from moratorium

Home > Unix > epoll(2)とselect(2)の計算量