# Tony Finch's blog Published articles for Tony Finch's blog. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## A revised algorithm for converting Gregorian dates to day counts DevFeed: [A revised algorithm for converting Gregorian dates to day counts]() Original publisher: [Read original article]() Published: 2026-08-09T02:29:48Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [Algorithm](), [DateTime](), [C](), [Code](), [function](), [Compiler]() Tags: [algorithm](), [c](), [code](), [compiler](), [data-type](), [function](), [range]() ### AI overview The article revisits an algorithm for converting Gregorian dates into Julian Day numbers or related day counts such as rata die. It explains the March-based month pattern, leap-year corrections, integer arithmetic, and limitations caused by overflow in the output data type. ### Source excerpt 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 March 31 days April 30 days May 31 days June 30 days July 31 days August 31 days September 30 days October 31 days November 30 days December 31 days January 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 express ## One page of async Rust DevFeed: [One page of async Rust]() Original publisher: [Read original article]() Published: 2026-02-17T19:34:20Z Content type: tutorial Language: en Sources: [Tony Finch's blog]() Topics: [async](), [Rust](), [Code](), [Compiler]() Tags: [async](), [code](), [compiler](), [rust]() ### AI overview A practical exploration of implementing a fake-time task simulation with lower-level async Rust. It explains futures, polling, pinning, contexts, wakers, and the boilerplate involved. ### Source excerpt 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 real sleep()ing, and I want to ensure that the mutations happen in the right order. I thought about doing this by representing each task as an enum State with a big match state to handle each step. But then I thought, isn't async supposed to be able to write the enum State and match state for me? And then I wondered how much the simulation would be overwhelmed by boilerplate if I wrote it using async. Rather than digging around for a crate that solves my problem, I thought I would use this as an opportunity to learn a little about lower-level async Rust. Turns out, if I strip away as much as possible, the boilerplate can fit on one side of a sheet of paper if it is printed at a normal font size. Not too bad! But I have questions... async fn-damentals pin a task noop context primops, generally primops, minimally contexts and wakers primops, commandingly primops, yieldingly fake sleep in action questions async fn-damentals My starting point was to write: async fn deep_thought() -> u32 { 42 } fn main() { deep_thought(); } playground When I call deep_thought() I immediately get a Future. As the compiler warns, none of the code in deep_thought() runs, it just constructs a value of an ineffable type which contains the initial state of deep_thought()'s state machine. To actually run it, I need to poll() it. The Future::poll() method has a signature that immediately presents a number of obstacles: fn poll( self: Pin<&mut Self>, ctx: &mut Context<'_>, ) -> Poll pin a task Unlike normal Rust data structures, a Future can contain references to itself. (In a ## GCRA vs leaky / token buckets DevFeed: [GCRA vs leaky / token buckets]() Original publisher: [Read original article]() Published: 2026-01-15T20:23:39Z Content type: tutorial Language: en Sources: [Tony Finch's blog]() Topics: [Algorithms]() ### AI overview The note explains why the GCRA, leaky bucket, and token bucket rate-limiting algorithms behave equivalently, deriving the GCRA formulation into leaky bucket code through transformations. ### Source excerpt 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 request, and a bucket counting the available capacity. The rate determines how quickly capacity becomes available. It's easy to see that leaky bucket and token bucket are equivalent, because they simply count in opposite directions: leaky -= (now - previous) * rate leaky = clamp(0, leaky, quota) leaky += cost previous = now return leaky < quota ? ALLOW : DENY tokens += (now - previous) * rate tokens = clamp(0, tokens, quota) tokens -= cost previous = now return tokens > 0 ? ALLOW : DENY GCRA tracks a "not-before" time, and allows requests that occur after that point in time. The not-before time is normally in the recent past, and requests increase it towards and possibly (when the client is over its limit) beyond the present time. time = clamp(now - window, time, now) time += cost / rate return time < now ? ALLOW : DENY It's not trivially obvious that GCRA is equivalent to the other two. But we can convert the GCRA code into the leaky bucket code with a few transformations, as follows. We can change from absolute time to relative time by taking now away from the equations: bucket = clamp(-window, time, 0) bucket += cost / rate return bucket < 0 ? ALLOW : DENY But that change is incomplete: the stored bucket is relative to the time of the previous request. To make it relative to the current time, we need to remember when the previous request occurred, and after retrieving the bucket we need to shift it to account for the passage of time: bucket -= now - previous bucket = clamp(-window, time, 0) bucket += cost / rate previous = now return bucket < 0 ? ALLOW : DENY Now we will change ## HTTP RateLimit headers DevFeed: [HTTP RateLimit headers]() Original publisher: [Read original article]() Published: 2026-01-14T02:34:22Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [HTTP](), [Algorithms](), [Internet Engineering Task Force (IETF)](), [client]() Tags: [algorithm](), [client](), [headers](), [http](), [ietf](), [server]() ### AI overview The article examines the IETF draft for HTTP RateLimit headers and argues that the headers can support linear rate-limit algorithms such as GCRA, encouraging smoother client request behavior than quota-reset algorithms. ### Source excerpt 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 require (or at least it assumes) that the server uses bad quota-reset rate limit algorithms. Quota-reset algorithms encourage clients into cyclic burst-pause behaviour; the draft has several paragraphs discussing this problem. However, if we consider that RateLimit headers are supposed to tell the client what acceptable behaviour looks like, they can be used with any rate limit algorithm. (And it isn't too hard to rephrase the draft so that it is written in terms of client behaviour instead of server behaviour.) When a client has more work to do than will fit in a single window's quota, linear rate limit algorithms such as GCRA encourage the client to smooth out its requests nicely. In this article I'll describe how a server can use a linear rate limit algorithm with HTTP RateLimit headers. spec summary policy parameters linear rate limit algorithm other rate limiters spec summary The draft specifies two headers: RateLimit-Policy: describes input parameters to a rate limit algorithm, which the server chooses based on the request in some unspecified way. The policies are expected to be largely static for a particular client. The parameters are, the name of the policy pk, the partition key q, the quota w, the window qu, the quota units RateLimit: describes which policies the server applied to this request, and the output results of the rate limit algorithm. The results are likely to vary per request depending on client behaviour or server load, etc. The results are, the name of the policy pk, the partition key r, the available quota t, the effective window Both headers can list ## hybrid quota-linear rate limiter DevFeed: [hybrid quota-linear rate limiter]() Original publisher: [Read original article]() Published: 2026-01-13T00:12:01Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [rate-limiting](), [Algorithms]() Tags: [algorithm](), [quotas](), [rate-limiting]() ### AI overview The article explores a hybrid quota-linear rate limiter intended to enforce request quotas more precisely within a time window while limiting storage costs and avoiding bursty client behavior. It compares linear rate limiting with fixed-window quota resets and notes trade-offs, including throttling response time and burstiness. ### Source excerpt 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. T ## Four variants of array-shuffle algorithms DevFeed: [Four variants of array-shuffle algorithms]() Original publisher: [Read original article]() Published: 2025-12-25T23:45:02Z Content type: tutorial Language: en Sources: [Tony Finch's blog]() Topics: [Algorithms](), [Algorithms, Complexity]() Tags: [algorithm](), [permutations]() ### AI overview The article examines four symmetric variants of an array-shuffling algorithm. It distinguishes sampling-based and permutation-based approaches, and places the common Durstenfeld shuffle among the variants. ### Source excerpt 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 permutation. The most common variant is Richard Durstenfeld's shuffle algorithm, which moves the boundary downwards and swaps elements in the lower part of the array. Knuth describes it in TAOCP vol. 2 sect. 3.4.2; TAOCP doesn't discuss the other variants. (Obeying Stigler's law, it is often called a "Fisher-Yates" shuffle, but their pre-computer algorithm is arguably different from the modern algorithm.) the four variants In the pseudocode below, min and max are the inclusive bounds on the array to be shuffled; the arguments to rand() are the inclusive bounds on its return value; and the loop bounds are inclusive too. I chose this style to make the symmetries more obvious. In all variants, it's possible for the indexes this (the boundary between the parts of the array) and that (chosen at random) to be the same, in which case the swap is a no-op. I could have written the loop bounds as min and max instead of min+1 and max-1 to make the variants look as similar as possible, but it's more realistic to omit the loop iterations when this and that are guaranteed to be equal. It should be clear that rand() is invoked for spans of each size between 2 and N (where N = max - min + 1) so the algorithms produce N! possible permutations as expected. boundary moves down, pick from lower shuffle(a, min, max) for this = max to min+1 step -1 that = rand(min, this) swap a[this] and a[that] boundary moves up, pick from higher shuffle(a, min, max) for this = min to max-1 step +1 that = rand(this, max) swap a[this] and a[that] boundary moves down, pick from higher shuffle(a, min, max) for this = max-1 t ## How to Configure Leaky Bucket, GCRA, and Exponential Rate Limiters DevFeed: [How to Configure Leaky Bucket, GCRA, and Exponential Rate Limiters]() Original publisher: [Read original article]() Published: 2025-09-14T03:30:44Z Content type: tutorial Language: en Sources: [Tony Finch's blog]() Topics: [rate-limiting](), [client](), [HTTP](), [email](), [Server]() Tags: [client](), [email](), [http](), [rate-limiting](), [servers]() ### AI overview This article explains how to configure leaky bucket, GCRA, and exponential rate limiters using a limit and a period. It describes average rates, burst sizes, forgetting behavior, and an email-server example for detecting spam. ### Source excerpt 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 explain GCRA better without the standard obfuscatory terminology, and to compare GCRA with a non-stupid version of the leaky bucket algorithm. It wasn't written with my old exponential ratelimiting in mind, so I didn't match up the vocabulary. In the exponential ratelimiting article I tried to explain how the different terms correspond to the same ideas, but I botched it by trying to be too abstract. So let's try again. parameters It's simplest to configure these ratelimiters (leaky bucket, GCRA, exponential) with two parameters: limit period The maximum permitted average rate is calculated from these parameters by dividing them: rate = limit / period The period is the time over which client behaviour is averaged, which is also how long it takes for the ratelimiter to forget past behaviour. In my GCRA article I called it the window. Linear ratelimiters (leaky bucket and GCRA) are 100% forgetful after one period; the exponential ratelimiter is 67% forgetful. The limit does double duty: as well as setting the maximum average rate (measured in requests per period) it sets the maximum size (measured in requests) of a fast burst of requests following a sufficiently long quiet gap. how bursty You can increase or decrease the burst limit - while keeping the average rate limit the same - by increasing or decreasing both the limit and the period. For example, I might set limit = 600 requests per period = 1 hour. If I want to allow the same average rate, but with a smaller burst size, I might set limit = 10 requests per period = 1 minute. anecdote When I was looking after email servers ## first-class merges and cover letters DevFeed: [first-class merges and cover letters]() Original publisher: [Read original article]() Published: 2025-09-11T01:26:47Z Content type: opinion Language: en Sources: [Tony Finch's blog]() Topics: [Git](), [version-control](), [Development](), [pull-requests](), [Code review]() Tags: [branch](), [git](), [merge](), [review](), [version-control](), [workflow]() ### AI overview This commentary examines shortcomings in Git branches and common merge and rebase workflows. It argues that improving merges, rather than branches alone, could make branch-based development more effective, while considering trade-offs between detailed history and clean logical changes. ### Source excerpt 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 like raw git ref plumbing than a high-level porcelain feature. In particular, jj lacks signed or annotated tags, and it doesn't have branch names that always automatically refer to the tip. This is clearly a temporary state of affairs because jj is still incomplete and under development and these gaps are going to be filled. But the discussions have led me to think about how git's branches are unsatisfactory, and what could be done to improve them. branch merge rebase squash fork cover letters previous branch workflow questions branch One of the huge improvements in git compared to Subversion was git's support for merges. Subversion proudly advertised its support for lightweight branches, but a branch is not very useful if you can't merge it: an un-mergeable branch is not a tool you can use to help with work-in-progress development. The point of this anecdote is to illustrate that rather than trying to make branches better, we should try to make merges better and branches will get better as a consequence. Let's consider a few common workflows and how git makes them all unsatisfactory in various ways. Skip to cover letters and previous branch below where I eventually get to the point. merge A basic merge workflow is, create a feature branch hack, hack, review, hack, approve merge back to the trunk The main problem is when it comes to the merge, there may be conflicts due to concurrent work on the trunk. Git encourages you to resolve conflicts while creating the merge commit, which tends to bypass the normal review process. Git also gives you an ugly useless canned commit messa ## What Strong Typing Means in Programming Languages DevFeed: [What Strong Typing Means in Programming Languages]() Original publisher: [Read original article]() Published: 2025-08-28T01:33:05Z Content type: opinion Language: en Sources: [Tony Finch's blog]() Topics: [Programming language](), [Programming](), [integrity](), [Polymorphism](), [Java](), [TypeScript](), [Lean]() Tags: [integrity](), [java](), [languages](), [polymorphism](), [programming-language](), [rust](), [type-system](), [typescript]() ### AI overview The article explains why "strongly typed" is a poorly defined term and examines several possible meanings, including static versus dynamic typing, soundness of static type systems, and runtime type safety. It argues that these properties are not simply yes-or-no and discusses trade-offs and examples from languages including Java, TypeScript, Rust, Lean, JavaScript, Lua, and C. ### Source excerpt 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. Some developers like to argue that these kinds of integrity checks must be completely perfect or else they are entirely worthless. Charitably (it took me a while to think of a polite way to phrase this), that betrays a lack of engineering maturity. Software engineers, like any engineers, have to create working systems from imperfect materials. To do so, we must understand what guarantees we can rely on, where our mistakes can be caught early, where we need to establish processes to catch mistakes, how we can control the consequences of our mistakes, and how to remediate when somethng breaks because of a mistake that wasn't caught. strong how? So, what are the ways that a programming language can be strongly or weakly typed? In what ways are real programming languages "mid"? Statically typed as opposed to dynamically typed? Many languages have a mixture of the two, such as run time polymorphism in OO languages (e.g. Java), or gradual type systems for dynamic languages (e.g. TypeScript). Sound static type system? It's common for static type systems to be deliberately unsound, such as covariant subtyping in arrays or functions (Java, again). Gradual type systems migh have gaping holes for usability reasons (TypeScript, again). And some type systems might be unsound due to bugs. (There are a few of these in Rust.) Unsoundness isn't a disaster, if a programmer won't cause it without being aware of the risk. For example: in Lean you can write "sorry" as a kind of "to do" annotation that deliberately breaks soundness; and Idris 2 has type-in-type so it accepts Girard's paradox. T ## A simplified p-fast trie for prefix and predecessor searches DevFeed: [A simplified p-fast trie for prefix and predecessor searches]() Original publisher: [Read original article]() Published: 2025-08-06T17:19:09Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [Algorithm](), [hash](), [Cache](), [Query (disambiguation)]() Tags: [algorithm](), [cache](), [hash](), [query]() ### AI overview The article presents a simplified revision of a p-fast trie, a wide fan-out variant of an x-fast trie. It describes a hash-table layout for storing unique prefixes and outlines longest-prefix, predecessor, and successor searches. ### Source excerpt 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 simplified revision. ("p" now stands for prefix.) layout A p-fast trie stores a lexicographically ordered set of names. A name is a sequence of characters from some small-ish character set. For example, DNS names can be represented as a set of about 50 letters, digits, punctuation and escape characters, usually one per byte of name. Names that are arbitrary bit strings can be split into chunks of 6 bits to make a set of 64 characters. Every unique prefix of every name is added to a hash table. An entry in the hash table contains: A shared reference to the closest name lexicographically greater than or equal to the prefix. Multiple hash table entries will refer to the same name. A reference to a name might instead be a reference to a leaf object containing the name. The length of the prefix. To save space, each prefix is not stored separately, but implied by the combination of the closest name and prefix length. A bitmap with one bit per possible character, corresponding to the next character after this prefix. For every other prefix that matches this prefix and is one character longer than this prefix, a bit is set in the bitmap corresponding to the last character of the longer prefix. search The basic algorithm is a longest-prefix match. Look up the query string in the hash table. If there's a match, great, done. Otherwise proceed by binary chop on the length of the query string. If the prefix isn't in the hash table, reduce the prefix length and search again. (If the empty prefix isn't in the hash table then there are no names to find.) If the prefix is in the hash table, check ## p-fast trie: lexically ordered hash map DevFeed: [p-fast trie: lexically ordered hash map]() Original publisher: [Read original article]() Published: 2025-08-04T20:52:21Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [hash](), [Query (disambiguation)](), [Rust]() Tags: [array](), [bits](), [hash](), [map](), [maps](), [query]() ### AI overview This article sketches the p-fast trie, a proposed lexically ordered hash map that replaces a qp-trie's tree and interior pointers with stratified hash-map levels keyed by prefixes. It describes O(1) exact-match lookups and O(log k) predecessor and successor searches, while noting that the practical benefit is uncertain. ### Source excerpt 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 corresponds to a prefix of the key. Exact-match lookups are normal O(1) hash map lookups. Predecessor / successor searches use binary chop on the length of the key. Where a qp-trie search is O(k), where k is the length of the key, a p-fast trie search is O(log k). This smaller O(log k) bound is why I call it a "p-fast trie" by analogy with the x-fast trie, which has O(log log N) query time. (The "p" is for popcount.) I'm not sure if this asymptotic improvement is likely to be effective in practice; see my thoughts towards the end of this note. layout A p-fast trie consists of: Leaf objects, each of which has a name. Each leaf object refers to its successor forming a circular linked list. (The last leaf refers to the first.) Multiple interior nodes refer to each leaf object. A hash map containing every (strict) prefix of every name in the trie. Each prefix maps to a unique interior node. Names are treated as bit strings split into chunks of (say) 6 bits, and prefixes are whole numbers of chunks. An interior node contains a (1<<6) == 64 wide bitmap with a bit set for each chunk where prefix+chunk matches a key. Following the bitmap is a popcount-compressed array of references to the leaf objects that are the closest predecessor of the corresponding prefix+chunk key. Prefixes are strictly shorter than names so that we can avoid having to represent non-values after the end of a name, and so that it's OK if one name is a prefix of another. The size of chunks and bitmaps might change; 6 is a guess that I expect will work OK. For restricted alphabets you can use something like my DNS trie n ## clamp / median / range DevFeed: [clamp / median / range]() Original publisher: [Read original article]() Published: 2025-07-02T01:33:08Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [Programming](), [Code](), [function](), [syntax](), [iteration]() Tags: [article](), [comparison](), [function](), [languages](), [sequence](), [syntax]() ### AI overview The article explores stylistic conventions for comparison operators, including chained comparisons, ordering values from least to greatest, and arranging clamp arguments to match that order. It then considers median-of-three implementations that are insensitive to argument order and proposes a speculative range syntax for pattern matching, iteration, and slicing. ### Source excerpt 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, if min <= x && x <= max { // ... } A rule of thumb is to prefer less than (or equal) operators and avoid greater than. In a sequence of comparisons, order values from (expected) least to greatest. clamp style The clamp() function ensures a value is between some min and max, def clamp(min, x, max): if x < min: return min if max < x: return max return x I like to order its arguments matching the expected order of the values, following my rule of thumb for comparisons - and the description of what clamp() does. (I used this flavour of clamp() in my article about GCRA.) But I seem to be unusual in this preference, based on a few examples I have seen recently. clamp is median Last month, Fabian Giesen pointed out a way to resolve this difference of opinion: A function that returns the median of three values is equivalent to a clamp() function that doesn't care about the order of its arguments. This version is written so that it returns NaN if any of its arguments is NaN. (When an argument is NaN, both of its comparisons will be false.) fn med3(a: f64, b: f64, c: f64) -> f64 { match (a <= b, b <= c, c <= a) { (false, false, false) => f64::NAN, (false, false, true) => b, // a > b > c (false, true, false) => a, // c > a > b (false, true, true) => c, // b <= c <= a (true, false, false) => c, // b > c > a (true, false, true) => a, // c <= a <= b (true, true, false) => b, // a <= b <= c (true, true, true) => b, // a == b == c } } When two of its arguments are constant, med3() should compile to the same code as a simple clamp(); but med3()'s misuse-resistance comes at a small cost when t ## Golang and Let's Encrypt: a free software story DevFeed: [Golang and Let's Encrypt: a free software story]() Original publisher: [Read original article]() Published: 2025-06-26T01:41:49Z Content type: opinion Language: en Sources: [Tony Finch's blog]() Topics: [let's encrypt](), [free software](), [Pull Request](), [CASE](), [Testing](), [CI/CD]() Tags: [bug](), [continuous-integration](), [free-software](), [golang](), [let-s-encrypt](), [pull-request](), [review](), [testing]() ### AI overview The author recounts fixing a Let's Encrypt Boulder bug involving mail-domain validation as a newcomer to Golang. They describe relying on Let's Encrypt's cloud test setup, submitting a small pull request, and seeing it merged into production within a few days. ### Source excerpt 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 responsibility for Cambridge University's DNS. So I knew how Let's Encrypt should validate mail domains. Let's Encrypt was about one year old. Unusually, the code that runs their operations, Boulder, is free software and open to external contributors. Boulder is written in Golang, and I had not previously written any code in Golang. But its reputation is to be easy to get to grips with. So, in principle, the bug was straightforward for me to fix. How difficult would it be as a Golang newbie? And what would Let's Encrypt's contribution process be like? the hack I cloned the Boulder repository and had a look around the code. As is pretty typical, there are a couple of stages to fixing a bug in an unfamiliar codebase: work out where the problem is try to understand if the obvious fix could be better In this case, I remember discovering a relatively substantial TODO item that intersected with the bug. I can't remember the details, but I think there were wider issues with DNS lookups in Boulder. I decided it made sense to fix the immediate problem without getting involved in things that would require discussion with Let's Encrypt staff. I faffed around with the code and pushed something that looked like it might work. A fun thing about this hack is that I never got a working Boulder test setup on my workstation (or even Golang, I think!) - I just relied on the Let's Encrypt cloud test setup. The feedback time was very slow, but it was tolerable for a simple one-off change. the fix My pull request was small, +48-14. After a couple of rounds of review and within a few days, it was merged ## performance of random floats DevFeed: [performance of random floats]() Original publisher: [Read original article]() Published: 2025-06-08T02:08:35Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [floating-point](), [Benchmark](), [Code](), [Arm](), [Compiler]() Tags: [arm](), [benchmark](), [code](), [compiler](), [floating-point](), [performance]() ### AI overview This article benchmarks two methods for converting random integers into floating-point values between 0.0 and 1.0: bit manipulation and shift-convert-multiply. It discusses their generated amd64 and Arm64 code, including notably compact Arm64 translations produced by recent Clang versions, and describes tests on Apple M1 Pro and AMD Ryzen 7950X systems. ### Source excerpt 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: I've edited this post substantially after discovering some problems with the results.) recap code bithack multiply benchmark results conclusion recap Briefly, there are two basic ways to convert a random integer to a floating point number between 0.0 and 1.0: Use bit fiddling to construct an integer whose format matches a float between 1.0 and 2.0; this is the same span as the result but with a simpler exponent. Bitcast the integer to a float and subtract 1.0 to get the result. Shift the integer down to the same range as the mantissa, convert to float, then multiply by a scaling factor that reduces it to the desired range. This produces one more bit of randomness than the bithacking conversion. (There are other less basic ways.) code The double precision code for the two kinds of conversion is below. (Single precision is very similar so I'll leave it out.) It's mostly as I expect, but there are a couple of ARM instructions that surprised me. bithack The bithack function looks like: double bithack52(uint64_t u) { u = ((uint64_t)(1023) << 52) | (u >> 12); return(bitcast(double, u) - 1.0); } It translates fairly directly to amd64 like this: bithack52: shr rdi, 12 movabs rax, 0x3ff0000000000000 or rax, rdi movq xmm0, rax addsd xmm0, qword ptr [rip + .number] ret .number: .quad 0xbff0000000000000 On arm64 the shift-and-or becomes one bfxil instruction (which is a kind of bitfield move), and the constant -1.0 is encoded more briefly. Very neat! bithack52: mov x8, #0x3ff0000000000000 fmov d0, #-1.00000000 bfxil x8, x0, #12, #52 fmov d1, x8 fadd d0, d1, d0 ret multiply The shift-conv ## the algebra of dependent types DevFeed: [the algebra of dependent types]() Original publisher: [Read original article]() Published: 2025-05-29T00:07:51Z Content type: article Language: en Sources: [Tony Finch's blog]() Topics: [Programming](), [Functional programming](), [Standard ML](), [Rust]() Tags: [algebra](), [enum](), [functional-programming](), [languages](), [programming-languages](), [type-system](), [type-theory](), [types]() ### AI overview An explanation of why big-sigma and big-pi notation appears in dependent type theory. It connects dependent functions and dependent pairs to algebraic data types, showing how products correspond to multiplication and sum types to addition, with examples from type theory, Standard ML, Haskell, and Rust. ### Source excerpt 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 stumbled on an explanation for Π (dependent functions) and Σ (dependent pairs) which turn out to be nicer than I expected, and closely related to every-day algebraic data types. sizes of types The easiest way to understand algebraic data types is by counting the inhabitants of a type. For example: the unit type () has one inhabitant, (), and the number 1 is why it's called the unit type; the bool type hass two inhabitants, false and true. I have even seen these types called 1 and 2 (cruelly, without explanation) in occasional papers. product types Or pairs or (more generally) tuples or records. Usually written, (A, B) The pair contains an A and a B, so the number of possible values is the number of possible A values multiplied by the number of possible B values. So it is spelled in type theory (and in Standard ML) like, A * B sum types Or disjoint union, or variant record. Declared in Haskell like, data Either a b = Left a | Right b Or in Rust like, enum Either { Left(A), Right(B), } A value of the type is either an A or a B, so the number of possible values is the number of A values plus the number of B values. So it is spelled in type theory like, A + B dependent pairs In a dependent pair, the type of the second element depends on the value of the first. The classic example is a slice, roughly, struct IntSlice { len: usize, elem: &[i64; len], } (This might look a bit circular, but the idea is that an array [i64; N] must be told how big it is - its size is an explicit part of its type - but an IntSlice knows its own size. The traditional dependent "vector" type is a sized li