7
\$\begingroup\$

The purpose of the code is to simplify benchmarking of arbitrary functions. The reason I want to benchmark things is that I would like to get a "feeling" of performance. Although the framework leans on synthetic benchmarks, I think it is a good starting point.

After trying to write a benchmarking framework a few times (1, 2) I've decided to nail down the model that I would like to use. Full code with dependencies can be found on this commit.

benchmark_v2:

#ifndef AREA51_BENCHMARK_V2_HPP
#define AREA51_BENCHMARK_V2_HPP

#include "algorithm.hpp"
#include "transform_iterator.hpp"
#include "utilities.hpp"

#include <tuple>
#include <array>
#include <chrono>
#include <utility>
#include <vector>
#include <fstream>
#include <string>
#include <stdexcept>

namespace shino
{
    template<typename Generator, typename ... Callables>
    class benchmark
    {
        Generator gen;
        std::tuple<Callables...> callables;
        std::vector<std::array<std::chrono::duration<double>, sizeof...(Callables)>> timings;
        std::vector<typename Generator::input_type> inputs;
    public:
        using input_type = typename Generator::input_type;
        static constexpr std::size_t function_count = sizeof...(Callables);

        template<typename Gen,
                typename = shino::enable_sfinae<Gen, Generator>,
                typename ... ArgTypes>
        benchmark(Gen &&generator, ArgTypes &&... args):
                gen(std::forward<Gen>(generator)),
                callables(std::forward_as_tuple(std::forward<ArgTypes>(args)...))
        {}

        template<typename Gen,
                typename = shino::enable_sfinae<Gen, Generator>,
                typename Tuple>
        benchmark(Gen &&generator, Tuple &&tup):
                gen(std::forward<Gen>(generator)),
                callables(std::forward<Tuple>(tup))
        {}

        template<typename InputType,
                typename = enable_sfinae<InputType, input_type>>
        void time(InputType &&input,
                  std::size_t runcount)
        {
            inputs.push_back(input);
            time_all(std::make_index_sequence<sizeof...(Callables)>{},
                     std::forward<InputType>(input), runcount);
        }

        template<typename OutputIterator,
                typename Unit = std::chrono::milliseconds>
        void get_as(OutputIterator first)
        {
            auto converter = [](const auto &readings) {
                std::array<Unit, function_count> converted_readings;
                std::transform(readings.begin(),
                               readings.end(),
                               converted_readings.begin(),
                               [](const auto &reading) {
                                   return std::chrono::duration_cast<Unit>(reading);
                               }
                );
            };

            auto converting_iterator = shino::transformer(converter, first);
            std::copy(timings.begin(), timings.end(), converting_iterator);
        }

        template<typename Unit = std::chrono::milliseconds>
        auto get_as()
        {
            std::vector<std::array<Unit, function_count>> converted_readings(timings.size());

            get_as<Unit>(converted_readings.begin());
            return converted_readings;
        }

        template <typename Unit = std::chrono::milliseconds>
        void save_as(const std::string& metafilename,
                     const std::array<std::string, function_count>& filenames,
                     const std::string& xlabel = "Data size",
                     const std::string& ylabel = "Time")
        {
            std::ofstream metafile(metafilename);
            if (!metafile.is_open())
            {
                throw std::runtime_error("Couldn't create meta file");
            }

            metafile << xlabel << '\n';
            metafile << ylabel << '\n';

            for (const auto& filename : filenames)
            {
                metafile << filename << '\n';
            }

            if (!metafile.good())
            {
                //might be useful to check if the file was overridden
                throw std::runtime_error("Couldn't write everything to meta file, but opened it.");
            }

            for (std::size_t filenames_index = 0; filenames_index < filenames.size(); ++filenames_index)
            {
                const auto& filename = filenames[filenames_index];
                std::ofstream file(filename);

                if (!file.is_open())
                {
                    throw std::runtime_error("couldn't open one of the benchmark results file");
                }

                auto benchmark_name = filename;
                strip_directory(benchmark_name);
                strip_file_extension(benchmark_name);

                file << benchmark_name << '\n';

                for (std::size_t timings_index = 0; timings_index < timings.size(); ++timings_index)
                {
                    file << inputs[timings_index] << ' '
                         << std::chrono::duration_cast<Unit>(timings[timings_index][filenames_index]).count() << '\n';
                }

                if (!file.good())
                {
                    throw std::runtime_error("Could complete writing of " + filename);
                }
            }
        }

