Re: Popcount optimization for the slow-path lookups

Hi Andy!

On 05.12.2025 14:07, Andrew Pogrebnoi wrote:
> Hello hackers,
> 
> I want to propose an optimization for pg_popcount32_slow() and
> pg_popcount64_slow() where lookups into pg_number_of_ones[] are made
> branchless. It shows speedup around 58% for uint64 and 35% for uint32 words
> compared to the current, looped version. This is on x86. It is much more
> significant on Arm64 (Apple M1): ~x2.6 for uint64 and ~x2.25 for uint32
> words.
> 
> I probably have to guard the lookup in pg_popcount64_slow() with `#if
> SIZEOF_LONG == 8` like it's done for __builtin_popcountl() in the same
> function. What do you think?
> 
> For benchmarks, I used functions with the copies of the lookup loop from
> pg_popcount32/64_slow(), measuring them against branchless counterparts.
> Then in C++ I pre generated two static vectors with random uint64's and
> uint32's, each of 5M size and ran lookups using google/benchmark [0]. I've
> run it on M1 and x86 Macs.
> 
> Results:
> 
> X86
> ```
> % g++ pop.cc -std=c++11 -isystem benchmark/include -L../benchmark/build/src
> -lbenchmark -lpthread -o mybenchmark && ./mybenchmark
> 2025-12-05T10:13:34+02:00
> Running ./mybenchmark
> Run on (12 X 3200 MHz CPU s)
> CPU Caches:
>   L1 Data 32 KiB
>   L1 Instruction 32 KiB
>   L2 Unified 256 KiB (x6)
>   L3 Unified 12288 KiB
> Load Average: 3.23, 4.56, 2.92
> --------------------------------------------------------------------
> Benchmark                          Time             CPU   Iterations
> --------------------------------------------------------------------
> Popcnt64_BranchlessLookup       17.2 ns         17.2 ns     39247568
> Popcnt64_PG                     27.2 ns         27.0 ns     25415636
> Popcnt32_BranchlessLookup       14.5 ns         14.4 ns     48441566
> Popcnt32_PG                     19.5 ns         19.4 ns     36125676
> ```
> 
> Apple M1
> ```
> $ g++ popcnt.cc -std=c++11 -isystem benchmark/include
> -L../benchmark/build/src -lbenchmark -lpthread -o mybenchmark &&
> ./mybenchmark
> 2025-12-05T08:59:12+00:00
> Running ./mybenchmark
> Run on (10 X 48 MHz CPU s)
> CPU Caches:
>   L1 Data 128 KiB (x10)
>   L1 Instruction 192 KiB (x10)
>   L2 Unified 12288 KiB (x10)
> Load Average: 0.28, 0.07, 0.02
> --------------------------------------------------------------------
> Benchmark                          Time             CPU   Iterations
> --------------------------------------------------------------------
> Popcnt64_BranchlessLookup       6.52 ns         6.52 ns    113974186
> Popcnt64_PG                     17.1 ns         17.1 ns     43015334
> Popcnt32_BranchlessLookup       4.34 ns         4.34 ns    145674483
> Popcnt32_PG                     9.79 ns         9.79 ns     75893374
> ```
> 
> 
> I also tried the Parallel summing of adjacent bits (see Hacker's Delight
> [1], Chapter 5)
> This is the code for uint64:
> ```
> #define POPCOUNT_M0 0x5555555555555555 // 01010101 ...
> #define POPCOUNT_M1 0x3333333333333333 // 00110011 ...
> #define POPCOUNT_M2 0x0F0F0F0F0F0F0F0F // 00001111 ...
> 
> static inline int
> pg_popcount_word64(uint64 word)
> {
>     word = word - ((word >> 1) & POPCOUNT_M0);
>     word = ((word >> 2) & POPCOUNT_M1) + (word & POPCOUNT_M1);
>     word = ((word >> 4) + word) & POPCOUNT_M2;
>     word += word >> 8;
>     word += word >> 16;
>     word += word >> 32; // this step is omitted for the uint32 version
> 
>     return word & 0x3F;
> }
> ```
> 
> However, it doesn't show any improvements compared to the branchless look
> up on M1 and a slight gain for uint64 on x86.
> 
> The same tests with the summing of adjacent bits:
> x86
> ```
> % g++ pop.cc -std=c++11 -isystem benchmark/include -L../benchmark/build/src
> -lbenchmark -lpthread -o mybenchmark && ./mybenchmark
> 2025-12-05T10:13:34+02:00
> Running ./mybenchmark
> Run on (12 X 3200 MHz CPU s)
> CPU Caches:
>   L1 Data 32 KiB
>   L1 Instruction 32 KiB
>   L2 Unified 256 KiB (x6)
>   L3 Unified 12288 KiB
> Load Average: 3.23, 4.56, 2.92
> --------------------------------------------------------------------
> Benchmark                          Time             CPU   Iterations
> --------------------------------------------------------------------
> Popcnt64_BranchlessLookup       17.2 ns         17.2 ns     39247568
> Popcnt64_AdjacentBits           16.8 ns         16.7 ns     41481236
> Popcnt64_PG                     27.2 ns         27.0 ns     25415636
> Popcnt32_BranchlessLookup       14.5 ns         14.4 ns     48441566
> Popcnt32_AdjacentBits           15.5 ns         15.4 ns     44454323
> Popcnt32_PG                     19.5 ns         19.4 ns     36125676
> ```
> 
> M1
> ```
> $ g++ popcnt.cc -std=c++11 -isystem benchmark/include
> -L../benchmark/build/src -lbenchmark -lpthread -o mybenchmark &&
> ./mybenchmark
> 2025-12-05T08:59:12+00:00
> Running ./mybenchmark
> Run on (10 X 48 MHz CPU s)
> CPU Caches:
>   L1 Data 128 KiB (x10)
>   L1 Instruction 192 KiB (x10)
>   L2 Unified 12288 KiB (x10)
> Load Average: 0.28, 0.07, 0.02
> --------------------------------------------------------------------
> Benchmark                          Time             CPU   Iterations
> --------------------------------------------------------------------
> Popcnt64_BranchlessLookup       6.52 ns         6.52 ns    113974186
> Popcnt64_AdjacentBits           8.05 ns         8.05 ns     86988490
> Popcnt64_PG                     17.1 ns         17.1 ns     43015334
> Popcnt32_BranchlessLookup       4.34 ns         4.34 ns    145674483
> Popcnt32_AdjacentBits           7.27 ns         7.27 ns     96050714
> Popcnt32_PG                     9.79 ns         9.79 ns     75893374
> ```
> 
> 
> 
> [0] https://github.com/google/benchmark
> [1] https://dl.acm.org/doi/book/10.5555/2462741
> 
> -----
> Cheers,
> Andy
> 

I would like to test if I can reproduce your results. Could you share
your test program?

You also don't specify an optimization level. That means the default
level -O0 is used. Does it make it a difference if you run e.g. with -O3?

--
David Geier