Выполняет ли epoll () свою работу в O (1)?

в Википедии написано

в отличие от старых системных вызовов, которые работайте на О (Н), эполл работает внутри O (1) [2]).

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

однако, исходный код в fs/eventpoll.c на Linux-2.6.38, кажется, он реализован с деревом RB для поиска, которое имеет 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)
{

на самом деле, я не мог видеть ни одной man-страницы, говорящей, что сложность epoll () - O(1). Почему он известен как O (1)?

1 53
linux network-programming epoll

1 ответ:

это имеет смысл только для ep_find. Я провел всего несколько минут с ним и я вижу ep_find только называется epoll_ctl.

так действительно, когда вы добавляете дескрипторы (EPOLL_CTL_ADD) эта дорогостоящая операция выполняется. Но когда делать реальная работа (epoll_wait) это не так. Вы только добавить дескрипторов в начале.

в заключение, это не достаточно, чтобы спросить сложность epoll, так как нет epoll системный вызов. Вы хотите индивидуальные сложности epoll_ctl,epoll_wait etc.

прочее

есть и другие причины, чтобы избежать select и использовать epoll. При использовании select вы не знаете, сколько дескрипторов требует внимания. Поэтому вы должны следить за самым большим и петлей к нему.

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

теперь epoll это намного чище:

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