    private:
        void strip_file_extension(std::string& filename)
        {
            auto dot_location = shino::find_last_of(filename, '.');
            if (dot_location != std::string::npos)
            {
                filename.erase(dot_location);
            }
        }

        void strip_directory(std::string& filename)
        {
            auto last_slash_location = shino::find_last_of(filename, '/');
            if (last_slash_location != std::string::npos)
            {
                filename.erase(0, last_slash_location + 1);
            }
        }

        template<std::size_t Index, typename InputType,
                typename = enable_sfinae<InputType, input_type>>
        auto time_one(InputType &&input,
                      std::size_t runcount)
        {
            std::chrono::duration<double> timing(0);

            for (std::size_t i = 0; i < runcount; ++i)
            {
                auto callable_input = gen(input); //separate input creation from benchmark
                auto start = std::chrono::high_resolution_clock::now();
                std::apply(std::get<Index>(callables), callable_input);
                auto end = std::chrono::high_resolution_clock::now();
                timing += end - start;
            }

            return timing / runcount;
        }

        template<std::size_t ... Indices,
                typename InputType,
                typename = shino::enable_sfinae<InputType, input_type>>
        void time_all(std::index_sequence<Indices...>,
                      InputType &&input,
                      std::size_t runcount)
        {
            std::array<std::chrono::duration<double>, sizeof...(Callables)> a_run =
                    {time_one<Indices>(std::forward<InputType>(input), runcount)...};
            timings.push_back(a_run);
        }
    };

    template<typename Gen, typename ... Callables>
    auto benchmarker(Gen &&generator, Callables&& ... callables)
    {
        return benchmark<std::decay_t<Gen>,
                std::decay_t<Callables>...>{std::forward<Gen>(generator),
                                            std::forward_as_tuple(std::forward<Callables>(callables)...)};
    }
}

#endif //AREA51_BENCHMARK_V2_HPP

Model:

The model uses an Input Generator, restricted Callables which are the functions that are to be benchmarked. The motivation is that all of the functions has to be supplied with the same data. Currently it uses the same Input Generator, so the consistency of the input generated is the duty of the generator.

Constraints:

  • Generator has to provide input_type type alias or typedef, otherwise it won't be possible to relate the timing of the function to the input which caused it. It also has to be copy or move constructible. operator()() has to return std::tuple<> even if it is only one value. The cause stems from std::apply() not being able to compile with non tuple types.

  • Callables have to be copy or move constructible Callables.

On top of that, the following code should be well defined:

auto callable_input = generator(input);
std::apply(callable, callable_input);

i.e. function should be callable by unpacking input produced from Generator.

time:

Timing of functions are performed by always copying and passing the input generated by Generator. The motivation for always copying is that some algorithms (for example, sorting) will have advantage if the input is already sorted. runcount will specify how many times each of the callables will be run with the same input. The result is then averaged and added to the timings vector.

save_as:

This is an anomaly of the class and probably leads to a god object, but I thought that it is ok to leave it as part of the benchmark. It performs the following:

  • Creates metadata file with the given file name, and writes inside the following: x label, y label, names for the files that will contain results for each of the callables.

  • For each file name in the array (note that the size of array matches the number of callables registered), it creates the file with the specified name, and writes inside the following: strips off file extension and directory path from the file name and uses it as benchmark name, lines with x and y pairs, which are input and timing on that input respectively. Casts the time to the appropriate units if needed.

