深入理解 False Sharing：实测原子操作与缓存行对齐对性能的影响

平均耗时: 21.1ms
cache-misses: 165,853
cache-references: 4,599,762
miss ratio: 3.6%

平均耗时: 12.5ms
cache-misses: 157,214
cache-references: 400,988
miss ratio: 39.2%

平均耗时: 208.3ms
cache-misses: 441,606
cache-references: 34,764,460
miss ratio: 1.27%

平均耗时: 61.9ms
cache-misses: 197,364
cache-references: 550,613
miss ratio: 35.8%

// 单核多线程执行过程：
线程A: 写入变量X → 缓存行变为dirty（仅存在于唯一的L1缓存中）
// 上下文切换到线程B
线程B: 写入变量Y → 同一缓存行仍在L1缓存中，直接命中，无需写回或重新加载
// 上下文切换回线程A
线程A: 再次写入X → 缓存行仍然有效，直接命中

alignas(64) int counter1;

// MESI状态详解
M (Modified):   该CPU独占且已修改，是唯一的"权威"副本
E (Exclusive):  该CPU独占但未修改，与内存一致
S (Shared):     多个CPU共享，都与内存一致  
I (Invalid):    缓存行无效，需要重新获取

// 普通变量写入时的缓存操作：
CPU1: 获取缓存行 → 修改数据 → 标记Modified
CPU2: 发现Invalid → 请求数据 → 获取 → 修改 → 标记Modified

// 原子变量写入时的额外步骤：
CPU1: 获取缓存行 → 锁定缓存行 → 原子修改 → 释放锁定 → 标记Modified
CPU2: 发现Invalid → 请求数据 → 等待锁定释放 → 获取 → 锁定 → 原子修改...

// 原子变量 + False Sharing 的完整开销分解：

1. 原子操作本身的开销              (+100% 基准时间)
2. False Sharing导致的缓存冲突     (+200% 基准时间)  
3. 原子操作与缓存冲突的相互放大     (+300% 基准时间)
4. 内存屏障阻止CPU优化            (+200% 基准时间)
----------------------------------------
总开销：                          800% 基准时间

# 普通变量写入 (*target = i)
mov %eax, (%rdi)    # 一条简单的内存写入指令

# 原子变量 relaxed store (atomic.store(i, relaxed))
mov %eax, (%rdi)         # x86-64上，对齐的原子store编译为普通mov指令
                         # x86内存模型保证对齐的mov本身就是原子的

# 原子变量 seq_cst store (atomic.store(i, seq_cst))
xchg %eax, (%rdi)        # 使用xchg实现顺序一致性（xchg隐含LOCK前缀）

# 原子变量 RMW操作 (atomic.fetch_add(1, relaxed))
lock xadd %eax, (%rdi)   # RMW操作需要LOCK前缀保证原子性，无论内存序

// 单核环境：False Sharing几乎无额外开销
// 只有一个L1缓存，缓存行不会因为线程切换而失效

// 多核False Sharing开销分解：
1. 原子操作本身的开销              (+100% 基准时间)
2. False Sharing导致的缓存冲突     (+200% 基准时间)  
3. 原子操作与缓存冲突的相互放大     (+300% 基准时间)
4. 内存屏障阻止CPU优化            (+200% 基准时间)
----------------------------------------
总开销：                          800% 基准时间

// 普通变量：Load-Store单元可以并行处理多个操作
store1: mov %eax, 0(%rdi)    // 可以与下面的指令并行
store2: mov %ebx, 4(%rdi)    
store3: mov %ecx, 8(%rdi)

// 原子变量（relaxed store）：x86上编译为普通mov，但缓存一致性协议仍保证可见性
atomic_store1: mov %eax, 0(%rdi)    // 对齐的mov在x86上是原子的
atomic_store2: mov %ebx, 4(%rdi)    // CPU可以对relaxed store做一定重排
atomic_store3: mov %ecx, 8(%rdi)    // 但在false sharing下仍受缓存一致性协议约束

// 优化策略：False Sharing主要影响多核环境
struct ThreadSafeData {
    alignas(64) int counter1;  // 多核环境强烈推荐，避免False Sharing
    alignas(64) int counter2;  // 单核环境无需此对齐，但现代系统基本都是多核
};

#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#include <atomic>
#include <iomanip>
#include <cstring>
#include <unistd.h>
#include <algorithm>  // 为std::min_element和std::max_element添加
#include <cmath>      // 为std::sqrt添加

// 测试参数
constexpr int NUM_THREADS = 2;
constexpr int ITERATIONS = 5000000;
constexpr int NUM_RUNS = 5;  // 每个测试运行多次取平均值

// 不同的测试用例结构体
struct NormalFalseSharing {
    int counter1;
    int counter2;
    int counter3;
    int counter4;
};

struct NormalNoFalseSharing {
    alignas(64) int counter1;
    alignas(64) int counter2;
    alignas(64) int counter3;
    alignas(64) int counter4;
};

