Exploring Clang/LLVM optimization on programming horror
Recently, I've come across a not so efficient implementation of a isEven function (from r/programminghorror). bool isEven(int number) { int numberCompare = 0; bool even = true; while (number != numberCompare) { even = !even; numberCompare++; } return even; } The code is in C++, but the essence of th...
Hasnain says:
Some nice little compiler magic here.
“The code is in C++, but the essence of the algorithm is an iterative ascent to the input number from base case 0 (which is even), switching the boolean result at each iteration. It works, but you get a linear time O(n) isEven function compared to the obvious constant time O(1) modulo algorithm.
Surprisingly, Clang/LLVM is able to optimize the iterative algorithm down to the constant time algorithm”
Posted on 2021-08-18T07:26:20+0000