Подтвердить что ты не робот

'std::option' против наследования против других способов (производительность)

Меня интересует производительность std::variant. Когда я не должен использовать это? Кажется, что виртуальные функции все еще намного лучше, чем использование std::visit, что меня удивило!

В "Путешествии по C++" Бьярн Страуструп говорит об этом pattern checking после объяснения методов std::holds_alternatives и overloaded:

Это в основном эквивалентно вызову виртуальной функции, но потенциально быстрее. Как и со всеми претензиями производительность, это потенциально быстрее должно быть проверено измерениями, когда производительность критичный. В большинстве случаев разница в производительности незначительна.

Я оценил некоторые методы, которые мне приходили в голову, и вот результаты:

benchmark http://quick-bench.com/N35RRw_IFO74ZihFbtMu4BIKCJg

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

benchmark with op enabled

http://quick-bench.com/p6KIUtRxZdHJeiFiGI8gjbOumoc

Вот код, который я использовал для тестов; Я уверен, что есть лучший способ реализовать и использовать варианты их использования вместо виртуальных ключевых слов (наследование против std::варианта):

удалил старый код; посмотрите на обновления

Может кто-нибудь объяснить, как лучше всего реализовать этот вариант использования для std::variant, который привел меня к тестированию и бенчмаркингу:

В настоящее время я реализую RFC 3986, который является 'URI', и для моего случая использования этот класс будет использоваться скорее как const и, вероятно, не будет сильно изменен, и это более вероятно для пользователя, чтобы использовать этот класс для поиска каждой конкретной части URI вместо создания URI; поэтому имело смысл использовать std::string_view, а не разделять каждый сегмент URI на свой собственный std::string. Проблема была в том, что мне нужно было реализовать два класса для него; один, когда мне нужна только константная версия; и еще один, когда пользователь хочет создать URI, а не предоставлять его и осуществлять поиск по нему.

Поэтому я использовал template, чтобы исправить то, что имело свои проблемы; но потом я понял, что могу использовать std::variant<std::string, std::string_view> (или, может быть, std::variant<CustomStructHoldingAllThePieces, std::string_view>); поэтому я начал исследовать, чтобы увидеть, действительно ли это помогает использовать варианты или нет. Исходя из этих результатов, кажется, что я использую наследование, и virtual - мой лучший выбор, если я не хочу реализовывать два разных класса const_uri и uri.

Как ты думаешь, что мне делать?

Обновление (2)

Спасибо за @gan_ за упоминание и исправление проблемы с подъемом в моем тестовом коде. benchmark http://quick-bench.com/Mcclomh03nu8nDCgT3T302xKnXY

Я был удивлен результатом попытки "поймать ад", но благодаря этому комментарию теперь это имеет смысл.

Обновление (3)

Я удалил метод try-catch, так как он был действительно плохим; а также случайно изменил выбранное значение, и, судя по всему, я вижу более реалистичный тест. Кажется, что virtual не правильный ответ в конце концов. random access http://quick-bench.com/o92Yrt0tmqTdcvufmIpu_fIfHt0

http://quick-bench.com/FFbe3bsIpdFsmgKfm94xGNFKVKs  (без утечки памяти)

Обновление (4)

Я удалил накладные расходы на генерацию случайных чисел (я уже делал это в последнем обновлении, но похоже, что я выбрал неправильный URL для теста производительности) и добавил EmptyRandom для понимания базового уровня генерации случайных чисел. А также сделал несколько небольших изменений в Virtual, но я не думаю, что это повлияло на что-либо. empty random added http://quick-bench.com/EmhM-S-xoA0LABYK6yrMyBb8UeI

http://quick-bench.com/5hBZprSRIRGuDaBZ_wj0cOwnNhw  (удалил виртуальный, чтобы вы могли лучше сравнить остальные из них)

Обновление (5)

