Сравниваем производительности оператора<
#опытным

В этом посте я рассказал об отличном способе лексикографического сравнения набора объектов с помощью std::tie. Однако в комментариях несколько подписчиков задались вопросом, а не будет ли использование std::tie сильно ударять по производительности? Настоящих плюсовиков всегда на подкорке волнует вопрос оверхеда используемых инструментов. Поэтому сегодня мы выясним, есть ли разница в более менее практических вычислениях между разными вариантами оператора< .

Большое спасибо, @SoulslikeEnjoyer, за представление основного объема кода.

Сравним 4 реализации operator<:

struct Time_comparison_unreadable {
  int hours;
  int minutes;
  int seconds;

  bool operator<(const Time_comparison_unreadable& other) {
    if ((hours < other.hours) || (hours == other.hours && minutes < other.minutes) || (hours == other.hours && minutes == other.minutes && seconds < other.seconds))
      return true;
    else
      return false;
  }
};

struct Time_comparison_readable {
// fields
  bool operator<(const Time_comparison_readable& other) {
    if (hours < other.hours) return true;
    if (hours > other.hours) return false;
    if (minutes < other.minutes) return true;
    if (minutes > other.minutes) return false;
    if (seconds < other.seconds) return true;
    return false;
  }
};

struct Time_tie {
// fields
  bool operator<(const Time_tie& other) {
    return std::tie(hours, minutes, seconds) < std::tie(other.hours, other.minutes, other.seconds);
  }
};

struct Time_spaceship {
// fields
  auto operator<=>(const Time_spaceship &) const = default;
};

Первые 2 варианта - это обычные реализации лексикографического оператора сравнения, просто второй из них более читаемый. В структуре Time_tie мы используем std::tie для формирования тупла и используем оператор сравнения тупла. В последнем варианте используем дефолтно-сгенерированный spaceship оператор.

Для того, чтобы качественно сравнить время выполнения чего-либо aka провести перфоманс тесты, нам поможет фреймфорк google benchmark. Она предоставляет гибкие инструменты для управления запуском кода и измерением времени его работы. Не будем вдаваться в детали фреймворка, а сразу посмотрим код:

std::random_device dev;
std::mt19937 rng(dev());
std::uniform_int_distribution<int> dist(1,100);

template <typename TimeClass>
static void time_comparison_experiment(benchmark::State& state) {
  std::vector<TimeClass> v(1'000'000);
  std::generate(v.begin(), v.end(), [&] () -> TimeClass { return TimeClass{ dist(rng) % 24, dist(rng) % 60, dist(rng) % 60 }; });
  while (state.KeepRunning()) {
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(v.begin(), v.end());
    auto end = std::chrono::high_resolution_clock::now();
    
    auto elapsed_seconds =
    std::chrono::duration_cast<std::chrono::duration<double>>(
    end - start);
    state.SetIterationTime(elapsed_seconds.count());
    std::shuffle(v.begin(), v.end(), rng);
  }
}

BENCHMARK(time_comparison_experiment<Time_comparison_unreadable>)->UseManualTime()->Iterations(20);

BENCHMARK(time_comparison_experiment<Time_comparison_readable>)->UseManualTime()->Iterations(20);

BENCHMARK(time_comparison_experiment<Time_tie>)->UseManualTime()->Iterations(20);

BENCHMARK(time_comparison_experiment<Time_spaceship>)->UseManualTime()->Iterations(20);

Все просто: создаем вектор, наполняем его объектами с рандомным временем, в цикле производим сортировку как операцию, обильно использующую сравнение, и шаффлим элементы вектора перед каждой новой итерацией цикла. Сравнивать нам нужно только время выполнения самой операции сортировки и gbenchmark предоставляет возможность пользователю самому измерять только те операции, которые имеет смысл сравнивать.

В конце мы запускаем бенчмарк над функцией с измерением времени выполнения, говорим ему, что мы сами будет мерять время(UseManualTime), и сколько итераций цикла нужно выполнить(Iterations(20)).

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

Compare things. Stay cool.

#performance #cpp20