3 ms·
danluu knows much more about the subject matter than me. Meanwhile... If I take the main.cpp from http://www.strchr.com/media/crc32_popcnt.zip http://www.strc
by corysama 11y ago
danluu knows much more about the subject matter than me. Meanwhile...
If I take the main.cpp from http://www.strchr.com/media/crc32_popcnt.zip http://www.strchr.com/media/crc32_popcnt.zip that he comparing and paste it into a new, default, VC2010 project. Then compile it as a Release build, then the mixed disassembly for the inner loop of POPCNT_HardwareSubbuN() looks like
cnt += __popcnt(*(DWORD*)buf) +
__popcnt(*(DWORD*)(buf + sizeof(DWORD) )) +
__popcnt(*(DWORD*)(buf + sizeof(DWORD) * 2 )) +
__popcnt(*(DWORD*)(buf + sizeof(DWORD) * 3 ));
00E71BE0 popcnt ebx,dword ptr [edx+8]
00E71BE5 popcnt esi,dword ptr [edx+0Ch]
00E71BEA add esi,ebx
00E71BEC popcnt ebx,dword ptr [edx+4]
00E71BF1 add esi,ebx
00E71BF3 popcnt ebx,dword ptr [edx]
00E71BF7 add eax,ebx
00E71BF9 add eax,esi
buf += sizeof(DWORD) * 4;
00E71BFB add edx,10h
00E71BFE dec ecx
00E71BFF jne POPCNT_HardwareUnrolled+50h (0E71BE0h)
which looks to me to be as good or better than his inline asm
00000001000013c3 popcntq %r10, %r10
00000001000013c8 addq %r10, %rcx
00000001000013cb popcntq %r11, %r11
00000001000013d0 addq %r11, %r9
00000001000013d3 popcntq %r14, %r14
00000001000013d8 addq %r14, %r8
00000001000013db popcntq %rbx, %rbx
And does not have the odd
000000010000133e movl %ecx, %r10d
0000000100001341 movl %edx, %r11d
0000000100001344 movl %eax, %r14d
0000000100001347 movl %r8d, %ebx
He was complaining about.
Maybe there's some compiler issue about arrays that makes using "int cnt[4];" as the accumulator induce the seemingly extraneous movls?
- corysama 11y agoDouble-checked to make sure it wasn't a 64-bit issue: cnt += __popcnt(*(DWORD*)buf) + __popcnt(*(DWORD*)(buf + sizeof(DWORD) )) + __popcnt(*(DWORD*)(buf + sizeof(DWORD) * 2 )) + __popcnt(*(DWORD*)(buf + sizeof(DWORD) * 3 )); 000000013F231DF0 popcnt eax,dword ptr [r8+8] 000000013F231DF6 popcnt ecx,dword ptr [r8+0Ch] buf += sizeof(DWORD) * 4; 000000013F231DFC add r8,10h 000000013F231E00 add ecx,eax 000000013F231E02 popcnt eax,dword ptr [r8-0Ch] 000000013F231E08 add ecx,eax 000000013F231E0A popcnt eax,dword ptr [r8-10h] 000000013F231E10 add r9d,eax 000000013F231E13 add r9d,ecx 000000013F231E16 dec rdx 000000013F231E19 jne POPCNT_HardwareUnrolled+50h (13F231DF0h)
- minimax 11y agoThis also has the false dependency problem (using eax as the popcnt destination register three times), and neither one of your VC examples is using the 8 byte popcnt instruction.
- corysama 11y agoSwitching to __popcnt64 uses 8 byte popcnt. But, I can't get rid of the false dependency problem. RES64 cnt0=0, cnt1=0, cnt2=0, cnt3=0; SIZE_T ndqwords = len / (sizeof(RES64) * 4); for(; ndqwords; ndqwords--) { cnt0 += __popcnt64(*(RES64*)buf); cnt1 += __popcnt64(*(RES64*)(buf + sizeof(RES64) )); cnt2 += __popcnt64(*(RES64*)(buf + sizeof(RES64) * 2 )); cnt3 += __popcnt64(*(RES64*)(buf + sizeof(RES64) * 3 )); buf += sizeof(RES64) * 4; } cnt = cnt0 + cnt1 + cnt2 + cnt3; 000000013FD61FF3 popcnt rax,qword ptr [rdx] 000000013FD61FF8 add rdx,20h 000000013FD61FFC add r9,rax 000000013FD61FFF popcnt rax,qword ptr [rdx-18h] 000000013FD62005 add r10,rax 000000013FD62008 popcnt rax,qword ptr [rdx-10h] 000000013FD6200E add r8,rax 000000013FD62011 popcnt rax,qword ptr [rdx-8] 000000013FD62017 add r11,rax 000000013FD6201A dec rcx 000000013FD6201D jne main+0C3h (13FD61FF3h)
- corysama 11y agoThis gets rid of the false dependency problem. Not a shining example of simplicity or reliability. But, interesting that it works. struct A { RES64 cnt0; RES64 cnt1; RES64 cnt2; RES64 cnt3; } a; RES64 cnt0=0, cnt1=0, cnt2=0, cnt3=0; SIZE_T ndqwords = len / (sizeof(RES64) * 4); for(; ndqwords; ndqwords--) { a.cnt0 = __popcnt64(*(RES64*)buf); a.cnt1 = __popcnt64(*(RES64*)(buf + sizeof(RES64) )); a.cnt2 = __popcnt64(*(RES64*)(buf + sizeof(RES64) * 2 )); a.cnt3 = __popcnt64(*(RES64*)(buf + sizeof(RES64) * 3 )); cnt0 += a.cnt0; cnt1 += a.cnt1; cnt2 += a.cnt2; cnt3 += a.cnt3; buf += sizeof(RES64) * 4; } cnt = cnt0 + cnt1 + cnt2 + cnt3; 000000013F2320C0 popcnt rax,qword ptr [r8] 000000013F2320C5 popcnt rcx,qword ptr [r8+8] 000000013F2320CB popcnt rdx,qword ptr [r8+10h] 000000013F2320D1 popcnt rbx,qword ptr [r8+18h] 000000013F2320D7 add r11,rax 000000013F2320DA add rdi,rcx 000000013F2320DD add rsi,rdx 000000013F2320E0 add r8,20h 000000013F2320E4 add rbp,rbx 000000013F2320E7 dec r10 000000013F2320EA jne main+0D0h (13F2320C0h)
- comex 11y agoActually, it's not as good, because it doesn't take into account the false dependency issue - the register ebx is reused for three of the popcnts, making it impossible for them to execute in parallel on the buggy processors. But it's not out of the question that MSVC is better with intrinsics in general... I don't have any experience with it myself.