как сказал Хорхе Беллон в комментариях, я не думал о стоимости размещения; поэтому я конвертировал каждый тест для использования указателей. Это косвенное влияние, конечно, влияет на производительность, но теперь оно более справедливо. Так что сейчас в циклах нет распределения.

Вот код:

удалил старый код; посмотрите на обновления

Я провел несколько тестов. Похоже, что g++ лучше оптимизирует код:

-------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations
-------------------------------------------------------------------
EmptyRandom                   0.756 ns        0.748 ns    746067433
TradeSpaceForPerformance       2.87 ns         2.86 ns    243756914
Virtual                        12.5 ns         12.4 ns     60757698
Index                          7.85 ns         7.81 ns     99243512
GetIf                          8.20 ns         8.18 ns     92393200
HoldsAlternative               7.08 ns         7.07 ns     96959764
ConstexprVisitor               11.3 ns         11.2 ns     60152725
StructVisitor                  10.7 ns         10.6 ns     60254088
Overload                       10.3 ns         10.3 ns     58591608

И для лязга:

-------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations
-------------------------------------------------------------------
EmptyRandom                    1.99 ns         1.99 ns    310094223
TradeSpaceForPerformance       8.82 ns         8.79 ns     87695977
Virtual                        12.9 ns         12.8 ns     51913962
Index                          13.9 ns         13.8 ns     52987698
GetIf                          15.1 ns         15.0 ns     48578587
HoldsAlternative               13.1 ns         13.1 ns     51711783
ConstexprVisitor               13.8 ns         13.8 ns     49120024
StructVisitor                  14.5 ns         14.5 ns     52679532
Overload                       17.1 ns         17.1 ns     42553366

В данный момент для clang лучше использовать виртуальное наследование, но для g++ лучше использовать holds_alternative или get_if, но в целом std::visit кажется не лучшим выбором почти для всех моих до сих пор.

Я думаю, что будет хорошей идеей, если в C++ будет добавлено сопоставление с образцом (операторы переключателей, способные проверять больше, чем просто целочисленные литералы), мы будем писать более чистый и более понятный код.

Я задаюсь вопросом о результатах package.index(). Разве это не должно быть быстрее? что это делает?

Версия Clang: http://quick-bench.com/cl0HFmUes2GCSE1w04qt4Rqj6aI

Версия, которая использует One one вместо auto one = new One на основе комментария Максима Егорушкина: http://quick-bench.com/KAeT00__i2zbmpmUHDutAfiD6-Q (мало что меняет результат)

Обновление (6)

Я внес некоторые изменения, и теперь результаты сильно отличаются от компилятора к компилятору. Но кажется, что std::get_if и std::holds_alternatives являются лучшими решениями. virtual, кажется, работает лучше всего по неизвестным причинам с Clang сейчас. Это действительно удивляет меня, потому что я помню, что virtual был лучше в gcc. А также std::visit полностью вне конкуренции; в этом последнем тесте это даже хуже, чем поиск в vtable.

Вот эталонный тест (запустите его с GCC/Clang, а также с libstd C++ и lib C++):

http://quick-bench.com/LhdP-9y6CqwGxB-WtDlbG27o_5Y

#include <benchmark/benchmark.h>

#include <array>
#include <variant>
#include <random>
#include <functional>
#include <algorithm>

using namespace std;

struct One {
  auto get () const { return 1; }
 };
struct Two {
  auto get() const { return 2; }
 };
struct Three { 
  auto get() const { return 3; }
};
struct Four {
  auto get() const { return 4; }
 };

template<class... Ts> struct overload : Ts... { using Ts::operator()...; };
template<class... Ts> overload(Ts...) -> overload<Ts...>;


std::random_device dev;
std::mt19937 rng(dev());
std::uniform_int_distribution<std::mt19937::result_type> random_pick(0,3); // distribution in range [1, 6]

