Блог

Главная - Вопросы по программированию - Тест Google: Одна И Та Же Функция, Разные Данные

Тест Google: Одна И Та Же Функция, Разные Данные

#c #microbenchmark #google-benchmark

Вопрос:

Недавно я играл с платформой Google benchmark и хочу измерить время, затраченное функцией на данные с различными статистическими свойствами.

Для краткости давайте рассмотрим самый простой из возможных примеров: вычислите сумму нечетных элементов в векторе:

 #include <benchmark/benchmark.h>

#include <cstddef>
#include <limits>
#include <random>
#include <vector>

namespace
{
size_t sumOfOddElements(const std::vector<size_t> amp;numbers)
{
    size_t result{};
    for (const auto amp;number : numbers)
        if (number % 2 == 1)
            result  = number;
    return resu<
}

std::vector<size_t> produceElements(size_t n, double oddProbability)
{
    std::mt19937 gen{};
    gen.seed(123);

    std::uniform_real_distribution<double> coin{ 0.0, 1.0 };
    std::uniform_int_distribution<size_t>  numbers{
        0, std::numeric_limits<size_t>::max() / 2
    };

    std::vector<size_t> elements;
    elements.reserve(n);

    for (size_t i{}; i < n;   i)
    {
        auto coinValue = coin(gen);
        auto number    = numbers(gen);

        // odd
        if (coinValue < oddProbability)
            number = number * 2 - 1;
        // even
        else
            number = number * 2;

        elements.push_back(number);
    }

    return elements;
}

constexpr size_t kN{ 2'000'000 };

const std::vector<size_t> lotsOfOddElements{ produceElements(kN, 0.9) };
const std::vector<size_t> fewOddElements{ produceElements(kN, 0.1) };

template <class... Args>
void BM_sumOfOddElements(benchmark::State amp;state, Args amp;amp;...args)
{
    for (auto _ : state)
        benchmark::DoNotOptimize(sumOfOddElements(std::forward<Args>(args)...));
}

}    // namespace

BENCHMARK_CAPTURE(BM_sumOfOddElements, fewOddElements, fewOddElements)
    ->Unit(benchmark::kMillisecond)
    ->Iterations(10);
BENCHMARK_CAPTURE(BM_sumOfOddElements, lotsOfOddElements, lotsOfOddElements)
    ->Unit(benchmark::kMillisecond)
    ->Iterations(10);

BENCHMARK_MAIN();

Несмотря на то, что функция очень проста, я ограничиваю ее запуском только 10 итераций, так как функция, которую я на самом деле хочу профилировать, стоит дорого (где-то около 10 секунд на итерацию).

Поскольку количество итераций недостаточно велико, я сталкиваюсь с разными таймингами с разным порядком контрольных показателей:

 ----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
----------------------------------------------------------------------------------------------
BM_sumOfOddElements/fewOddElements/iterations:10          1.58 ms         1.58 ms           10
BM_sumOfOddElements/lotsOfOddElements/iterations:10       1.63 ms         1.63 ms           10
 
 ----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
----------------------------------------------------------------------------------------------
BM_sumOfOddElements/lotsOfOddElements/iterations:10       1.56 ms         1.57 ms           10
BM_sumOfOddElements/fewOddElements/iterations:10          1.72 ms         1.72 ms           10

Несмотря на то, что реальная функция выполняет большую работу, я наблюдаю аналогичное поведение в своих тестах.

I suspect the problem is in branch prediction, so I have some questions regarding this:

  1. When running multiple iterations, the measured time is more stable, but we don’t actually measure the «cold start» when branch prediction is not yet that good. Is it not what google benchmark is for?
  2. How to deal with the situation above assuming that running lots of iterations is infeasible? Do we run multiple executables? What do I have to do if I want to benchmark both vectors for different kN ? Do we have two executables for different statistical distributions or do we have lots of executables for each combination of data distribution and size?
  3. Я видел, как многие люди говорили, что «микробанкетирование-это сложно», поскольку предсказатель ветвей всегда улучшается с увеличением числа итераций. Например, вот сообщение в блоге, демонстрирующее, что предсказатель ветвей не перестает улучшаться с увеличением числа итераций. В конце концов, это, конечно, приводит к очень небольшому прогрессу, но в любом случае, как мы можем даже измерить это, поскольку оно всегда становится лучше?

Спасибо за Ваше время, с нетерпением ждем любых ответов 🙂

Метки: ,