58

Wikipedia says

unlike the older system calls, which operate at O(n), epoll operates in O(1) [2]).

http://en.wikipedia.org/wiki/Epoll

However, the source code at fs/eventpoll.c on Linux-2.6.38, seems it is implemented with an RB tree for searching, which has O(logN)

/*
 * Search the file inside the eventpoll tree. The RB tree operations
 * are protected by the "mtx" mutex, and ep_find() must be called with
 * "mtx" held.
 */
static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd)
{

In fact, I couldn't see any man page saying the complexity of epoll() is O(1). Why is it known as O(1)?

4

1 回答 1

27

一旦你寻找ep_find. 我只用了几分钟,我看到ep_find它只被调用epoll_ctl

因此,确实,当您添加描述符 ( EPOLL_CTL_ADD) 时,会执行昂贵的操作。但是当做真正的工作时(epoll_wait)它不是。您只需在开头添加描述符。

总之,仅仅问 的复杂性是不够的epoll,因为没有epoll系统调用。您想要等的个体复杂性epoll_ctlepoll_wait

其他的东西

还有其他原因要避免select和使用epoll. 使用select时,不知道需要注意多少个描述符。所以你必须跟踪最大的并循环到它。

rc = select(...);
/* check rc */
for (s = 0; s <= maxfd; s++) {
    if (FD_ISSET(s)) {
        /* ... */
    }
}

现在epoll它更干净了:

nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
/* check nfds */
for (n = 0; n < nfds; ++n) {
    /* events[n].data.fd needs attention */
}
于 2011-06-25T09:55:25.653 回答