1 files changed, 78 insertions, 0 deletions
diff --git a/2018/src/benchmark.rs b/2018/src/benchmark.rs
new file mode 100644
index 0000000..76de9e4
--- /dev/null
+++ b/2018/src/benchmark.rs
@@ -0,0 +1,78 @@
+use std::fmt;
+use std::time::{Instant, Duration};
+
+const MIN_DUR: f64 = 1.0;
+const MIN_TIMES: usize = 4;
+
+pub struct Bench {
+    pub executions: usize,
+    pub duration: f64,
+    pub duration_stddev: f64,
+}
+
+impl fmt::Display for Bench {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{} secs ± {} ({}%)",
+               self.duration, self.duration_stddev, self.duration_stddev / self.duration * 100.0)
+    }
+}
+
+fn duration_secs(d: Duration) -> f64 {
+    d.as_secs() as f64 + d.subsec_nanos() as f64 / 1.0e9
+}
+
+// Returns estimate of single-iteration time
+fn warmup<A, F: Fn() -> A>(func: F) -> f64 {
+    let mut ntimes = 1;
+    let mut time_taken = 0.0;
+
+    while time_taken < 0.5 {
+        let start = Instant::now();
+        for _ in 0..ntimes {
+            func();
+        }
+        let end = Instant::now();
+        time_taken = duration_secs(end - start);
+
+        ntimes *= 2;
+    }
+
+    time_taken / ntimes as f64
+}
+
+pub fn benchmark<A, F: Fn() -> A>(func: F) -> Bench {
+    let estimate = warmup(&func);
+    let ntimes_guess = if MIN_TIMES as f64 * estimate >= MIN_DUR {
+        MIN_TIMES
+    } else {
+        (MIN_DUR / estimate).ceil() as usize
+    };
+
+    let nparts = if ntimes_guess < 10 {
+        ntimes_guess
+    } else {
+        std::cmp::max(10, ntimes_guess / 10)
+    };
+    let nperpart = (ntimes_guess + nparts - 1) / nparts;
+
+    let ntimes = nparts * nperpart;
+
+    // eprintln!("BENCH: estimate={} ntimes_guess={} nparts={} nperpart={} ntimes={}", estimate, ntimes_guess, nparts, nperpart, ntimes);
+
+    let mut times = vec![0.0; nparts];
+
+    for i in 0..nparts {
+        let start = Instant::now();
+        for _ in 0..nperpart {
+            func();
+        }
+        let end = Instant::now();
+
+        times[i] = duration_secs(end - start);
+    }
+
+    let mean = times.iter().map(|&t| t).sum::<f64>() / ntimes as f64;
+    let stddev = times.iter().map(|t| (t - mean) * (t - mean)).sum::<f64>() / (ntimes - 1) as f64;
+
+    Bench { executions: 0, duration: mean, duration_stddev: stddev }
+}