Hacker News Reader

Comment by corysama | Hacker News Reader

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)

View on HN

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.

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)

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)

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.

Reply on news.ycombinator.com