epoll() 是否在 O(1) 中完成工作? [英] Does epoll(), do its job in O(1)?

问题描述

维基百科说

与旧的系统调用不同，后者运行时间为 O(n)，epoll 运行时间为O(1) [2]).

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)

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)
{

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

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

推荐答案

一旦你寻找 ep_find 就有意义了.我只用了几分钟，我看到 ep_find 只被 epoll_ctl 调用.

This makes sense once you look for ep_find. I only spent a few minutes with it and I see ep_find is only called by epoll_ctl.

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

So indeed, when you add the descriptors (EPOLL_CTL_ADD) that costly operation is performed. BUT when doing the real work (epoll_wait) it isn't. You only add the descriptors in the beginning.

总之，问epoll的复杂度是不够的，因为没有epoll系统调用.您想要 epoll_ctl、epoll_wait 等的个别复杂性.

In conclusion, it's not enough to ask the complexity of epoll, since there is no epoll system call. You want the individual complexities of epoll_ctl, epoll_wait etc.

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

There are other reasons to avoid select and use epoll. When using select, you don't know how many descriptors need attention. So you must keep track of the biggest and loop to it.

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

现在使用 epoll 会干净很多:

Now with epoll it's a lot cleaner:

nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
/* check nfds */
for (n = 0; n < nfds; ++n) {
    /* events[n].data.fd needs attention */
}

这篇关于epoll() 是否在 O(1) 中完成工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！