ベンチマーク

bench.d

// いろいろ残念な感じ

import std.datetime : StopWatch, TickDuration;

struct Performance(T)
{
    size_t executions;
    double second;
    T result;
    this (TickDuration td, size_t executions, T result)
    {
        this.executions = executions;
        this.second = td.to!("seconds", double) / executions;
        this.result = result;
    }
    string toString()
    {
        return 
            second.to!string() ~ " seconds in average of "
            ~ executions.to!string() ~ " times of execution";
    }
}


// func は size_t[] を 2 つ受け取って 1 つ返す関数。
// かかっている時間が deadline より短い時は回数を 2 倍にして計測しやすいようにする。
Performance!(size_t[]) multiplication_performance(alias func)(size_t[] lhs, size_t[] rhs, TickDuration deadline)
{
    StopWatch sw;
    size_t n = 1;
    while (true)
    {
        sw.reset();
        sw.start();
        size_t[] result = func(lhs, rhs);
        foreach (i; 1..n)
        {
            func(lhs, rhs);
        }
        sw.stop();
        if (deadline < sw.peek() || n == 1048576)
        {
            return Performance!(size_t[])(sw.peek(), n, result);
        }
        n <<= 1;
    }
}


// 乗算関数 karamul のパフォーマンスを測定
void multiplication_performances()
{
    StopWatch sw;
    auto deadline = TickDuration(TickDuration.ticksPerSec * 10);
    foreach (l; [
        1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96,
        128, 160, 200, 256, 320, 400, 512, 640, 800,
        1024, 1280, 1600, 2048, 2560, 3200, 4096, 5120, 6400, 8192, 10240, 12800, 16384
    ])
    {
        auto
            lhs = random_polynomial(l),
            rhs = random_polynomial(l);
        Performance!(size_t[]) perf;
        writefln("calculating 32*%d-terms multiplication", l);
        perf = multiplication_performance!karamul(lhs, rhs, deadline);
        perf.writeln(" by karatsuba");
        check(lhs, "*k", rhs, lhs.mul(rhs), perf.result); // ナイーブな乗算 (mul) と結果を比較
    }
}

import std.random : uniform;
//import std.datetime : Clock;

size_t[] random_polynomial(size_t length)
{
    size_t[] ret;
    ret.length = length;
    foreach (i; 0..length)
    {
        ret[i] = uniform(1, size_t.max);
    }
    return ret;
}