// Written in the D programming language

/**
Copyright: Copyright 2011-
License:   $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
Authors:   $(WEB erdani.com, Andrei Alexandrescu) and Kato Shoichi
Source:    $(PHOBOSSRC std/_benchmark.d)

Synopsis:
----
module nxt.module_one;
import std.benchmark, std.file;

void benchmark_fileWrite()
{
    std.file.write("/tmp/deleteme", "hello, world!");
}

void benchmark_fileRead()
{
    std.file.read("/tmp/deleteme");
}

mixin(scheduleForBenchmarking);

void main()
{
    printBenchmarks();
}
----

The code above prints:

---
===============================================================================
module_one                                             relative ns/iter  iter/s
===============================================================================
fileWrite                                                        144.2K    6.9K
fileRead                                                          27.1K   36.9K
===============================================================================
---
 */
module std.benchmark;

import std.algorithm, std.datetime, std.range, std.stdio, std.traits, std.typecons;
version(unittest) import std.random;

debug = std_benchmark;

/**
Benchmarks one or more functions for speed assessment and comparison,
and prints results as formatted text. A baseline timing that accounts
for benchmarking overheads is kept along with the results and
automatically deducted from all timings. A timing indistinguishable
from the baseline looping overhead appears with a run time of zero and
indicates a function that does too little work to be timed.

Measurement is done in epochs. For each function benchmarked, the
smallest time is taken over all epochs.

Benchmark results report time per iteration.

Params:

funs = If one ore more `funs` are provided, they must come as pairs
in which the first element is a string (the name of the benchmark) and
the second element is the alias of a function (the actual
benchmark). Each alias must refer to a function that takes either no
arguments or one integral argument (which is the iterations count).
target = `File` where output is printed.

Example:
---
printBenchmarks!(
    "file write", { std.file.write("/tmp/deleteme", "hello, world!"); },
    "file read",  { std.file.read("/tmp/deleteme"); })
    ();
---

The example above outputs to `stdout`:

---
===============================================================================
Benchmark                                              relative ns/iter  iter/s
===============================================================================
file write                                                       144.3K    6.9K
file read                                                         26.3K   38.0K
===============================================================================
---

With internal iteration, the results would be similar:

Example:
---
printBenchmarks!(
    "file write", { std.file.write("/tmp/deleteme", "hello, world!"); },
    "file read",  (uint n) {
        foreach (i; 0 .. n) std.file.read("/tmp/deleteme");
    })
    ();
---

In the example above, the framework iterates the first lambda many
times and collects timing information. For the second lambda, instead
of doing the iteration, the framework simply passes increasing values
of `n` to the lambda. In the end time per iteration is measured, so
the performance profile (and the printout) would be virtually
identical to the one in the previous example.

If the call to `printBenchmarks` does not provide a name for some
benchmarks, the name of the benchmarked function is used. (For
lambdas, the name is e.g. $(D __lambda5).)

Example:
---
void benchmark_fileWrite()
{
    std.file.write("/tmp/deleteme", "hello, world!");
}
printBenchmarks!(
    benchmark_fileWrite,
    "file read", { std.file.read("/tmp/deleteme"); },
    { std.file.read("/tmp/deleteme"); })
    ();
---

The example above outputs to `stdout`:

---
===============================================================================
Benchmark                                              relative ns/iter  iter/s
===============================================================================
fileWrite2()                                                      76.0K   13.2K
file read                                                         28.6K   34.9K
__lambda2                                                         27.8K   36.0K
===============================================================================
---

If the name of the benchmark starts with $(D "benchmark_") or $(D
"benchmark_relative_"), that prefix does not appear in the printed
name. If the prefix is $(D "benchmark_relative_"), the "relative"
column is filled in the output. The relative performance is computed
relative to the last non-relative benchmark completed and expressed in
either times (suffix $(D "x")) or percentage (suffix $(D "%")). The
percentage is, for example, $(D 100.0%) if benchmark runs at the same
speed as the baseline, $(D 200.0%) if the benchmark is twice as fast
as the baseline, and $(D 50%) if the benchmark is half as fast.

Example:
---
printBenchmarks!(
    "file write", { std.file.write("/tmp/deleteme", "hello, world!"); },
    "benchmark_relative_file read",  { std.file.read("/tmp/deleteme"); },
    "benchmark_relative_array creation",  { new char[32]; })
    ();
---

This example has one baseline and two relative tests. The output looks
as follows:

---
===============================================================================
Benchmark                                              relative ns/iter  iter/s
===============================================================================
file write                                                       140.2K    7.1K
file read                                                517.8%   27.1K   36.9K
array creation                                          1284.3%  116.0     8.6M
===============================================================================
---

According to the data above, file reading is $(D 5.178) times faster
than file writing, whereas array creation is $(D 1200) times faster
than file writing.

If no functions are passed as `funs`, calling `printBenchmarks`
prints the previously registered per-module benchmarks.
Refer to $(LREF scheduleForBenchmarking).
 */
