News for hackers. Stuff that matters.
Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by corysama on Tuesday August 11, 2015 @03:42PM (#10043795)
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 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?

Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by comex on Tuesday August 11, 2015 @04:22PM (#10044089)
Actually, 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.

Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by corysama on Tuesday August 11, 2015 @03:52PM (#10043871)
Double-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)
Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by minimax on Tuesday August 11, 2015 @04:52PM (#10044300)
This 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.
Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by corysama on Tuesday August 11, 2015 @05:18PM (#10044458)
Switching 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)
Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by corysama on Tuesday August 11, 2015 @06:23PM (#10044815)
This 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)
Re:Hand-Coded Assembly Beats Intrinsics in Speed and Simplicity by bro-stick on Tuesday August 11, 2015 @06:34PM (#10044862)
In writing a fast Hamming distance library in Go, dropping inline popcnt64 in using cgo was far slower than good, old-fashioned lookup table method for a single byte on a Haswell mobile processor. For the uint64 case, bitfolding was still faster than popcnt64. Perhaps for the vector buffer case, popcnt64 is faster.