如何正确对查表与直接计算进行性能基准测试？

问题背景 #

在对比查表实现与直接计算的性能时，Debug模式下查表速度是直接计算的4-5倍，符合预期；但开启-O2优化的Release模式下，查表速度比直接计算快数百倍，这与理论值（L1缓存查表约10周期，直接计算15-20周期，耗时应最多为查表的2倍）严重不符。核心问题是编译器优化了无实际副作用的计算循环，直接丢弃了未被使用的计算结果。

核心原因 #

编译器在-O2等优化级别下会执行死代码消除：如果循环内的计算结果未被后续代码使用（比如仅赋值给sign_of_product但未进一步处理），编译器会判定这段代码没有实际意义，直接删除整个循环，导致直接计算的耗时趋近于0，从而产生虚假的性能差距。

修正后的基准测试方案 #

1. 强制保留计算副作用 #

通过将计算结果累积到一个volatile变量中，让编译器无法判定代码是死代码。volatile关键字会告诉编译器该变量可能被外部修改，必须保留对它的所有操作。

示例：

// 定义volatile变量，确保结果被使用
volatile int8_t result_accumulator = 0;

在每个测试循环中，将结果累加到该变量：

// 单个点查表测试
for (int rept = 0; rept < REPETITIONS; rept++) {
    result_accumulator += lookup_table_sign[blade1][blade2];
}

// 单个点直接计算测试
for (int rept = 0; rept < REPETITIONS; rept++) {
    // 直接计算逻辑...
    result_accumulator += sign_of_product;
}

2. 修复数组越界bug #

原测试中单个点的blade1 = rand() % 256，但lookup_table_sign的大小是SIZE=64，会导致数组越界（未定义行为），修正为：

uint8_t blade1 = rand() % SIZE;
uint8_t blade2 = rand() % SIZE;

3. 随机化测试输入 #

使用随机生成的输入数组，避免编译器对固定输入做常量折叠或提前计算：

// 提前生成大量随机测试点
#include <vector>
#include <utility>

// ...

vector<pair<uint8_t, uint8_t>> test_points(REPETITIONS);
for (auto& p : test_points) {
    p.first = rand() % SIZE;
    p.second = rand() % SIZE;
}

// 单个点查表测试
auto start = std::chrono::high_resolution_clock::now();
for (auto& p : test_points) {
    result_accumulator += lookup_table_sign[p.first][p.second];
}
auto end = std::chrono::high_resolution_clock::now();

4. 调整测试时长 #

确保每个测试的运行时间至少在几百毫秒以上，减少计时误差。可以根据实际情况增大REPETITIONS的值，比如调整为1000000甚至更高。

5. 隔离测试环境 #

每个测试之间可以添加缓存预热步骤，或者分开编译运行不同的测试用例，避免前一个测试的缓存状态影响下一个测试的结果。

修改后的完整基准测试代码片段 #

// ... 其他代码保持不变 ...

int main() {
    initialize_constants();

    // ... 生成blades数组、创建lookup_table的代码保持不变 ...

#pragma region benchmark
    volatile int8_t result_accumulator = 0;
    const long long REPETITIONS = 1000000; // 增大重复次数，保证测试时长足够

    // 生成随机测试点
    vector<pair<uint8_t, uint8_t>> test_points(REPETITIONS);
    for (auto& p : test_points) {
        p.first = rand() % SIZE;
        p.second = rand() % SIZE;
    }

    // benchmark single point with table lookup
    auto start = std::chrono::high_resolution_clock::now();
    for (auto& p : test_points) {
        result_accumulator += lookup_table_sign[p.first][p.second];
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> elapsed_miliseconds = end - start;
    cout << "Lookup table (random points) took " << elapsed_miliseconds.count() << " ms" << endl;

    // benchmark entire table with table lookup
    start = std::chrono::high_resolution_clock::now();
    int full_table_repeats = REPETITIONS / (SIZE * SIZE);
    for (int rept = 0; rept < full_table_repeats; rept++) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                result_accumulator += lookup_table_sign[row][col];
            }
        }
    }
    end = std::chrono::high_resolution_clock::now();
    elapsed_miliseconds = end - start;
    cout << "Lookup entire table took " << elapsed_miliseconds.count() << " ms" << endl;

    // benchmark single point with direct calculation
    start = std::chrono::high_resolution_clock::now();
    for (auto& p : test_points) {
        uint8_t blade1 = p.first;
        uint8_t blade2 = p.second;
        uint8_t igc__blade1 = blade1 >> 1u;
        igc__blade1 ^= igc__blade1 >> 1u;
        igc__blade1 ^= igc__blade1 >> 2u;
        igc__blade1 ^= igc__blade1 >> 4u;

        uint8_t blade2__masked = igc__blade1 & blade2;
        uint8_t parity__2 = __builtin_popcount(blade2__masked & 0b11111110) & 1u;
        int8_t sign_of_product = 1 - 2 * parity__2;
        
        result_accumulator += sign_of_product;
    }
    end = std::chrono::high_resolution_clock::now();
    elapsed_miliseconds = end - start;
    cout << "Direct calculation (random points) took " << elapsed_miliseconds.count() << " ms" << endl;

    // benchmark entire table with direct calculation
    start = std::chrono::high_resolution_clock::now();
    for (int rept = 0; rept < full_table_repeats; rept++) {
        for (int blade1 = 0; blade1 < SIZE; blade1++) {
            for (int blade2 = 0; blade2 < SIZE; blade2++) {
                uint8_t igc__blade1 = blade1 >> 1u;
                igc__blade1 ^= igc__blade1 >> 1u;
                igc__blade1 ^= igc__blade1 >> 2u;
                igc__blade1 ^= igc__blade1 >> 4u;

                uint8_t blade2__masked = igc__blade1 & blade2;
                uint8_t parity__2 = __builtin_popcount(blade2__masked & 0b11111110) & 1u;
                int8_t sign_of_product = 1 - 2 * parity__2;
                
                result_accumulator += sign_of_product;
            }
        }
    }
    end = std::chrono::high_resolution_clock::now();
    elapsed_miliseconds = end - start;
    cout << "Direct calculation entire table took " << elapsed_miliseconds.count() << " ms" << endl;

    // 打印累加结果，防止编译器优化掉整个累加逻辑
    cout << "Accumulated result: " << (int)result_accumulator << endl;

#pragma endregion benchmark

    return 0;
}

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