I'm looking for the fastest way to popcount on large buffer of 512 or more bytes. I can guarantee any required alignment, and the buffer size is always a power of 2. The buffer corresponds to block allocations, so typically the bits are either all set, none set, or mostly set favoring the "left" of the buffer, with occasional holes.
Some solutions I've considered are:
- GCC's
__builtin_popcount
- Bitslice
popcount_24words
- Counting bits set, Brian Kernighan's way
I'm interested in the fastest solution, it must work on 32bit x86 chipset belonging to core2 or more recent. SSE and SIMD are of great interest. I'll be testing on the following quad core CPU:
matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
stepping : 11
cpu MHz : 1600.000
cache size : 4096 KB
physical id : 0
siblings : 4
core id : 0
cpu cores : 4
apicid : 0
initial apicid : 0
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips : 4800.21
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:
See a 32 bit version in the AMD Software Optimization guide, page 195 for one implementation.
This gives you assembly code for an x86 directly.
See a variant at Stanford bit-twiddling hacks
The Stanford version looks like the best one to me.
It looks very easy to code as x86 asm.
Neither of these use branch instructions.
These can be generalized to 64 bit versions.
With the 32 or 64 bit versions, you might consider doing a SIMD version.
SSE2 will do 4 double-words or two quadwords (either way 128 bits)
at once. What you want to do is implement the popcount for 32
or 64 bits in each of the 2 or 4 registers available.
You'll end up with 2 or 4 sets of popcounts in the XMM registers
when you are done; final step is to store and add those
popcounts together to get the final answer. Guessing,
I'd expect you do so slightly better doing 4 parallel 32
bit popcounts rather than 2 parallel 64 bit popcounts,
as the latter is likely to take 1 or 2 additional instructions
in each iteration, and its easy to add 4, 32 bit values together
the end.
If you had popcnt:
http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html
http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/intref_cls/common/intref_sse42_ATA.htm
I outline the best C/assembly functions I found for population count/Hamming weight of large buffers below.
The fastest assembly function is ssse3_popcount3, described here. It requires SSSE3, available on Intel Core 2 and later, and AMD chipsets arriving in 2011. It uses SIMD instructions to popcount in 16 byte chunks and unrolls 4 loop iterations at a time.
The fastest C function is popcount_24words, described here. It uses the bit-slicing algorithm. Of note I found that clang could actually generate appropriate vector assembly instructions, which gave impressive performance increases. This aside, the algorithm is still extremely fast.
I would suggest implementing one of the optimised 32 bit popcnt routines from Hacker's Delight, but do it for 4 x 32 bit integer elements in an SSE vector. You can then process 128 bits per iteration, which should give you around 4x throughput compared to an optimised 32 bit scalar routine.
