linux - epoll() 是否在 O(1) 中完成工作？

Question

维基百科说

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

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

但是，Linux-2.6.38 上 fs/eventpoll.c 的源代码， 似乎它是用一个用于搜索的 RB 树实现的，它有 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)
{

事实上，我看不到任何手册页说 epoll() 的复杂性是 O(1)。 为什么称为 O(1)？

Answer 1

只要您查找 ep_find，这就是有意义的。我只用了几分钟，我看到 ep_find 只被 epoll_ctl 调用。

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

总之，问epoll的复杂度是不够的，因为没有epoll系统调用。您想要 epoll_ctl、epoll_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 */
}