Epoll (), fait-il son travail dans O (1)?

Question

Wikipédia dit

contrairement à l'ancien système d'appels, qui fonctionner en O(n), epoll opère dans O(1) [2]).

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

Toutefois, le code source à fs/eventpoll.c sur Linux 2.6.38, il semble qu'il est mis en œuvre avec un RB de l'arbre de recherche, qui a 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)
{

En fait, je ne vois pas de page de manuel de dire la complexité de epoll() est O(1). Pourquoi est-il connu comme O(1)?

Answer 1

Cela fait sens une fois que vous regardez pour ep_find. J'ai seulement passé quelques minutes avec elle et je vois ep_find est appelé par epoll_ctl.

Donc en effet, lorsque vous ajoutez les descripteurs (EPOLL_CTL_ADD) que coûteuse opération est effectuée. MAIS en faisant le travail réel (epoll_wait), elle n'est pas. Vous ajoutez uniquement les descripteurs du début.

En conclusion, il ne suffit pas de demander à la complexité de l' epoll, car il n'y a pas d' epoll appel système. Vous voulez que la personne complexités de l' epoll_ctl, epoll_wait etc.

D'autres choses

Il y a d'autres raisons pour éviter select et l'utilisation epoll. Lors de l'utilisation de sélectionner, vous ne savez pas comment de nombreux descripteurs ont besoin d'attention. Donc, vous devez garder une trace de la plus grande et la boucle.

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

Maintenant, avec epoll c'est beaucoup plus propre:

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