template <std::size_t N>
std::array<int, N> get_random_array() {
  std::array<int, N> item;
  for (int i = 0 ; i < N; i++)
    item[i] = random_pick(rng);
  return item;
}

template <typename T, std::size_t N>
std::array<T, N> get_random_objects(std::function<T(decltype(random_pick(rng)))> func) {
    std::array<T, N> a;
    std::generate(a.begin(), a.end(), [&] {
        return func(random_pick(rng));
    });
    return a;
}


static void TradeSpaceForPerformance(benchmark::State& state) {
    One one;
    Two two;
    Three three;
    Four four;

  int index = 0;

  auto ran_arr = get_random_array<50>();
  int r = 0;

  auto pick_randomly = [&] () {
    index = ran_arr[r++ % ran_arr.size()];
  };

  pick_randomly();


  for (auto _ : state) {

    int res;
    switch (index) {
      case 0:
        res = one.get();
        break;
      case 1:
        res = two.get();
        break;
      case 2:
        res = three.get();
        break;
      case 3:
        res = four.get();
        break;
    }

    benchmark::DoNotOptimize(index);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }


}
// Register the function as a benchmark
BENCHMARK(TradeSpaceForPerformance);


static void Virtual(benchmark::State& state) {

  struct Base {
    virtual int get() const noexcept = 0;
    virtual ~Base() {}
  };

  struct A final: public Base {
    int get()  const noexcept override { return 1; }
  };

  struct B final : public Base {
    int get() const noexcept override { return 2; }
  };

  struct C final : public Base {
    int get() const noexcept override { return 3; }
  };

  struct D final : public Base {
    int get() const noexcept override { return 4; }
  };

  Base* package = nullptr;
  int r = 0;
  auto packages = get_random_objects<Base*, 50>([&] (auto r) -> Base* {
          switch(r) {
              case 0: return new A;
              case 1: return new B;
              case 3: return new C;
              case 4: return new D;
              default: return new C;
          }
    });

  auto pick_randomly = [&] () {
    package = packages[r++ % packages.size()];
  };

  pick_randomly();

  for (auto _ : state) {

    int res = package->get();

    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }


  for (auto &i : packages)
    delete i;

}
BENCHMARK(Virtual);




static void FunctionPointerList(benchmark::State& state) {

    One one;
    Two two;
    Three three;
    Four four;
  using type = std::function<int()>;
  std::size_t index;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
        case 0: return std::bind(&One::get, one);
        case 1: return std::bind(&Two::get, two);
        case 2: return std::bind(&Three::get, three);
        case 3: return std::bind(&Four::get, four);
        default: return std::bind(&Three::get, three);
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    index = r++ % packages.size();
  };


  pick_randomly();

  for (auto _ : state) {

    int res = packages[index]();

    benchmark::DoNotOptimize(index);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }

}
BENCHMARK(FunctionPointerList);



static void Index(benchmark::State& state) {

    One one;
    Two two;
    Three three;
    Four four;
  using type = std::variant<One, Two, Three, Four>;
  type* package = nullptr;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
            case 0: return one;
            case 1: return two;
            case 2: return three;
            case 3: return four;
            default: return three;
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    package = &packages[r++ % packages.size()];
  };


  pick_randomly();

  for (auto _ : state) {

    int res;
    switch (package->index()) {
      case 0: 
        res = std::get<One>(*package).get();
        break;
      case 1:
        res = std::get<Two>(*package).get();
        break;
      case 2:
        res = std::get<Three>(*package).get();
        break;
      case 3:
        res = std::get<Four>(*package).get();
        break;
    }

    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }

}
BENCHMARK(Index);



