Using select(2) the right way

I have worked on servers that had this problem with select(2). poll was better but kqueue was much much better (from near-100% utilization with a few thousand open fds to < 1% cpu utilization; please forgive the vague numbers, it was 7 years ago at a company that I no longer work for).

If you're using nonblocking I/O, or threads, select can become the bottleneck with a few thousand interesting connections at sizes that are much less than the FD_SETSIZE max.

The user-space CPU utilization should be near-0 since this is really a kernel I/O problem; the fact that it is much higher is an indication that a lot of wasted user space work is being done.

Select, by design, has a flaw: the kernel must scan the bitmask for the highest-numbered fd passed in, even if there is little change in the fd_set bitmask (as is usually the case). This means incurring a cost if any fd in the set has a high fd number. The fd on which you accept probably has a low number, but your client I/O fds will have increasing numbers as the server gets greater and greater utilization.

kqueue (and epoll, but I haven't used it) resolve this problem nicely. Only things that change state must be communicated. poll is better than select in this respect if the array is sparse, but if a large number of fds are interesting, it will also get expensive.

I've written lots of servers in C and found this article quite interesting.

The techniques that the author presents are new to me and I know that I will take them into consideration when I write a server in C the next time.

More importantly, they are techniques that I think library writers should use. My uneducated guess is that the underlying implementations of servers in Node.js and Iron, etc, could be improved with these ideas, even though they might not be directly applicable since those servers are written in different languages.

I can't vouch for the results, but the author's experiments seem conclusive.

The thing that really resonated for me in this article was the point that for most of us, the performance of select() or accept() really doesn't matter, because any time spent there is easily dwarfed by application logic, database lookups, queries to other services, etc.

You only really need to care about this if you're working on something mainly concerned with the connections themselves, like HAProxy.

Regarding this:

> epoll uses system calls (“slow”) to add or remove descriptor to the set. select does the same thing in userspace. If you have to add and remove many descriptors per iteration which is typical for short-lived connections then select might be more efficient.

I would have estimated that on a select system call the kernel needs to internally attach some kind of event listener for each passed FD and uninstall it before the system call returns. Which means select is interally a sequence of "iterate over all FDs, check if an event is available and if not install listener", "wait at least one event to happen" and finally "uinstall all listeners". While epoll requires only "wait for at least one event to be available and then iterate over the FDs and record all available events". So I would guess that while epoll requires more syscalls for setup it should be a lot more efficient if a FD is polled more than once. With edge triggering most of the registration/unregistration calls can also be avoided.

Or do kernels have special optimizations that make select internally more efficient than I described? Maybe some memoization of former used pollsets?

A lot of the advice seems misguided, if not wrong. Rather than optimize around the limitations of select(2), I'd suggest using different APIs instead.

For example:

> Literature ussually says that fd_set is limited to 1024 descriptors but some mention that you can increase that by defining FD_SETSIZE to a larger number.

If you just need a one off tool for a few descriptors, why not just use poll(2) instead? No problems with high fd numbers, and the API is quite simple.

> To find out which sockets have events some loop through data structures and check each socket they contain. But a much better way is to iterate through fd_set as array of long and check 32-64 bits at a time.

If you've reached the point at which this trade-off matters, you're better off switching to a socket API that scales well (epoll or kevent) and does this filtering for you. Or like another commenter suggested, using a library that abstracts this functionality.

> select modifies descriptor sets passed in. A common mistake is to create descriptor set from zero before calling select by looping through data structures and adding all sockets they contain. I’ve seen that to take huge amount of time due to locking and synchronization between threads. The correct way is to maintain a descriptor set all the time and create a copy of it and pass the copy to select.

Again -- if you've reached the point where this tradeoff matters, just go directly to epoll/kevent.

> Most programs will need to store some state associated with the socket. Map seems to be a good choice at first but you should use an array indexed by socket (it’s an int). The POSIX API says that kernel always has to use the lowest unused file descriptor when creating a new one. So the array will be as big as many connections your program handles and kernel will take care of finding a free slot in your array.

Maybe your program deals with non-socket fds, and the set of socket fds is fairly sparse. Using a map is actually pretty reasonable even if fds are dense.

  unsigned long *wfds = (unsigned long *)wfds_out;

Unless fd_set has the same or stricter alignment requirements as unsigned long, and fd_set and unsigned long are compatible effective types, this line of code provokes undefined behaviour twice (breaks strict alignment and breaks effective type access).

Another problem with select() is that trying to use a file descriptor above FD_SETSIZE in FD_SET() and the likes will actually result in overwriting the stack and will cause random segfaults in other areas of code. Note that sockets aren't the only thing using up file descriptors and it is quite easy to run into this issue. The solution is to use poll() as essentially a drop in replacement. Strangely the winsock version of select() acts more like poll and instead of a bitmask based on socket fds, uses an array of sockets so you can actually use a number of sockets up to FD_SETSIZE regardless of their file descriptor.

Btw "ussually" instead of usually

Does Apache web server use this trick?

It took me a few seconds to realize this article is not about select2[0], the javascript library.

[0]: https://select2.github.io/

The correct way to use select() is not to use it. You should instead use a library designed to do at a high level whatever it was you were going to use select() for. This library will then (hopefully) figure out what your application needs as efficiently as it can, rather than you having to spend a week researching how modern operating systems work to finally learn that you should have been using a library to do what you were about to try to reinvent.