How can something that “just works” be so annoying? situation We live in Cambridge off a little road down a drive in shared ownership between us and our neighbouring houses. All the utilities are buried under this drive, including the phone line. anticipation Over the last few years we have been canvassed repeatedly by CityFibre saying that they can deliver fibre all way to our house. I saw them digging trenches and leaving tails of purple fibre cladding along nearby roads, ready to hook up all the houses. I thought they would need to do something similar to deliver fibre to us. So when they turned up and knocked on our door, I talked to their salesbods and walked them up and down the drive and pointed out where the existing BT line goes. Then they gave up trying to sell to us. This happened about three times. disaffection We were not eager enough for an upgrade to deal with these impediments. notification A few months ago we were told that CityFibre would soon come and do the upgrade, since there’s a nationwide deadline for turning off the copper phone network at the end of the year. We expected that this would force them to actually plan some digging works, so we talked to our neighbours about it. We were all ready for some huge faff to follow the next visit by the CityFibre bods. installation CityFibre turned up on the promised morning bright and early. To our enormous surprise, a brown fibre housing was already poking out of the ground next to our copper phone line. It had been fed through 50 metres of 5cm duct without us being aware they were even working on the street. Within a couple of hours, the technicians had drilled through our wall, installed the ONT, blown fibre through the unexpected pipe, plugged in the CPE (superficially identical to the old one), and left telling us to anticipate that it might not work properly until tomorrow. activation Around lunch time, the copper phone line stopped working completely. Some faff ensued, switching all our devices over to the new WiFi network. For a while we thought this was the death of our land line, but in the course of debugging other issues, I realised that the router has a built-in VoIP adapter (I don’t think we were told it has a built-in VoIP adapter) so I plugged the phone in and it Just Worked: they had ported our phone number across and everything. Flawless. I was seriously impressed. rumination It has been a few weeks since the switchover, and apart from a couple of horrible Clown-afflicted IoT devices, it has been fairly smooth. What prompted me to write this up was realising that we delayed this upgrade for years because the sales people were not given enough technical information about how the installation process works: the fact that houses typically have a 5cm duct containing the copper lines (probably standard for the last 40 years) and the fact that fibre can be shoved through a few tens of metres without difficulty. And worse, the sales people didn’t have an esclation path for difficult cases: they just gave up instead. From a technical point of view, the installation was impeccable. (I guess the loose 24 hour window for the cutover time was because OpenReach and CityFibre don’t have tight requirements on ISP reconfiguration schedules.) From the sales point of view, it was crap. Maybe it would have gone faster if we offered to switch early without asking if the drive would be a problem? But I guess the difference between “yes!” and “yes, but will this be a problem?” is too much to expect from a minimum-wage door-to-door salesbod whose employer didn’t give them enough information or any escalation path.

