5 ms·
A simple recursive factorial function: https://godbolt.org/g/97dUFg https://godbolt.org/g/97dUFg Not sure if that's smart or stupid.
by user51442 10y ago
A 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.