SIMD 向量化优化

add r1, r2  →  1次加法，处理1对数字

vaddps ymm1, ymm2  →  1次指令，同时处理8对float（AVX2，256位寄存器）

标量计算：
[a1] + [b1] = [c1]   ← 第1次指令
[a2] + [b2] = [c2]   ← 第2次指令
[a3] + [b3] = [c3]   ← 第3次指令
[a4] + [b4] = [c4]   ← 第4次指令
（4条指令）

SIMD计算：
[a1 a2 a3 a4] + [b1 b2 b3 b4] = [c1 c2 c3 c4]
（1条指令，理论上快4倍！）

# 查看你的CPU支持哪些指令集
cat /proc/cpuinfo | grep flags | head -1
# 看到 avx2、sse4_2 等字样

// 编译时加上优化选项
// g++ -O3 -march=native myprogram.cpp

void addArrays(float* a, float* b, float* result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];   // 编译器可能自动转成 SIMD 指令
    }
}

g++ -O3 -march=native -S myprogram.cpp -o output.asm
grep -i "vaddps\|vmulps" output.asm   # 看到这些说明用上了AVX指令

// ❌ 无法向量化：sum 依赖上一次迭代的结果
float sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];   // 每次都依赖上一次的 sum
}

// ✅ 4路展开，4个独立累加器，可以并行
float sum0 = 0, sum1 = 0, sum2 = 0, sum3 = 0;
int i = 0;
for (; i + 4 <= n; i += 4) {
    sum0 += a[i];
    sum1 += a[i+1];
    sum2 += a[i+2];
    sum3 += a[i+3];
}
float sum = sum0 + sum1 + sum2 + sum3;
for (; i < n; i++) sum += a[i];  // 处理剩余的

// ❌ 编译器不知道 a、b、result 是否指向重叠内存，不敢随意重排计算顺序
void addArrays(float* a, float* b, float* result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

// ✅ restrict 关键字承诺"这些指针不重叠"，编译器才敢大胆向量化
void addArrays(float* __restrict a, float* __restrict b, 
                float* __restrict result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

// ❌ 难以向量化：每个元素走的分支可能不同
for (int i = 0; i < n; i++) {
    if (a[i] > 0) result[i] = a[i] * 2;
    else result[i] = 0;
}

// ✅ 改写成无分支形式（用乘法代替if），更容易向量化
for (int i = 0; i < n; i++) {
    result[i] = (a[i] > 0) * a[i] * 2;   // bool 自动转 0/1
}

#include <immintrin.h>   // AVX intrinsics

void addArraysSIMD(float* a, float* b, float* result, int n) {
    int i = 0;
    
    // 每次处理8个float（AVX2，256位 = 8×32位）
    for (; i + 8 <= n; i += 8) {
        __m256 va = _mm256_loadu_ps(&a[i]);       // 加载8个float进寄存器
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vresult = _mm256_add_ps(va, vb);   // 一条指令完成8次加法
        _mm256_storeu_ps(&result[i], vresult);    // 存回内存
    }
    
    // 处理剩余不足8个的元素（标量方式补尾）
    for (; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

// 处理1000万个float相加

// 标量版本
for (int i = 0; i < n; i++) result[i] = a[i] + b[i];
// 耗时：~8ms

// AVX2手动向量化
addArraysSIMD(a, b, result, n);
// 耗时：~2ms（约4倍提升，受内存带宽限制，未达到理论8倍）

// 加载/存储
__m256 v = _mm256_loadu_ps(ptr);        // 加载8个float（无对齐要求）
__m256 v = _mm256_load_ps(ptr);         // 加载8个float（要求32字节对齐，更快）
_mm256_storeu_ps(ptr, v);               // 存储

// 算术运算
_mm256_add_ps(a, b);    // 加法
_mm256_sub_ps(a, b);    // 减法
_mm256_mul_ps(a, b);    // 乘法
_mm256_div_ps(a, b);    // 除法

// 比较与选择
_mm256_cmp_ps(a, b, _CMP_GT_OS);        // 比较，生成掩码
_mm256_blendv_ps(a, b, mask);           // 根据掩码选择

// 水平求和（把8个数加成1个，常用于reduce）
__m256 v = ...;
__m128 hi = _mm256_extractf128_ps(v, 1);
__m128 lo = _mm256_castps256_ps128(v);
__m128 sum = _mm_add_ps(hi, lo);
// ...继续水平相加直到剩1个数

#include <experimental/simd>
namespace stdx = std::experimental;

void addArrays(float* a, float* b, float* result, int n) {
    using simd_t = stdx::native_simd<float>;
    int width = simd_t::size();   // 自动获取当前CPU的SIMD宽度
    
    int i = 0;
    for (; i + width <= n; i += width) {
        simd_t va(a + i, stdx::element_aligned);
        simd_t vb(b + i, stdx::element_aligned);
        simd_t vresult = va + vb;   // 像普通运算符一样写代码！
        vresult.copy_to(result + i, stdx::element_aligned);
    }
    for (; i < n; i++) result[i] = a[i] + b[i];
}

#include <xsimd/xsimd.hpp>

void addArrays(float* a, float* b, float* result, int n) {
    using batch = xsimd::batch<float>;
    std::size_t inc = batch::size;
    
    std::size_t i = 0;
    for (; i < n - n % inc; i += inc) {
        batch va = batch::load_unaligned(&a[i]);
        batch vb = batch::load_unaligned(&b[i]);
        batch vres = va + vb;
        vres.store_unaligned(&result[i]);
    }
    for (; i < n; i++) result[i] = a[i] + b[i];
}

// ❌ AoS：SIMD难以加载，因为x/y/z交错排列，不连续
struct Point { float x, y, z; };
std::vector<Point> points;

// ✅ SoA：x坐标连续存储，可以直接SIMD批量加载
struct PointsSoA {
    std::vector<float> x, y, z;
};

void scalePoints(PointsSoA& p, float factor) {
    addArraysSIMD(p.x.data(), ..., factor, p.x.size());  // 直接SIMD处理整个x数组
}

✅ 值得手动优化的场景：
- 大规模数值计算（科学计算、图形学、音视频处理）
- 已确认是性能瓶颈（用 perf 验证过）
- 数据规模大（几千个元素以上才能摊薄开销）

❌ 不值得的场景：
- 数据量很小（SIMD的"启动开销"可能超过收益）
- 逻辑复杂、分支多（向量化收益有限，代码可读性大幅下降）
- 还没确认是瓶颈（过早优化是万恶之源）

第1层：选对算法和数据结构（O(n log n) vs O(n²)）→ 收益最大
第2层：Cache-friendly 布局（SoA、连续内存）       → 通常2-4倍提升
第3层：SIMD 向量化                                → 通常2-8倍提升（叠加在第2层之上）
第4层：手写汇编/极致指令调优                       → 边际收益递减，维护成本剧增