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…
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…
The nsnotifyd daemon monitors a set of DNS zones and runs a command when any of them change. It listens for DNS NOTIFY messages so it can respond to changes promptly. It also uses each zone’s SOA refresh and retry parameters to poll for updates if nsnotifyd does not receive NOTIFY messages more frequently. It comes with a client program nsnotify for sending notify messages. This nsnotifyd-2.4…
I’m writing a simulation, or rather, I’m procrastinating, and this blog post is the result of me going off on a side-track from the main quest. The simulation involves a bunch of tasks that go through a series of steps with delays in between, and each step can affect some shared state. I want it to run in fake virtual time so that the delays are just administrative updates to variables without any…
In this note I’ll show why the rate limit algorithms GCRA, leaky bucket, and token bucket behave the same. The parameters of the algorithms are a time window and a maximum quota of usage (e.g. requests or bytes) per window. The quota limits the size of a fast burst of requests. The maximum sustained rate is, rate = quota / window Leaky bucket and token bucket store the time of the previous…
There is an IETF draft that aims to standardize RateLimit header fields for HTTP . A RateLimit header in a successful response can inform a client when it might expect to be throttled, so it can avoid 429 Too Many Requests errors. Servers can also include RateLimit headers in a 429 response to make the error more informative. The draft is in reasonably good shape. However as written it seems to…
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…
Here’s a pearlescent winter holiday gift for you! There are four variants of the algorithm for shuffling an array, arising from two independent choices: whether to swap elements in the higher or lower parts of the array whether the boundary between the parts moves upwards or downwards The variants are perfectly symmetrical, but they work in two fundamentally different ways: sampling or…
Concrete tetrapods are used to dissipate wave energy in coastal defences. There’s a bit of a craze for making tetrapod-shaped things: recently I’ve seen people making a plush tetrapod and a tetrapod lamp . So I thought it might be fun to model one. I found a nice way to describe tetrapods that relies on very few arbitrary aesthetic choices. Click here to play with an animated tetrapod which I made…
Last year I wrote a pair of articles about ratelimiting: GCRA: leaky buckets without the buckets exponential rate limiting Recently, Chris “cks” Siebenmann has been working on ratelimiting HTTP bots that are hammering his blog. His articles prompted me to write some clarifications, plus a few practical anecdotes about ratelimiting email. mea culpa The main reason I wrote the GCRA article was to…
Although it looks really good, I have not yet tried the Jujutsu (jj) version control system , mainly because it’s not yet clearly superior to Magit . But I have been following jj discussions with great interest. One of the things that jj has not yet tackled is how to do better than git refs / branches / tags. As I underestand it, jj currently has something like Mercurial bookmarks, which are more…
What does it mean when someone writes that a programming language is “strongly typed”? I’ve known for many years that “strongly typed” is a poorly-defined term. Recently I was prompted on Lobsters to explain why it’s hard to understand what someone means when they use the phrase. I came up with more than five meanings! how strong? The various meanings of “strongly typed” are not clearly yes-or-no.…
Previously, I wrote some sketchy ideas for what I call a p-fast trie , which is basically a wide fan-out variant of an x-fast trie. It allows you to find the longest matching prefix or nearest predecessor or successor of a query string in a set of names in O(log k) cache misses, where k is the key length. My initial sketch was more complicated and greedy for space than necessary, so here’s a…
Here’s a sketch of an idea that might or might not be a good idea. Dunno if it’s similar to something already described in the literature – if you know of something, please let me know via the links in the footer! The gist is to throw away the tree and interior pointers from a qp-trie. Instead, the p-fast trie is stored using a hash map organized into stratified levels, where each level…
Here are a few tangentially-related ideas vaguely near the theme of comparison operators. comparison style clamp style clamp is median clamp in range range style style clash? comparison style Some languages such as BCPL, Icon, Python have chained comparison operators , like if min <= x <= max : ... In languages without chained comparison, I like to write comparisons as if they were chained, like,…
Here’s a story from nearly 10 years ago. the bug I think it was my friend Richard Kettlewell who told me about a bug he encountered with Let’s Encrypt in its early days in autumn 2015: it was failing to validate mail domains correctly . the context At the time I had previously been responsible for Cambridge University’s email anti-spam system for about 10 years, and in 2014 I had been given…
A couple of years ago I wrote about random floating point numbers . In that article I was mainly concerned about how neat the code is, and I didn’t pay attention to its performance. Recently, a comment from Oliver Hunt and a blog post from Alisa Sireneva prompted me to wonder if I made an unwarranted assumption. So I wrote a little benchmark, which you can find in pcg-dxsm.git . (Note 2025-06-09:…
In hot weather I like to drink my coffee in an iced latte. To make it, I have a very large Bialetti Moka Express . Recently when I got it going again after a winter of disuse, it took me a couple of attempts to get the technique right, so here are some notes as a reminder to my future self next year. It’s worth noting that I’m not fussy about my coffee: I usually drink pre-ground beans from the…
TIL (or this week-ish I learned) why big-sigma and big-pi turn up in the notation of dependent type theory. I’ve long been aware of the zoo of more obscure Greek letters that turn up in papers about type system features of functional programming languages, μ , Λ , Π , Σ . Their meaning is usually clear from context but the reason for the choice of notation is usually not explained. I recently…
About half a year ago I encountered a paper bombastically titled “the ultimate conditional syntax” . It has the attractive goal of unifying pattern match with boolean if tests, and its solution is in some ways very nice. But it seems over-complicated to me, especially for something that’s a basic work-horse of programming. I couldn’t immediately see how to cut it down to manageable proportions,…