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

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

в отличие от более старых системных вызовов, которые работают на O (n), epoll работает в 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)
{

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

Ответ 1

Это имеет смысл, если вы ищете 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 */
}