C++中使用gettimeofday计时出现重复结果问题

Hey there, let's break down why you're seeing those duplicate timing results and how to fix this issue for your hash table benchmark.

Why the Duplicates Are Happening #

The root problem here is that individual hash table insert operations are probably faster than the resolution of gettimeofday. While gettimeofday claims microsecond precision, many systems have a coarser clock tick (sometimes as low as 10-100 microseconds). When you measure each tiny insert operation separately, most of your time differences will read as zero—since the operation finishes before the clock updates. This leads to repeated identical results when you aggregate the data.

On top of that, gettimeofday can be thrown off by system time adjustments (like NTP syncs), which adds inconsistency to your measurements.

Solutions to Fix This #

1. Batch Insertions for More Reliable Timing

Instead of timing every single insert, wrap the entire loop of insertions within one start/end timer. This way, you measure the total time for all operations, then divide by the number of insertions to get an average per-operation time. This eliminates the noise from measuring sub-clock-resolution operations individually.

Here's how to adjust your code:

double benchmark(int amountOfInsertions){
    int valueToInsert;
    struct timeval tv_timeStart, tv_timeEnd;
    double totalTime = 0;

    // Start timer once before all insertions
    gettimeofday(&tv_timeStart, NULL);

    for (int i = 0; i < amountOfInsertions; i++){
        valueToInsert = generateRandomVariable();
        insert(valueToInsert);
    }

    // End timer after all insertions are done
    gettimeofday(&tv_timeEnd, NULL);

    // Calculate total time in milliseconds
    totalTime = (tv_timeEnd.tv_sec - tv_timeStart.tv_sec) * 1000.0;
    totalTime += (tv_timeEnd.tv_usec - tv_timeStart.tv_usec) / 1000.0;

    // Return average time per insertion (adjust based on your needs)
    return totalTime / amountOfInsertions;
}

2. Use a Higher-Precision Monotonic Timer

For even better accuracy, switch to clock_gettime with the CLOCK_MONOTONIC clock. This clock is built for measuring elapsed time—it's monotonic (never goes backward, even if system time changes) and often has nanosecond precision, which is perfect for fast operations like hash table inserts.

Here's an example implementation:

#include <time.h> // Required for clock_gettime

double benchmark(int amountOfInsertions){
    int valueToInsert;
    struct timespec ts_start, ts_end;
    double totalTime = 0;

    // Start the monotonic timer
    clock_gettime(CLOCK_MONOTONIC, &ts_start);

    for (int i = 0; i < amountOfInsertions; i++){
        valueToInsert = generateRandomVariable();
        insert(valueToInsert);
    }

    // Stop the timer
    clock_gettime(CLOCK_MONOTONIC, &ts_end);

    // Calculate total time in milliseconds
    totalTime = (ts_end.tv_sec - ts_start.tv_sec) * 1000.0;
    totalTime += (ts_end.tv_nsec - ts_start.tv_nsec) / 1000000.0;

    return totalTime / amountOfInsertions;
}

Bonus Tips for Better Benchmarks #

• Run multiple iterations: Repeat the entire benchmark several times and take the average of the results to reduce variance.
• Warm up first: Do a few dummy insertions before starting the timer to initialize the hash table's internal structures and account for caching effects.

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