moratorium

2007年11月20日

研究室で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)の曲線になってませんな...。

trackbackURL:

いや、それはたぶん同じことを言っていて、リンク先のほうは「ひとつのコネクションを裁くのにかかる時間」なのではー

いや、そりゃまぁそうなんですが、元記事だと1万コネクションになっても対した問題にならなさそうな言い方だと思ったんですね。

1万回程度loopしても対した問題にならないんじゃ？という反論が来てもまぁそうかとなってしまう説明の仕方だなぁと。でもO(n ^ 2)だと話は違いますよね。

というエントリでした。舌足らずで申し訳ないですが。