static void GetIf(benchmark::State& state) {
    One one;
    Two two;
    Three three;
    Four four;
  using type = std::variant<One, Two, Three, Four>;
  type* package = nullptr;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
            case 0: return one;
            case 1: return two;
            case 2: return three;
            case 3: return four;
            default: return three;
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    package = &packages[r++ % packages.size()];
  };

  pick_randomly();

  for (auto _ : state) {

    int res;
    if (auto item = std::get_if<One>(package)) {
      res = item->get();
    } else if (auto item = std::get_if<Two>(package)) {
      res = item->get();
    } else if (auto item = std::get_if<Three>(package)) {
      res = item->get();
    } else if (auto item = std::get_if<Four>(package)) {
      res = item->get();
    }

    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }


}
BENCHMARK(GetIf);

static void HoldsAlternative(benchmark::State& state) {
    One one;
    Two two;
    Three three;
    Four four;
  using type = std::variant<One, Two, Three, Four>;
  type* package = nullptr;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
            case 0: return one;
            case 1: return two;
            case 2: return three;
            case 3: return four;
            default: return three;
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    package = &packages[r++ % packages.size()];
  };

  pick_randomly();

  for (auto _ : state) {

    int res;
    if (std::holds_alternative<One>(*package)) {
      res = std::get<One>(*package).get();
    } else if (std::holds_alternative<Two>(*package)) {
      res = std::get<Two>(*package).get();
    } else if (std::holds_alternative<Three>(*package)) {
      res = std::get<Three>(*package).get();
    } else if (std::holds_alternative<Four>(*package)) {
      res = std::get<Four>(*package).get();
    }

    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }

}
BENCHMARK(HoldsAlternative);


static void ConstexprVisitor(benchmark::State& state) {

    One one;
    Two two;
    Three three;
    Four four;
  using type = std::variant<One, Two, Three, Four>;
  type* package = nullptr;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
            case 0: return one;
            case 1: return two;
            case 2: return three;
            case 3: return four;
            default: return three;
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    package = &packages[r++ % packages.size()];
  };

  pick_randomly();

  auto func = [] (auto const& ref) {
        using type = std::decay_t<decltype(ref)>;
        if constexpr (std::is_same<type, One>::value) {
            return ref.get();
        } else if constexpr (std::is_same<type, Two>::value) {
            return ref.get();
        } else if constexpr (std::is_same<type, Three>::value)  {
          return ref.get();
        } else if constexpr (std::is_same<type, Four>::value) {
            return ref.get();
        } else {
          return 0;
        }
    };

  for (auto _ : state) {

    auto res = std::visit(func, *package);

    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }

}
BENCHMARK(ConstexprVisitor);

static void StructVisitor(benchmark::State& state) {



  struct VisitPackage
  {
      auto operator()(One const& r) { return r.get(); }
      auto operator()(Two const& r) { return r.get(); }
      auto operator()(Three const& r) { return r.get(); }
      auto operator()(Four const& r) { return r.get(); }
  };

    One one;
    Two two;
    Three three;
    Four four;
  using type = std::variant<One, Two, Three, Four>;
  type* package = nullptr;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
            case 0: return one;
            case 1: return two;
            case 2: return three;
            case 3: return four;
            default: return three;
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    package = &packages[r++ % packages.size()];
  };

  pick_randomly();

  auto vs = VisitPackage();

  for (auto _ : state) {

    auto res = std::visit(vs, *package);

    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }

}
BENCHMARK(StructVisitor);


static void Overload(benchmark::State& state) {


    One one;
    Two two;
    Three three;
    Four four;
  using type = std::variant<One, Two, Three, Four>;
  type* package = nullptr;

  auto packages = get_random_objects<type, 50>([&] (auto r) -> type {
        switch(r) {
            case 0: return one;
            case 1: return two;
            case 2: return three;
            case 3: return four;
            default: return three;
        }
    });
  int r = 0;

  auto pick_randomly = [&] () {
    package = &packages[r++ % packages.size()];
  };

  pick_randomly();

  auto ov = overload {
      [] (One const& r) { return r.get(); },
      [] (Two const& r) { return r.get(); },
      [] (Three const& r) { return r.get(); },
      [] (Four const& r) { return r.get(); }
    };

  for (auto _ : state) {

    auto res = std::visit(ov, *package);


    benchmark::DoNotOptimize(package);
    benchmark::DoNotOptimize(res);

    pick_randomly();
  }

}
BENCHMARK(Overload);


