Like many, when I first saw VPTERNLOG, my reaction was “\(\log_2(3) \approx 1.58\) is a nice reduction in depth, but my code mostly doesn’t have super deep reductions.” A little bit of thinking reveals a big win at smaller (reasonable) scales: a binary operator takes two values and outputs one, while a ternary operator takes three and outputs...
Per Vognsen sent me a link to Maziarz et al’s Hashing Modulo Alpha-Equivalence because its Lemma 6.6 claims to solve a thorny problem we have both encountered several times. Essentially, the lemma says that computing the natural recursive combination of hash values over \(2^b\) bits for two distinct trees (ADT instances) \(a\) and \(b\) yields a...
It looks like internauts are having another go at the “UUID as primary key” debate, where the fundamental problem is the tension between nicely structured primary keys that tend to improve spatial locality in the storage engine, and unique but otherwise opaque identifiers that avoid running into Hyrum’s law when communicating with external...
Sometimes you just want to abuse Linux perf to make it do a thing it’s not designed for, and a proper C program would represent an excessive amount of work. Here are two tricks I find helpful when jotting down hacky analysis scripts. Programmatically interacting with addr2line -i Perf can resolve symbols itself, but addr2line is a lot more...
Originally posted on the Backtrace I/O tech blog. All long-lived programs are either implemented in dynamic languages,1 or eventually Greenspun themselves into subverting static programming languages to create a dynamic system (e.g., Unix process trees). The latter approach isn’t a bad idea, but it’s easy to introduce more flexibility than...
Originally posted on the Backtrace I/O tech blog. Slitter is Backtrace’s deliberately middle-of-the-road thread-caching slab allocator, with explicit allocation class tags (rather than derived from the object’s size class). It’s mostly written in Rust, and we use it in our C backend server. Slitter’s design is about as standard as it gets: we...