5 ms·
for (s = i = 0; i < NUMBER; ++i) { s += 1; } I'm surprised gcc can't figure out that this is NUMBER*(NUMBER-1) and eliminate the loop entirely.
by martincmartin 6y ago
for (s = i = 0; i < NUMBER; ++i) {
s += 1;
}
I'm surprised gcc can't figure out that this is NUMBER*(NUMBER-1) and eliminate the loop entirely.
- zozbot234 6y agoIt probably can, at high-enough optimization level.
- jrockway 6y agogcc and clang both perform this optimization for me at -O3.
- martincmartin 6y agoThanks. On godbolt, I see clang do it at -O3. But gcc still has a loop, where the body has add but no mul, although I don't fully understand the body. Where do you see it in gcc? https://godbolt.org/z/sP194Y https://godbolt.org/z/sP194Y
- martincmartin 6y agoThey used -O2, which produces the straight forward loop. [0] But with -O3, for NUMBER > 51, is uses some other odd loop. [1] Seems to be O(n) no matter what though. [0]: https://godbolt.org/z/czcaYf https://godbolt.org/z/czcaYf [1]: https://godbolt.org/z/sP194Y https://godbolt.org/z/sP194Y
- saagarjha 6y agoClang knows what’s up: https://godbolt.org/z/7zKffz https://godbolt.org/z/7zKffz. GCC is adding the numbers four at a time by stuffing 0, 1, 2, 3 in an XMM register, taking a packed addition within the register, and then doing a pairwise packed addition of the register with 4, 4, 4, 4 to get the next four numbers.
- bigdict 6y ago> I'm surprised gcc can't figure out that this is NUMBER * (NUMBER-1) Huh? Do you mean NUMBER instead? If it were s += i then that would be NUMBER * (NUMBER-1) / 2.
- martincmartin 6y agoYou're right, I forgot the / 2.
- entha_saava 6y agoDid you mean s += i; ?