Early readiness interfaces required the program to pass its full set of file descriptors on every call and received the full set back (the select/poll style). Later ones (epoll, kqueue) register interest once and return only what changed. Explain the difference in complexity terms and why it mattered.
answer
- O(n) scan vs O(1) register + O(k) ready
- copy whole set twice per call
- kernel keeps an incremental ready list
- stateful registration = closed-handle bugs
- per-kernel APIs -> portability layer
basics
~20 sScan-based interfaces are O(n) per call in both copying and kernel work, where n is all watched handles — even if one is ready. Registration-based ones pay O(1) amortised per registration and return O(k) ready events, so cost tracks activity, not the size of the watch set.
solid answer
~60 sWith a scan-based interface every loop iteration copies the entire descriptor set into the kernel, the kernel checks each descriptor, then copies results back and the program scans them again to find the ready few. That is **O(n) per iteration for n watched handles**, repeated at event rate — so with 10,000 idle connections and one active one you do 10,000 units of work to learn about one. Registration-based interfaces split it: *register* interest once (O(1) amortised, persisted in the kernel), then *wait* returns only the handles that became ready, **O(k) for k ready events**. Cost now tracks activity, not the watch set. That turns "one busy connection among 10,000" from a 10,000-unit operation into a 1-unit one. Secondary wins: no per-call copying of large sets, no fixed descriptor ceiling that some scan APIs imposed, and the kernel can maintain a ready list incrementally as events occur. The cost is a stateful, less portable API — kernel-side registration must be kept in sync as handles are opened and closed.
code
text · 8 linesscan style, every iteration:
copy_in(all n handles) -> kernel checks n -> copy_out(n) -> user scans n
cost = O(n) per iteration, regardless of activity
registration style:
once per connection: register(handle, interest) # O(1)
every iteration: events = wait() -> returns k ready
cost = O(k) per iterationgo deeper
Know that older interfaces ask about every handle every time while newer ones remember your interest and return only what fired.
State the complexity: O(n) per call versus O(1) register plus O(k) per wait, and why that matters with many idle connections.
Add the copying and cache costs, the closed-or-duplicated-handle pitfall, and how portability layers hide the per-kernel differences.
Discuss where the next bottleneck moves — per-event system calls — and when to reach for batched submission/completion rings or kernel-bypass instead.
## Two ways to ask "which of these is ready?" Any event-driven server needs a way to park one thread until *something* among many handles becomes actionable. There are two API shapes for that question, and the difference is the difference between a linear scan and an index. **Stateless scan.** The program passes the complete set of handles it cares about on every call. The kernel walks the set, marks which are ready, and returns. The classic examples take either a bitmask of descriptors or an array of descriptor/interest structures. Nothing is remembered between calls. **Stateful registration.** The program creates a kernel-side object and adds handles to it once, with the events it cares about. Then it calls wait, which returns only the handles that have become ready since it last looked. Registrations persist across calls; add and remove are separate operations. ## The complexity argument Let *n* be the number of watched handles and *k* the number ready at a given moment. In real servers with keep-alive connections, *k* is tiny compared with *n* — a few dozen active among tens of thousands registered. - Scan style: each wait call costs O(n) to copy the set in, O(n) inside the kernel to inspect each entry, O(n) to copy results out, and O(n) in your loop to find the ready ones. Multiply by the number of loop iterations per second. Total work grows with the product of watch-set size and event rate. - Registration style: adding a handle is O(1) amortised and happens once per connection. Wait returns an array of exactly the ready events, so per iteration you pay O(k). The kernel maintains a ready list incrementally: when a network packet arrives and makes a socket readable, the socket is appended to its ready list right there, so wait typically pops from a list rather than inspecting anything. That is the whole story, and it is the same story as scanning an array versus keeping an index. It matters because event loops run this call millions of times a day; a per-call term proportional to *total connections* means adding idle users slows down active ones. With registration, ten thousand idle connections are ten thousand cheap kernel entries that cost nothing until they fire. ## Secondary differences that come up - **Copying.** Scan interfaces move the whole set across the user/kernel boundary twice per call. At 10,000 descriptors that is real bandwidth and cache pollution per iteration. - **Ceilings.** Some bitmask-based scan interfaces had a compile-time maximum descriptor number, which is a hard wall rather than a slowdown. Array-based scan interfaces removed the ceiling but kept the O(n) behaviour. - **Statefulness cuts both ways.** Registration must be maintained: register on accept, modify when you start or stop caring about writability, and understand what happens when a handle is closed while registered (the registration normally disappears with the last reference to the underlying object — but if the handle was duplicated, it may not, which produces the notorious "events for a descriptor I closed" bug). - **Portability.** The registration APIs are per-kernel: epoll on Linux, kqueue on the BSDs and macOS, event ports on Solaris-derived systems, completion ports on Windows (a completion model rather than a readiness one). Portable servers hide all of them behind one abstraction layer, which is why almost every runtime ships such a layer rather than calling the kernel directly. - **Expressiveness.** kqueue watches more than descriptors — timers, process exits, filesystem changes — through the same queue, which lets a loop have a single wait point. Scan interfaces cover descriptors only, so other event sources must be funnelled through a pipe (the classic self-pipe trick) to become visible to the loop. ## Where the remaining cost goes Registration removed the readiness-discovery bottleneck, so at very high event rates the next costs become the *per-event* system calls: one wait, then one or more reads and writes per ready handle. That is what drove the next step — batched submission/completion ring interfaces where many operations are submitted and reaped with a single (or zero) system call, and which are completion-based rather than readiness-based. ## How to say it "Scan interfaces are O(n) in the number of watched handles per call; registration interfaces are O(1) to register and O(k) in the number of ready events per wait. With tens of thousands of mostly idle connections, that is the difference between work proportional to your user base and work proportional to your traffic. The price is a stateful kernel-side registration you must keep in sync, and an API that differs per operating system."
- If registration is strictly better asymptotically, when would you still use a scan-based interface?When n is small and portability matters more than throughput — a tool watching three or four handles pays no meaningful O(n) penalty and gains code that runs unchanged everywhere. Scan interfaces are also stateless, so there is no registration to leak or desynchronise, which makes short-lived programs simpler. The asymptotic win only shows up once the watch set is large and mostly idle.
- What breaks if you close a handle that is still registered with a kernel readiness queue?Normally the registration is dropped when the last reference to the underlying object disappears, so closing is enough. But if the handle was duplicated, the object outlives the descriptor number you closed and the queue can still report events for it — and that number may already have been reused by a new connection, so events get delivered to the wrong logical owner. The safe discipline is to deregister explicitly before closing and to key your state on a generation counter, not on the raw descriptor number.
Scanning is walking every room of a hotel each minute to see who wants service; registration is a call board where only rooms that pressed the button light up.
saying these in an interview costs you the question
- Saying registration-based interfaces are faster "because they are newer" without the O(n) versus O(k) argument.
- Claiming the gain comes from avoiding blocking — both styles block once per loop iteration.
- Assuming a registration-based interface makes reads cheaper; only readiness discovery changed.
- Ignoring that registration is stateful and must be kept in sync with opens and closes.
- Treating completion ports as the same category as readiness queues.