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屋！