Работает ли epoll () в O (1)? - PullRequest
Новая
       66

Работает ли epoll () в O (1)?

54 голосов
/ 25 июня 2011

Википедия говорит

в отличие от старых системных вызовов, которые работают на O (n), epoll работает на O (1) [2]).

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

Однако исходный код в fs / eventpoll.c в Linux-2.6.38, похоже, реализован с помощью дерева RB для поиска, которое имеет O (logN) * ​​1010 * 

/*
 * 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)
{

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

1 Ответ

24 голосов
/ 25 июня 2011

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

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

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

Прочие вещи

Существуют другие причины, по которым следует избегать 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 */
}
...