Many years ago I wrote about how to convert Gregorian dates to Julian Day numbers or similar counts such as rata die as used in Calendrical Calculations. This algorithm is the core of C’s mktime() function that converts a broken-down date-time into linear time_t. I recently learned from Ben Joffe that I was missing a few tricks, and my old code wasn’t as good as it could have been. Here’s a better version (using conventional not C numbering): if m > 2 { m -= 2; } else { m += 10; y -= 1; } y*365 + y/4 - y/100 + y/400 + m*979/32 + d - 336 the main idea Julian years Gregorian correction the month pattern the epoch domains and ranges leap year test length of month the main idea There’s a helpful coincidence in the Gregorian calendar. Although the month lengths aren’t obviously regular, there’s a repeating 5 month pattern that becomes easier to see when you start from March, as illustrated by the table below. This pattern resets at the end of February, midway through its third repeat, coincidentally at the same point that leap days occur. Thus the first line of the code above adjusts the month and year numbers so that January and February are counted at the end of the previous year, and the coincidental alignment occurs at the boundary between the adjusted year numbers. I’ll explain the details of the adjustment as I discuss the relevant parts of the second line 31 days April 30 days May 31 days June 30 days July 31 days 31 days September 30 days October 31 days November 30 days December 31 days 31 days February 28 or 29 Julian years The first part of the main formula counts the number of days before the start of year y, in terms of normal years and leap days. y * 365 + y / 4 The adjustment subtracts one from the year in January and February. The effect is that the leap day in year 4 is counted as a day before the start of the adjusted beginning of year 4, i.e. before March, i.e. exactly the right place. I previously combined this part of the expression into a single term, y * 1461 / 4 Ben Joffe pointed out that when it is written this way the function is only able to make use of 25% of the range of its output data type, because the multiplication overflows for very large year numbers. And on modern CPUs it isn’t actually faster to eliminate the addition. Gregorian correction The next part corrects the number of leap years before the current year. - y/100 + y/400 It works in basically the same way as the Julian leap year calculation, but whereas y/4 trivially compiles to a simple shift operation, this needs a bit more cleverness. As Hacker’s Delight explains, a modern compiler will turn y/100 into a multiply-and-shift: y * (1<<N) * (1/25) >> (N+2) That is, the compiler uses a fixed-point representation of the reciprocal of the divisor. Then it uses common subexpression elimination to suppress the second multiplication by 1/25. So these two divisions are turned into a wide multiply and two shifts. Neat. the month pattern The next part counts the number of days in this (adjusted) year before the start of month m. m * 979 / 32 I previously wrote it using the number of days in the repeating pattern of 5 months, m * 153 / 5 But this is relatively difficult for compilers to optimize well (clang uses two multiplications instead of one), and they don’t know the range of m is limited, so we can do better by turning it into a multiply-and-shift by hand. 979/32 == 30.59375 which is close enough to the exact value 153/5 == 30.6 Either of these expressions produce the right 5 month long/short pattern, but the pattern doesn’t necessarily line up with the normal month numbering. (The two expressions above need different adjustments.) We move March to number 1, just before the start of the pattern. When counting the days before April, we get 31 more than the count for March; when counting the days before May, we get 30 more than the count for April, etc. January is adjusted to follow December to match the adjusted year numbering. m *979/32 diff -------------------- 1 30 March 2 61 31 April 3 91 30 May 4 122 31 5 152 30 6 183 31 7 214 31 8 244 30 9 275 31 10 305 30 December 11 336 31 January 12 367 31 13 397 30 the epoch Because calendars count from 1, the Gregorian date 0001-01-01 gets numbered rata die 1. The adjustments turn January into month 11, and so (as in the second column in the table above) we count 336 days in the adjusted year 0 before January. We need to subtract those extra days to compensate for the adjustment. We can change the offset to choose a different epoch, e.g. the MJD epoch 1858-11-17 is r.d. 678576, and the Unix epoch 1970-01-01 is r.d. 719163. domains and ranges In my old C code I casually used int, which misleadingly implied that it worked with proleptic Gregorian calendar dates before year 1. However signed division and modulus on common CPUs and low-level programming languages truncates towards zero, but this algorithm needs Euclidean or flooring division (which are equivalent for positive divisors). So it’s better to use u32 for these calculations. (Compilers also do a better job when this code uses unsigned integers.) To support negative years, a multiple of 400 years can be added to move year 0 to the middle of the u32 range, and subtracted from the return value to produce a signed count of days. leap year test Ben Joffe also examined fast leap year tests. My new favourite one is I think the neatest if not the fastest: if y % 25 == 0 { y % 16 == 0 } else { y % 4 == 0 } Note that 25 * 16 == 400, so it’s a leap year if it’s divisible by both 25 and by 16, else if it’s divisible by 4 but not by 25. The classic version of this check first tests divisibility by 100. CPUs that rely on branch prediction will correctly predict it 99% of the time: much better than the 75% you get from testing divisibilty by 4 first! But nowadays this if is compiled into a CMOV or CSEL (so branch prediction doesn’t matter), and divisibility by 25 is easier to compile than divisibility by 100. length of month What prompted me to revisit this code was the idea that it’s possible to work out a simpler multiply-and-shift optimization when the values have limited ranges (as in m*979/32 above) and/or when we don’t depend on the exact result of the multiplication. I previously wrote this code for calculating the length of a month: if m == 2 { 28 + is_leap_year(y) as u32 } else { 30 + (m * 275 % 9 > 3) as u32 } The multiply-and-shift idea led me to this replacement for months other than February: 30 + (m * 7 % 16 < 9) as u32 I found it by writing a brute force program that tries successive bitmask widths and multipliers, until it finds a case where all the long months produce results greater than all the short months, or vice versa (as in the winner). But there’s a neater expression, apparently due to Dr Matthias Kretz: 30 | (m ^ (m >> 3)) This uses two tricks: The 1 bit of the month number matches the odd/even long/short pattern in the months before August (month 8), when the phase flips. The flip is done by using the 8 bit to toggle the 1 bit. Bitwise or with 30 sets bits 2, 4, 8, 16 so the higher bits of the month number don’t matter. It compiles to just two ARM instructions: eor w0, w0, w0, lsr #3 orr w0, w0, #0x1e It’s so sweet I actually love how much better it is than my attempt!