void printBenchmarks(funs...)(File target = stdout)
{
    BenchmarkResult[] results;
    static if (funs.length > 0)
    {
        benchmark!(funs)(results);
    }
    else
    {
        runBenchmarks(results);
    }
    printResults(results);
}

/**
Benchmarks functions and appends the results to the `results`
parameter. This function is used by $(LREF printBenchmarks), and the
`funs` parameter has the same requirements as for that function.

Using `benchmark` directly is recommended for custom processing and
printing of _benchmark results.

Example:
---
BenchmarkResults[] timings;
benchmark!(
    "file write", { std.file.write("/tmp/deleteme", "hello, world!"); },
    "file read",  { std.file.read("/tmp/deleteme"); })
    (timings);
foreach (ref datum; timings)
{
    writefln("%s: %s ns/iteration", datum.benchmarkName,
        datum.perIteration.to!("nsecs", uint));
}
---
 */
void benchmark(funs...)(ref BenchmarkResult[] results, string moduleName = null)
{
    auto times = benchmarkImpl!(onlyAliases!funs)();
    uint curBenchmark = 0;
    string name;
    TickDuration lastBaseline;

    foreach (i, fun; funs)
    {
        static if (is(typeof(fun): string))
        {
            name = fun;
        }
        else
        {
            if (!name) name = funs[i].stringof;
            const isRelative = skipOver(name, "benchmark_") &&
                skipOver(name, "relative_");
            double relative;
            if (isRelative)
            {
                relative = cast(double) lastBaseline.to!("nsecs", uint) /
                    times[curBenchmark].to!("nsecs", uint);
            }
            else
            {
                lastBaseline = times[curBenchmark];
            }
            results ~= BenchmarkResult(
                moduleName,
                name,
                times[curBenchmark++],
                relative);
            name = null;
        }
    }
}

/**
   Result of one function's benchmark.
*/
struct BenchmarkResult
{
    /**
       Module name in which the function resides (`null` if not applicable).
    */
    string moduleName;
    /**
       Name of the benchmark (sans the `benchmark_` or $(D
       benchmark_relative_) prefix, if any).
    */
    string benchmarkName;
    /**
       Time per iteration.
    */
    TickDuration perIteration;
    /**
       Relative timing (if benchmark is a _relative one). Refer to the
       definition of `benchmarkModule` below for what constitutes a
       relative benchmark. For relative benchmarks, `relative` is
       $(D 1.0) if the benchmark has the same speed as its baseline,
       $(D 2.0) is the benchmark is twice as fast, and $(D 0.5) if the
       benchmark has half the speed. For non-_relative benchmarks, $(D
       relative) is set to `NaN`, which is testable with $(XREF
       math,isNaN).
     */
    double relative;
}

