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...

Click to view the original at

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