struct AtomicFalseSharing {
    std::atomic<int> counter1{0};
    std::atomic<int> counter2{0};
    std::atomic<int> counter3{0};
    std::atomic<int> counter4{0};
};

struct AtomicNoFalseSharing {
    alignas(64) std::atomic<int> counter1{0};
    alignas(64) std::atomic<int> counter2{0};
    alignas(64) std::atomic<int> counter3{0};
    alignas(64) std::atomic<int> counter4{0};
};

// 辅助函数
template<typename TimePoint>
double get_duration_ms(TimePoint start, TimePoint end) {
    return std::chrono::duration<double, std::milli>(end - start).count();
}

// 清理系统状态的函数
void clear_system_state() {
    // 强制进行垃圾回收和缓存刷新
    std::this_thread::sleep_for(std::chrono::milliseconds(100));
    
    // 分配并释放一些内存来"污染"缓存
    volatile char* temp = new char[1024 * 1024];  // 1MB
    for (int i = 0; i < 1024 * 1024; i += 64) {
        temp[i] = i & 0xFF;
    }
    delete[] temp;
    
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
}

// 单独的测试函数
class IndependentTest {
public:
    enum TestType {
        NORMAL_FALSE_SHARING,
        NORMAL_NO_FALSE_SHARING,
        ATOMIC_FALSE_SHARING,
        ATOMIC_NO_FALSE_SHARING
    };
    
    static double run_single_test(TestType type) {
        switch (type) {
            case NORMAL_FALSE_SHARING:
                return test_normal_false_sharing();
            case NORMAL_NO_FALSE_SHARING:
                return test_normal_no_false_sharing();
            case ATOMIC_FALSE_SHARING:
                return test_atomic_false_sharing();
            case ATOMIC_NO_FALSE_SHARING:
                return test_atomic_no_false_sharing();
        }
        return 0.0;
    }
    
private:
    static double test_normal_false_sharing() {
        NormalFalseSharing data{};
        
        auto start = std::chrono::high_resolution_clock::now();
        
        std::vector<std::thread> threads;
        for (int t = 0; t < NUM_THREADS; ++t) {
            threads.emplace_back([&data, t]() {
                int* target = nullptr;
                switch(t) {
                    case 0: target = &data.counter1; break;
                    case 1: target = &data.counter2; break;
                    case 2: target = &data.counter3; break;
                    case 3: target = &data.counter4; break;
                }
                
                for (int i = 0; i < ITERATIONS; ++i) {
                    *target = i;
                }
            });
        }
        
        for (auto& thread : threads) {
            thread.join();
        }
        
        auto end = std::chrono::high_resolution_clock::now();
        return get_duration_ms(start, end);
    }
    
    static double test_normal_no_false_sharing() {
        NormalNoFalseSharing data{};
        
        auto start = std::chrono::high_resolution_clock::now();
        
        std::vector<std::thread> threads;
        for (int t = 0; t < NUM_THREADS; ++t) {
            threads.emplace_back([&data, t]() {
                int* target = nullptr;
                switch(t) {
                    case 0: target = &data.counter1; break;
                    case 1: target = &data.counter2; break;
                    case 2: target = &data.counter3; break;
                    case 3: target = &data.counter4; break;
                }
                
                for (int i = 0; i < ITERATIONS; ++i) {
                    *target = i;
                }
            });
        }
        
        for (auto& thread : threads) {
            thread.join();
        }
        
        auto end = std::chrono::high_resolution_clock::now();
        return get_duration_ms(start, end);
    }
    
    static double test_atomic_false_sharing() {
        AtomicFalseSharing data{};
        
        auto start = std::chrono::high_resolution_clock::now();
        
        std::vector<std::thread> threads;
        for (int t = 0; t < NUM_THREADS; ++t) {
            threads.emplace_back([&data, t]() {
                std::atomic<int>* target = nullptr;
                switch(t) {
                    case 0: target = &data.counter1; break;
                    case 1: target = &data.counter2; break;
                    case 2: target = &data.counter3; break;
                    case 3: target = &data.counter4; break;
                }
                
                for (int i = 0; i < ITERATIONS; ++i) {
                    target->store(i, std::memory_order_relaxed);
                }
            });
        }
        
        for (auto& thread : threads) {
            thread.join();
        }
        
        auto end = std::chrono::high_resolution_clock::now();
        return get_duration_ms(start, end);
    }
    
    static double test_atomic_no_false_sharing() {
        AtomicNoFalseSharing data{};
        
        auto start = std::chrono::high_resolution_clock::now();
        
        std::vector<std::thread> threads;
        for (int t = 0; t < NUM_THREADS; ++t) {
            threads.emplace_back([&data, t]() {
                std::atomic<int>* target = nullptr;
                switch(t) {
                    case 0: target = &data.counter1; break;
                    case 1: target = &data.counter2; break;
                    case 2: target = &data.counter3; break;
                    case 3: target = &data.counter4; break;
                }
                
                for (int i = 0; i < ITERATIONS; ++i) {
                    target->store(i, std::memory_order_relaxed);
                }
            });
        }
        
        for (auto& thread : threads) {
            thread.join();
        }
        
        auto end = std::chrono::high_resolution_clock::now();
        return get_duration_ms(start, end);
    }
};