/*
  Given a bunch of aliases, benchmarks them all and returns their
  respective durations.
*/
private TickDuration[fun.length] benchmarkImpl(fun...)()
{
    immutable uint epochs = 1000;
    TickDuration minSignificantDuration = TickDuration.from!"usecs"(50);

    // Baseline function. Use asm inside the body to avoid
    // optimizations.
    static void baseline() { asm { nop; } }

    // Use a local pointer to avoid TLS access overhead
    auto theStopWatch = &.theStopWatch;

    // All functions to look at include the baseline and the measured
    // functions.
    import std.meta;
    alias AliasSeq!(baseline, fun) allFuns;
    TickDuration baselineTimePerIteration;
    TickDuration[fun.length] result;

    // MEASUREMENTS START HERE

    foreach (i, measured; allFuns)
    {
        TickDuration bestEpoch;

        // So we have several epochs, and bestEpoch will track the
        // minimum time across epochs.
        foreach (epoch; 0 .. epochs)
        {
            // Within each epoch, we call the function repeatedly
            // until we collect at least a total time of
            // minSignificantDuration.
            for (uint repeats = 1; repeats < 1_000_000_000; repeats *= 10)
            {
                auto elapsed = callFun!(allFuns[i])(repeats, *theStopWatch);

                if (elapsed < minSignificantDuration)
                {
                    // Crappy measurement, try again with more repeats
                    continue;
                }

                // Good measurement, record it if it's better than the
                // minimum.

                // Removing this useless test exposes a codegen bug.
                if (!repeats) throw new Exception(null);

                auto timePerIteration = elapsed / cast(double) repeats;
                if (bestEpoch == bestEpoch.init || timePerIteration < bestEpoch)
                {
                    bestEpoch = timePerIteration;
                }
                break;
            }
        }

        // Store the final result
        static if (i == 0)
        {
            baselineTimePerIteration = bestEpoch;
        }
        else
        {
            result[i - 1] = bestEpoch;
        }
    }

    // MEASUREMENTS JUST ENDED

    // Subtract the baseline from all results
    foreach (i, f; fun)
    {
        //writeln(__traits(identifier, fun[i]));
        if ((result[i] -= baselineTimePerIteration) < TickDuration.init) {
            result[i] = TickDuration.init;
        }
    }

    // Return result sans the baseline
    return result;
}

unittest
{
    import std.conv : to;

    debug(std_benchmark) {} else void writefln(S...)(S args){}

    int a = 123_456_789;
    auto r = benchmarkImpl!(
        {auto b = to!string(a);},
        {auto b = to!wstring(a);},
        {auto b = to!dstring(a);})
        ();
    auto names = [ "intToString", "intToWstring", "intToDstring" ];
    foreach (i, timing; r)
        writefln("%s: %sns/call", names[i], r[i].to!("nsecs", int)());
}

// Verify Example 2
unittest
{
    import std.conv;

    debug (std_benchmark) {} else void writefln(S...)(S args){}

    int a = 123_456_789;
    auto r = benchmarkImpl!(
        (uint n) { foreach (i; 0 .. n) auto b = to!string(a); },
        (uint n) { foreach (i; 0 .. n) auto b = to!wstring(a); },
        (uint n) { foreach (i; 0 .. n) auto b = to!dstring(a); })
        ();
    auto names = [ "intToString", "intToWstring", "intToDstring" ];
    foreach (i, timing; r)
        writefln("%s: %sns/call", names[i], r[i].to!("nsecs", int)());
}

/*
 * Calls a function either by alias or by string. Returns the duration
 * per iteration.
 */
private TickDuration callFun(alias measured)(uint repeats, ref StopWatch theStopWatch)
{
    with (theStopWatch) running ? reset() : start();

    static if (is(typeof(measured(repeats))))
    {
        // Internal iteration
        measured(repeats);
    }
    else
    {
        // External iteration
        foreach (j; 0 .. repeats)
        {
            measured();
        }
    }

    return theStopWatch.peek();
}

/*
 * Given a bunch of aliases and strings, keeps only aliases of symbols
 * that start with "benchmark_".
 */
private template onlyBenchmarks(T...)
{
    import std.meta;

    static if (!T.length)
    {
        alias T onlyBenchmarks;
    }
    else static if (T[0].stringof.length > 10 && T[0].stringof[0 .. 10] == "benchmark_")
    {
        alias AliasSeq!(T[0], onlyBenchmarks!(T[1 .. $])) onlyBenchmarks;
    }
    else
    {
        alias AliasSeq!(onlyBenchmarks!(T[1 .. $])) onlyBenchmarks;
    }
}

