7 ms·
Try with gcc 6.2 options -Ofast -march=native: int square(int num) { int a = 0; for (int x = 0; x < num; x+=2) { if (!(x % 2)) { a += x
by rzimmerman 10y ago
Try with gcc 6.2 options -Ofast -march=native:
int square(int num) {
int a = 0;
for (int x = 0; x < num; x+=2) {
if (!(x % 2)) {
a += x;
}
}
return a;
}
All kinds of loop unrolling and vector instructions.
Now remove the "!"
- OskarS 10y agoDude, modern compilers are smart.
- user51442 10y agoA simple recursive factorial function: https://godbolt.org/g/97dUFg https://godbolt.org/g/97dUFg Not sure if that's smart or stupid.
- deleted 10y ago[deleted]
- GlitchMr 10y agoIt does try to vectorize it (doing multiple math operations at once is faster). (1 * 5 * 9 * 13 * 17 * ...) * (2 * 6 * 10 * 14 * 18 * ...) * (3 * 7 * 11 * 15 * 19 * ...) * (4 * 8 * 12 * 16 * 20 * ...) (it's not precisely that, but close enough) It isn't optimal however, optimal code would be pre-computed results (signed integer overflow is undefined, so n <= 12 is defined) (if signed integer overflow would be defined to be 2's complement overflow, you can still use a table, as n > 33 gives 0)
- Tuna-Fish 10y agoDude, your code got: 1. Turned from recursive form into iterative form 2. Unrolled heavily 3. Autovectorized (!) The throughput will be substantially more than the simple version.
- user51442 10y agoWell, the optimizations are pretty smart to be sure, the stupid thing is that anything over 12! overflows (as GlitchMr points out). I'd like to know how the recursion to iteration step was done.
- eutectic 10y agoPresumably there is a pass to turn f(recur(x), y) into recur(f(y, acc), x) and then tail-call optimization can be applied. This works for any associative f.
- jdcarter 10y agoI took that and check out what Clang does with 32-bit ints: https://godbolt.org/g/ORsX5h https://godbolt.org/g/ORsX5h vs. what it does with 64-bit ints: https://godbolt.org/g/2wBzn3 https://godbolt.org/g/2wBzn3 Can anybody explain the 32 bit version?
- user2994cb 10y agoHarder to vectorize 64-bit arithmetic?
- CorvusCrypto 10y agowas going to say this. It probably only does SSE and not SSE2. Therefore vectorization only happens for 32 bit ints.
- user2994cb 10y agoSeems to need -mavx2 to really go to town with 64 bit: https://godbolt.org/g/6EFYeY https://godbolt.org/g/6EFYeY
- jdcarter 10y agoThank you both, I appreciate the insight!
- CorvusCrypto 10y agoIt's just vectorizing calculations so that it's faster than pure iterative calculation. 64 bit version doesn't get this probably because that optimizer isn't SSE2 aware yet (just a guess I actually don't know) and can't do SIMD arithmetic with 2 64 bit floats
- lisivka 10y agoUse -Os to check. Compiler turned recursive function to loop.
- yellowapple 10y agoInterestingly, all the RISC architectures except for 64-bit ARM seem to compile down to something a lot simpler.
- topkekz 10y agoCheck this one (clang) https://godbolt.org/g/Brn57Z https://godbolt.org/g/Brn57Z
- Veedrac 10y agoThat's not smart - that's pattern matching.
- harpocrates 10y agoFor anyone too lazy: https://godbolt.org/g/jvSKCD https://godbolt.org/g/jvSKCD I would be much more impressed if I hadn't taken a compilers course. I reckon (god alone knows exactly what GCC does) this is just linear induction variable substitution[1] (so `x` gets replace with `i*2`), then associativity of integer multiplication, then some (probably builtin) rule that `n%n` is always 0. From there, it is pretty straightforward. Don't get me wrong - the devil is in the details and getting optimizations that are both powerful and only applied when they are valid, and at the right time is difficult as hell. That said, I do expect compilers to be at least this smart. [1]: https://en.wikipedia.org/wiki/Induction_variable#Induction_variable_substitution https://en.wikipedia.org/wiki/Induction_variable#Induction_v...
- digler999 10y ago> I do expect compilers to be at least this smart. Does anyone know if, internally, compilers second-guess / double-check themselves ? For instance, when they detect a clever shortcut do they generate and quickly run [1] the optimized bytecode on a sampling of inputs to verify it is functionally-equivalent to what non-optimized bytecode outputs ? [1] obviously cross-compilers are a thing, so this wouldn't be possible if it were compiling/optimizing for a separate architecture.
- jcranmer 10y agoDetecting functional equivalence of Turing-complete languages is a very non-trivial problem. So, no, compilers don't try to construct runtime proofs of their correctness. There are people who do do more exhaustive checks of the peephole optimizations for correctness--or finding new opportunities (see John Regehr's Souper work). But production compilers are well-known (at least by anyone who works on them) for having lots of bugs in these kinds of optimizations.
- drdrey 10y agoI think Nuno Lopes also did some work on proving the correctness of instcombine optimizations, for instance: http://blog.regehr.org/archives/1170 http://blog.regehr.org/archives/1170
- im3w1l 10y agoGCC is messing up here. Compare with clang! https://godbolt.org/g/HCifdP https://godbolt.org/g/HCifdP
- frederikvs 10y agoWait, that contains no loop. Is clang using mathematical rules for series summation? Awesome!
- janekm 10y agoIt gets even better after playing with the code a bit: https://godbolt.org/g/kUMCpl https://godbolt.org/g/kUMCpl magic constants galore... where does 3435973837 come from? ;)
- frederikvs 10y agoIt's 0xCCCCCCCD in hex, which looks a lot more structured at least. Though how exactly this makes sense is still unclear :-) [edit] and playing around with the increment of x it keeps throwing in some magical values which are a repeating pattern in hex, with the LSB off by one usually...
- john_reel 10y agoWell if A=1 (I know it’s not), D is 5-1. I’ve noticed that whatever you change five to fits this pattern. Ex: +=3 in the code gives you AAAAAAAB, and B would be (3-1) if A=1. I
- im3w1l 10y agoI thought 0xCCCCCCCD was a very nice number so I asked myself why it would come out like that. I wondered whether 0.CCCCCCCC.... = 4/5 had anything to do with it. Using hexadecimal we have 5 * 3 = 10 - 1, so 5 * C = 40 - 4 so 5 * (1 + C + C0 + C00 + C000...) = 5 - 4 + 40 - 40 + 400... where the last term is = 0 mod 2^32 ----- D This relates to 0.CCCCCC.... = 4 / 5 Because in order for that to come out right, multiplying 0.CCCC... with 5 has to have all intermediate terms cancel, leaving only a 4. So why would it take its digit from 4 / 5 and not 1 / 5? Because it takes x=4 to make the 5-x subtraction in 5 - x + x0 - x0 + x00 to come out to 1. So this gives us a general rule for inversion (for numbers less than 16). Take the hexadecimal expansion of (n-1) / n, truncate to get enough hex chars, add 1 to the least significant hex digit. I.e. the inversion of 3 would be 0xAAAAAAAB
- Sean1708 10y ago> Now remove the "!" To be fair 4.6 and clang also do that, and I suspect so do earlier versions if I could be arsed to fix the compilation error. Also as pointed out elsewhere clang turns the "!" version into a simple equation in terms of n, so I'm actually kind of disappointed in GCC here.
- bartl 10y agoIf that function is really supposed to return the square of a number, you took a wrong turn somewhere. Because it says the square of 16 is 56. Now here's a more efficient algorithm which does produce the currect result: int square(int num) { int a = 0; for (int x = 1, n = num; x <= num; x+=x, n+=n) { if( num & x) { a += n; } } return a; } It would be nice if this site allowed us to run/step through the code, to see exactly what it is doing.
- rzimmerman 10y agoOh, sorry, I never bothered to change the function name. It's just an interesting loop.
- joelthelion 10y agoWhy the hell doesn't gcc eliminate the loop in this case? https://godbolt.org/g/eXLhxH https://godbolt.org/g/eXLhxH
- noselasd 10y agoOddly enough, gcc 5.4 does.
- 0x6c6f6c 10y agoAlright maybe I'm stupid but I could have sworn that more than square(int): # @square(int) xor eax, eax ret is required to perform this, what's going on?
- akeruu 10y agoX can always by devided by 2, meaning the condition will always be false thus returning "a" unchanged. "xor eax, eax" is a shortcut to "mov eax, 0".
- syncsynchalt 10y ago"xor r,r" is intel-ese for "set r to zero". For various reasons it's faster and smaller than the more obvious "mov r,0". From this we can see that gcc and clang have figured out that the "if" can never be true, then they elided the loop, then optimized out the variable, ending in the equivalent of "return 0;".
- cestith 10y agoTry the same thing again with -Os and see the difference.