1
Superoptimizing an FPU emulator
purplesyringa.moeSuperoptimization is the process where a compiler automatically finds the optimal sequence for a loop-free sequence of instructions.
– Wikipedia
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.
When 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 ⋅ 2 10 in binary, it would return 0.00001 ⋅ 2 10 = 2 5 .
This 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?
return x; // x itself is the lowest bit
} else {
return x - f32::from_bits(x.to_bits() & (x.to_bits() - 1)); // x, minus x without lowest bit
}
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.
You must log in or register to comment.

