c++ - `std::variant` vs. inheritance vs. other ways (performance)

Question

I'm wondering about std::variant performance. When should I not use it? It seems like virtual functions are still much better than using std::visit which surprised me!

In "A Tour of C++" Bjarne Stroustrup says this about pattern checking after explaining std::holds_alternatives and the overloaded methods:

This is basically equivalent to a virtual function call, but potentially faster. As with all claims of performance, this ‘‘potentially faster’’ should be verified by measurements when performance is critical. For most uses, the difference in performance is insignificant.

I've benchmark some methods that came in my mind and these are the results:

http://quick-bench.com/N35RRw_IFO74ZihFbtMu4BIKCJg

You'll get a different result if you turn on the optimization:

http://quick-bench.com/p6KIUtRxZdHJeiFiGI8gjbOumoc

Here's the code I've used for benchmarks; I'm sure there's better way to implement and use variants for using them instead of virtual keywords (inheritance vs. std::variant):

removed the old code; look at the updates

Can anyone explain what is the best way to implement this use case for std::variant that got me to testing and benchmarking:

I'm currently implementing RFC 3986 which is 'URI' and for my use case this class will be used more as a const and probably won't be changed a lot and it's more likely for the user to use this class to find each specific portion of the URI rather than making a URI; so it made sense to make use of std::string_view and not separating each segment of the URI in its own std::string. The problem was I needed to implement two classes for it; one for when I only need a const version; and another one for when the user wants to create the URI rather than providing one and searching through it.

So I used a template to fix that which had its own problems; but then I realized I could use std::variant<std::string, std::string_view> (or maybe std::variant<CustomStructHoldingAllThePieces, std::string_view>); so I started researching to see if it actually helps to use variants or not. From these results, it seems like using inheritance and virtual is my best bet if I don't want to implement two different const_uri and uri classes.

What do you think should I do?

---

Update (2)

Thanks for @gan_ for mentioning and fixing the hoisting problem in my benchmark code. http://quick-bench.com/Mcclomh03nu8nDCgT3T302xKnXY

I was surprised with the result of try-catch hell but thanks to this comment that makes sense now.

Update (3)

I removed the try-catch method as it was really bad; and also randomly changed the selected value and by the looks of it, I see more realistic benchmark. It seems like virtual is not the correct answer after all. http://quick-bench.com/o92Yrt0tmqTdcvufmIpu_fIfHt0

http://quick-bench.com/FFbe3bsIpdFsmgKfm94xGNFKVKs (without the memory leak lol)

Update (4)

I removed the overhead of generating random numbers (I've already did that in the last update but it seems like I had grabbed the wrong URL for benchmark) and added an EmptyRandom for understanding the baseline of generating random numbers. And also made some small changes in Virtual but I don't think it affected anything. http://quick-bench.com/EmhM-S-xoA0LABYK6yrMyBb8UeI

http://quick-bench.com/5hBZprSRIRGuDaBZ_wj0cOwnNhw (removed the Virtual so you could compare the rest of them better)

---

Update (5)

as Jorge Bellon said in the comments, I wasn't thinking about the cost of allocation; so I converted every benchmark to use pointers. This indirection has an impact on performance of course but it's more fair now. So right now there's no allocation in the loops.

Here's the code:

removed the old code; look at the updates

I ran some benchmarks so far. It seems like g++ does a better job of optimizing the code:

-------------------------------------------------------------------
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

And for clang:

-------------------------------------------------------------------
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

Right now, for clang, it's better to use virtual inheritance but for g++ it's better to use holds_alternative or get_if but in overall, std::visit seems to be not a good choice for almost all of my benchmarks so far.

I'm thinking it'll be a good idea if pattern matching (switch statements capable of checking more stuff than just integer literals) would be added to the c++, we would be writing cleaner and more maintainable code.

I'm wondering about the package.index() results. Shouldn't it be faster? what does it do?

Clang version: http://quick-bench.com/cl0HFmUes2GCSE1w04qt4Rqj6aI

The version that uses One one instead of auto one = new One based on Maxim Egorushkin's comment: http://quick-bench.com/KAeT00__i2zbmpmUHDutAfiD6-Q (not changing the outcome much)

---

Update (6)

I made some changes and the results are very different from compiler to compiler now. But it seems like std::get_if and std::holds_alternatives are the best solutions. virtual seems to work best for unknown reasons with clang now. That really surprises me there because I remember virtual being better in gcc. And also std::visit is totally out of competition; in this last benchmark it's even worse than vtable lookup.

Here's the benchmark (run it with GCC/Clang and also with libstdc++ and libc++):

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 {
    

Answer 1

std::visit seems to lack some optimizations yet on some implementations. That being said there's a central point thats not very well seen in this lab-like setup - which is that variant based design is stack based vs. the virtual inheritance pattern which will naturally gravitate towards being heap based. In a real world scenario this means the memory layout could very well be fragmented (perhaps over time - once objects leave the cache, etc.) - unless it can somehow be avoided. The opposite is the variant based design that can be layout in contigoues memory. I believe this is an extremely important point to consider when performance is concerned that cannot be underestimated.

To illustrate this, consider the following:

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

vs.

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

This fragmentation is somewhat difficult to built into a benchmark test like this one. If this is (also) within the context of bjarne's statement is not clear to me when he said it could potentially be faster (which I do believe holds true).

Another very important thing to remember for the std::variant based design is that the size of each element uses up the size of the largest possible element. Therefore if objects do not have roughly the same size this has to be considered carefully since it may have a bad impact on the cache as a result.

Considering these points together it's hard to say which is best to use in the general case - however it should be clear enough if the set is a closed 'smallish' one of roughtly the same size - then the variant style shows great potential for being faster (as bjarne notes).

We now only considered performance and there are indeed other reasons for choosing one or the other pattern: In the end, you just have to get out the comfort of the 'lab' and design and benchmark your real world use cases.