Posts

Don't forget to add the niche

Rust is my favorite programming language. One of the many things I love about Rust is its layout optimizations that allow you to use high-level data types while still getting the same, or even better size and cache optimality than you would with C/C++. Possibly Rust's most impressive layout optimization is the famous niche optimization for enums, which is also, unfortunately, not the best advertised or the most obvious to exploit. When I'm writing Rust code, I use enums, especially Option and Result , all the time , so I've gotten somewhat keen to the mechanics of the optimization. In my opinion, it could stand to be easier to trigger; if you don't know the rules of niche optimization, you're almost certainly leaving cheap or free performance on the table. In some cases, the unused space is already there in your enum, going unused, but the compiler will not perform niche optimization unless you explicitly add a niche to your struct. Playground link with all ex...
Post a Comment
Read more

Between a block and a hard place

Image
Early this year, I saw a popular video on TikTok demonstrating a very unusual way of computing the digits of \(\pi\) using basic physics. At the time, I rederived the solution in a couple hours and then moved on. However, I was reminded of the problem recently and realized it might make for interesting blog material. Although I'm sure it's been written about countless times by now due to its popularity, I still felt the urge to redo the problem with extra rigor and write about it. @3blue1brown I’m still astounded this is true. #math #physics ♬ original sound - Grant Sanderson The setup is as follows: two blocks of masses \(m\) and \(M\), \(m < M\), lie on a frictionless plane. There is a wall behind the smaller block, and the larger block slides towards it with velocity \(V_0\). The larger block collides with the smaller block, which rebounds off the wall like a squash ball, over and over, until the larger block is completely turned ...
Post a Comment
Read more

Computing the probability of generating conflicting random strings

At work today, I was faced with the problem of generating unique, random identifiers for wire transfers that would fit inside of an ACH descriptor field. An ACH descriptor may contain at most 10 upper-case characters; for the random identifiers, we wished to restrict ourselves to letters only. However, with so few characters available in such a short string, the risk of generating conflicting IDs seemed significant, so I did some napkin math and quickly found that there was about a 50% chance of generating a conflict within 10 million identifiers. Not really a long-term scalable solution. I was particulary curious about whether adding digits to the IDs would result in a quantifiable improvement to the collision probability. After getting home, I did the math more rigorously on a notepad. First, preliminaries: there are \(n = 26^{10}\) possible strings we can generate. We consider a trial of length \(k\) to be a sequence of events where we select \(k - 1\) distinct...
Post a Comment
Read more