epoll()函数能够在O(1)时间内完成其工作吗？

Question

维基百科指出，与旧的系统调用一次操作O(n)相比，epoll的操作复杂度为O(1) [2]。

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

然而，在Linux-2.6.38的fs/eventpoll.c源代码中，它似乎使用了红黑树进行搜索实现，其时间复杂度为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)
{

实际上，我没有看到任何一个 man 页会说 epoll() 的复杂度是 O(1)。为什么它被称为 O(1)？

- ddoman

---

我会点赞的，因为你确实做了功课，但是我的每日投票已经用完了 :P - user456814

@ddoman的意思是，你在提问之前自己做了一些先前的研究。许多新用户（和老用户！）在Stack Overflow上甚至都不愿意这样做。 - In silico

研究，为了进行研究 :) - user456814

嗯，谷歌似乎同意这一点。 - Caffeinated

说“epoll”的运行时间是O(1)有些不准确。就添加和删除描述符而言，epoll 的运行时间是O(log(n))，就准备好的描述符而言，它是O(n)，而就监视 描述符而言，它是O(1)——这也是epoll的全部意义所在。添加/删除描述符是一件很少发生的事情，等待准备好则很频繁，您通常会将许多个描述符放入集合中，而这些描述符实际上都没有准备好。就此而言，虽然epoll 实际上并不 是真正的O(1)，但是它在最重要的地方确实是如此。常见情况很快，不常见情况则不是。 - Damon

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 */
}

- cnicutar

---

select返回准备好的fd数量，在最坏的情况下，你需要遍历它们所有（如果maxfd有事件）。 - nos

@nos 你会如何使用那个数字来替换循环？ - cnicutar

有些地方需要一个文件描述符列表。如果我使用select，我经常使用一个链表。int handled = 0; while(client) { if(FD_ISSET(client->fd,read_set) {handle(client); handled++; } if(handled == rc) break; client = clients->next;} 只需检查实际监视的FD，无需从0到rc进行检查，并且在处理完select报告的所有事件后无需再检查更多的fds。 - nos

是的，你说得对，你可以缩短循环。但是，正如你在评论中正确指出的那样，在不幸的情况下，如果“末尾”附近的描述符需要注意，仍然必须处理所有列表。如果该列表很大且描述符是第一个和最后一个... - cnicutar

Answer 2

我认为如果你请求1个事件，使用epollet时，epoll wait是O(1)的。如果使用一个不错的哈希表实现，upd和add可以平摊为O(1)。

这需要进行检查，并且man页面应该提到复杂度！

- Christophe Raffalli