3 ms·
I've tried this with GCC 4.7.1 on Debian x86_64 and did not get it to work in constant time with -O2. I'm guessing (from the OP's usage of -install_name) that
by wulczer 14y ago
I've tried this with GCC 4.7.1 on Debian x86_64 and did not get it to work in constant time with -O2.
I'm guessing (from the OP's usage of -install_name) that he's been compiling this on OSX. I wonder what did my compiler miss that the OP's didn't?
EDIT: just tried with clang and got constant time behaviour, interesting
EDIT 2: reading the comments in the post, I now suspect it has to do with integer overflow. However, compiling with -fwrapv did not change anything. Need to dig into it more.
EDIT 3: it seem that clang simply notices that the computation can be done in constant time, whereas gcc does not. I'm not sure if it's actually useful in real world code, but it's certainly somewhat magical to see a compiler understand that you can substitute the entire loop with a simple calculation
- keeperofdakeys 14y agoI assume the OP would be using llvm, as this is the default OSX compiler, and the gcc command is usually just an alias or link to clang. In real world code this kind of optimisation is designed to catch things programmers aren't aware of, for a large decrease in required computation. In this case, sum(1 .. n) == n*(n+1)/2.
- DeepDuh 14y agooverflow exception is plausible (it overflows anyway but the question is whether the system will let it continue). Performance timing without validating your results is, well, not worth anything.