Ответ 1
Системный вызов опроса должен каждый раз копировать список файловых дескрипторов в ядро. Это происходит только один раз с epoll_ctl
, но не каждый раз, когда вы вызываете epoll_wait
.
Кроме того, epoll_wait
имеет значение O(1)
в отношении количества наблюдаемых дескрипторов 1 что означает, что неважно, будете ли вы ждать одного дескриптора или 5000 или 50 000 дескрипторов. poll
, будучи более эффективным, чем select
, все равно приходится перебирать список каждый раз (т.е. O(N)
в отношении количества дескрипторов).
И, наконец, epoll может в дополнение к "нормальному" режиму работать в режиме "edge triggered", что означает, что ядру не нужно отслеживать, сколько данных вы прочитали после того, как вам была указана готовность. Этот режим сложнее понять, но несколько более эффективен.
1 Как правильно указал Дэвид Шварц,
epoll_wait
, конечно, еще O(N)
в отношении происходящих событий. Вряд ли это может быть иначе, с любым интерфейсом. Если N событий происходит в дескрипторе, который просматривается, то приложение должно получать N уведомлений и должно выполнять N "вещи", чтобы реагировать на происходящее. Это опять-таки немного, но не принципиально отличается в режиме запуска по краям, где вы фактически получаете
M
события с M <= N
. В режиме запуска по краю, когда одно и то же событие (скажем, POLLIN
) происходит несколько раз, вы, вероятно, получите меньше уведомлений, возможно, только одного. Тем не менее, это не сильно меняет значительную нотацию как-то.
Однако epoll_wait
не зависит от количества просмотренных дескрипторов. В предположении, что он используется в предполагаемом, "нормальном" способе (то есть множестве дескрипторов, нескольких событий), это действительно имеет значение, и здесь оно действительно O(1)
.
Как аналогия, вы можете думать о хэш-таблице. Хэш-таблица получает доступ к своему контенту в O(1)
, но можно утверждать, что вычисление хэша на самом деле O(N)
в отношении длины ключа. Это технически абсолютно правильно, и, вероятно, существуют случаи, когда это проблема, однако для большинства людей это просто не имеет значения.