epoll（）在O（1）中做什么工作？

维基百科说

不同于在O（n）操作的较旧的系统调用，epoll在O（1）[2]中操作）。

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

然而，Linux-2.6.38上的fs / eventpoll.c的源代码似乎是用search的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时，你不知道有多less描述符需要注意。 所以你必须跟踪最大和循环。

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