editar - linux easytag

¿Tiene epoll(), hace su trabajo en O(1)?

Question

Wikipedia dice

a diferencia de las llamadas a sistemas más antiguos, que funcionan 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 de manual que diga que la complejidad de epoll () es O (1). ¿Por qué se conoce como O (1)?

Answer 1

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

Entonces, de hecho, cuando agrega los descriptores ( EPOLL_CTL_ADD ) se realiza la operación costosa. PERO al hacer el trabajo real ( 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 epoll llamada al sistema epoll . Desea las complejidades individuales de epoll_ctl , epoll_wait etc.

Otras cosas

Hay otras razones para evitar select y usar epoll . Al utilizar Select, no sabe cuántos descriptores necesitan atención. Así que debes hacer un seguimiento de lo más grande y hacer un bucle.

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