Using select(2)
Tags: c, asyncio, select
Published: 2021-11-01 21:44:50

---
title: Using select(2)
published: true
date: 2017-04-06 00:00:00 UTC
tags: c,asyncio,select
canonical_url: http://aivarsk.com/2017/04/06/select/
---

This started out as a Hacker News comment about a blog post about [select being fundamentally broken](https://idea.popcount.org/2017-01-06-select-is-fundamentally-broken/) After that the same author wrote why [epoll is broken as well](https://idea.popcount.org/2017-02-20-epoll-is-fundamentally-broken-12/). I don’t know what problem author is trying to solve but let’s pick this one:

> Let’s say you run an HTTP server, serving a large number of short lived connections. You want to accept() as many connections per second as possible. Doing accept() in only one process will surely be CPU-bound. How to fix it?

Now I’m no network programming expert but I have written enough of networking code in C (and C++, Python, Java) over the last 17+ years and I have thought about [the C10K problem](http://www.kegel.com/c10k.html) and read papers on architecture of servers, proxies, load balancers and using socket API efficiently. People working on [libev](http://software.schmorp.de/pkg/libev.html) and [HAProxy](http://www.haproxy.org/) definitely have a better understanding and might find flaws in my arguments.

## Using `select` the correct way

Literature usually 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. Last time I checked it did not work on Linux although it did on SunOS and AIX. However `fd_set` is just an array of bits and you can allocate memory for as many bits as you need. And turns out that all `select` implementations I worked with accepted larger arrays of bits than the standard `fd_set` allocated. I still had to put `#define FD_SETSIZE 65536` in my code for SunOS to use `select_large_fdset` function instead of `select`.

```
fd_set *wfds_out = calloc(FDS_BYTES(65536), 1);

```

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 any of bits is set only then check them individually in a nested loop. Some implementations even check read, write and exception sets at the same time by ORing bits - Linux kernel does that in `fs/select.c`.

```
unsigned long *wfds = (unsigned long *)wfds_out;
for (unsigned i = 0; i < FDS_LONGS(maxfd); i++, *wfds++) {
  unsigned long bits = *wfds;
  if (bits != 0) {

    unsigned long bit = 1;
    for (unsigned j = 0; j < FDS_BITPERLONG; j++, bit <<= 1) {

      if (bits & bit) {
        int fd = i * FDS_BITPERLONG + j;

```

Once a notification is received for listener socket the best approach is to call `accept` multiple times up to certain limit (10? 50?) or until EAGAIN or EWOULDBLOCK error is returned indicating there are no connections pending. This way more useful work is done per iteration amortizing the cost of “expensive” `select` call. I found this reading “Scalability of Linux Event-Dispatch Mechanisms” by Abhishek Chandra and David Mosberger.

```
while (1) {
  int client = accept(server, (struct sockaddr *)&sin4, &sin4_len);
  if (client == -1 && (errno == EAGAIN || errno == EWOULDBLOCK)) {
    break;
  }

```

Another useful idea is to trade latency for throughput with interval control. It works by limiting how many `select` calls are performed per second and enforce it by sleeping before the next call to `select`. During that time more events will occur on sockets and the next `select` call will return more events to process. Again, more useful work will be done per iteration. The source for this is paper “Efficient Network I/O Polling with Fine-Grained Interval Control” by Eiji Kawai, Youki Kadobayashi, Suguru Yamaguchi.

```
while (1) {
  tnow = usec();
  if (tnow - tprev < 1000) {
    struct timespec spec;
    spec.tv_nsec = 1000 - (tnow - tprev);
    nanosleep(&spec, NULL);
  } else {
    tprev = tnow;
  }

  int nready = select(server + 1, &rfds_out, NULL, NULL, NULL);
 

```

## All the small things

`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`.

`select` returns number of file descriptors in resulting sets. You should count events you have processed and stop once you reach number returned by `select`.

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.

And if you use the hard limit returned by `getrlimit` you can always pre-allocate both the array for state of connections and descriptor sets for `select`. Which means no re-allocations during runtime and no synchronization between threads. If the state of your connections is really big, allocate array of pointers.

## Results

So I wrote [sample code](https://github.com/aivarsk/misc/tree/master/select) using most of the ideas I described above. I wrote it from scratch not using any of my previous work so it “works on my computer” and there are bugs. I used a a small Linux virtual machine to run it with just 1 CPU and 512 Mb of RAM. This is how I started the server:

```
./accept-server 1025 > accept-server.log

```

And client in a different console:

```
./accept-client 100 127.0.0.1 1025 > /dev/null 

```

And it gave me following results:

```
awk '{count[$1]++} END {for (word in count) print word, count[word]}' accept-server.log | sort -n
1496608453 40154
1496608454 46292
1496608455 44843
1496608456 47250
1496608457 48005
1496608458 47204
1496608459 45685
1496608460 45992
1496608461 41870
1496608462 44020
1496608463 45392
1496608464 44592
...

```

First column is the timestamp (seconds since epoch) and second is number of connections accepted.

`accept-server` was consuming 24% of CPU time and `accept-client` 71% of CPU time. I think results are pretty good: 40,000 `accept` calls per second. Passing new sockets to worker threads would take some time but it’s still possible to handle tens of thousands of `accept` calls with a single thread.

## `select` vs others

`poll` transfers 8-16 bytes per descriptor to the kernel compared up to 3 bits for `select`. `poll` is more efficient for very sparse descriptor set and I would use it if I had a listener thread (`poll` for few sockets) and separate thread for connections (`select` for thousands of sockets).

`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. In fact it was for synthetic tests I did years ago. Just search for [EVBACKEND\_EPOLL in libev documentation](http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod)

## Closing words

I usually ignore topics about the fastest networking code since for problems I work on application logic and database access code is the bottleneck. I have seen badly written networking code that caused problems but not code where the `accept` call is the bottleneck. The other thing is once you reach certain number events per second you should distribute work among several processes and machines anyway. That may differ if you work for Google or large ISP or try to develop a load balancer or a proxy.

Martin Thompson often talks about [mechanical sympathy](https://mechanical-sympathy.blogspot.com/) - that you have to understand how the hardware works and take that into consideration when you design software. Well, you should have sympathy for your Operating System and it’s APIs and find the best way to use it.

Use [libev](http://software.schmorp.de/pkg/libev.html), [Boost.Asio](http://www.boost.org/doc/libs/1_64_0/doc/html/boost_asio.html) or other libraries. I do. Just because I know how to use `select` efficiently does not mean I want to write low-level code.