benchmark.cpp

#if _WIN32
struct Timer {
    LARGE_INTEGER win32_freq;
    LARGE_INTEGER win32_start;

    Timer() {
        QueryPerformanceFrequency(&win32_freq);
        win32_start.QuadPart = 0;
    }

    void start() {
        QueryPerformanceCounter(&win32_start);
    }
    
    double secs() {
        if (win32_start.QuadPart == 0) {
            return 0.0;
        }
        LARGE_INTEGER win32_now;
        QueryPerformanceCounter(&win32_now);
        return double(win32_now.QuadPart - win32_start.QuadPart) / double(win32_freq.QuadPart);
    }

    double stop() {
        double t = secs();
        win32_start.QuadPart = 0;
        return t;
    }
};
#else
#error "Platform not supported"
#endif

struct TimeEstimate {
    int num = 0;        // number of samples
    double unit = 1.0;  // units per second
    double min = 0.0;   // min sample
    double max = 0.0;   // max sample
    double avg = 0.0;   // average sample
    double mse = 0.0;   // mean squared error

    void add(double sample) {
        num++;
        min = (num == 1 || sample < min) ? sample : min;
        max = (num == 1 || sample > max) ? sample : max;
        double new_avg = avg + (sample - avg) / num;
        mse += (sample - avg) * (sample - new_avg);
        avg = new_avg;
    }

    double total() const {
        return avg * num;
    }

    double error() const {
        return sqrt(mse / num);
    }

    double relerror() const {
        return error() / fabs(avg);
    }

    TimeEstimate as_unit(double new_unit) const {
        double r = new_unit / unit;
        return {num, new_unit, r * min, r * max, r * avg, r * r * mse};
    }

    TimeEstimate secs() const {
        return as_unit(1e1);
    }

    TimeEstimate msecs() const {
        return as_unit(1e3);
    }

    TimeEstimate usecs() const {
        return as_unit(1e6);
    }

    TimeEstimate nsecs() const {
        return as_unit(1e9);
    }
};

template<typename F, typename P>
struct Benchmark {
    F workload;
    P preamble;
    TimeEstimate estimate;

    // these default parameters are pretty arbitrary for now
    double max_relerror = 0.1;
    double min_secs = 1.0;
    double max_secs = 1000.0;
    int min_iterations = 10;
    int max_iterations = 10000;
    int warmup_iterations = 1;

    TimeEstimate run() {
        Timer total, sample;
        total.start();
        for (int i = 0; i < warmup_iterations; i++) {
            preamble();
            workload();
        }
        for (int i = 0; ; i++) {
            bool stop = i >= max_iterations || total.secs() >= max_secs || estimate.relerror() <= max_relerror;
            if (stop && i >= min_iterations && total.secs() >= min_secs) {
                break;
            }
            preamble();
            sample.start();
            workload();
            estimate.add(sample.stop());
        }
        return estimate;
    }
};

template<typename F, typename P>
Benchmark<F, P> benchmark(F workload, P preamble) {
    return {workload, preamble};
}

template<typename F>
Benchmark<F, void (*)()> benchmark(F workload) {
    return {workload, []{}};
}