// 统计辅助函数
struct TestResult {
    double min_time;
    double max_time;
    double avg_time;
    double stddev;
    
    TestResult(const std::vector<double>& times) {
        min_time = *std::min_element(times.begin(), times.end());
        max_time = *std::max_element(times.begin(), times.end());
        
        double sum = 0.0;
        for (double t : times) sum += t;
        avg_time = sum / times.size();
        
        double variance = 0.0;
        for (double t : times) {
            variance += (t - avg_time) * (t - avg_time);
        }
        stddev = std::sqrt(variance / times.size());
    }
};

void run_test_suite(IndependentTest::TestType type, const std::string& name) {
    std::cout << "\n=== " << name << " ===\n";
    
    std::vector<double> times;
    
    for (int run = 0; run < NUM_RUNS; ++run) {
        std::cout << "运行 " << (run + 1) << "/" << NUM_RUNS << "... ";
        std::cout.flush();
        
        // 清理系统状态
        clear_system_state();
        
        // 运行测试
        double time = IndependentTest::run_single_test(type);
        times.push_back(time);
        
        std::cout << std::fixed << std::setprecision(1) << time << "ms\n";
    }
    
    TestResult result(times);
    
    std::cout << "结果统计:\n";
    std::cout << "  平均: " << std::fixed << std::setprecision(1) << result.avg_time << "ms\n";
    std::cout << "  最小: " << result.min_time << "ms\n";
    std::cout << "  最大: " << result.max_time << "ms\n";
    std::cout << "  标准差: " << std::setprecision(2) << result.stddev << "ms\n";
    std::cout << "  变异系数: " << std::setprecision(1) 
              << (result.stddev / result.avg_time * 100) << "%\n";
}

void show_system_info() {
    std::cout << "=== 系统信息 ===\n";
    std::cout << "CPU核心数: " << std::thread::hardware_concurrency() << "\n";
    std::cout << "sizeof(int): " << sizeof(int) << " 字节\n";
    std::cout << "sizeof(std::atomic<int>): " << sizeof(std::atomic<int>) << " 字节\n";
    std::cout << "缓存行大小: 通常为64字节\n";
    std::cout << "测试参数: " << NUM_THREADS << " 线程, " 
              << ITERATIONS << " 次迭代, " << NUM_RUNS << " 次运行\n";
}

void show_memory_layout() {
    std::cout << "\n=== 内存布局验证 ===\n";
    
    NormalFalseSharing nfs{};
    std::cout << "普通变量(False Sharing):\n";
    std::cout << "  counter1: " << &nfs.counter1 << "\n";
    std::cout << "  counter2: " << &nfs.counter2 << " (距离: " 
              << (char*)&nfs.counter2 - (char*)&nfs.counter1 << " 字节)\n";
    
    NormalNoFalseSharing nnfs{};
    std::cout << "普通变量(无False Sharing):\n";
    std::cout << "  counter1: " << &nnfs.counter1 << "\n";
    std::cout << "  counter2: " << &nnfs.counter2 << " (距离: " 
              << (char*)&nnfs.counter2 - (char*)&nnfs.counter1 << " 字节)\n";
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cout << "用法: " << argv[0] << " <test_number>\n";
        std::cout << "  1: 普通变量 + False Sharing\n";
        std::cout << "  2: 普通变量 + 无False Sharing\n";
        std::cout << "  3: 原子变量 + False Sharing\n";
        std::cout << "  4: 原子变量 + 无False Sharing\n";
        std::cout << "  0: 显示系统信息和内存布局\n";
        return 1;
    }
    
    int test_num = std::atoi(argv[1]);
    
    if (test_num == 0) {
        show_system_info();
        show_memory_layout();
        return 0;
    }
    
    show_system_info();
    
    switch (test_num) {
        case 1:
            run_test_suite(IndependentTest::NORMAL_FALSE_SHARING, 
                          "普通变量 + False Sharing");
            break;
        case 2:
            run_test_suite(IndependentTest::NORMAL_NO_FALSE_SHARING, 
                          "普通变量 + 无False Sharing");
            break;
        case 3:
            run_test_suite(IndependentTest::ATOMIC_FALSE_SHARING, 
                          "原子变量 + False Sharing");
            break;
        case 4:
            run_test_suite(IndependentTest::ATOMIC_NO_FALSE_SHARING, 
                          "原子变量 + 无False Sharing");
            break;
        default:
            std::cout << "无效的测试编号: " << test_num << "\n";
            return 1;
    }
    
    return 0;
}