More from samwho.dev
body { text-wrap: pretty; } @media (prefers-reduced-motion: reduce) { * { transition: none; animation: none; } } turing-machine { width: 100%; display: block; position: relative; padding-bottom: 1em; } turing-machine .program-container { position: relative; display: flex; justify-content: center; } turing-machine table { border: none; font-family: Fira Code; border-collapse: collapse; border-spacing: 0; margin: 1px; margin-top: 0.5em; width: auto; } turing-machine thead td { text-align: center; } turing-machine td { text-align: left; padding-left: 3vw; padding-right: 3vw; padding-top: 0.2em; padding-bottom: 0.2em; border: 1px dashed #bbbbbb; } turing-machine thead td { border: 0; } turing-machine .container { z-index: 1; background-color: white; } turing-machine .svg-container { padding-bottom: 1px; padding-top: 0.5em; line-height: 0; overflow-x: scroll; overflow-y: hidden; position: relative; scrollbar-width: none; cursor: grab; cursor: -webkit-grab; } turing-machine .svg-container::-webkit-scrollbar { display: none; } turing-machine .controls-container { line-height: 1.5; display: flex; align-items: center; justify-content: center; gap: 0.3em; margin-top: 0.2em; padding-bottom: 0.2em; } turing-machine .controls-container button { color: black; background-color: #aaaaaa; border-radius: 30%/50%; padding: 0.3em; height: 2em; min-width: 3em; text-align: center; border: none; cursor: pointer; } turing-machine .controls-container select { color: black; border: 2px solid #aaaaaa; background-color: #ffffff; border-radius: 30%/50%; padding: 0.15em; height: 2em; min-width: 3em; text-align: center; cursor: pointer; font-family: "Fira Code"; } turing-machine .controls-container button:disabled { background-color: #eeeeee; color: #aaaaaa; cursor: auto; } turing-machine .controls-container button:disabled:hover { background-color: #eeeeee; } turing-machine .controls-container button:hover { background-color: #999999; } turing-machine .controls-container button:active { background-color: #888888; } turing-machine .error { width: 80%; margin-top: 0.5em; margin-bottom: 0.5em; border-radius: 10px; background-color: #ffdddd; color: red; font-family: "Fira Code"; font-size: 1.5em; font-weight: bold; text-align: center; margin: auto; } .dragging { cursor: grabbing !important; cursor: -webkit-grabbing !important; } .sticky { position: sticky !important; top: 0; } turing-machine .gradient { content: ""; z-index: 2; position: sticky; top: 0; left: 0; pointer-events: none; background-image: linear-gradient(90deg, rgba(255,255,255,1) 0%, rgba(255,255,255,0) 20%, rgba(255,255,255,0) 80%, rgba(255,255,255,1) 100%); width: 100%; margin-top: -62px; height: 64px; } turing-machine svg { user-select: none; /*touch-action: none;*/ } turing-machine svg text { font-family: "Fira Code"; } turing-machine tr { padding-top: 0.5em; padding-bottom: 0.5em; } turing-machine .instruction { color: black; display: inline-block; border-radius: 0.5em; padding: 0.1em; min-width: 4.5ch; height: 100%; text-align: center; } turing-machine .pointer { display: inline-block; border-radius: 0.5em; position: absolute; z-index: -1; } turing-machine program { display: none; } turing-machine controls { display: none; } turing-machine.heading svg text { font-family: "Lora"; font-weight: bold; } figure.hero { font-family: "Lora"; text-align: center; padding-top: 1em; padding-bottom: 2em; margin-top: 1em; width: 100%; max-width: 100%; } figure.hero turing-machine { padding: 0; margin: 0; } figure.hero turing-machine .svg-container { margin: 0; padding-top: 0; } figure.hero turing-machine .gradient { top: 0; } figure.hero .signature { margin-top: 0.5rem; max-width: 200px; } figure.hero .portrait { margin-top: 1em; width: 250px; max-width: 250px; } figure.hero p { padding: 0; font-size: 0.9em; } figure.hero figcaption { font-family: "Lora"; font-style: small-caps; font-size: 0.8em; } @keyframes pulse { 0% { transform: scale(1); } 50% { transform: scale(1.1); } 100% { transform: scale(1); } } .symbol { display: inline-block; border: 1px solid black; width: 1.5em; height: 1.5em; font-family: "Fira Code"; text-align: center; } .inline-instruction { display: inline-block; font-family: "Fira Code"; background-color: rgba(0, 158, 115, 0.7); color: black; border-radius: 0.5em; padding: 0.1em; min-width: 3ch; padding-left: 0.2em; padding-right: 0.2em; text-align: center; } li:has(.inline-instruction) { margin-top: 0.35em; margin-bottom: 0.35em; } .inline-state { display: inline-block; font-family: "Fira Code"; background-color: rgb(86, 180, 233); color: black; border-radius: 0.5em; padding: 0.1em; min-width: 3ch; padding-left: 0.2em; padding-right: 0.2em; text-align: center; } li:has(.inline-state) { margin-top: 0.35em; margin-bottom: 0.35em; } .inline-value { display: inline-block; font-family: "Fira Code"; background-color: rgb(230, 159, 0); color: black; border-radius: 0.5em; padding: 0.1em; min-width: 3ch; padding-left: 0.2em; padding-right: 0.2em; text-align: center; } li:has(.inline-value) { margin-top: 0.35em; margin-bottom: 0.35em; } figure { margin: auto; margin-top: 2em; margin-bottom: 2em; } figure img { max-width: 400px; } figure figcaption { max-width: 500px; color: #666; font-size: 0.8em; font-style: italic; text-align: center; font-family: "Lora"; text-wrap: pretty; margin: auto; } ALAN M. TURING 23 June 1912 – 7 June 1954 B B | | L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) L P( ) -> F In 1928, David Hilbert, one of the most influential mathematicians of his time, asked whether it is possible to create an algorithm that could determine the correctness of a mathematical statement. This was called the "decision problem," or "Entscheidungsproblem" in Hilbert's native German. In 1936 both Alan Turing and Alonzo Church independently reached the conclusion, using different methods, that the answer is "no." The way Turing did it was to imagine a "universal machine", a machine that could compute anything that could be computed. This idea, the "Turing machine" as Alonzo Church christened it in 1937, laid the foundations for the device you are using to read this post. If we look hard enough we can see Turing's legacy in today's CPUs. By the end of this post, you will know: What a Turing machine is. What can and cannot be computed. What it means to be Turing complete. How modern computers relate to Turing machines. How to write and run your own programs for a Turing machine. # What is a Turing machine? You might expect a universal machine, capable of computing anything that can be computed, to be a complex device. Nothing could be further from the truth. The machine has just 4 parts, and the language used to program it has just 5 instructions. theoretical machine. It was created as a thought experiment to explore the limits of what can be computed. Some have of course been built, but in 1936 they existed only in the heads of Turing and those who read his paper. The parts are: a !tape, a !head, a !program, and a !state. When you're ready, go ahead and press !play. start What you're seeing here is a program that executes P(0) to print 0 to the tape, moves the head right with the R instruction, then !jumps back to the start. It will go on printing 0s forever. At any point, feel free to !pause, step the machine !forwards or !backwards one instruction at a time, or !restart the program from the beginning. There is also a speed selector on the far right of the controls if you want to speed up the machine. Notice that !state and !value never change. Every time the machine performs a !jump, the current state and value are used to pick the correct next row of instructions to execute. This program only has a single state, start, and every time it jumps, the symbol under the !head is !blank. Let's take a look at a program with multiple states. one one | | P(1) R -> zero This program prints alternating 0s and 1s to the tape. It has 2 states, zero and one, to illustrate what happens when you !jump to a different state. Things moving too fast? The slider below can be used to adjust the speed of all the Turing machines on this page. 100% You can also achieve this same result by using a single !state and alternating the !value. Here's an example of that: start start | 1 | R P(0) -> start start | 0 | R P(1) -> start The !value column always stays up to date with what the current symbol is under the !head, then when we !jump that value is used to know which row of instructions to execute. Combining state and value gives us a surprising amount of control over what our !program does. We've so far seen 3 instructions: P prints a given symbol to the tape. R moves the tape head right. ↪︎ jumps to a given state. There are 2 more: L moves the tape head left. H halts the machine. 1 1 | | P(a) L -> 2 2 | | P(l) L -> 3 3 | | P(A) H This program prints the word "Alan" from right to left then halts. If you can't see the full word, you can drag the !tape left and right. If the machine has halted, you can use !restart to start it again from the beginning. All of it! You're probably not going to get Crysis running at 60fps on a simulated Turing machine, but all of the calculations required to render each frame can be done with just these 5 instructions. Everything you have ever seen a computer do can be done with a Turing machine. We'll see a glimpse of how that can work in practice a little later. The last example I want to show you before we move on is the very first program Alan Turing showed the world. It's the first program featured in his 1936 paper: "On Computable Numbers, with an application to the Entsheidungsproblem." c c | | R -> e e | | P(1) R -> k k | | R -> b Turing liked to leave spaces between symbols, going as far as to even define them as "F-squares" and "E-squares". F for figure, and E for erasable. His algorithms would often make use of E-squares to help the machine remember the location of specific !tape squares. # What does it mean to compute? Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable. Here I'm giving the machine a !tape that starts out with the values 2 and 6 in binary separated by a !blank. b1 b1 | 1 | R -> b1 b1 | | R -> b2 b2 | 0 | R -> b2 b2 | 1 | R -> b2 b2 | | L -> dec dec | 0 | P(1) L -> dec dec | 1 | P(0) L -> b3 dec | | H b3 | 0 | L -> b3 b3 | 1 | L -> b3 b3 | | L -> inc inc | 0 | P(1) R -> b1 inc | 1 | P(0) L -> inc inc | | P(1) R -> b1 This program adds the two numbers together, arriving at the answer 8. It does this by decrementing from the right number and incrementing the left number until the right number is 0. Here's the purpose of each state: b1 Move right until the first !blank square is found. This is to navigate past the first number. b2 Move right until the second !blank square is found. This is to navigate past the second number. dec Decrement the current number by 1. In practice this will always be the right number. It decrements by flipping bits until it either reaches a 1, where it will navigate back to the left number, or a !blank, which it will interpret as the number having hit 0. b3 Move left until the first !blank square again. This is only ever used after we've decremented the rightmost number. We can't reuse the b1 state here because when we reach the !blank, we want to jump to inc. inc Increment the current number by 1. Similar to decrementing, this will only ever happen on the leftmost number in practice. This is done by flipping bits until we reach a 0, at which point we navigate back to the right number. That we can write this program at all is proof that addition is computable, but it also implies that all integers are computable. If we can add any 2 integers, we can compute any other integer. 1 is 0+1, 2 is 1+1, 3 is 2+1, and so on. # Binary vs Decimal You may have wondered why I'm choosing to work with binary numbers rather than decimal. It's not just because that's how modern computers work. I'm going to show you 2 examples, and from those examples you'll be able to see why modern computers choose to work in binary. The first example is a program that increments a binary number in an endless loop. move move | 0 | R -> move move | | L -> flip flip | 0 | P(1) R -> move flip | 1 | P(0) L -> flip flip | | P(1) R -> move The second example is a program that increments a decimal number in an endless loop. back inc | 1 | P(2) -> back inc | 2 | P(3) -> back inc | 3 | P(4) -> back inc | 4 | P(5) -> back inc | 5 | P(6) -> back inc | 6 | P(7) -> back inc | 7 | P(8) -> back inc | 8 | P(9) -> back inc | 9 | P(0) L -> inc inc | | P(1) -> back back | | L -> inc back | * | R -> back These two programs are doing the same thing, but the program for manipulating decimal numbers is much longer. We've even introduced some new syntax, the * symbol, to handle a !value under the !head that does not match any of the other values for that !state. It's for this reason when programming Turing machines we prefer binary numbers: the programs end up being shorter and easier to reason about. This benefit also translates to the physical world. Components that switch between 2 states are cheaper, smaller, and more reliable than components that switch between 10. It was more practical to build computers that worked in binary than ones that work in decimal, though attempts to build decimal computers were made. # What can't be computed? To approach this question we need to explain the "Halting problem." It goes like this: The answer is no, and this is what Turing essentially proved. The proof is complicated and I'm not ashamed to admit I don't understand it, but there is an example I can give you that can be intuitively understood to be "undecidable." Imagine you write a program that takes as its input the program being used to decide whether it will halt or not. What it then does is run the decider program on itself, and then do the opposite of what the decider program says. function undecidable(willHalt) { if (willHalt(undecidable)) { while (true); } else { return true; } } This program intentionally enters an infinite loop if it is told it will halt, and halts if it is told it will run forever. It seems like a silly example, the kind of answer a cheeky high school student might try to get away with, but it is a legitimate counterexample to the idea that the halting problem can be solved. If you were to imagine encoding the program and input into something that could be represented on the !tape, there would be no !program that could determine whether the program would halt or not. Imagining this encoding becomes quite natural when you realise that modern programs are encoded as binary data to be saved to disk. # What does it mean to be Turing complete? If you've been involved in the world of programming for more than a few years, there's a good chance you've come across the term "Turing complete." Most likely in the context of things that really ought not to be Turing complete, like C++ templates, TypeScript's type system or Microsoft Excel. But what does it mean? Like the Halting problem, the proof is complicated but there's a straightforward test you can apply to something to judge it Turing complete: I've written this post, with the Turing machine simulations, in JavaScript. Therefore JavaScript is Turing complete. The C++ template example given above simulates a Turing machine in C++'s template system. The TypeScript example takes the route of writing an interpreter for a different Turing complete language. You're right, and everyone tends to cheat a bit with the definition. When someone says something is Turing complete, what they mean is it would be Turing complete if it had an infinite amount of memory. The infinite tape limitation means no Turing machine could ever exist in our physical reality, so that requirement tends to get waived. # How does this all relate to modern computers? If you read around the topic of Turing machines outside of this post, you might see it said that modern computers are effectively Turing machines. You would be forgiven for finding it difficult to imagine how you go from adding 2 integers in binary on a !tape to running a web browser, but the line is there. A key difference between our Turing machine and the device you're reading this on is that your device's CPU has "registers." These are small pieces of memory that live directly on the CPU and are used to store values temporarily while they're being operated on. Values are being constantly loaded from memory into registers and saved back again. You can think of registers as variables for your CPU, but they can only store fixed-size numbers. We can create registers in our Turing machine. We can do this by creating a "format" for our tape. Here we define 3 registers: A, B, and C. Each register contains a 3 bits and can store numbers between 0 and 7. Then at the far left we have an H, which stands for "home", which will help us navigate. To increment register C, we can write a program like this: goto_c goto_c | C | R R R -> inc inc | 0 | P(1) -> goto_h goto_h | * | L -> goto_h goto_h | H | H We're making a lot more liberal use of the * symbol here to help us navigate to specific parts of the !tape without having to enumerate all possible values that could be under the !head on the way there. This program is effectively equivalent to the following x86 assembly code, if x86 had a register named c: mov c, 0 ; Load 0 into c inc c ; Increment c by 1 If we wanted to add values in A and B, storing the result in C, we need to do more work. Here's the assembly code we're trying to replicate: mov a, 2 ; Load 2 into a mov b, 3 ; Load 3 into b add c, a ; Add a to c add c, b ; Add b to c Before you scroll down I will warn you that the program is long and complex. It is the last program we will see in this post, and I don't expect you to understand it in full to continue to the end. Its main purpose is to show you that we can implement operations seen in modern assembly code on a Turing machine. initb initb | * | R P(0) R P(1) R P(1) R -> start start | * | L -> start start | H | R -> go_a go_a | * | R -> go_a go_a | A | R R R -> dec_a dec_a | 0 | P(1) L -> cry_a dec_a | 1 | P(0) -> go_c1 cry_a | 0 | P(1) L -> cry_a cry_a | 1 | P(0) -> go_c1 cry_a | * | R P(0) R P(0) R P(0) -> goto_b go_c1 | * | R -> go_c1 go_c1 | C | R R R -> inc_c1 inc_c1 | 0 | P(1) -> h2a inc_c1 | 1 | P(0) L -> cry_ca cry_ca | 0 | P(1) -> h2a cry_ca | 1 | P(0) L -> cry_ca cry_ca | * | R -> h2a h2a | * | L -> h2a h2a | H | R -> go_a goto_b | * | R -> goto_b goto_b | B | R R R -> dec_b dec_b | 0 | P(1) L -> dec_bc dec_b | 1 | P(0) -> go_c2 dec_bc | 0 | P(1) L -> dec_bc dec_bc | 1 | P(0) -> go_c2 dec_bc | * | R P(0) R P(0) R P(0) -> end go_c2 | * | R -> go_c2 go_c2 | C | R R R -> inc_c2 inc_c2 | 0 | P(1) -> go_hb inc_c2 | 1 | P(0) L -> cry_cb cry_cb | 0 | P(1) -> go_hb cry_cb | 1 | P(0) L -> cry_cb cry_cb | * | R -> go_hb go_hb | * | L -> go_hb go_hb | H | R -> goto_b end | * | L -> end end | H | H This is painfully laborious, and it doesn't even precisely match the assembly code. It destroys the values in A and B as it adds them together, and it doesn't handle overflow. But it's a start, and I hope it gives you a glimpse of how this theoretical machine can be built up to operate like a modern CPU. If you watch the program run to completion, something that might strike you is just how much work is required to do something as simple as adding 2 numbers. Turing machines were not designed to be practical, Turing never intended anyone to go out and build one of these machines in the hope it will be useful. Modern machines have circuits within them that can add 2 numbers together by passing 2 electrical signals in and getting the sum as a single signal out. This happens in less than a nanosecond. Modern machines have memory where any byte can be accessed at any time, no tape manipulation required. This memory access takes a few dozen nanoseconds. # Writing and running your own programs I've built a web-based development environment for writing programs that will run on the Turing machine visualisations you've seen throughout the post. You can access the editor here. I encourage you to play around with it. Set a simple goal, like adding together 2 numbers without going back to look at the way I did it in the post. It's a great way to get a feel for how the machine works. # Conclusion To recap, we've covered: What a Turing machine is. What can and cannot be computed. What it means to be Turing complete. How modern computers relate to Turing machines. And you now have access to an environment for writing and running your own Turing machine programs. If you use it to make something neat, please do reach out to me and show me! My email address is hello@samwho.dev. # Further reading Turing's original paper on computable numbers. The Annotated Turing I referenced this throughout the making of this post. It is a fabulous read, strongly recommend. Alan Turing: The Enigma by Andrew Hodges. An excellent biography of Turing, I read this during the writing of this post. Calculating a Mandelbrot Set using a Turing Machine. This was exceptionally useful for me to understand how to get from Turing machines to modern computers. # Acknowledgements These posts are never a solo effort, and this one is no exception. Sincere thanks go to the following people: To my wife, Sophie, who drew the biographical sketches you're seeing at the end here, and for putting up with my incessant talking about this post the last 2 weeks. Everyone who let me watch them read this post in real-time over a video call and gave me feedback: Jaga Santagostino, Robert Aboukhalil, Tarun Verghis, Tyler Sparks. Everyone who came to hang out and help out in the Twitch streams when I was building out the early versions of the Turing machine visualisations. Everyone who supports my work on Patreon. Everyone who works on the tools used to build this post: TypeScript, Bun, Two.js, Tween.js, Monaco, Peggy, Zed, and many other indirect dependencies. We really do stand upon the shoulders of giants. Hut 8, Bletchley Park, where Turing worked during World War II. It was in this hut that Alan worked with his team to break the German Naval Enigma code.
.bf { width: 100%; height: 150px; } @media only screen and (min-width: 320px) and (max-width: 479px) { .bf { height: 200px; } } @media only screen and (min-width: 480px) and (max-width: 676px) { .bf { height: 200px; } } @media only screen and (min-width: 677px) and (max-width: 991px) { .bf { height: 150px; } } form { display: flex; flex-direction: column; align-items: center; justify-content: stretch; } input { border: 1px solid rgb(119, 119, 119); padding: 0.25rem; border-radius: 0.25rem; height: 2em; line-height: 2em; } .aside { padding: 2rem; width: 100vw; position: relative; margin-left: -50vw; left: 50%; background-color: #eeeeee; display: flex; align-items: center; flex-direction: column; } .aside > * { flex-grow: 1; } .aside p { padding-left: 1rem; padding-right: 1rem; max-width: 780px; font-style: italic; font-family: Lora, serif; text-align: center; } Everyone has a set of tools they use to solve problems. Growing this set helps you to solve ever more difficult problems. In this post, I'm going to teach you about a tool you may not have heard of before. It's a niche tool that won't apply to many problems, but when it does you'll find it invaluable. It's called a "bloom filter." Before you continue! This post assumes you know what a hash function is, and if you don't it's going to be tricky to understand. Sam has written a post about hash functions, and recommendeds that you read this first. # What bloom filters can do Bloom filters are similar to the Set data structure. You can add items to them, and check if an item is present. Here's what it might look like to use a bloom filter in JavaScript, using a made-up BloomFilter class: let bf = new BloomFilter(); bf.add("Ant"); bf.add("Rhino"); bf.contains("Ant"); // true bf.contains("Rhino"); // true While this looks almost identical to a Set, there are some key differences. Bloom filters are what's called a probabalistic data structure. Where a Set can give you a concrete "yes" or "no" answer when you call contains, a bloom filter can't. Bloom filters can give definite "no"s, but they can't be certain about "yes." In the example above, when we ask bf if it contains "Ant" and "Rhino", the true that it returns isn't a guarantee that they're present. We know that they're present because we added them just a couple of lines before, but it would be possible for this to happen: let bf = new BloomFilter(); bf.add("Ant"); bf.add("Rhino"); bf.contains("Fox"); // true We'll demonstrate why over the course of this post. For now, we'll say that when bloom filters return true it doesn't mean "yes", it means "maybe". When this happens and the item has never been added before, it's called a false-positive. The opposite, claiming "no" when the answer is "yes," is called a false-negative. A bloom filter will never give a false-negative, and this is what makes them useful. It's not strictly lying, it's just not giving you a definite answer. Let's look at an example where we can use this property to our advantage. # When bloom filters are useful Imagine you're building a web browser, and you want to protect users from malicious links. You could build and maintain a list of all known malicious links and check the list every time a user navigates the browser. If the link they're trying to visit is in the list, you warn the user that they might be about to visit a malicious website. If we assume there are, say, 1,000,000 malicious links on the Internet, and each link is 20 characters long, then the list of malicious links would be 20MB in size. This isn't a huge amount of data, but it's not small either. If you have lots of users and want to keep this list up to date, the bandwidth could add up. However, if you're happy to accept being wrong 0.0001% of the time (1 in a million), you could use a bloom filter which can store the same data in 3.59MB. That's an 82% reduction in size, and all it costs you is showing the user an incorrect warning 1 in every million links visited. If you wanted to take it even further, and you were happy to accept being wrong 0.1% of the time (1 in 1000), the bloom filter would only be 1.8MB. This use-case isn't hypothetical, either. Google Chrome used a bloom filter for this exact purpose until 2012. If you were worried about showing a warning when it wasn't needed, you could always make an API that has the full list of malicious links in a database. When the bloom filter says "maybe," you would then make an API call to check the full list to be sure. No more spurious warnings, and the bloom filter would save you from having to call the API for every link visited. # How bloom filters work At its core, a bloom filter is an array of bits. When it is created, all of the bits are set to 0. We're going to represent this as a grid of circles, with each circle representing 1 bit. Our bloom filters in this post are all going to have 32 bits in total. this one and let me know what you think. Click here to go back to normal. To add an item to the bloom filter, we're going to hash it with 3 different hash functions, then use the 3 resulting values to set 3 bits. If you're not familiar with hashing, I recommend reading my post about it before continuing. For this post I'm choosing to use 3 of the SHA family of hash functions: sha1, sha256, and sha512. Here's what our bloom filter looks like if we add the value "foo" to it: The bits in positions 15, 16 and 27 have been set. Other bits, e.g. 1 have not been set. You can hover or tap the bits in this paragraph to highlight them in the visualisation. We get to this state by taking the hash value of "foo" for each of our 3 hash functions and modulo it by the number of bits in our bloom filter. Modulo gets us the remainder when dividing by 32, so we get 27 with sha1, 15 with sha256 and 16 with sha512. The table below shows what's happening, and you can try inputting your own values to see what bits they would set if added. Go ahead and add a few of your own values to our bloom filter below and see what happens. There's also a check button that will tell you if a value is present within the bloom filter. A value is only considered present if all of the bits checked are set. You can start again by hitting the clear button. You might occasionally notice that only 2, or even 1, bits get set. This happens when 2 or more of our hash functions produce the same value, or we attempt to set a bit that has already been set. Taking that a bit further, have a think about the implications of a bloom filter that has every bit set. bit is set, then won't the bloom filter claim it contains every item you check? That's a false-positive every time! Exactly right. A bloom filter with every bit set is equivalent to a Set that always returns true for contains. It will claim to contain everything you ask it about, even if that thing was never added. # False-positive rates The rate of false-positives in our bloom filter will grow as the percentage of set bits increases. Drag the slider below the graph to see how the false-positive rate changes as the number of set bits increases. It grows slowly at first, but as we get closer to having all bits set the rate increases. This is because we calculate the false-positive rate as x^3, where x is the percentage of set bits and 3 is the number of hash functions used. To give an example of why we calculate it with this formula, imagine we have a bloom filter with half of its bits set, x = 0.5. If we assume that our hash function has an equal chance of setting any of the bits, then the chance that all 3 hash functions set a bit that is already set is 0.5 * 0.5 * 0.5, or x^3. Let's have a look at the false-positive rate of bloom filters that use different numbers of hash functions. The problem that using lots of hash functions introduces is that it makes the bloom filter fill up faster. The more hash functions you use, the more bits get set for each item you add. There's also the cost of hashing itself. Hash functions aren't free, and while the hash functions you'd use in a bloom filter try to be as fast as possible, it's still more expensive to run 100 of them than it is to run 3. It's possible to calculate how full a bloom filter will be after inserting a number of items, based on the number of hash functions used. The graph below assumes a bloom filter with 1000 bits. The more hash functions we use, the faster we set all of the bits. You'll notice that the curve tails off as more items are added. This is because the more bits that are set, the more likely it is that we'all attempt to set a bit that has already been set. In practice, 1000 bits is a very small bloom filter, occupying only 125 bytes of memory. Modern computers have a lot of memory, so let's crank this up to 100,000 bits (12.5kB) and see what happens. The lines barely leave the bottom of the graph, meaning the bloom filter will be very empty and the false-positive rate will be low. All this cost us was 12.5kB of memory, which is still a very small amount by 2024 standards. # Tuning a bloom filter Picking the correct number of hash functions and bits for a bloom filter is a fine balance. Fortunately for us, if we know up-front how many unique items we want to store, and what our desired false-positive rate is, we can calculate the optimal number of hash functions, and the required number of bits. The bloom filter page on Wikipedia covers the mathematics involved, which I'm going to translate into JavaScript functions for us to use. I want to stress that you don't need to understand the maths to use a bloom filter or read this post. I'm including the link to it only for completeness. # Optimal number of bits The following JavaScript function, which might look a bit scary but bear with me, takes the number of items you want to store (items) and the desired false-positive rate (fpr, where 1% == 0.01), and returns how many bits you will need to achieve that false-positive rate. function bits(items, fpr) { const n = -items * Math.log(fpr); const d = Math.log(2) ** 2; return Math.ceil(n / d); } We can see how this grows for a variety of fpr values in the graph below. # Optimal number of hash functions After we've used the JavaScript above to calculate how many bits we need, we can use the following function to calculate the optimal number of hash functions to use: function hashFunctions(bits, items) { return Math.ceil((bits / items) * Math.log(2)); } Pause for a second here and have a think about how the number of hash functions might grow based on the size of the bloom filter and the number of items you expect to add. Do you think you'll use more hash functions, or fewer, as the bloom filter gets larger? What about as the number of items increases? The more items you plan to add, the fewer hash functions you should use. Yet, a larger bloom filter means you can use more hash functions. More hash functions keep the false-positive rate lower for longer, but more items fills up the bloom filter faster. It's a complex balancing act, and I am thankful that mathematicians have done the hard work of figuring it out for us. # Caution While we can stand on the shoulders of giants and pick the optimal number of bits and hash functions for our bloom filter, it's important to remember that these rely on you giving good estimates of the number of items you expect to add, and choosing a false-positive rate that's acceptable for your use-case. These numbers might be difficult to come up with, and I recommend erring on the side of caution. If you're not sure, it's likely better to use a larger bloom filter than you think you need. # Removing items from a bloom filter We've spent the whole post talking about adding things to a bloom filter, and the optimal parameters to use. We haven't spoken at all about removing items. And that's because you can't! In a bloom filter, we're using bits, individual 1s and 0s, to track the presence of items. If we were to remove an item by setting its bits to 0, we might also be removing other items by accident. There's no way of knowing. Click the buttons of the bloom filter below to see this in action. First we will add "foo", then "baz", and then we will remove "baz". Hit "clear" if you want to start again. The end result of this sequence is a bloom filter that doesn't contain "baz", but doesn't contain "foo" either. Because both "foo" and "baz" set bit 27, we accidentally clobber the presence of "foo" while removing "baz". Something else you might have noticed playing with the above example is that if you add "foo" and then attempt to remove "baz" before having added it, nothing happens. Even though 27 is set, bits 18 and 23 are not, so the bloom filter cannot contain "baz". Because of this, it won't unset 27. # Counting bloom filters While you can't remove items from a standard bloom filter, there are variants that allow you to do so. One of these variants is called a "counting bloom filter," which uses an array of counters instead of bits to keep track of items. Now when you go through the sequence, the end result is that the bloom filter still contains "foo." It solves the problem. The trade-off, though, is that counters are bigger than bits. With 4 bits per counter you can increment up to 15. With 8 bits per counter you can increment up to 255. You'll need to pick a counter size sufficient to never reach the maximum value, otherwise you risk corrupting the bloom filter. Using 8x more memory than a standard bloom filter could be a big deal, especially if you're using a bloom filter to save memory in the first place. Think hard about whether you really need to be able to remove items from your bloom filter. Counting bloom filters also introduce the possibility of false-negatives, which are impossible in standard bloom filters. Consider the following example. Because "loved" and "response" both hash to the bits 5, 22, and 26, when we remove "response" we also remove "loved". If we write this as JavaScript the problem becomes more clear: let bf = new CountingBloomFilter(); bf.add("loved"); bf.add("your"); bf.remove("response"); bf.contains("loved"); // false Even though we know for sure we've added "loved" in this snippet, the call to contains will return false. This sort of false-negative can't happen in a standard bloom filter, and it removes one of the key benefits of using a bloom filter in the first place: the guarantee of no false-negatives. # Bloom filters in the real-world Real-world users of bloom filters include Akamai, who use them to avoid caching web pages that are accessed once and never again. They do this by storing all page accesses in a bloom filter, and only writing them into cache if the bloom filter says they've been seen before. This does result in some pages being cached on the first access, but that's fine because it's still an improvement. It would be impractical for them to store all page accesses in a Set, so they accept the small false-positive rate in favour of the significantly smaller bloom filter. Akamai released a paper about this that goes into the full details if you're interested. Google's BigTable is a distributed key-value store, and uses bloom filters internally to know what keys are stored within. When a read request for a key comes in, a bloom filter in memory is first checked to see if the key is in the database. If not, BigTable can respond with "not found" without ever needing to read from disk. Sometimes the bloom filter will claim a key is in the database when it isn't, but this is fine because when that happens a disk access will confirm the key in fact isn't in the database. # Conclusion Bloom filters, while niche, can be a huge optimisation in the right situation. They're a wonderful application of hash functions, and a great example of making a deliberate trade-off to achieve a specific goal. Trade-offs, and combining simpler building blocks to create more complex, purpose-built data structures, are present everywhere in software engineering. Being able to spot where a data structure could net a big win can separate you from the pack, and take your career to the next level. I hope you've enjoyed this post, and that you find a way to apply bloom filters to a problem you're working on. # Acknowledgements Enormous thank you to my reviewers, without whom this post would be a shadow of what you read today. In no particular order: rylon, Indy, Aaron, Sophie, Davis, ed, Michael Drury, Anton Zhiyanov, Christoph Berger.
form { padding-top: 0.5em; padding-left: 0.5em; padding-right: 0.5em; display: flex; justify-content: center; gap: 0.3em; } form input[type=text] { flex: 4 1 auto; min-width: 0; border-radius: 0.3em; border: 1px solid #aaaaaa; padding: 0.3em; } form button { flex: 1 1 auto; max-width: 140px; } form button:disabled { opacity: 0.5 !important; } form button.add { background-color: #009E73; color: white; border: 0; border-radius: 0.3em; cursor: pointer; } form button.check { background-color: #56B4E9; color: white; border: 0; border-radius: 0.3em; cursor: pointer; } form button.clear { background-color: #D55E00; color: white; border: 0; border-radius: 0.3em; cursor: pointer; } .grid-2x2 { display: "grid"; } .grid { user-select: none; cursor: pointer; margin-top: 1rem; margin-bottom: 1rem; border: 1px solid #009E73; width: 100%; display: grid; grid-template-columns: repeat(8, 1fr); grid-template-rows: repeat(2, 1fr); } .grid-item { display: flex; align-items: center; justify-content: center; aspect-ratio: 1/1; } .grid-active { background-color: #009E73; color: white; } .above-grid { display: flex; justify-content: center; } .hash-examples { padding-top: 0.5rem; padding-bottom: 0.5rem; margin: auto; display: flex; flex-direction: column; align-items: center; } .hash-examples div { margin: auto; } .hash-examples code { display: block; white-space: pre; font-weight: bold; } .hash-examples p { font-size: 0.75rem; font-style: italic; text-align: center; font-family: Lora, serif; width: 75%; } .blob { cursor: pointer; background: #CC79A7; display: flex; justify-content: center; align-items: center; font-size: 1.5rem; color: white; border-radius: 50%; margin: 10px; height: 3rem; width: 3rem; min-width: 3rem; max-width: 3rem; box-shadow: 0 0 0 0 #CC79A7FF; transform: scale(1); animation: pulse 2s infinite; } @keyframes pulse { 0% { transform: scale(0.85); box-shadow: 0 0 0 0 #CC79A77F; } 70% { transform: scale(1); box-shadow: 0 0 0 1rem rgba(0, 0, 0, 0); } 100% { transform: scale(0.85); box-shadow: 0 0 0 0 rgba(0, 0, 0, 0); } } .blob-click { cursor: default; animation: tick 1s linear; background: #009E73FF; } @keyframes tick { 0% { transform: scale(1); box-shadow: 0 0 0 0 #009E73FF; } 50% { box-shadow: 0 0 0 1rem #009E737F; } 100% { box-shadow: 0 0 0 2rem #009E7300; } } .aside { padding: 2rem; width: 100vw; position: relative; margin-left: -50vw; left: 50%; background-color: #eeeeee; display: flex; align-items: center; flex-direction: column; } .aside > * { flex-grow: 1; } .aside p { padding-left: 1rem; padding-right: 1rem; max-width: 780px; font-style: italic; font-family: Lora, serif; text-align: center; } .pct25 { width: 100%; height: 200px; } .datasets th { text-align: left; } .datasets { table-layout: fixed; } As a programmer, you use hash functions every day. They're used in databases to optimise queries, they're used in data structures to make things faster, they're used in security to keep data safe. Almost every interaction you have with technology will involve hash functions in one way or another. Hash functions are foundational, and they are everywhere. But what is a hash function, and how do they work? In this post, we're going to demystify hash functions. We're going to start by looking at a simple hash function, then we're going to learn how to test if a hash function is good or not, and then we're going to look at a real-world use of hash functions: the hash map. clicked. # What is a hash function? Hash functions are functions that take an input, usually a string, and produce a number. If you were to call a hash function multiple times with the same input, it will always return the same number, and that number returned will always be within a promised range. What that range is will depend on the hash function, some use 32-bit integers (so 0 to 4 billion), others go much larger. If we were to write a dummy hash function in JavaScript, it might look like this: function hash(input) { return 0; } Even without knowing how hash functions are used, it's probably no surprise that this hash function is useless. Let's see how we can measure how good a hash function is, and after that we'll do a deep dive on how they're used within hash maps. # What makes a hash function good? Because input can be any string, but the number returned is within some promised range, it's possible that two different inputs can return the same number. This is called a "collision," and good hash functions try to minimise how many collisions they produce. It's not possible to completely eliminate collisions, though. If we wrote a hash function that returned a number in the range 0 to 7, and we gave it 9 unique inputs, we're guaranteed at least 1 collision. hash("to") == 3 hash("the") == 2 hash("café") == 0 hash("de") == 6 hash("versailles") == 4 hash("for") == 5 hash("coffee") == 0 hash("we") == 7 hash("had") == 1 To visualise collisions, I'm going to use a grid. Each square of the grid is going to represent a number output by a hash function. Here's an example 8x2 grid. Click on the grid to increment the example hash output value and see how we map it to a grid square. See what happens when you get a number larger than the number of grid squares. { let grid = document.getElementById("first-grid"); let hash = document.getElementById("grid-hash"); let modulo = document.getElementById("grid-modulo"); grid.addEventListener("click", (e) => { e.preventDefault(); let number = parseInt(hash.innerText) + 1; hash.innerText = number.toString(); modulo.innerText = (number % 16).toString(); grid.querySelector(".grid-active").classList.remove("grid-active"); grid.children[number % 16].classList.add("grid-active"); return false; }); }); 13 % 16 == 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Every time we hash a value, we're going to make its corresponding square on the grid a bit darker. The idea is to create an easy way to see how well a hash function avoids collisions. What we're looking for is a nice, even distribution. We'll know that the hash function isn't good if we have clumps or patterns of dark squares. This is a great observation. You're absolutely right, we're going to be creating "pseudo-collisions" on our grid. It's okay, though, because if the hash function is good we will still see an even distribution. Incrementing every square by 100 is just as good a distribution as incrementing every square by 1. If we have a bad hash function that collides a lot, that will still stand out. We'll see this shortly. Let's take a larger grid and hash 1,000 randomly-generated strings. You can click on the grid to hash a new set of random inputs, and the grid will animate to show you each input being hashed and placed on the grid. The values are nice and evenly distributed because we're using a good, well-known hash function called murmur3. This hash is widely used in the real-world because it has great distribution while also being really, really fast. What would our grid look like if we used a bad hash function? function hash(input) { let hash = 0; for (let c of input) { hash += c.charCodeAt(0); } return hash % 1000000; } This hash function loops through the string that we're given and sums the numeric values of each character. It then makes sure that the value is between 0 and 1000000 by using the modulus operator (%). Let's call this hash function stringSum. Here it is on the grid. Reminder, this is 1,000 randomly generated strings that we're hashing. This doesn't look all that different from murmur3. What gives? The problem is that the strings we're giving to be hashed are random. Let's see how each function performs when given input that is not random: the numbers from 1 to 1000 converted to strings. Now the problem is more clear. When the input isn't random, the output of stringSum forms a pattern. Our murmur3 grid, however, looks the same as how it looked with random values. How about if we hash the top 1,000 most common English words: It's more subtle, but we do see a pattern on the stringSum grid. As usual, murmur3 looks the same as it always does. This is the power of a good hash function: no matter the input, the output is evenly distributed. Let's talk about one more way to visualise this and then talk about why it matters. # The avalanche effect Another way hash functions get evaluated is on something called the "avalanche effect." This refers to how many bits in the output value change when just a single bit of the input changes. To say that a hash function has a good avalanche effect, a single bit flip in the input should result in an average of 50% the output bits flipping. It's this property that helps hash functions avoid forming patterns in the grid. If small changes in the input result in small changes in the output, you get patterns. Patterns indicate poor distribution, and a higher rate of collisions. Below, we are visualising the avalanche effect by showing two 8-bit binary numbers. The top number is the input value, and the bottom number is the murmur3 output value. Click on it to flip a single bit in the input. Bits that change in the output will be green, bits that stay the same will be red. murmur3 does well, though you will notice that sometimes fewer than 50% of the bits flip and sometimes more. This is okay, provided that it is 50% on average. Let's see how stringSum performs. Well this is embarassing. The output is equal to the input, and so only a single bit flips each time. This does make sense, because stringSum just sums the numeric value of each character in the string. This example only hashes the equivalent of a single character, which means the output will always be the same as the input. # Why all of this matters We've taken the time to understand some of the ways to determine if a hash function is good, but we've not spent any time talking about why it matters. Let's fix that by talking about hash maps. To understand hash maps, we first must understand what a map is. A map is a data structure that allows you to store key-value pairs. Here's an example in JavaScript: let map = new Map(); map.set("hello", "world"); console.log(map.get("hello")); Here we take a key-value pair ("hello" → "world") and store it in the map. Then we print out the value associated with the key "hello", which will be "world". A more fun real-world use-case would be to find anagrams. An anagram is when two different words contain the same letters, for example "antlers" and "rentals" or "article" and "recital." If you have a list of words and you want to find all of the anagrams, you can sort the letters in each word alphabetically and use that as a key in a map. let words = [ "antlers", "rentals", "sternal", "article", "recital", "flamboyant", ] let map = new Map(); for (let word of words) { let key = word .split('') .sort() .join(''); if (!map.has(key)) { map.set(key, []); } map.get(key).push(word); } This code results in a map with the following structure: { "aelnrst": [ "antlers", "rentals", "sternal" ], "aceilrt": [ "article", "recital" ], "aabflmnoty": [ "flamboyant" ] } # Implementing our own simple hash map Hash maps are one of many map implementations, and there are many ways to implement hash maps. The simplest way, and the way we're going to demonstrate, is to use a list of lists. The inner lists are often referred to as "buckets" in the real-world, so that's what we'll call them here. A hash function is used on the key to determine which bucket to store the key-value pair in, then the key-value pair is added to that bucket. Let's walk through a simple hash map implementation in JavaScript. We're going to go through it bottom-up, so we'll see some utility methods before getting to the set and get implementations. class HashMap { constructor() { this.bs = [[], [], []]; } } We start off by creating a HashMap class with a constructor that sets up 3 buckets. We use 3 buckets and the short variable name bs so that this code displays nicely on devices with smaller screens. In reality, you could have however many buckets you want (and better variable names). class HashMap { // ... bucket(key) { let h = murmur3(key); return this.bs[ h % this.bs.length ]; } } The bucket method uses murmur3 on the key passed in to find a bucket to use. This is the only place in our hash map code that a hash function is used. class HashMap { // ... entry(bucket, key) { for (let e of bucket) { if (e.key === key) { return e; } } return null; } } The entry method takes a bucket and a key and scans the bucket until it finds an entry with the given key. If no entry is found, null is returned. class HashMap { // ... set(key, value) { let b = this.bucket(key); let e = this.entry(b, key); if (e) { e.value = value; return; } b.push({ key, value }); } } The set method is the first one we should recognise from our earlier JavaScript Map examples. It takes a key-value pair and stores it in our hash map. It does this by using the bucket and entry methods we created earlier. If an entry is found, its value is overwritten. If no entry is found, the key-value pair is added to the map. In JavaScript, { key, value } is shorthand for { key: key, value: value }. class HashMap { // ... get(key) { let b = this.bucket(key); let e = this.entry(b, key); if (e) { return e.value; } return null; } } The get method is very similar to set. It uses bucket and entry to find the entry related to the key passed in, just like set does. If an entry is found, its value is returned. If one isn't found, null is returned. That was quite a lot of code. What you should take away from it is that our hash map is a list of lists, and a hash function is used to know which of the lists to store and retrieve a given key from. Here's a visual representation of this hash map in action. Click anywhere on the buckets to add a new key-value pair using our set method. To keep the visualisation simple, if a bucket were to "overflow", the buckets are all reset. Because we're using murmur3 as our hash function, you should see good distribution between the buckets. It's expected you'll see some imbalance, but it should generally be quite even. To get a value out of the hash map, we first hash the key to figure out which bucket the value will be in. Then we have to compare the key we're searching for against all of the keys in the bucket. It's this search step that we minimise through hashing, and why murmur3 is optimised for speed. The faster the hash function, the faster we find the right bucket to search, the faster our hash map is overall. This is also why reducing collisions is so crucial. If we did decide to use that dummy hash function from all the way at the start of this article, the one that returns 0 all the time, we'll put all of our key-value pairs into the first bucket. Finding anything could mean we have to check all of the values in the hash map. With a good hash function, with good distribution, we reduce the amount of searching we have to do to 1/N, where N is the number of buckets. Let's see how stringSum does. Interestingly, stringSum seems to distribute values quite well. You notice a pattern, but the overall distribution looks good. stringSum. I knew it would be good for something. Not so fast, Haskie. We need to talk about a serious problem. The distribution looks okay on these sequential numbers, but we've seen that stringSum doesn't have a good avalanche effect. This doesn't end well. # Real-world collisions Let's look at 2 real-world data sets: IP addresses and English words. What I'm going to do is take 100,000,000 random IP addresses and 466,550 English words, hash all of them with both murmur3 and stringSum, and see how many collisions we get. IP Addresses murmur3 stringSum Collisions 1,156,959 99,999,566 1.157% 99.999% English words murmur3 stringSum Collisions 25 464,220 0.005% 99.5% When we use hash maps for real, we aren't usually storing random values in them. We can imagine counting the number of times we've seen an IP address in rate limiting code for a server. Or code that counts the occurrences of words in books throughout history to track their origin and popularity. stringSum sucks for these applications because of it's extremely high collision rate. # Manufactured collisions Now it's murmur3's turn for some bad news. It's not just collisions caused by similarity in the input we have to worry about. Check this out. What's happening here? Why do all of these jibberish strings hash to the same number? I hashed 141 trillion random strings to find values that hash to the number 1228476406 when using murmur3. Hash functions have to always return the same output for a specific input, so it's possible to find collisions by brute force. trillion? Like... 141 and then 12 zeroes? Yes, and it only took me 25 minutes. Computers are fast. Bad actors having easy access to collisions can be devastating if your software builds hash maps out of user input. Take HTTP headers, for example. An HTTP request looks like this: GET / HTTP/1.1 Accept: */* Accept-Encoding: gzip, deflate Connection: keep-alive Host: google.com You don't have to understand all of the words, just that the first line is the path being requested and all of the other lines are headers. Headers are Key: Value pairs, so HTTP servers tend to use maps to store them. Nothing stops us from passing any headers we want, so we can be really mean and pass headers we know will cause collisions. This can significantly slow down the server. This isn't theoretical, either. If you search "HashDoS" you'll find a lot more examples of this. It was a really big deal in the mid-2000s. There are a few ways to mitigate this specific to HTTP servers: ignoring jibberish header keys and limiting the number of headers you store, for example. But modern hash functions like murmur3 offer a more generalised solution: randomisation. Earlier in this post we showed some examples of hash function implementations. Those implementations took a single argument: input. Lots of modern hash functions take a 2nd parameter: seed (sometimes called salt). In the case of murmur3, this seed is a number. So far, we've been using 0 as the seed. Let's see what happens with the collisions I've collected when we use a seed of 1. Just like that, 0 to 1, the collisions are gone. This is the purpose of the seed: it randomises the output of the hash function in an unpredictable way. How it achieves this is beyond the scope of this article, all hash functions do this in their own way. The hash function still returns the same output for the same input, it's just that the input is a combination of input and seed. Things that collide with one seed shouldn't collide when using another. Programming languages often generate a random number to use as the seed when the process starts, so that every time you run your program the seed is different. As a bad guy, not knowing the seed, it is now impossible for me to reliably cause harm. If you look closely in the above visualisation and the one before it, they're the same values being hashed but they produce different hash values. The implication of this is that if you hash a value with one seed, and want to be able to compare against it in the future, you need to make sure you use the same seed. Having different values for different seeds doesn't affect the hash map use-case, because hash maps only live for the duration the program is running. Provided you use the same seed for the lifetime of the program, your hash maps will continue to work just fine. If you ever store hash values outside of your program, in a file for example, you need to be careful you know what seed has been used. # Playground As is tradition, I've made a playground for you to write your own hash functions and see them visualised with the grids seen in this article. Click here to try it! # Conclusion We've covered what a hash function is, some ways to measure how good it is, what happens when it's not good, and some of the ways they can be broken by bad actors. The universe of hash functions is a large one, and we've really only scratched the surface in this post. We haven't spoken about cryptographic vs non-cryptographic hashing, we've touched on only 1 of the thousands of use-cases for hash functions, and we haven't talked about how exactly modern hash functions actually work. Some further reading I recommend if you're really enthusiastic about this topic and want to learn more: https://github.com/rurban/smhasher this repository is the gold standard for testing how good hash functions are. They run a tonne of tests against a wide number of hash functions and present the results in a big table. It will be difficult to understand what all of the tests are for, but this is where the state of the art of hash testing lives. https://djhworld.github.io/hyperloglog/ this is an interactive piece on a data structure called HyperLogLog. It's used to efficiently count the number of unique elements in very, very large sets. It uses hashing to do it in a really clever way. https://www.gnu.org/software/gperf/ is a piece of software that, when given the expected set of things you want to hash, can generate a "perfect" hash function automatically. Feel free to join the discussion on Hacker News! # Acknowledgements Thanks to everyone who read early drafts and provided invaluable feedback. delroth, Manon, Aaron, Charlie And everyone who helped me find murmur3 hash collisions: Indy, Aaron, Max # Patreon After the success of Load Balancing and Memory Allocation, I have decided to set up a Patreon page: https://patreon.com/samwho. For all of these articles going forward, I am going to post a Patreon-exclusive behind-the-scenes post talking about decisions, difficulties, and lessons learned from each post. It will give you a deep look in to how these articles evolve, and I'm really stoked about the one I've written for this one. If you enjoy my writing, and want to support it going forward, I'd really appreciate you becoming a Patreon. ❤️
.memory { width: 100%; margin-bottom: 1.5em; margin-top: 0.5em; } input[type=range]:focus { outline: none; } a[simulation] { cursor: pointer; } .size { color: #0072B2 !important; font-weight: bold; } .free { color: #009E73 !important; font-weight: bold; } .allocated { color: #D55E00 !important; font-weight: bold; } .usable-memory { color: #E69F00 !important; font-weight: bold; } One thing that all programs on your computer have in common is a need for memory. Programs need to be loaded from your hard drive into memory before they can be run. While running, the majority of what programs do is load values from memory, do some computation on them, and then store the result back in memory. In this post I'm going to introduce you to the basics of memory allocation. Allocators exist because it's not enough to have memory available, you need to use it effectively. We will visually explore how simple allocators work. We'll see some of the problems that they try to solve, and some of the techniques used to solve them. At the end of this post, you should know everything you need to know to write your own allocator. › malloc and free To understand the job of a memory allocator, it's essential to understand how programs request and return memory. malloc and free are functions that were first introduced in a recognisable form in UNIX v7 in 1979(!). Let's take a look at a short C program demonstrating their use. If you have beginner-level familiarity with another language, e.g. JavaScript, Python, or C#, you should have no problem following along. You don't need to understand every word, as long as you get the overall idea. This is the only C code in the article, I promise. #include <stdlib.h> int main() { void *ptr = malloc(4); free(ptr); return 0; } In the above program we ask for 4 bytes of memory by calling malloc(4), we store the value returned in a variable called ptr, then we indicate that we're done with the memory by calling free(ptr). These two functions are how almost all programs manage the memory they use. Even when you're not writing C, the code that is executing your Java, Python, Ruby, JavaScript, and so on make use of malloc and free. › What is memory? The smallest unit of memory that allocators work with is called a "byte." A byte can store any number between 0 and 255. You can think of memory as being a long sequence of bytes. We're going to represent this sequence as a grid of squares, with each square representing a byte of memory. In the C code from before, malloc(4) allocates 4 bytes of memory. We're going to represent memory that has been allocated as darker squares. Then free(ptr) tells the allocator we're done with that memory. It is returned back to the pool of available memory. Here's what 4 malloc calls followed by 4 free calls looks like. You'll notice there's now a slider. Dragging the slider to the right advances time forward, and dragging it left rewinds. You can also click anywhere on the grid and then use the arrow keys on your keyboard, or you can use the left and right buttons. The ticks along the slider represent calls to malloc and free. Wait a sec... What is malloc actually returning as a value? What does it mean to "give" memory to a program? What malloc returns is called a "pointer" or a "memory address." It's a number that identifies a byte in memory. We typically write addresses in a form called "hexadecimal." Hexadecimal numbers are written with a 0x prefix to distinguish them from decimal numbers. Move the slider below to see a comparison between decimal numbers and hexadecimal numbers. 0 == 0x0 Here's our familiar grid of memory. Each byte is annotated with its address in hexadecimal form. For space reasons, I've omitted the 0x prefix. The examples we use in this article pretend that your computer only has a very small amount of memory, but in real life you have billions of bytes to work with. Real addresses are much larger than what we're using here, but the idea is exactly the same. Memory addresses are numbers that refer to a specific byte in memory. › The simplest malloc The "hello world" of malloc implementations would hand out blocks of memory by keeping track of where the previous block ended and starting the next block right after. Below we represent where the next block should start with a grey square. You'll notice no memory is freed. If we're only keeping track of where the next block should start, and we don't know where previous blocks start or end, free doesn't have enough information to do anything. So it doesn't. This is called a "memory leak" because, once allocated, the memory can never be used again. Believe it or not, this isn't a completely useless implementation. For programs that use a known amount of memory, this can be a very efficient strategy. It's extremely fast and extremely simple. As a general-purpose memory allocator, though, we can't get away with having no free implementation. › The simplest general-purpose malloc In order to free memory, we need to keep better track of memory. We can do this by saving the address and size of all allocations, and the address and size of blocks of free memory. We'll call these an "allocation list" and a "free list" respectively. We're representing free list entries as 2 grey squares linked together with a line. You can imagine this entry being represented in code as address=0 and size=32. When our program starts, all of memory is marked as free. When malloc is called, we loop through our free list until we find a block large enough to accommodate it. When we find one, we save the address and size of the allocation in our allocation list, and shrink the free list entry accordingly. Where do we save allocations and free list entries? Aren't we pretending our computer only has 32 bytes of memory? You caught me. One of the benefits of being a memory allocator is that you're in charge of memory. You could store your allocation/free list in a reserved area that's just for you. Or you could store it inline, in a few bytes immediately preceding each allocation. For now, assume we have reserved some unseen memory for ourselves and we're using it to store our allocation and free lists. So what about free? Because we've saved the address and size of the allocation in our allocation list, we can search that list and move the allocation back in to the free list. Without the size information, we wouldn't be able to do this. Our free list now has 2 entries. This might look harmless, but actually represents a significant problem. Let's see that problem in action. We allocated 8 blocks of memory, each 4 bytes in size. Then we freed them all, resulting in 8 free list entries. The problem we have now is that if we tried to do a malloc(8), there are no items in our free list that can hold 8 bytes and the malloc(8) will fail. To solve this, we need to do a bit more work. When we free memory, we should make sure that if the block we return to the free list is next to any other free blocks, we combine them together. This is called "coalescing." Much better. › Fragmentation A perfectly coalesced free list doesn't solve all of our problems. The following example shows a longer sequence of allocations. Have a look at the state memory is in at the end. We end this sequence with 6 of our 32 bytes free, but they're split into 2 blocks of 3 bytes. If we had to service a malloc(6), while we have enough free memory in theory, we wouldn't be able to. This is called "fragmentation." Sadly not. Remember earlier we talked about how the return value of malloc is the address of a byte in memory? Moving allocations won't change the pointers we have already returned from malloc. We would change the value those pointers are pointed at, effectively breaking them. This is one of the downsides of the malloc/free API. If we can't move allocations after creating them, we need to be more careful about where we put them to begin with. One way to combat fragmentation is, confusingly, to overallocate. If we always allocate a minimum of 4 bytes, even when the request is for 1 byte, watch what happens. This is the exact same sequence of allocations as above. Now we can service a malloc(6). It's worth keeping in mind that this is just one example. Programs will call malloc and free in very different patterns depending on what they do, which makes it challenging to design an allocator that always performs well. malloc, the start of the free list seems to fall out of sync with allocated memory. Is that a bug in the visualisation? No, that's a side-effect of overallocating. The visualisation shows "true" memory use, whereas the free list is updated from the allocator's perspective. So when the first malloc happens, 1 byte of memory is allocated but the free list entry is moved forward 4 bytes. We trade some wasted space in return for less fragmentation. It's worth noting that this unused space that results from overallocation is another form of fragmentation. It's memory that cannot be used until the allocation that created it is freed. As a result, we wouldn't want to go too wild with overallocation. If our program only ever allocated 1 byte at a time, for example, we'd be wasting 75% of all memory. Another way to combat fragmentation is to segment memory into a space for small allocations and a space for big ones. In this next visualisation we start with two free lists. The lighter grey one is for allocations 3 bytes or smaller, and the darker grey one is for allocations 4 bytes or larger. Again, this is the exact same sequence of allocations as before. Nice! This also reduces fragmentation. If we're strictly only allowing allocations of 3 bytes or less in the first segment, though, then we can't service that malloc(6). The trade-off here is that reserving a segment of memory for smaller allocations gives you less memory to work with for bigger ones. the first allocation in the dark grey free list is 3 bytes! You said this was for allocations 4 bytes and up. What gives? Got me again. This implementation I've written will put small allocations in the dark grey space when the light grey space is full. It will overallocate when it does this, otherwise we'd end up with avoidable fragmentation in the dark grey space thanks to small allocations. Allocators that split memory up based on the size of allocation are called "buddy allocators." In practice they have many more size classes than the 2 in our example. › A quick malloc puzzle What happens if you malloc(0)? Have a think about this before playing with the slider below. This is using our free list implementation that mandates a minimum size of 4 bytes for allocations. All memory gets allocated, but none is actually used. Do you think this is correct behaviour? It turns out that what happens when you malloc(0) differs between implementations. Some of them behave as above, allocating space they probably didn't have to. Others will return what's called a "null pointer", a special pointer that will crash your program if you try to read or write the memory it points to. Others pick one specific location in memory and return that same location for all calls to malloc(0), regardless how many times it is called. Moral of the story? Don't malloc(0). › Inline bookkeeping Remember earlier on when you asked about where allocation list and free list information gets stored, and I gave an unsatisfying answer about how it's stored in some other area of memory we've reserved for ourselves? This isn't the only way to do it. Lots of allocators store information right next to the blocks of memory they relate to. Have a look at this. What we have here is memory with no allocations, but free list information stored inline in that memory. Each block of memory, free or used, gets 3 additional bytes of bookkeeping information. If address is the address of the first byte of the allocation, here's the layout of a block: address + 0 is the size of the block address + 1 is whether the block is free (1) or used (2) address + 2 is where the usable memory starts address + 2 + size -- the size of the block again So in this above example, the byte at 0x0 is storing the value 29. This means it's a block containing 29 bytes of memory. The value 1 at 0x1 indicates that the block is free memory. size twice? Isn't that wasteful? It seems wasteful at first, but it is necessary if we want to do any form of coalescing. Let's take a look at an example. Here we've allocated 4 bytes of memory. To do this, our malloc implementation starts at the beginning of memory and checks to see if the block there is used. It knows that at address + 1 it will find either a 1 or a 2. If it finds a 1, it can check the value at address for how big the block is. If it is big enough, it can allocate into it. If it's not big enough, it knows it can add the value it finds in address to address to get to the start of the next block of memory. This has resulted in the creation of a used block (notice the 2 stored in the 2nd byte), and it has pushed start of the free block forward by 7 bytes. Let's do the same again and allocate another 4 bytes. Next, let's free our first malloc(4). The implementation of free is where storing information inline starts to shine. In our previous allocators, we had to search the allocation list to know the size of the block being freed. Now we know we'll find it at address. What's better than that is that for this free, we don't even need to know how big the allocation is. We can just set address + 1 to 1! How great is that? Simple, fast. What if we wanted to free the 2nd block of used memory? We know that we want to coalesce to avoid fragmentation, but how do we do that? This is where the seemingly wasteful bookkeeping comes into play. When we coalesce, we check to see the state of the blocks immediately before and immediately after the block we're freeing. We know that we can get to the next block by adding the value at address to address, but how do we get to the previous block? We take the value at address - 1 and subtract that from address. Without this duplicated size information at the end of the block, it would be impossible to find the previous block and impossible to coalesce properly. Allocators that store bookkeeping information like this alongside allocations are called "boundary tag allocators." Surprisingly, nothing truly prevents this. We rely heavily, as an industry, on the correctness of code. You might have heard of "buffer overrun" or "use after free" bugs before. These are when a program modifies memory past the end of an allocated block, or accidentally uses a block of memory after freeing it. These are indeed catastrophic. They can result in your program immediately crashing, they can result in your program crashing in several minutes, hours, or days time. They can even result in hackers using the bug to gain access to systems they shouldn't have access to. We're seeing a rise in popularity of "memory safe" languages, for example Rust. These languages invest a lot in making sure it's not possible to make these types of mistake in the first place. Exactly how they do that is outside of the scope of this article, but if this interests you I highly recommend giving Rust a try. You might have also realised that calling free on a pointer that's in the middle of a block of memory could also have disastrous consequences. Depending on what values are in memory, the allocator could be tricked into thinking it's freeing something but what it's really doing is modifying memory it shouldn't be. To get around this, some allocators inject "magic" values as part of the bookkeeping information. They store, say, 0x55 at address + 2. This would waste an extra byte of memory per allocation, but would allow them to know when a mistake has been made. To reduce the impact of this, allocators often disable this behaviour by default and allow you to enable it only when you're debugging. › Playground If you're keen to take your new found knowledge and try your hand at writing your own allocators, you can click here to go to my allocator playground. You'll be able to write JavaScript code that implements the malloc/free API and visualise how it works! › Conclusion We've covered a lot in this post, and if it has left you yearning for more you won't be disappointed. I've specifically avoided the topics of virtual memory, brk vs mmap, the role of CPU caches, and the endless tricks real malloc implementations pull out of their sleeves. There's no shortage of information about memory allocators on the Internet, and if you've read this far you should be well-placed to dive in to it. Got feedback? Join the discussion on Hacker News! › Acknowledgments Special thanks to the following people: Chris Down for lending me his extensive knowledge of real-world memory allocators. Anton Verinov for lending me his extensive knowledge of the web, browser developer tools, and user experience. Blake Becker, Matt Kaspar, Krista Horn, Jason Peddle, and Josh W. Comeau for their insight and constructive reviews.
More in programming
While the world frets about the future of AI, the universal basic income advocates have an answer ready for the big question of "what are we all going to do when the jobs are gone": Just pay everyone enough to loaf around as they see fit! Problem solved, right? Wrong. The purpose of work is not just about earning your keep, but also about earning a purpose and a place in the world. This concept is too easily dismissed by intellectuals who imagines a world of liberated artists and community collaborators, if only unshackled by the burdens of capitalism. Because that's the utopia that appeals to them. But we already know what happens to most people who lose their job. It's typically not a song-and-dance of liberation, but whimper with increasing despair. Even if they're able to draw benefits for a while. Some of that is probably gendered. I think men have a harder time finding a purpose without a clear and externally validated station of usefulness. As a corollary to the quip that "women want to be heard, men want to be useful" from psychology. Long-term unemployment, even cushioned by state benefits, often leads men to isolation and a rotting well-being. I've seen this play out time and again with men who've lost their jobs, men who've voluntarily retired from their jobs, and men who've sold their companies. As the days add up after the centering purpose in their life disappeared, so does the discontent with "the problem of being". Sure, these are just anecdotes. Some men are thrilled to do whatever, whenever, without financial worries. And some women mourn a lost job as deeply as most men do. But I doubt it's evenly split. Either way, I doubt we'll be delighted to discover what societal pillars wither away when nobody is needed for anything. If all labor market participation rests on intrinsic motivation. That strikes me as an obvious dead end. We may not have a say in the manner, of course. The AI revolution, should it materialize like its proponents predict, has the potential to be every bit as unstoppable as the agricultural, industrial, and IT revolutions before it. Where the Luddites and the Amish, who reject these revolutions, end up as curiosities on the fringe of modern civilization. The rest of us are transformed, whether we like it or not. But generally speaking, I think we have liked it! I'm sure it was hard to imagine what we'd all be doing after the hoe and the horse gave way to the tractor and combine back when 97% of the population worked the land. Same when robots and outsourcing claimed the most brutish assembly lines in the West. Yet we found our way through both to a broadly better place. The IT revolution feels trickier. I've personally worked my life in its service, but I'm less convinced it's been as universal good as those earlier shifts. Is that just nostalgia? Because I remember a time before EVERYTHING IS COMPUTER? Possibly, but I think there's a reason the 80s in particular occupy such a beloved place in the memory of many who weren't even born then. What's more certain to me is that we all need a why, as Viktor Frankl told us in Man's Search for Meaning. And while some of us are able to produce that artisanal, bespoke why imagined by some intellectuals and academics, I think most people need something prepackaged. And a why from work offers just that. Especially in a world bereft of a why from God. It's a great irony that the more comfortable and frictionless our existence becomes, the harder we struggle with the "the problem of being". We just aren't built for a life of easy leisure. Not in mass numbers, anyway. But while the masses can easily identify the pathology of that when it comes to the idle rich, and especially their stereotyped trust-fund offspring, they still crave it for themselves. Orwell's thesis is that heaven is merely that fuzzily-defined place that provides relief from the present hardships we wish to escape. But Dostoevsky remarks that should man ever find this relief, he'd be able to rest there for just a moment, before he'd inevitably sabotage it — just to feel something again. I think of that often while watching The Elon Show. Musk's craving for the constant chaos of grand gestures is Dostoevsky's prediction underwritten by the wealth of the world's richest man. Heaven is not a fortune of $200 billion to be quietly enjoyed in the shade of a sombrero. It's in the arena. I’ve also pondered this after writing about why Apple needs a new asshole in charge, and reflecting on our book, It Doesn't Have To Be Crazy At Work. Yes, work doesn’t have to be crazy, but for many, occasional craziness is part of the adventure they crave. They’ll tolerate an asshole if they take them along for one such adventure — accepting struggle and chaos as a small price to feel alive. It's a bit like that bit from The Babylon Bee: Study Finds 100% Of Men Would Immediately Leave Their Desk Job If Asked To Embark Upon A Trans-Antarctic Expedition On A Big Wooden Ship. A comical incarnation of David Graeber's Bullshit Jobs thesis that derives its punchline from how often work lacks a Big Why. So when a megalomanic like Musk — or even just a run-of-the-mill asshole with a grand vision — offers one, the call of the wild beckons. Like that big wooden ship and the open sea. But even in the absence of such adventure, a stupid email job offers something. Maybe it isn't much, maybe it doesn't truly nourish the soul, but it's something. In the Universal Basic Income scenario of having to design your own adventure entirely from scratch, there is nothing. Just a completely blank page with no deadline to motivate writing the first line. If we kill the old 9-5 "why", we better find a new one. That might be tougher than making silicon distill all our human wisdom into vectors and parameters, but we have to pull it off.
A thing you should know is that you get put on a lot of lists if you spend a decent chunk of time publishing blog posts on your website. Your website and contact information will be shared around on these lists, for the purpose of soliciting you for guest posts. If you’re not familiar with the concept, guest posts are a way for other people to take advantage of your website’s search ranking as a way to divert traffic to other websites. There are benefits to doing this. The most straightforward one is SEO. Here, outward going links serves a heuristic web search engines look to for quality when weighing results. Guest posts can also have some additional gray hat goals, including audience segmenting and identification via things like UTM-driven campaigns. There are also straight-up cons such as linking to spyware, cryptominers and other forms of malware, and browser-based zero day exploits. Curiouser and curiouser I’ve always been curious about what exactly you get when you agree to a guest post offer. So, I dredged my spam folder and found one that sounded more direct and sincere. Here’s the cold call email pitch: Subject: Body: Keeping up with annual home and property maintenance is essential for preserving value and preventing costly repairs down the line. Whether it's inspecting your roof, cleaning gutters, or checking heating systems, regular upkeep can save homeowners time, money, and stress. I’m putting together an article that highlights key tasks for effective yearly maintenance, offering tips to help homeowners protect their biggest investment. I think this piece could really resonate with your audience! Let me know if you'd be interested in featuring it on your website. Thank you so much for your time today! Erin Reynolds P.S. If you’d like to propose an alternative topic, please do so. I would be happy to write on a topic that best suits your website. Don’t want to hear from me again? Please let me know. My reply reads: Hi Erin, This might be a weird one, but bear with me: My blog is a personal site, and its content is focused on web development and internet culture. I've always wanted to take someone up on this sort of offer, presented in the context of the article being something you get if you take the person reaching out on the offer to write a guest post. Is this something you'd be interested in? Erin took me up on my offer, and wrote about annual home and property maintenance. To her credit, she also did ask me if there was another subject I was interested in, but I figured we could stay the course of the original pitch. She was also prompt and communicative throughout the process, and delivered exactly what was promised. Here is the article in question: By Erin Reynolds, [diymama.net](https://diymama.net/) There's a quiet rhythm to living in a well-loved home. If you listen closely, your house speaks to you-whispers, mostly. The soft drip of a tired faucet, the groan of an HVAC unit that's been running too long, or the gentle scold of a clogged dryer vent. These aren't just annoyances. They re the language of upkeep, and whether you're in your first place or celebrating twenty years in the same four walls, learning to listen—and act—is everything. Annual maintenance isn't just about fixing what's broken. It's about stewardship, about being the kind of homeowner who doesn't wait for the ceiling to leak before checking the roof. There's something incredibly satisfying about having all your home maintenance documents in one tidy digital folder-no more rummaging through drawers for that appliance manual or the roof warranty. Digitizing receipts, inspection reports, and service invoices gives you a clear, accessible record of everything that's been done and when. Saving these as PDFs makes them universally readable and easy to share, whether you're selling your home or just need to reference them quickly. When you use a tool to create PDF files, you can convert virtually any document into a neat, portable format. You might not think much about gutters unless they're sagging or spilling over during a thunderstorm, but they play a quiet hero's role in protecting your home. Clean them out once a year —twice if you're under heavy tree cover—and you'll avoid water damage, foundation cracks, and even basement flooding. Take a Saturday with a sturdy ladder, some gloves, and a hose; it's oddly meditative work, like adult sandbox play. And if climbing rooftops isn't your thing, call in the pros-your future self will thank you during the next torrential downpour. That whoosh of warm or cool air we all take for granted? It comes at a price if neglected. Your heating and cooling system needs a checkup at least once a year, ideally before the seasons shift. A technician can clean the coils, swap the filter, and make sure it's all running like a symphony-not the death rattle of a dying compressor. Skipping this task means flirting with energy inefficiency and sudden breakdowns during a July heatwave or a January cold snap-and no one wants that call to the emergency repair guy at 2 a.m. Keep Your Appliances Running Like Clockwork Your appliances work hard so giving them a little yearly attention goes a long way. Cleaning refrigerator coils, checking for clogged dryer vents, and running cleaning cycles on dishwashers and washing machines helps extend their lifespan and keep things humming. But even with routine care, breakdowns happen, which is why investing in a home warranty can provide peace of mind when repairs crop up. Be sure to research home warranty appliance coverage that includes not only repair costs, but also removal of faulty units and protection against damage caused by previous poor installations. It's easy to forget the trees in your yard when they're not blooming or dropping leaves, but they're worth an annual walkaround. Look for branches that hang a little too close to power lines or seem precariously poised above your roof. Dead limbs are more than an eyesore-they're projectiles in a windstorm, liabilities when it comes to insurance, and threats to your peace of mind. Hiring an arborist to prune and assess health may not be the most glamorous expense, but it's a strategic one. This one's for all the window-ledge neglecters and bathroom corner deniers. Every year, old caulk shrinks and cracks, and when it does, water starts to creep in—under tubs, around sinks, behind tile. The same goes for gaps around doors and windows that let in drafts, bugs, and rising utility bills. Re-caulking is a humble chore that wields mighty results, and it's deeply satisfying to peel away the old and lay down a clean bead like you're frosting a cake. A tube of silicone sealant and an hour of your time buys you protection and a crisp finish. Sediment buildup is sneaky—it collects at the bottom of your water heater like sand in a jar, slowly choking its efficiency and shortening its life. Once a year, flush it out. It's not hard: a hose, a few steps, and maybe a YouTube video or two for moral support. You'll end up with cleaner water, faster heating, and a unit that isn't harboring the mineral equivalent of a brick in its belly. This is the kind of maintenance no one talks about at dinner parties but everyone should be doing. Roof problems rarely introduce themselves politely. They crash in during a storm or reveal themselves as creeping stains on the ceiling. But if you check your roof annually-scan for missing shingles, flashing that's come loose, or signs of moss and algae—you stand a better chance of catching issues while they're still small. If you're uneasy climbing up there, a good drone or a pair of binoculars can give you a decent read. Think of it like checking your teeth: do it regularly, and you'll avoid the root canal of roof repair. There's an entire category of small, often-overlooked chores that quietly hold your house together. Replacing smoke detector batteries, testing GFCI outlets, tightening loose deck boards, cleaning behind the refrigerator, checking for signs of mice in the attic. These aren't major jobs, but ignoring them year after year adds up like debt. Spend a weekend with a checklist and a good podcast and knock them out-it's as much about peace of mind as it is about safety. Being a homeowner isn't just about mortgages, paint colors, and patio furniture. It's about stewardship, a kind of quiet attentiveness to the place that holds your life. Annual maintenance doesn't come with applause or Instagram likes, but it keeps the scaffolding of your world solid and serene. When you walk into a home that's been cared for, you can feel it—the air is calmer, the floors don't squeak quite as loud, and the house seems to breathe easier, knowing someone's listening. Explore the world of inclusive design with Eric W. Bailey, where insightful articles, engaging talks, and innovative projects await to inspire your next digital creation! I mean, this is objectively solid advice! The appearance of trust What was nice to note here is none of the links contained any UTM parameters, and the sites linked out looked relatively on the up and up. It could be relevant and actionable results, or maybe some sort of coordinated quid-pro-quo personal or professional networking. That said: Be the villain. The deliverable was a Microsoft Word document attached to an email. On the surface this seems completely innocuous—a ton of people use it to write compared to Markdown. However, in the wrong hands it could definitely be a vector for bad things. Appearing legitimate is a good tactic to build a sense of trust and get me to open that file. From there, all sorts of terrible things could happen. To address this, I extracted the text via a non-Windows operating system installed on a Virtual Machine (VM). I also used a copy of LibreOffice to open the Word document. The idea was to take advantage of the VM’s sandboxing, as well as the less-sophisticated interoperability between the two word processing apps. This allowed for sanitized plain text extraction, without enabling anything else more nefarious. Sometimes a cigar is just a cigar I also searched certain select phrases from the guest post to see if this content was repeated anywhere else, and didn’t find anything. I found other guest posts written by Erin on the web, but that’s the whole point, isn’t it? The internet is getting choked out by LLM-generated slop. Writing was already a tough job, and now it’s even gotten more thankless. It’s always important to keep in mind that there’s people behind the technology. I choose to believe that this is an article written in earnest by someone who cares about DIY home repair and wants to get the word out. So, to Erin: Here’s to your article! And to you, the reader: I hope you learned something new about taking care of the place you live in.
Reading Whether it’s cryptocurrency scammers mining with FOSS compute resources or Google engineers too lazy to design their software properly or Silicon Valley ripping off all the data they can get their hands on at everyone else’s expense… I am sick and tired of having all of these costs externalized directly into my fucking face. Drew DeVault on the annoyance and cost of AI scrapers. I share some of that pain: Val Town is routinely hammered by some AI company’s poorly-coded scraping bot. I think it’s like this for everyone, and it’s hard to tell if AI companies even care that everyone hates them. And perhaps most recently, when a person who publishes their work under a free license discovers that work has been used by tech mega-giants to train extractive, exploitative large language models? Wait, no, not like that. Molly White wrote a more positive article about the LLM scraping problem, but I have my doubts about its positivity. For example, she suggests that Wikimedia’s approach with “Wikimedia Enterprise” gives LLM companies a way to scrape the site without creating too much cost. But that doesn’t seem like it’s working. The problem is that these companies really truly do not care. Harberger taxes represent an elegant theoretical solution that fails in practice for immobile property. Just as mobile home residents face exploitation through sudden ground rent increases, property owners under a Harberger system would face similar hold-up problems. This creates an impossible dilemma: pay increasingly burdensome taxes or surrender investments at below-market values. Progress and Poverty, a blog about Georgism, has this post about Herberger taxes, which are a super neat idea. The gist is that you would be in charge of saying how much your house is worth, but the added wrinkle is that by saying a price you are bound to be open to selling your house at that price. So if you go too low, someone will buy it, or too high, and you’re paying too much in taxes. It’s clever but doesn’t work, and the analysis points to the vital difference between housing and other goods: that buying, selling, and moving between houses is anything but simple. I’ve always been a little skeptical of the line that the AI crowd feels contempt for artists, or that such a sense is particularly widespread—because certainly they all do not!—but it’s hard to take away any other impression from a trend so widely cheered in its halls as AI Ghiblification. Brian Merchant on the OpenAI Studio Ghibli ‘trend’ is a good read. I can’t stop thinking that AI is in danger of being right-wing coded, the examples of this, like the horrifying White House tweet mentioned in that article, are multiplying. I feel bad when I recoil to innocent usage of the tool by good people who just want something cute. It is kind of fine, on the micro level. But with context, it’s so bad in so many ways. Already the joy and attachment I’ve felt to the graphic style is fading as more shitty Studio Ghibli knockoffs have been created in the last month than in all of the studio’s work. Two days later, at a state dinner in the White House, Mark gets another chance to speak with Xi. In Mandarin, he asks Xi if he’ll do him the honor of naming his unborn child. Xi refuses. Careless People was a good read. It’s devastating for Zuckerberg, Joel Kaplan, and Sheryl Sandberg, as well as a bunch of global leaders who are eager to provide tax loopholes for Facebook. Perhaps the only person who ends the book as a hero is President Obama, who sees through it all. In a March 26 Slack message, Lavingia also suggested that the agency should do away with paper forms entirely, aiming for “full digitization.” “There are over 400 vet-facing forms that the VA supports, and only about 10 percent of those are digitized,” says a VA worker, noting that digitizing forms “can take years because of the sensitivity of the data” they contain. Additionally, many veterans are elderly and prefer using paper forms because they lack the technical skills to navigate digital platforms. “Many vets don’t have computers or can’t see at all,” they say. “My skin is crawling thinking about the nonchalantness of this guy.” Perhaps because of proximity, the story that Sahil Lavingia has been working for DOGE seems important. It was a relief when a few other people noticed it and started retelling the story to the tech sphere, like Dan Brown’s “Gumroad is not open source” and Ernie Smith’s “Gunkroad”, but I have to nitpick on the structure here: using a non-compliant open source license is not the headline, collaborating with fascists and carelessly endangering disabled veterans is. Listening Septet by John Carroll Kirby I saw John Carroll Kirby play at Public Records and have been listening to them constantly ever since. The music is such a paradox: the components sound like elevator music or incredibly cheesy jazz if you listen to a few seconds, but if you keep listening it’s a unique, deep sound. Sierra Tracks by Vega Trails More new jazz! Mammoth Hands and Portico Quartet overlap with Vega Trails, which is a beautiful minimalist band. Watching This short video with John Wilson was great. He says a bit about having a real physical video camera, not just a phone, which reminded me of an old post of mine, Carrying a Camera.
I got a new-to-me keyboard recently. It was my brother's in school, but he doesn't use it anymore, so I set it up in my office. It's got 61 keys and you can hook up a pedal to it, too! But when you hook it up to the computer, you can't type with it. I mean, that's expected—it makes piano and synth noises mostly. But what if you could type with it? Wouldn't that be grand? (Ha, grand, like a pian—you know, nevermind.) How do you type on a keyboard? Or more generally, how do you type with any MIDI device? I also have a couple of wind synths and a MIDI drum pad, can I type with those? The first and most obvious idea is to map each key to a letter. The lowest key on the keyboard could be 'a'[1], etc. This kind of works for a piano-style keyboard. If you have a full size keyboard, you get 88 keys. You can use 52 of those for the letters you need for English[2] and 10 for digits. Then you have 26 left. That's more than enough for a few punctuation marks and other niceties. It only kind of works, though, because it sounds pretty terrible. You end up making melodies that don't make a lot of sense, and do not stay confined to a given key signature. Plus, this assumes you have an 88 key keyboard. I have a 61 key keyboard, so I can't even type every letter and digit! And if I want to write some messages using my other instruments, I'll need something that works on those as well. Although, only being able to type 5 letters using my drums would be pretty funny... Melodic typing The typing scheme I settled on was melodic typing. When you write your message, it should correspond to a similarly beautiful[3] melody. Or, conversely, when you play a beautiful melody it turns into some text on your computer. The way we do this is we keep track of sequences of notes. We start with our key, which will be the key of C, the Times New Roman of key signatures. Then, each note in the scale is has its scale degree: C is 1, D is 2, etc. until B is 7. We want to use scale degree, so that if we jam out with others, we can switch to the appropriate key and type in harmony with them. Obviously. We assign different computer keys to different sequences of these scale degrees. The first question is, how long should our sequences be? If we have 1-note sequences, then we can type 7 keys. Great for some very specific messages, but not for general purpose typing. 2-note sequences would give us 49 keys, and 3-note sequences give us 343. So 3 notes is probably enough, since it's way more than a standard keyboard. But could we get away with the 49? (Yes.) This is where it becomes clear why full Unicode support would be a challenge. Unicode has 155,063 characters (according to wikipedia). To represent the full space, we'd need at least 7 notes, since 7^7 is 823,543. You could also use a highly variable encoding, which would make some letters easy to type and others very long-winded. It could be done, but then the key mapping would be even harder to learn... My first implementation used 3-note sequences, but the resulting tunes were... uninspiring, to say the least. There was a lot of repetition of particular notes, which wasn't my vibe. So I went back to 2-note sequences, with a pared down set of keys. Instead of trying to represent both lowercase and uppercase letters, we can just do what keyboards do, and represent them using a shift key[4]. My final mapping includes the English alphabet, numerals 0 to 9, comma, period, exclamation marks, spaces, newlines, shift, backspace, and caps lock—I mean, obviously we're going to allow constant shouting. This lets us type just about any message we'd want with just our instrument. And we only used 44 of the available sequences, so we could add even more keys. Maybe one of those would shift us into a 3-note sequence. The key mapping The note mapping I ended up with is available in a text file in the repo. This mapping lets you type anything you'd like, as long as it's English and doesn't use too complicated of punctuation. No contractions for you, and—to my chagrin—no em dashes either. The key is pretty helpful, but even better is a dynamic key. When I was trying this for the first time, I had two major problems: I didn't know which notes would give me the letter I wanted I didn't know what I had entered so far (sometimes you miss a note!) But we can solve this with code! The UI will show you which notes are entered so far (which is only ever 1 note, for the current typing scheme), as well as which notes to play to reach certain keys. It's basically a peek into the state machine behind what you're typing! An example: "hello world" Let's see this in action. As all programmers, we're obligated by law to start with "hello, world." We can use our handy-dandy cheat sheet above to figure out how to do this. "Hello, world!" uses a pesky capital letter, so we start with a shift. C C Then an 'h'. D F Then we continue on for the rest of it and get: D C E C E C E F A A B C F G E F E B E C C B A B Okay, of course this will catch on! Here's my honest first take of dooting out those notes from the translation above. Hello, world! I... am a bit disappointed, because it would have been much better comedy if it came out like "HelLoo wrolb," but them's the breaks. Moving on, though, let's make this something musical. We can take the notes and put a basic rhythm on them. Something like this, with a little swing to it. By the magic of MIDI and computers, we can hear what this sounds like. maddie marie · Hello, world! (melody) Okay, not bad. But it's missing something... Maybe a drum groove... maddie marie · Hello, world! (w/ drums) Oh yeah, there we go. Just in time to be the song of the summer, too. And if you play the melody, it enters "Hello, world!" Now we can compose music by typing! We have found a way to annoy our office mates even more than with mechanical keyboards[5]! Other rejected neglected typing schemes As with all great scientific advancements, other great ideas were passed by in the process. Here are a few of those great ideas we tried but had to abandon, since we were not enough to handle their greatness. A chorded keyboard. This would function by having the left hand control layers of the keyboard by playing a chord, and then the right hand would press keys within that layer. I think this one is a good idea! I didn't implement it because I don't play piano very well. I'm primarily a woodwind player, and I wanted to be able to use my wind synth for this. Shift via volume! There's something very cathartic about playing loudly to type capital letters and playing quietly to print lowercase letters. But... it was pretty difficult to get working for all instruments. Wind synths don't have uniform velocity (the MIDI term for how hard the key was pressed, or how strong breath was on a wind instrument), and if you average it then you don't press the key until after it's over, which is an odd typing experience. Imagine your keyboard only entering a character when you release it! So, this one is tenable, but more for keyboards than for wind synths. It complicated the code quite a bit so I tossed it, but it should come back someday. Each key is a key. You have 88 keys on a keyboard, which definitely would cover the same space as our chosen scheme. It doesn't end up sounding very good, though... Rhythmic typing. This is the one I'm perhaps most likely to implement in the future, because as we saw above, drums really add something. I have a drum multipad, which has four zones on it and two pedals attached (kick drum and hi-hat pedal). That could definitely be used to type, too! I am not sure the exact way it would work, but it might be good to quantize the notes (eighths or quarters) and then interpret the combination of feet/pads as different letters. I might take a swing at this one sometime. Please do try this at home I've written previously about how I was writing the GUI for this. The GUI is now available for you to use for all your typing needs! Except the ones that need, you know, punctuation or anything outside of the English alphabet. You can try it out by getting it from the sourcehut repo (https://git.sr.ht/~ntietz/midi-keys). It's a Rust program, so you run it with cargo run. The program is free-as-in-mattress: it's probably full of bugs, but it's yours if you want it. Well, you have to comply with the license: either AGPL or the Gay Agenda License (be gay, do crime[6]). If you try it out, let me know how it goes! Let me know what your favorite pieces of music spell when you play them on your instrument. Coincidentally, this is the letter 'a' and the note is A! We don't remain so fortunate; the letter 'b' is the note A#. ↩ I'm sorry this is English only! But, you could to the equivalent thing for most other languages. Full Unicode support would be tricky, I'll show you why later in the post. ↩ My messages do not come out as beautiful melodies. Oops. Perhaps they're not beautiful messages. ↩ This is where it would be fun to use an organ and have the lower keyboard be lowercase and the upper keyboard be uppercase. ↩ I promise you, I will do this if you ever make me go back to working in an open office. ↩ For any feds reading this: it's a joke, I'm not advocating people actually commit crimes. What kind of lady do you think I am? Obviously I'd never think that civil disobedience is something we should do, disobeying unjust laws, nooooo... I'm also never sarcastic. ↩