/*
  Eliminates strings, keeping only aliases.
 */
private template onlyAliases(T...)
{
    import std.meta;

    static if (!T.length)
    {
        alias T onlyAliases;
    }
    else static if (!is(typeof(T[0]) : string))
    {
        alias AliasSeq!(T[0], onlyAliases!(T[1 .. $])) onlyAliases;
    }
    else
    {
        alias AliasSeq!(onlyAliases!(T[1 .. $])) onlyAliases;
    }
}

unittest
{
    alias onlyAliases!("hello", int, "world", double) aliases;
    static assert(aliases.length == 2);
    static assert(is(int == aliases[0]));
    static assert(is(double == aliases[1]));
}

debug (std_benchmark) mixin(scheduleForBenchmarking);

/*
Generates benchmarking code for a bunch of functions passed as
strings. Intended to be used during compilation as part of $(D
scheduleForBenchmarking).
 */
string benchmarkModuleCodegen()(string[] funs...)
{
    auto result = q{addBenchmarks(& benchmark!(};
    foreach (fun; funs)
    {
        import std.algorithm;
        if (!startsWith(fun, "benchmark_"))
        {
            continue;
        }
        result ~= fun;
        result ~= ", ";
    }
    result ~= q{), "test");};
    return result;
}

/**
The examples shown so far feature simple, ad-hoc benchmarks, but $(D
std.benchmark) allows for superior automation and systematic use aimed
at large projects.

The code $(D mixin(scheduleForBenchmarking)) planted at module level
schedules the entire module for benchmarking. The actual benchmarking
can be done globally by calling $(LREF printBenchmarks) (with no
arguments) or $(LREF runBenchmarks). Either call is usually made from
`main`.

In a multi-module application, several modules may define benchmarks,
and `printBenchmarks` distinguishes each visually.

Example:
---
module nxt.acme;
import std.file, std.array;

void benchmark_fileWrite()
{
    std.file.write("/tmp/deleteme", "hello, world!");
}

void benchmark_relative_fileRead()
{
    std.file.read("/tmp/deleteme");
}

mixin(scheduleForBenchmarking);
---

Typically the `mixin` is guarded by a version so benchmarks are only run if desired.

Example:
---
version (benchmark_enabled) mixin(scheduleForBenchmarking);
---
 */
@property string scheduleForBenchmarking()
{
    return `
shared static this()
{
    mixin("enum code = benchmarkModuleCodegen(__traits(allMembers, "~
            .stringof[7 .. $]~"));");
    mixin(code);
}`;
}

debug (std_benchmark)
{
    private void benchmark_fileWrite()
    {
        import std.file;
        std.file.write("/tmp/deleteme", "hello, world!");
    }

    private void benchmark_fileRead()
    {
        import std.file;
        std.file.read("/tmp/deleteme");
    }

    private void benchmark_appendBuiltin(uint n)
    {
        string a;
        foreach (i; 0 .. n)
        {
            a ~= 'x';
        }
    }

    private void benchmark_relative_appendAppender(uint n)
    {
        import std.range;
        auto a = appender!string();
        foreach (i; 0 .. n)
        {
            put(a, 'x');
        }
    }

    private void benchmark_relative_appendConcat(uint n)
    {
        string a;
        foreach (i; 0 .. n)
        {
            a = a ~ 'x';
        }
    }
}

/*
Adds benchmarks to the global queue of benchmarks to be executed. Most
frequently used implicitly by $(LREF scheduleForBenchmarking).
 */
void addBenchmarks(
    void function(ref BenchmarkResult[], string) fun,
    string moduleName)
{
    allBenchmarks ~= tuple(moduleName, fun);
}

// One benchmark stopwatch
private StopWatch theStopWatch;

/*
Array containing all benchmarks to be executed. Usually they are
executed by calling `runBenchmarks` or `printBenchmarks`.
 */
private Tuple!(string, void function(ref BenchmarkResult[], string))[]
allBenchmarks;

/**

Performs all benchmarks previously scheduled with $(LREF
scheduleForBenchmarking), application-wide. Usually not called
directly, but instead as support for $(LREF printBenchmarks). User
code may be interested in using this function directly for
e.g. results formatting.

  */
