Wikipedia says
unlike the older system calls, which operate at O(n), epoll operates in O(1) [2]).
http://en.wikipedia.org/wiki/Epoll
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) {
In fact, I couldn’t see any man page saying the complexity of epoll() is O(1). Why is it known as O(1)?
Advertisement
Answer
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
.
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.
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.
Other stuff
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)) { /* ... */ } }
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 */ }