3 ms·
I just tested GCC, ICC, and Clang to see how well they perform these optimizations on their own. Code for my test is here: https://gist.github.com/nkurz/6844ad
by nkurz 12y ago
I just tested GCC, ICC, and Clang to see how well they perform these optimizations on their own. Code for my test is here: https://gist.github.com/nkurz/6844adbc58a03eb3420f https://gist.github.com/nkurz/6844adbc58a03eb3420f
The short answer is that they all do it well. For a loop like this compiled with -O3:
for (int i = 0; i < COUNT; i++) {
compilerSum += randomInt[i]/CONST;
}
ICC 14.0.3 takes 4.1 cycles per iteration, Clang 3.4.1 takes 3.8 cycles, and GCC 4.8.1 manages to spend only 1.3 cycles for each division!
Apparently GCC realized it was able to not only use a shortcut for the division, but also managed to vectorize the loop. Here's the inner loop it produced:
4019f0: 66 0f 6f 00 movdqa (%rax),%xmm0
4019f4: 48 83 c0 10 add $0x10,%rax
4019f8: 48 39 c5 cmp %rax,%rbp
4019fb: 66 0f 6f c8 movdqa %xmm0,%xmm1
4019ff: 66 0f 6f e0 movdqa %xmm0,%xmm4
401a03: 66 0f 62 c8 punpckldq %xmm0,%xmm1
401a07: 66 0f 6a e0 punpckhdq %xmm0,%xmm4
401a0b: 66 0f f4 cb pmuludq %xmm3,%xmm1
401a0f: 66 0f f4 e3 pmuludq %xmm3,%xmm4
401a13: 0f c6 cc dd shufps $0xdd,%xmm4,%xmm1
401a17: 66 0f fa c1 psubd %xmm1,%xmm0
401a1b: 66 0f 72 d0 01 psrld $0x1,%xmm0
401a20: 66 0f fe c1 paddd %xmm1,%xmm0
401a24: 66 0f 72 d0 02 psrld $0x2,%xmm0
401a29: 66 0f fe d0 paddd %xmm0,%xmm2
401a2d: 75 c1 jne 4019f0 <main+0xb0>
I put the other two here: https://gist.github.com/nkurz/b1c3e01498dd11fda42f https://gist.github.com/nkurz/b1c3e01498dd11fda42f
I didn't look closely enough to identify which methods they were using. Can someone else tell?
- kenferry 12y agoFish got his code committed into clang. I'm not sure about gcc, but it might have copied it from there.
- pbsd 12y agoGCC's vectorized loop is using the usual "round-up" method, but we can easily implement the distributive method there by mixing 32 and 64-bit arithmetic: ; xmm7 = 0 magic 0 magic ; xmm6 = 0 ; xmm5 = 0 (accumulator) division_loop: vmovdqu xmm4, [rax] ; xmm4 = w3 w2 w1 w0 vpunpckldq xmm0, xmm4, xmm6 ; xmm0 = 0 w1 | 0 w0 vpunpckhdq xmm2, xmm4, xmm6 ; xmm2 = 0 w3 | 0 w2 vpmuludq xmm1, xmm0, xmm7 ; xmm1 = w1 * magic | w0 * magic vpmuludq xmm3, xmm2, xmm7 ; xmm3 = w3 * magic | w2 * magic vpaddq xmm1, xmm1, xmm0 ; xmm1 = w1 * magic + w1 | w0 * magic + w0 vpaddq xmm3, xmm3, xmm2 ; xmm3 = w3 * magic + w3 | w2 * magic + w2 vpsrlq xmm1, xmm1, XX ; XX = shift constant vpsrlq xmm3, xmm3, XX ; XX = shift constant vshufps xmm1, xmm1, xmm3, 10001000b ; back to w3 w2 w1 w0 vpaddd xmm5, xmm5, xmm1 ; add to accumulator add rax, 16 cmp rax, rbp jnz division_loop The shifts can be further tweaked to allow to use a blend instead of a shuffle, in case there's a penalty for changing from integer to floating-point domains. Saturating increment also works well, despite there not being a PADDUSD instruction; it can be done in two cycles: ; xmm6 = -1 -1 -1 -1 vpcmpeqd xmm3, xmm4, xmm6 ; xmm3[i] = (xmm4[i] == -1 ? -1 : 0) vpsubd xmm4, xmm4, xmm6 ; xmm4[i] += 1 vpaddd xmm4, xmm4, xmm3 ; xmm4[i] += xmm3[i]
- nkurz 12y agoNice work! Seems like it extends fine to AVX2 for doing 8 divides at a time in less than 1 cycle per division if for some reason you need to divide a whole array by the same constant. Though rare, this is impressive considering the tradition of expensive division. I don't know if you will have a domain penalty for the vshufps, but I think the answer is yes, and that the blend would be better. The blend can also run on p015, versus only p5 for the shufps, so it might pipeline better. I hadn't realized until now that vshufps had different semantics than vpshufd and is able to combine from two different registers. If there is no penalty, this could be quite a useful instruction. Any reason for using 'w' for your 32-bit elements rather than 'd' for double-word as used in the instruction names?
- pbsd 12y agoAccording to Agner Fog, data domain penalties with SHUFPS are nonexistent, or at least pretty hard to trigger, on Haswell. Previous chips might complain, though. Problem with blends is that they require SSE4.1+, unlike the current version that is fully SSE2 (modulo AVX encoding niceties). I chose 'w' for no real reason other than being thinking of 'word' at the time.
- nkurz 12y agoI just tested, and I can now confirm that there is no domain switching penalty for using vshufps versus vpshufd on integer data for XMM and YMM on Haswell, nor for XMM on Sandy Bridge (no YMM comparison possible there because vpshufd requires AVX2).