void runBenchmarks(ref BenchmarkResult[] results)
{
    foreach (b; allBenchmarks)
    {
        b[1](results, b[0]);
    }
}

/**
Prints benchmark results as described with $(LREF
printBenchmarks). This is useful if benchmark postprocessing is
desired before printing.
 */
void printResults(in BenchmarkResult[] data, File target = stdout)
{
    if (data.empty)
    {
        return;
    }

    enum columns = 79;
    string thisModule, thisGroup;

    void printModuleHeader()
    {
        target.writefln(
            "==================================================" ~
            "=============================\n" ~
            "%-*s%8s%8s%8s\n" ~
            "=================================================" ~
            "==============================", columns - 24,
            thisModule is null ? "Benchmark" : thisModule,
            "relative", "t/iter", "iter/s");
    }

    foreach (i, datum; data)
    {
        if (thisModule != datum.moduleName || i == 0)
        {
            thisModule = datum.moduleName;
            printModuleHeader();
        }
        double itersPerSecond = 1.0 / datum.perIteration.to!("seconds", double)();
        auto name = datum.benchmarkName;
        if (datum.relative is double.init)
        {
            // Write without relative information
            target.writefln("%-*s %6.1ms  %6.1m",
                    columns - 16, name,
                    datum.perIteration.to!("seconds", double)(),
                    itersPerSecond);
        }
        else
        {
            // Write with relative information
            double relative = datum.relative;
            string fmt;
            if (relative < 1000)
            {
                // represent relative speed as percent
                fmt = "%-*s %7.1f%%  %6.1m  %6.1m";
                relative *= 100;
            }
            else
            {
                // represent relative speed as multiplication factor
                fmt = "%-*s  %6.1mx  %6.1m  %6.1m";
            }
            target.writefln(fmt,
                    columns - 25, name,
                    relative,
                    datum.perIteration.to!("seconds", double)(),
                    itersPerSecond);
        }
    }
    target.writeln(repeat('=', columns));
}

/**
Suspends and resumes the current benchmark, respectively. This is useful
if the benchmark needs to set things up before performing the
measurement.

Example:
----
import std.algorithm;
void benchmark_findDouble(uint n)
{
    // Fill an array of random numbers and an array of random indexes
    benchmarkSuspend();
    auto array = new double[n];
    auto indexes = new size_t[n];
    foreach (i; 0 .. n)
    {
        array[i] = uniform(0.0, 1000.0);
        indexes[i] = uniform(0, n);
    }
    benchmarkResume();

    // The actual benchmark begins here
    foreach (i; 0 .. n)
    {
        auto balance = std.algorithm.find(array, array[indexes[i]]);
    }
}
unittest
{
    TODO writeln(benchmark!benchmark_findDouble(10_000).to!("msecs", uint));
}
----
 */
void benchmarkSuspend()
{
    theStopWatch.stop();
}

/// Ditto
void benchmarkResume()
{
    theStopWatch.start();
}

unittest
{
    void benchmark_findDouble(uint n)
    {
        // Fill an array of random numbers and an array of random indexes
        benchmarkSuspend();
        auto array = new double[n];
        auto indexes = new size_t[n];
        foreach (i; 0 .. n)
        {
            array[i] = uniform(0.0, 1000.0);
            indexes[i] = uniform(0, n);
        }
        benchmarkResume();

        // The actual benchmark begins here
        foreach (i; 0 .. n)
        {
            auto balance = std.algorithm.find(array, array[indexes[i]]);
        }
    }

    //writeln(benchmark!benchmark_findDouble(10_000)[0].to!("msecs",
    //uint));
    benchmarkImpl!benchmark_findDouble();
}

/++
   Aliases from $(D std.datetime).
  +/
alias std.datetime.AutoStart AutoStart;
/// ditto
alias std.datetime.StopWatch StopWatch;
/// ditto
alias std.datetime.ComparingBenchmarkResult ComparingBenchmarkResult;
/// ditto
alias std.datetime.comparingBenchmark comparingBenchmark;
/// ditto
alias std.datetime.measureTime measureTime;