I love that randomness can, in of itself, be a form of computation. Superoptimization tries to find the best possible machine-code for a given function by searching. A lot. But what if you just…randomly changed the assembly of a program. Sure, 99+% would be incorrect, but there’s a chance you find something interesting! This was the idea behind STOKE, some Stanford research that, on occasion, would beat out human-written x86 assembly! For a little snippet of OpenSSL’s big-number library, STOKE found an 11 instruction solution. LLVM -O0 was 116 instructions. Even GCC -O3 was 27 instructions. The tradeoff of course is, insane computational cost. They gave 40 dual core Opteron a budget of 30 minutes of search for each small function. The OpenSSL optimization took about 17 minutes, resulting in a ~1.6x speedup over GCC. Not a bad optimization, but compilation was about uhh…10,000x slower. I do think it’s (at least theoretically) interesting for hot-path optimization, where you might be willing to spend the compilation budget to save a few nanoseconds. I like to imagine a very unusual (but possible!) processor. Custom hardware that does a randomized search for machine-code optimizations with extremely quick formal verification. A chip solely designed to make the software on…other chips faster!