// BENCHMARK_MAIN();

Результаты для компилятора GCC:

-------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations
-------------------------------------------------------------------
TradeSpaceForPerformance       3.71 ns         3.61 ns    170515835
Virtual                       12.20 ns        12.10 ns     55911685
FunctionPointerList           13.00 ns        12.90 ns     50763964
Index                          7.40 ns         7.38 ns    136228156
GetIf                          4.04 ns         4.02 ns    205214632
HoldsAlternative               3.74 ns         3.73 ns    200278724
ConstexprVisitor              12.50 ns        12.40 ns     56373704
StructVisitor                 12.00 ns        12.00 ns     60866510
Overload                      13.20 ns        13.20 ns     56128558

Результаты для компилятора clang (что меня удивляет):

-------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations
-------------------------------------------------------------------
TradeSpaceForPerformance       8.07 ns         7.99 ns     77530258
Virtual                        7.80 ns         7.77 ns     77301370
FunctionPointerList            12.1 ns         12.1 ns     56363372
Index                          11.1 ns         11.1 ns     69582297
GetIf                          10.4 ns         10.4 ns     80923874
HoldsAlternative               9.98 ns         9.96 ns     71313572
ConstexprVisitor               11.4 ns         11.3 ns     63267967
StructVisitor                  10.8 ns         10.7 ns     65477522
Overload                       11.4 ns         11.4 ns     64880956

Лучший бенчмарк на данный момент (будет обновляться): http://quick-bench.com/LhdP-9y6CqwGxB-WtDlbG27o_5Y (также ознакомьтесь с GCC)

4b9b3361

ОТВЕТЫ

Ответ 1

std::visit, похоже, еще не имеет некоторых оптимизаций в некоторых реализациях. Тем не менее, есть центральный момент, который не очень хорошо виден в этой лабораторной установке - то, что дизайн на основе variant основан на стеке, а не на виртуальном паттерне inheritance, который естественным образом будет стремиться к тому, чтобы основываться на куче. В реальном сценарии это означает, что компоновка памяти вполне может быть фрагментирована (возможно, со временем - после того, как объекты выйдут из кэша и т.д.) - если этого как-то не избежать. Противоположностью является проект на основе variant, который может быть размещен в постоянной памяти. Я считаю, что это чрезвычайно важный момент, который следует учитывать применительно к производительности, который нельзя недооценивать.

Чтобы проиллюстрировать это, рассмотрим следующее:

std::vector<Base*> runtime_poly_;//risk of fragmentation

против

std::vector<my_var_type> cp_time_poly_;//no fragmentation (but padding 'risk')

Эту фрагментацию сложно встроить в такой тест, как этот. Если это (также) в контексте заявления Бьярне, мне неясно, когда он сказал, что это могло бы потенциально быстрее (что я действительно верю).

Еще одна очень важная вещь, которую следует помнить при проектировании на основе std::variant, это то, что размер каждого элемента использует размер максимально возможного элемента. Поэтому, если объекты не имеют примерно одинаковый размер, это следует тщательно рассмотреть, так как это может плохо повлиять на кеш.

Рассматривая эти пункты вместе, трудно сказать, какой из них лучше всего использовать в общем случае - однако должно быть достаточно ясно, если набор является "маленьким" закрытым с примерно одинаковым размером - тогда вариантный стиль демонстрирует большой потенциал для ускорения. (как отмечает Бьярне).

Сейчас мы рассматривали только производительность, и есть действительно другие причины для выбора того или иного шаблона: в конце концов, вам нужно вывести комфорт из "лаборатории", разработать дизайн и сравнить ваши реальные варианты использования.