A few weeks ago I was enjoying a couple of boiled eggs (in the shell, with plenty of salt and pepper, and buttery fingers of toast to dunk into the runny yolk) and pondering how fiddly it is to cut off one end of the shell after boiling compared to eating a poached egg. And I was annoyed because (I thought) I didn’t know how to poach eggs. misconceptions For decades I have been under the impression that poached eggs are difficult, because cheffy bods on the telly make such a fuss over cooking them. They led me to believe two falsehoods, both of which have a grain of truth, but it turns out they are not the overwhelming obstacles I thought. I decided to see what happens if I just don’t do any of the chef tricks. How bad could it be? If the poached eggs turned out to be a disaster, I would at least have confirmed what I believed. If not, I have added some delicious food to my repertoire. What did I believe? And what did I learn… If you just break an egg into boiling water, it’ll dissolve into a soupy mess? Yes the egg will spread out and the water will get messy, but almost all of the egg will hold together neatly by itself. If you don’t do the cheffy faff, your poached eggs will be inedible? In fact the fuss is mostly about levelling up from basic to restaurant-standard presentation. A no-fuss but frilly egg is still nice to eat. basic tricks The key trick for boiling an egg is to have plenty of boiling water in the pan before adding the eggs. That gives you a stable temperature and therefore predictable cooking times. To boil large hen eggs from room temperature, I aim for about 4 minutes for a runny yolk, or 8 minutes for a slightly fudgy hard-boiled yolk. For poached eggs, the water should be at a gentle simmer to avoid agitating the wispy white more than necessary. I add plenty of salt for seasoning. A cooking time of 3 minutes is about right. The key trick for poaching eggs is not to worry about the wispy whites in the water. It might be messy but it’ll be fine. Break the eggs near the surface of the water so they aren’t agitated too much from plunging in. When the surface of the white has started coagulating, give them a nudge to make sure they are moving enough to cook evenly and aren’t stuck to the bottom of the pan. Unlike a boiled egg, I can lift the poached egg out of the water with a slotted spoon and jiggle it to judge when it is ready, which is better than relying on my oven timer that can only be set in increments of a whole minute, and handy when I forget to set it… cheffy faff There are about half a dozen ways to improve the presentation of poached eggs. Use very fresh eggs, because they hold their shape better with less wispy white. I only have supermarket eggs, so egg age is not something I can control. Use a fine mesh strainer to separate the loose wispy white from the firm inner white. I think watching this trick taught me that raw eggs are a lot more cohesive and robust than I thought, and they don’t just dissolve into water. Get the water spinning like a vortex before adding the egg. Helen Rennie has a video on poaching eggs in which she discusses why this method is better in a restaurant (after about 6m10s). It requires a very large pot so it isn’t ideal for cooking a few portions at home. Break the egg into a small dish or ladle, so it can be introduced to the water more gently. This is worth doing but nevertheless I don’t bother :-) Add a little vinegar to the water. I don’t believe this has any effect on how the whites spread. It’s possible to use vinegar to coagulate the whites before poaching, but this requires a lot of vinegar and takes a long time, and harms the flavour of the eggs. Most of the spreading of a poached egg is due to turbulence when it plunges into the water, and it happens far too fast to be affected by a little vinegar. Wrap the egg in cling film. I don’t care enough about how neat my eggs are to fiddle with throwaway plastic and risk spilling egg in a clumsy mess. We have some reusable silicone things that cook eggs in a style somewhere between poached and coddled. We almost never use them because they are fiddly and tend to undercook the tops of the eggs even with a lid to keep the steam in. Trim the egg with a knife after cooking. Almost as wasteful as the strainer method! Or… don’t! thoughts In retrospect it’s curious that I was discouraged from even trying to poach eggs for such a long time, and that it took so little to discourage me. I suppose it illustrates how offputting extra steps can be to a beginner. It wasn’t clear to me which steps were optional and what were the consequences of omitting them. It’s something to keep in mind when writing documentation, I guess :-)

