为何Numba实现的popcount代码比等效C代码快一倍？

Numba实现代码 #

from numba import njit
import numba as nb

@nb.njit(nb.uint64(nb.uint64))
def popcount(x): 
      b=0
      while(x > 0):
          x &= x - nb.uint64(1)   
          b+=1
      return b

@njit
def timed_loop(n):
    summand = 0
    for i in range(n):
        summand += popcount(i)
    return summand

该代码用于累加从0到n-1所有整数的popcount（置位位数）。

Numba性能测试结果 #

%timeit timed_loop(1000000)
340 µs ± 1.08 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

LLVM会将该popcount函数智能转换为CPU原生POPCNT指令，理论性能优异。

对比用的C代码 #

#include <stdio.h>
#include <time.h>

// Function to calculate the population count (number of set bits) of an integer using __builtin_popcount
int popcount(int num) {
    return __builtin_popcount(num);
}

int main() {
    unsigned int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);

    // Variables to store start and end times
    struct timespec start_time, end_time;

    // Get the current time as the start time
    clock_gettime(CLOCK_MONOTONIC, &start_time);

    int sum = 0;
    for (unsigned int i = 0; i < n; i++) {
        sum += popcount(i);
    }

    // Get the current time as the end time
    clock_gettime(CLOCK_MONOTONIC, &end_time);

    // Calculate the elapsed time in microseconds
    long long elapsed_time = (end_time.tv_sec - start_time.tv_sec) * 1000000LL +
                            (end_time.tv_nsec - start_time.tv_nsec) / 1000;

    printf("Sum of population counts from 0 to %d-1 is: %d\n", n, sum);
    printf("Elapsed time: %lld microseconds\n", elapsed_time);

    return 0;
}

使用-march=native -Ofast编译，gcc和clang结果相近：

./popcount 
Enter the value of n: 1000000
Sum of population counts from 0 to 1000000-1 is: 9884992
Elapsed time: 732 microseconds

核心原因分析 #

1. 数据类型宽度差异

Numba代码全程使用64位无符号整数（uint64），而C代码采用32位整数（int/unsigned int）。虽然POPCNT指令对32位、64位操作的延迟相近，但LLVM（Numba后端）对64位数据的循环向量化效率更高——它可利用AVX2等256位SIMD寄存器一次处理4个64位整数，累加操作的指令吞吐量更优，减少了循环迭代次数与指令调度开销。

2. 编译器优化策略差异

Numba使用的LLVM版本对这类简单循环的向量化、内联优化更激进：

• popcount会被完全内联到timed_loop中，LLVM还会将popcount与累加操作合并为紧凑的指令序列，避免额外寄存器移动开销。
• GCC/Clang在-Ofast下虽也会内联__builtin_popcount，但对32位累加循环的向量化策略相对保守，未充分利用SIMD并行累加能力。

3. 类型匹配减少隐式开销

Numba中循环变量i、累加器summand与popcount的输入输出类型完全匹配（均为uint64），无类型转换开销；而C代码中循环变量是unsigned int、累加器是int，每次累加都存在隐式类型扩展，积少成多后拉大了性能差距。

4. 计时方式的细微影响

%timeit会自动预热JIT代码并多次运行取平均，排除单次波动；而C代码是单次运行计时，若系统存在临时负载，单次计时可能偏高（但这不是差距的主要原因）。

验证优化方法 #

修改C代码为64位类型并优化编译参数，可缩小性能差距：

#include <stdio.h>
#include <time.h>
#include <stdint.h>

uint64_t popcount(uint64_t num) {
    return __builtin_popcountll(num);
}

int main() {
    uint64_t n;
    printf("Enter the value of n: ");
    scanf("%lu", &n);

    struct timespec start_time, end_time;
    clock_gettime(CLOCK_MONOTONIC, &start_time);

    uint64_t sum = 0;
    for (uint64_t i = 0; i < n; i++) {
        sum += popcount(i);
    }

    clock_gettime(CLOCK_MONOTONIC, &end_time);

    long long elapsed_time = (end_time.tv_sec - start_time.tv_sec) * 1000000LL +
                            (end_time.tv_nsec - start_time.tv_nsec) / 1000;

    printf("Sum of population counts from 0 to %lu-1 is: %lu\n", n, sum);
    printf("Elapsed time: %lld microseconds\n", elapsed_time);

    return 0;
}

用gcc -march=native -Ofast -o popcount popcount.c编译后，性能会接近Numba的测试结果。

内容的提问来源于stack exchange，提问作者Simd