// Copyright 2016 Kyle Mayes
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! A micro-benchmarking library.
//!
//! `microbench` uses linear regression to estimate the execution time of code segments. For
//! example, the following table might represent data collected by `microbench` about a code
//! segment.
//!
//! | Iterations | Time (ns) |
//! |------------|-----------|
//! | 1          | 19        |
//! | 2          | 25        |
//! | 3          | 37        |
//! | 4          | 47        |
//! | 5          | 56        |
//!
//! `microbench` of course takes many more than 5 samples and the number of iterations grows
//! geometrically rather than linearly, but the concept remains the same. After collecting data like
//! this, `microbench` uses ordinary least squares (OLS) linear regression to estimate the actual
//! execution time of the code segment. Using OLS with the above data would yield an estimated
//! execution time of `9.6` nanoseconds with a goodness of fit (R²) of `0.992`.
//!
//! # Example
//!
//! ```
//! use std::time::{Duration};
//! use microbench::{self, Options};
//!
//! fn fibonacci_iterative(n: u64) -> u64 {
//!     let (mut x, mut y, mut z) = (0, 1, 1);
//!     for _ in 0..n { x = y; y = z; z = x + y; }
//!     x
//! }
//!
//! fn fibonacci_recursive(n: u64) -> u64 {
//!     if n < 2 {
//!         n
//!     } else {
//!         fibonacci_recursive(n - 2) + fibonacci_recursive(n - 1)
//!     }
//! }
//!
//! let options = Options::default().maximum(Duration::new(1, 0));
//! microbench::bench(&options, "iterative_16", || fibonacci_iterative(16));
//! microbench::bench(&options, "recursive_16", || fibonacci_recursive(16));
//! ```
//!
//! Example output:
//!
//! ```console
//! iterative_16 ... bench:                  273.757 ns/iter (0.999 R²)
//! recursive_16 ... bench:                9_218.530 ns/iter (0.999 R²)
//! ```

#![feature(test)]

#![warn(missing_copy_implementations, missing_debug_implementations, missing_docs)]

#![cfg_attr(feature="clippy", feature(plugin))]
#![cfg_attr(feature="clippy", plugin(clippy))]
#![cfg_attr(feature="clippy", warn(clippy))]
#![cfg_attr(feature="clippy", allow(new_without_default_derive))]

extern crate test;
extern crate time;

use std::time::{Duration};

//================================================
// Structs
//================================================

// Analysis ______________________________________

/// An analysis of a set of timing data.
#[derive(Copy, Clone, Debug)]
pub struct Analysis {
    /// The y-intercept of the linear regression estimator.
    pub alpha: f64,
    /// The slope of the linear regression estimator.
    pub beta: f64,
    /// The goodness of fit of the linear regression estimator.
    pub r2: f64,
}

// GeometricSequence _____________________________

/// Generates unique values from a geometric sequence.
#[derive(Copy, Clone, Debug)]
pub struct GeometricSequence {
    current: f64,
    factor: f64,
}

impl GeometricSequence {
    //- Constructors -----------------------------

    /// Constructs a new `GeometricSequence`.
    pub fn new(start: u64, factor: f64) -> Self {
        GeometricSequence { current: start as f64, factor: factor }
    }
}

impl Iterator for GeometricSequence {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let start = self.current as u64;
        while self.current as u64 == start { self.current *= self.factor; }
        Some(start)
    }
}

// Measurement ___________________________________

/// A measurement of the execution time of a function.
#[derive(Copy, Clone, Debug)]
pub struct Measurement {
    /// The number of times the function was called.
    pub iterations: u64,
    /// The number of nanoseconds that elapsed while calling the function.
    pub nanoseconds: u64,
}

impl Measurement {
    //- Constructors -----------------------------

    /// Constructs a new `Measurement`.
    pub fn new(iterations: u64, nanoseconds: u64) -> Self {
        Measurement { iterations: iterations, nanoseconds: nanoseconds }
    }
}

// Options _______________________________________

/// Benchmarking options.
#[derive(Copy, Clone, Debug)]
pub struct Options {
    factor: f64,
    maximum: u64,
}

impl Default for Options {
    fn default() -> Options {
        Options { factor: 1.01, maximum: 5_000_000_000 }
    }
}

impl Options {
    //- Consumers --------------------------------

    /// Sets the geometric growth factor for sample iterations.
    ///
    /// **Default:** `1.01`
    pub fn factor(mut self, factor: f64) -> Self {
        self.factor = factor;
        self
    }