get_as:

This one simply writes all of the timings into the specified sequence. The no-argument overload returns a vector of them.

Format of the output:

The reason I chose the format is that it is pretty easy to parse using a python script which will plot graphs for me.

Example:

I've used code in this post

#include "../area51/random_engine.hpp"
#include "../area51/benchmark_v2.hpp"

#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <random>

template<typename It>
It partition(It begin, It end, It pivot)
{
    std::swap(*begin, *pivot);
    pivot = begin;
    It i{ begin }, j = std::next(begin, 1);
    for(;j != end; j++)
    {
        if(*j < *pivot)
            std::swap(*j, *++i);
    }
    std::swap(*pivot, *i);
    return i;
}

template<typename It>
void quick_sort(It begin, It end)
{
    if (std::distance(begin, end) == 0)
        return;
    It pivot{ begin };
    It elementAtCorrectPosition = partition(begin, end, pivot);
    quick_sort(begin, elementAtCorrectPosition);
    quick_sort(std::next(elementAtCorrectPosition, 1), end);
}

class generator
{
    shino::random_int_generator<int, std::mt19937_64> gen;
public:
    using input_type = std::size_t;

    std::tuple<std::vector<int>> operator()(input_type size)
    {
        static std::vector<int> v;
        if (v.size() == size)
        {
            return v;

        }
        v.resize(size);
        gen(v.begin(), v.end());

        return v;
    }
};

int main()
{
    auto standard_sort = [](std::vector<int>& v)
    {
        std::sort(v.begin(), v.end());
    };
    auto user_quicksort = [](std::vector<int>& v)
    {
        quick_sort(v.begin(), v.end());
    };

    auto bench = shino::benchmarker(generator{}, standard_sort, user_quicksort);

    for (std::size_t i = 100; i <= 100'000; i += 100)
    {
        bench.time(i, 5);
    }

    std::string dir = "../benchmarks/";
    bench.save_as<std::chrono::microseconds>(dir + "benchmarks.txt",
                  {dir + "standard sort timings.txt", dir + "quicksort timings.txt"},
                  "Array size", "Milliseconds");
}

But the results were pretty weird.

enter image description here

I'm interested in any comments and suggestions, but would prefer the ones that would allow restricting environmental and compiler effects on the benchmarking code.

\$\endgroup\$
  • \$\begingroup\$ I've setup a repository for the example, but I'm afraid CMake file will not work for anyone except me, since it has some system specific flags. If you really want to run the benchmark yourself, you will need to modify the cmake file first. \$\endgroup\$ – Incomputable Mar 17 '17 at 20:34
3
\$\begingroup\$

After using it in some setups, I believe I found most of the strengths and weaknesses.

Strengths:

  • Great model. No matter in which situations I couldn't use it, those situations didn't make sense from correct benchmarking point of view (e.g. not "apples to apples comparison").

  • Nice decoupling of output format and presentation format. Programmers can use modules such as matplotlib.pyplot to draw beautiful plots. Although some more decoupling wouldn't hurt, for casual use it is fine.

  • Flexibility. I would say that it is possible to adhere public interface in any situation, although some edge cases might get extreme obfuscation.

  • Easy to use correctly, hard to use incorrectly.

Weaknesses:

  • Too generic. Even simple usage requires a lot of code. The best cure for illness would be writing some default generators.

  • Lacks a lot of functionality, though it might be due to immaturity (both me and the library).

  • Benchmarker doesn't try to save results by any possible means. Say there is a benchmark running for a few hours, and programmer forgot to create a folder(s) or the path has high restrictions. What will happen is the program will just crash and the results will be lost. The benchmarker has to give its life to preserve the results in any way possible. Also, it would be great if user could stop the benchmark if it takes too long, and ask using some onscreen text on what to do next.

  • God object. Or at least going to become so.

The library has a chance to become a google benchmark killer. But it is a long road to get there. Also, the timings_session should stay there to get single shot benchmarks.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.