基于SSE2指令集优化卡方函数的进一步性能优化咨询

我已将标准C实现的卡方检验函数转换为SSE2 intrinsics版本，两者输出结果一致。在4KB随机数据测试中，平均性能提升了70-90ms，现寻求进一步的优化方向。

常规C实现代码 #

int observed[256] = {0};
double chiSquare = 0.0;
double expected = (double)size / 256; // 固定期望取值
// 统计每个字节值的出现频率
for (int i = 0; i < size; i++) {
    observed[data[i]]++;
}
// 计算卡方统计量
for (int i = 0; i < 256; i++) {
    double diff = observed[i] - expected;
    chiSquare += (diff * diff) / expected;
}
return chiSquare;

SSE2 intrinsics实现代码 #

int observed[256] = {0};
const double expected = (double)size / 256;  // 将expected设为常量
double chiSquare = 0.0;
// 按16字节（128位）块处理数据
for (int i = 0; i < size; i += 16) {
    __m128i dataChunk = _mm_loadu_si128((__m128i*)(data + i));
    // 将8位值解包为16位值用于计数
    __m128i dataUnpacked = _mm_unpacklo_epi8(dataChunk, _mm_setzero_si128());
    // 并行提取并处理8个值
    for (int j = 0; j <= 1; j++) {
        uint16_t values[8];
        _mm_storeu_si128((__m128i*)values, dataUnpacked);
        for (int k = 0; k < 8; k++) {
            observed[values[k]]++;
        }
        dataUnpacked = _mm_unpackhi_epi8(dataChunk, _mm_setzero_si128());
    }
}
// 使用SSE2计算卡方统计量
__m128d sum = _mm_setzero_pd();
for (int i = 0; i < 256; i += 2) {
    __m128d observedVec = _mm_set_pd(observed[i + 1], observed[i]);
    __m128d diff = _mm_sub_pd(observedVec, _mm_set1_pd(expected));
    __m128d squaredDiff = _mm_mul_pd(diff, diff);
    __m128d result = _mm_div_pd(squaredDiff, _mm_set1_pd(expected));
    sum = _mm_add_pd(sum, result);
}
// 累加sum中的结果
double sumArray[2];
_mm_storeu_pd(sumArray, sum);
for (int i = 0; i < 2; i++) {
    chiSquare += sumArray[i];
}
return chiSquare;

可优化的方向 #

1. 计数阶段充分利用SIMD并行性 #

当前计数逻辑是将SIMD寄存器数据存回栈数组，再循环逐个递增observed元素，完全浪费了SIMD并行能力。可改为：

• 使用多个__m128i寄存器作为临时计数器，对16字节块内的字节进行并行计数，比如用掩码生成+_mm_add_epi32累加的SIMD直方图算法。
• 先在寄存器中暂存部分计数，最后一次性合并到全局observed数组，减少频繁内存写操作。

2. 预存常量减少重复计算 #

卡方统计量计算循环中，_mm_set1_pd(expected)被重复调用，可提前存入__m128d常量：

const __m128d expectedVec = _mm_set1_pd(expected);
// 后续循环直接复用
__m128d diff = _mm_sub_pd(observedVec, expectedVec);
__m128d result = _mm_div_pd(squaredDiff, expectedVec);

3. 优化内存访问对齐 #

• 若输入数据data能保证16字节对齐，将_mm_loadu_si128替换为_mm_load_si128，对齐加载性能远高于非对齐加载。
• 无法保证对齐时，可预处理拷贝数据到对齐缓冲区，或用__attribute__((aligned(16)))声明对齐数组。

4. 简化卡方统计量的最终累加 #

当前需将sum寄存器值存回数组再累加，可改用SSE2指令完成水平加法，避免内存操作：

// 合并sum中的两个double元素
__m128d temp = _mm_shuffle_pd(sum, sum, 0x1); // 交换两个元素
sum = _mm_add_pd(sum, temp);
chiSquare = _mm_cvtsd_f64(sum); // 提取最终结果

5. 减少循环嵌套与冗余操作 #

计数阶段的j和k循环可合并优化：直接从dataChunk提取所有16个字节，无需分两次unpack后存回数组，优先用SIMD指令完成计数逻辑。

6. 编译选项优化 #

开启编译器最高级优化：

• 使用-O3选项，让编译器自动优化寄存器分配、循环展开等。
• 添加-msse2（对应平台的SSE2启用选项），确保生成最优SIMD指令。

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