¿Epoll(), hace su trabajo en O(1)?

Question

¿Epoll(), hace su trabajo en O(1)?

Wikipedia dice

A diferencia de las llamadas al sistema más antiguas, que operar en O (n), epoll opera en O (1) [2]).

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

Sin embargo, el código fuente en fs/eventpoll.c en Linux 2.6.38, parece que está implementado con un árbol RB para la búsqueda, que tiene 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)
{

De hecho, no pude ver ninguna página man diciendo que la complejidad de epoll() es O(1). ¿Por qué se conoce como O(1)?

53

linux network-programming epoll

Author: ddoman, 2011-06-25

Source

1 answers

score 23 · Accepted Answer

Esto tiene sentido una vez que busque ep_find. Solo pasé unos minutos con él y veo que ep_find solo es llamado por epoll_ctl.

Así que de hecho, cuando se añaden los descriptores (EPOLL_CTL_ADD) que la operación costosa se realiza. PERO al hacer el verdadero trabajo (epoll_wait) no lo es. Solo agregas los descriptores al principio.

En conclusión, no es suficiente preguntar la complejidad de epoll, ya que no hay una llamada al sistema epoll. Quieres las complejidades individuales de epoll_ctl, epoll_wait sucesivamente.

Otras cosas

Hay otras razones para evitar select y usar epoll. Al usar select, no sabes cuántos descriptores necesitan atención. Así que usted debe mantener un registro de la más grande y bucle a ella.

rc = select(...);
/* check rc */
for (s = 0; s <= maxfd; s++) {
    if (FD_ISSET(s)) {
        /* ... */
    }
}

Ahora con epoll es mucho más limpio:

nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
/* check nfds */
for (n = 0; n < nfds; ++n) {
    /* events[n].data.fd needs attention */
}