For moon child . This post describes a reader/writer version management scheme I recently came up with. I find it interesting because it is wait-free for readers and for the writer doesn’t need atomics (including fences) on TSO , or on ARMv8-a 1 for readers that keep up with the writer supports dynamic reader registration (dually, supports sleeping readers) bounds the number of protected (live)…
Nothing novel, just a different presentation for a decade-old data structure . I want to nail the presentation because this data structure is useful in many situations. Augmented FIFOs come up frequently in streaming analytics. For example, to compute the sum of the last \(k\) values observed in a stream (or more generally, in the turnstile model ), we can increment an accumulator by each value as…
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 one. In a reduction, each application of the binary…
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 collision probability at most \(\frac{|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 entities and generally prevent unintentional information…