epoll()在O(1)中完成它的工作吗？

Question

维基百科说

与在O(n)下运行的旧系统调用不同,epoll在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 */
}