On 2020-08-08 at 18:53:36 -0400, David Mertz mertz@gnosis.cx wrote:
... my discovery was that "LLVM figures out Gauss' simplification and does it in constant time no matter the N. After that I looked at the LLVM bytecode to see, "Yup, it does." The optimizer is pretty smart about variations in writing the code in some slightly different ways, but I don't know exactly what it would take to fool it into missing the optimization.
I was trying to learn something about 80X86 (where X might have been the empty string) assembly language by examing the output from Microsoft's C compiler. It made the same optimization, thus thwarting that particular effort, and that was probably 35 years ago now. For small N, it's really just constant folding, loop unrolling, and peephole optimizations; these days, "small N" might be a billion or 2**32.
The point isn't that it't not suprising, of course, but that it's not something new.