KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Wikipedia says unlike the older system calls, which operate at O(n), epoll operates in O(1) [2]). http://en.wikipedia.org/wiki/Epoll However, the source code at fs/eventpoll.c on Linux-2.6.38, seems it is implemented with an RB tree for searching, which has 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) { In fact, I couldn't see any man page saying the complexity of epoll() is O(1). Why is it known as O(1)?
Tags (comma-separated)
Save Edits
Cancel