A while back I wrote about the linear rate limit algorithms leaky bucket and GCRA. Since then I have been vexed by how common it is to implement rate limiting using complicated and wasteful algorithms (for example). But linear (and exponential) rate limiters have a disadvantage: they can be slow to throttle clients whose request rate is above the limit but not super fast. And I just realised that this disadvantage can be unacceptable in some situations, when it’s imperative that no more than some quota of requests is accepted within a window of time. In this article I’ll explore a way to enforce rate limit quotas more precisely, without undue storage costs, and without encouraging clients to oscillate between bursts and pauses. However I’m not sure it’s a good idea. linear reaction time fixed window quota resets hybrid quota-linear algorithm discussion opinion linear reaction time How many requests does a linear rate limiter allow before throttling? The parameters for a rate limiter are: q, the permitted quota of requests w, the accounting time window So the maximum permitted rate is q/w. Let’s consider a client whose rate is some multiple a > 1 of the permitted rate (a for abuse factor) c = a * q/w I’ll model the rate limiter as a token bucket which starts off with q tokens at time 0. The bucket accumulates tokens at the permitted rate and the client consumes them at its request rate. (It is capped at q tokens but we can ignore that detail when a > 1.) b(t) = q + t*q/w - t*a*q/w The time taken for n requests is t(n) = n/c = (n*w) / (a*q) After n requests the bucket contains b(n) = q + n/a - n The rate limter throttles the client when the bucket is empty. b(t) = 0 = q + t * (1 - a) * q/w 0 = 1 - t * (a - 1) / w t = w / (a - 1) b(n) = 0 = q + n * (1/a - 1) 0 = q - n * (a - 1) / a n = q * a / (a - 1) For example, if the client is running at twice the permitted rate, a=2, they will be allowed q*2 requests within w seconds before they are throttled. That’s a bit slow. The problem is that the bucket starts with a full quota of tokens, and during the first window of time another quota-full is added. So a linear rate limiter seems to be more generous in its startup phase than its parameters suggest. fixed window quota resets This is a fairly common rate limit algorithm that enforces quotas more precisely than linear rate limiters. It is similar to a token bucket, but it resets the bucket to the full quota q after each window w. The disadvantage of periodically resetting the bucket is that careless clients are likely to send a fast burst of requests every window. (A linear rate limiter will tend to smooth out requests from careless clients, though it can’t prevent deliberately abusive burstiness.) And a quota-reset rate limiter uses more space than a linear rate limiter: it needs a separate bucket counter as well as a timestamp. each client has the time when its window started and a bucket of tokens if c == NULL c = new Client c.bucket = quota c.time = now reset the bucket when the window has expired if c.time + window <= now c.bucket = quota c.time = now the request is allowed if the client has a token to spend if c.bucket >= 1 c.bucket -= 1 return ALLOW else return DENY hybrid quota-linear algorithm The idea is to have two operating modes: Low-traffic clients are allowed to make bursts of requests, because that’s good for interactive latency. High-traffic clients are required to smooth out their requests to an even rate. The algorithm switches to smooth mode when a client consumes its entire quota and the bucket reaches zero, and switches back to bursty mode when the bucket recovers to a full quota. Bursty mode avoids being too generous by adding at most one quota of tokens to the bucket per window. Smooth mode also avoids being too generous by starting with an empty bucket. I’ve written this pseudocode in a repetitive style because that makes each paragraph more independent of its context, though it is still somewhat stateful and the order of the clauses matters. the rate limit is derived from the quota and window rate = quota / window a client that returns after a long absence is reinitialized like a new client; in bursty mode the time is the start of a fixed window and the bucket contains a whole number of tokens; we subtract one from the quota to account for the current request fn reset() c.bucket = quota - 1 c.time = now c.mode = BURSTY return ALLOW initialize the state of a new client if c == NULL c = new Client return reset() reset the state when a bursty client’s window has expired if c.mode == BURSTY and c.time + window <= now return reset() when a client consumes its last token, switch modes; in smooth mode the time is updated for every request and the bucket can hold fractional tokens; apply a negative penalty so we don’t allow any over-quota requests before the end of the fixed window; add one to allow the next request at the start of the next window if c.mode == BURSTY and c.bucket == 1 remaining = c.time + window - now c.bucket = -remaining * rate + 1 c.time = now c.mode = SMOOTH return ALLOW smooth mode accumulates tokens proportional to the time since the client’s previous request; update the request time so that tokens accumulate at the same rate whether the request is allowed or denied if c.mode == SMOOTH c.bucket += (now - c.time) * rate c.time = now when the bucket has refilled, switch back to bursty mode if c.mode == SMOOTH and c.bucket >= quota return reset() we have dealt with all the special cases; in either mode the request is allowed if the client has a token to spend if c.bucket >= 1 c.bucket -= 1 return ALLOW else return DENY discussion This hybrid algorithm has a similar effect to running both a quota-reset and a linear rate limiter in parallel, but it uses less space. The precision of quota enforcement in smooth mode is maybe arguable: It guarantees that the client remains below the limit on average over the whole time it is in smooth mode. But if it slows down for a while (but not long enough to return to bursty mode) it can speed up again and make more requests than its quota within a window. opinion I think it’s a mistake to try to treat each time window in strict isolation when assessing a client’s request quota. A linear rate limiter only seems to be unduly generous on startup if you ignore the fact that the client was quiet in the previous window. As well as being more expensive than necessary (in some cases disgracefully wasteful), algorithms like sliding-window and quota-reset encourage clients into cyclic burst-pause behaviour which is unhealthy for servers. And I’ve seen developers complaining about how annoying it is to use glut/famine rate limiters. By contrast, rate limiters that measure longer-term average behaviour by keeping state across multiple windows can naturally encourage clients to smooth out their requests. So on balance I think that instead of using this hybrid quota-linear rate limiter, you should reframe your problem so that you can use a simple linear rate limiter like GCRA.