Why epoll is More Efficient Than select/poll

In network programming, understanding the differences between I/O multiplexing models like select, poll, and epoll is key to building high-performance servers.

Let's explore why epoll is overwhelmingly more efficient.

Starting with their commonalities, select/poll and epoll are both system calls designed to implement I/O multiplexing.

They both real-time check which sockets have incoming data or are ready to send data. When there are no events, they put the process to sleep to conserve CPU resources. Among the monitored sockets,

if even one becomes ready for an operation, they wake up the process to notify that there are tasks ready to be worked on.

Data Copy Cost to Kernel: Memory Copy #

The most intuitive difference lies in how they manage the list of monitored targets.

• select/poll: Each time they are called, the entire list of file descriptors to be monitored must be copied from user space to kernel space. Passing thousands of FDs to the kernel every time places a burden on the CPU.
• epoll: With the epoll_ctl function, an interest list can be pre-registered within the kernel. Subsequently, when epoll_wait is called, only FDs with changes need to be exchanged, eliminating the overhead of copying the entire list every time.

Data Structure and Search Time Complexity #

The performance difference is stark in how the kernel manages file descriptors and checks for state changes.

select/poll is O(N)

• It uses a simple array (poll) or bitmap (select) structure.
• To determine which data has arrived, it must loop through all FDs from beginning to end.
• The problem is that even if only 1 out of 10,000 connected clients sends data, the kernel still has to check all 10,000 FDs.

epoll is close to O(1)

• It uses a red-black tree and a ready list (doubly linked list) internally within the kernel.
  • red black tree: Handles insertion, deletion, and searching of FDs in O(log N) time.
  • Ready List: A list that specifically collects FDs where events have occurred.
• When data arrives via a hardware interrupt, the kernel immediately places the corresponding FD into the ready list. Since epoll_wait only returns information from the ready list, its performance scales proportionally to the number of events that occurred, regardless of the total number of connected clients.

Event Detection Method: Level Triggered vs. Edge Triggered #

epoll supports the Edge Trigger (ET) mode, which is not available in select/poll.

• Level Trigger: Continuously sends notifications as long as a specific state persists. It keeps notifying even if data remains in the buffer.
• Edge Trigger: Notifies only at the moment a state changes, exactly once when new data arrives.
  • Its advantage is that it can drastically reduce unnecessary system calls, enabling extreme performance optimization. However, programming complexity increases.

In summary, the select/poll approach involves traversing the entire list to check who sent data, whereas epoll only checks those who sent data.

Therefore, there's a stark difference in copy costs and FD search speed, and epoll's support for ET reduces overhead.

FD Exchange #

The reason for passing FDs is to ask the kernel to monitor these channels of interest for any changes.

All I/O, such as network sockets or files, is managed by the operating system. However, the actual data processing is done by user applications.

Essentially, when a user program wants to know if data is arriving on socket 1 and if socket 5 is ready to send data, it passes a list to the kernel.

FDs are used because in Unix-like systems, all resources (sockets, pipes, etc.) are managed by a numerical identifier called an FD.

Without select or epoll, we would have to call read to read data from a single socket and remain blocking until data arrives.

If there are 1000 connections, we would either have to create 1000 threads or check them one by one sequentially, which is highly inefficient.

Instead, by passing a list of FDs to the kernel all at once, the kernel monitors them simultaneously. When an event occurs on any FD, it signals and wakes up the process to execute.