3 ms·
The O(1) part is: * It's O(1) for user mode to know which fd in the set is signaled after returning from the wait syscall. With select() or poll() the caller
by asveikau 11y ago
The O(1) part is:
* It's O(1) for user mode to know which fd in the set is signaled after returning from the wait syscall.
With select() or poll() the caller needs to traverse the list to know which fd is ready. With epoll(), kqueue(), or IOCP, you are draining a queue consuming events, each event removed from the queue in O(1) without re-scanning the entire table.
* It's O(1) to add an fd to the set of watched fds, or to re-enter the "blocked" state.
Because select() and poll() specify the entire list of watched fds all the time, the kernel side ends up copying and scanning the whole list at every wait step [O(n)], whereas epoll/kqueue/IOCP just leave the list of FDs in kernel memory across calls.
- userbinator 11y agoI was curious enough about the O(1) claims to look at the source code[1], and I don't think this is true: It's O(1) to add an fd to the set of watched fds It uses a red-black tree to keep track of the set of watched fds associated with each epoll fd, which makes insertion O(log n). However, waiting and notification can be done in O(1). [1] http://lxr.free-electrons.com/source/fs/eventpoll.c http://lxr.free-electrons.com/source/fs/eventpoll.c
- asveikau 11y agoOK, so I was being a bit fast and loose with my description of insert. What I was going for is it doesn't copy and scan the entire list every time. It's also not too hard to imagine a constant time implementation. The api would allow for it. Whereas poll is broken at the api level. It assumes O(n) at every call and there's no good way to get around it.