\nSuperoptimization is the process where a compiler automatically finds the optimal sequence for a loop-free sequence of instructions.
\n
Compilers are good at making mechanical transformations that make code faster. Unfortunately, most of them are not as good at non-trivial reasoning, so they can’t invent a completely novel approach to solving your problem.
\nWhen designing a library for floating-point calculations, I had to implement a function that takes a float f and produces a float corresponding to the lowest set bit in f. For example, if f=1.01101⋅210 in binary, it would return 0.00001⋅210=25.
\nThis can be implemented with bit twiddling, but the straightforward algorithm breaks for powers of two, so I had to insert an if:
if f32::from_bits(x.to_bits() & !f32::MANTISSA_MASK) == x { // is x a power of two?\n return x; // x itself is the lowest bit\n} else {\n return x - f32::from_bits(x.to_bits() & (x.to_bits() - 1)); // x, minus x without lowest bit\n}This if really annoyed me. It’s slowed down for the common case, and branches could be mispredicted. I wanted to find a formula that automatically handled powers of two, but try as I might, I couldn’t find anything convincingly optimal.
So I made a non-orthodox play.
\nWhat if there was a way to find such a formula automatically? No, not by spawning an LLM swarm, but by brute-forcing all possible formulas. LLMs can miss stuff or overindex on popular patterns; brute-force can’t.
\nBut how do we check if a formula is correct? Theorem provers are too slow, but we can design a few representative test cases and hope that whatever formula we find is correct. And if it has a counterexample, just add it to the list of test cases and repeat.
\nThis is not as insane as it sounds: by this moment I had already implemented an algorithm with 6 operations, so I just needed to iterate over formulas with 5 ops or fewer. I knew that the following operations could be useful:
\nThere are 65=7776 ways to choose 5 operations, each of which can be one of 6 variants, and C5=42 possible parentheses placements. That’s not a lot!
\nBut we also need to choose the inputs to each operation, which can be either the input value x or some constant. I guessed that we’ll only need constants that cover various fields of the float binary representation, and not completely random ones, reducing the list to 64 different constants. That’s 656 combinations, which sounds like a lot, but in practice we can cull many of them.
To implement the search efficiently, I build up the formula set inductively.
\nFormulas with 0 operations are just x and constants; formulas with n operations can be found by combining all pairs of formulas with k and n−1−k operations:
\nfor n_ops in 1..N_OPS {\n let mut new_exprs = FxHashSet::default();\n for a_ops in 0..n_ops {\n let b_ops = n_ops - 1 - a_ops;\n let a_exprs = &exprs_per_op_count[a_ops];\n let b_exprs = &exprs_per_op_count[b_ops];\n for a_expr in a_exprs {\n for b_expr in b_exprs {\n for op in OPS {\n // New expression: `a_expr op b_expr`\n new_exprs.insert(Expr {\n values: core::array::from_fn(|i| {\n op(a_expr.values[i], b_expr.values[i])\n }),\n });\n }\n }\n }\n }\n}Induction allows us to prune duplicates. For example, (x+1)+2 and (x+2)+1 are different expressions, but they return the same values. Keeping just one expression for each set of outputs allows further iterations to complete faster. This is the reason why brute-force can complete in just 4 minutes! (I’m sure it can be optimized further, but I preferred watching YouTube over optimizing a one-off script.)
\nTo save time and memory, I avoid deduplication on the last iteration and output all matching candidates. Memory usage matters because I had 20 test cases by this point, so I had to store 80 bytes per expression, and there are a lot of expressions.
\nSo, did this exhaustive search find anything interesting? Yes! There were several formulas with 5 operations, e.g. this one:
\nreturn x - f32::from_bits(x.to_bits() & (\n (f32::EXPONENT_MASK - (x | f32::EXPONENT_MASK)) ^ !f32::EXPONENT_MASK\n));I couldn’t find formulas with 4 operations, but this approach has a limitation: it doesn’t take into account that calculations can be reused. So, for example, if x & 1 is used in two places, it will count that as two operations, not one. I was hoping that one of the 5-op formulas could actually be expressed as 4 operations via reuse, and after manually checking every formula, the very last one turned out to have this property! Here’s what it looks like:
let a = x.to_bits() & !f32::MANTISSA_MASK; // x without mantissa bits\nreturn f32::from_bits(x.to_bits() & (a - x.to_bits())) - f32::from_bits(a);It behaves a little differently for powers of two – it flips the sign bit, which I don’t care about. And the logic doesn’t make sense at first glance, and yet it works.
\nThe reason why only this formula can reuse a is the subexpression a - x.to_bits(). It’s equivalent to -(x & f32::MANTISSA_MASK), which is how other formulas refer to it. All formulas compute x & !f32::MANTISSA_MASK and x & f32::MANTISSA_MASK, but this one rewrites the latter as x - (x & f32::MANTISSA_MASK), and then merges that with negation to save one operation!
I was flabbergasted when I realized it found such a clever rewrite. You don’t need an LLM to be amazed by what computers can invent! And it doesn’t destroy industries.
\nAnyway, this code now lives in my work-in-progress FPU emulator and I’m proud of it.
","headings":[{"level":3,"text":"Brute-force","id":"brute-force"},{"level":3,"text":"Search","id":"search"},{"level":3,"text":"Results","id":"results"}]}}