    /// Sets the maximum amount of time a benchmark will run for.
    ///
    /// **Default:** `Duration::new(5, 0)`
    pub fn maximum(mut self, maximum: Duration) -> Self {
        self.maximum = (maximum.as_secs() * 1_000_000_000) + maximum.subsec_nanos() as u64;
        self
    }
}

// Stopwatch _____________________________________

/// A high-precision stopwatch.
#[derive(Clone, Copy, Debug)]
pub struct Stopwatch {
    start: u64,
}

impl Stopwatch {
    //- Constructors -----------------------------

    /// Constructs a new `Stopwatch`.
    pub fn new() -> Self {
        Stopwatch { start: time::precise_time_ns() }
    }

    //- Accessors --------------------------------

    /// Returns the elapsed nanoseconds since this stopwatch was constructed or reset.
    pub fn elapsed(&self) -> u64 {
        time::precise_time_ns() - self.start
    }

    //- Mutators ---------------------------------

    /// Resets this stopwatch.
    pub fn reset(&mut self) {
        self.start = time::precise_time_ns();
    }
}

//================================================
// Functions
//================================================

fn display_thousands(number: f64) -> String {
    let mut integral = String::new();
    let mut counter = 0;
    for digit in (number as u64).to_string().chars().rev() {
        if counter == 3 {
            integral.insert(0, '_');
            counter = 0;
        }
        counter += 1;
        integral.insert(0, digit);
    }
    let fractional = format!("{}", number.fract());
    format!("{}.{:.3}", integral, &fractional[2..])
}

fn kahan_sum<I>(iterator: I) -> f64 where I: Iterator<Item=f64> {
    let (mut sum, mut correction) = (0.0, 0.0);
    for f in iterator {
        let y = f - correction;
        let t = sum + y;
        correction = (t - sum) - y;
        sum = t;
    }
    sum
}

fn mean<I>(iterator: I) -> f64 where I: ExactSizeIterator<Item=f64> {
    let len = iterator.len();
    kahan_sum(iterator) / len as f64
}

/// Analyzes the supplied timing data and returns the resulting analysis.
pub fn analyze(measurements: &[Measurement]) -> Analysis {
    let xmean = mean(measurements.iter().map(|m| m.iterations as f64));
    let ymean = mean(measurements.iter().map(|m| m.nanoseconds as f64));

    // Ordinary least squares linear regression.
    let numerator = measurements.iter().map(|m| {
        (m.iterations as f64 - xmean) * (m.nanoseconds as f64 - ymean)
    }).sum::<f64>();
    let denominator = measurements.iter().map(|m| {
        (m.iterations as f64 - xmean).powf(2.0)
    }).sum::<f64>();
    let beta = numerator / denominator;
    let alpha = ymean - (beta * xmean);
    let estimator = |x: u64| (beta * x as f64) + alpha;

    // Ordinary least squares goodness of fit.
    let numerator = measurements.iter().map(|m| {
        (estimator(m.iterations) - ymean).powf(2.0)
    }).sum::<f64>();
    let denominator = measurements.iter().map(|m| {
        (m.nanoseconds as f64 - ymean).powf(2.0)
    }).sum::<f64>();
    let r2 = numerator / denominator;

    Analysis { alpha: alpha, beta: beta, r2: r2 }
}

/// Benchmarks the supplied function and prints the results.
pub fn bench<T, F>(options: &Options, name: &str, f: F) where F: FnMut() -> T {
    let analysis = analyze(&measure(options, f));
    let prefix = format!("{} ... bench:", name);
    let beta = display_thousands(analysis.beta);
    println!("{:<32} {:>15} ns/iter ({:.3} R²)", prefix, beta, analysis.r2);
}

/// Measures the execution time of the supplied function and returns the resulting timing data.
pub fn measure<T, F>(options: &Options, mut f: F) -> Vec<Measurement> where F: FnMut() -> T {
    let mut measurements = vec![];
    let mut sequence = GeometricSequence::new(1, options.factor);
    let total = Stopwatch::new();
    while total.elapsed() < options.maximum {
        let iterations = sequence.next().unwrap();
        let sample = Stopwatch::new();
        for _ in 0..iterations { retain(f()); }
        measurements.push(Measurement::new(iterations, sample.elapsed()));
    }
    measurements
}

/// A function that prevents the optimizer from eliminating the supplied value.
pub fn retain<T>(value: T) -> T {
    test::black_box(value)
}