Premature Optimization Is Fun Sometimes

invlpg – Premature Optimization is Fun Sometimes

A colleague of mine was recently discussing a connectivity monitoring system he is working on with me. It’s nothing fancy, just sending ICMP Echo Requests to a couple of different servers, and monitoring latency and dropped packet averages over 1-minute, 5-minute, and 15-minute periods. Up came the topic of how this data should be stored, the natural thought was a 512 entry ring buffer, containing entries like the following:

struct ping_timestamp { uint64_t sent_ns; // when the packed was sent (unit: ns) uint64_t received_ns; // when the packet was received (unit: ns) in_addr_t source_addr; // source address uint16_t seq_no; // echo request sequence number bool received; // has the request been received? };

And backed by the following array

struct ping_timestamp pings_rb[512];

// ...

printf("%zu\n", sizeof(pings_rb));

// 12288

12 KiB. Pretty wasteful, right? We can certainly do better. Do we need to keep fields for both sent and received? What we’re really interested is the latency. We need to know when a packet was sent, only up until we know when it was received, at that point, the data we want to keep is received - sent, so why don’t we make it a tagged union?

struct ping_timestamp_2 { union { uint64_t sent_ts; // unit: 100μs uint64_t elapsed_ts; // unit: 100μs }; in_addr_t source_addr; uint16_t seq_no; bool received; };

// ...

printf("%zu\n", sizeof(pings_rb));

// 8192

Not bad, we’ve shaved off an entire page. We can still do better.

Nanosecond precision? In our case, ping times are measured in the tens or hundreds, or even thousands of milliseconds. We don’t need to keep all of those extra bits around. If we change the unit from nanosecond to 100 microsecond increments (0.1ms), then 43-bits is sufficient for us to keep track of pings for up to 20-years1. 20-years is a bit excessive still, but it doesn’t hurt to be at least a little bit future proof.

And received? 8-bit for a true/false value seems altogether too much. The answer: bitfields.

struct ping_timestamp_3 { uint64_t sent_or_elapsed_ts: 43; uint64_t received: 1; uint64_t seq_no: 16; in_addr_t source_addr; };

// ...

printf("%zu\n", sizeof(pings_rb));

// 8192

Wait, what? Why haven’t we saved any space?

The answer is struct padding. The layout of ping_timestamp_2 looks like this:

0 8 16 24 32 40 48 56 64... +-------+-------+-------+-------+-------+-------+-------+-------+ | sent/elapsed | +-------+-------+-------+-------+-------+-------+-------+-------+ ...64 72 80 88 96 104 112 120 128 +-------+-------+-------+-------+-------+-------+-------+-------+ | source_address | seq_no | recv? | pad | +---------------------------------------------------------------+ Where the padding byte at the end is to ensure alignment requirements. ping_timestamp_3 on the other end, looks like this:

0 8 16 24 32 40 R? 48 56 64... +-------+-------+-------+-------+-------+-------+-------+-------+ | sent/elapsed || seq_no | P | +-------+-------+-------+-------+-------+-------+-------+-------+ ...64 72 80 88 96 104 112 120 128 +-------+-------+-------+-------+-------+-------+-------+-------+ | source_address | padding | +---------------------------------------------------------------+ So our optimization there didn’t actually save any space. We’re wasting 36-bits of padding. Is there any way we can somehow do better?

We keep track of the source address due to frequent changes while our product is in operation (on a mobile data network). When the address changes, we also reset the sequence number for reasons that aren’t relevant to the current topic. We have seen, in the past, packets with differing source addreses but identical sequence numbers due to be processed by our application at the same time (the joys of asynchronous programming), so the source address serves to disambiguate these changes.

But there’s another way to disambiguate.

An ICMP echo request has a 16-bit long identifier field to allow applications to identify which echo request packets were sent by them. Its value is completely arbitray. On Linux iputils ping sets it to getpid() & 0xFFFF; on OpenBSD a random number is used instead.

Although it’s 16-bits long, we don’t actually need to use the full 16-bits. There’s 4 free bits left in the first 8-bytes of our ping_timestamp_3. Our thought was to use a rolling 4-bit counter, that is increased whenever our source address changes (this is monitored elsewhere in the application), allowing us to uniquely identify2 which source address the packet came from.

Our final struct looks like this:

struct ping_timestamp { uint64_t elapsed_or_sent_ts : 43; uint64_t received : 1; uint64_t counter: 4; uint64_t seq_no: 16; };

// ...

printf("%zu\n", sizeof(pings_rb));

// 4096

Much better. A whole 8-kilobytes of savings, and down to a single page of data. You may have noticed that I have changed the order of the fields slightly. This is to line seq_no up on a 16-bit boundary, so that loading it...

Premature Optimization Is Fun Sometimes

Related Articles

The Newest Instagram "Exploit" Is the Goofiest I've Seen

It's Not Just X. It's Y

Amazon, Facebook, FBI have access to a private intelligence-sharing network

Show HN: GoPeek – open links in live mini browser windows without new tabs

Agent Memory: An Anatomy