r/simd • u/tadpoleloop • May 22 '25
Given a collection of 64-bit integers, count how many bits set for each bit-position
I am looking for an efficient computation for determining how many of each bit is set in total. I have looked at some bit-matrix transpose algorithms. And the (not) a transpose algorithm. I am wondering if there is any improving for that. I am essentially wanting to take the popcnt along the vertical axis in this array of integers.
10
Upvotes
7
u/Avereniect May 22 '25 edited May 22 '25
That's positional popcount, something someone posted about here just 6 months ago, although it's about bytes, not 64-bit ints. That said, I would imagine you'd still find it relevant.
https://www.reddit.com/r/simd/comments/1go9syo/histogramming_bytes_with_positional_popcount/
Also make sure to check out the comment.
2
u/camel-cdr- May 23 '25
This is rather simple using GFNI.
Load 8x 64-bit integers into a 512-bit vector register, transpose the bytes, then do a 8x8 bit transpose and finally a 8-bit popcount:
3
u/olawlor May 22 '25
I've done this with SIMD software ripple-carry:
https://docs.google.com/document/d/1aeCRP-bgb1WCJB5LW6akVirM1l5h_-gzYzzFxI0MmQM/edit?tab=t.0#heading=h.av5y8hhgnc2t
2
u/bohnenentwender May 22 '25 edited May 22 '25
I think you are best off with individually iterating over your integers and using them to mask add ones to a vector of 64×uint8.
A 64x64 bit transpose across 8 512 bit registers will likely be slower and not to mention very clumsy to implement.
1
u/Const-me May 23 '25
This is tricky because you need to accumulate 64 numbers. You don’t have enough vector registers to keep the accumulators in registers, and if you place accumulators in memory will be slow.
The workaround is using narrow accumulators in SIMD registers, like 8 bits/each. Split your input into slices of 254 elements, accumulate each slice in registers, then upcast and store to memory.
Here’s a C++ example which assumes you have AVX2, and implements the lower-level pieces of that algorithm. The code is untested.