Does epoll(), do its job in O(1)?

Question

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

Answer 1

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