概念

多态（polymorphism），字面意思的解释是指一个 function or object 可以在不同情况下有不同的行为。多态从实现上大致分为静态多态（static polymorphism）和动态多态（dynamic polymorphism）两种。

以下三节主要参考：Polymorphism in C++ - cppdev 与 Performance of dynamic polymorphism - cppdev 两篇文章

动态多态（Dynamic Polymorphism）

动态指是真正执行的代码是在 运行时 才能确定的。实现主要依赖于 virtual function 的 overriding。

example：

class Base
{
public:
    int a;
    virtual void doSomething()
    {
        std::cout << "doSomething from Base\n";
    }
 
    virtual void doOtherThing()
    {
        std::cout << "doOtherThing from Base\n";
    }
};
 
class Derived : public Base
{
public:
    int b, c;
    void doSomething() override // override implies virtual
    {
        std::cout << "doSomething from Derived\n";
    }
};
 
std::shared_ptr<Base> b{std::make_shared<Derived>()};
b->doSomething(); // prints "doSomething from Derived"

当一个 function 被 virtual 定义时，编译器会得知这个 function 可能会在子类中被重定义，因此只能在 runtime 时才能得到正确的执行代码。那么程序如何在运行时找到正确的 function？这里就需要依赖 vtable 与 vptr 结构。

vtable 与 vptr

每个包含 virtual function 的 class 都会包含一个 vptr 用于指向一个 vtable 结构。vtable 用于存储一个 class 的所有 virtual function 的地址信息。

vtable

通过 -O0 得到的编译代码中，vtable 信息如下：

compile

具体的编译结果可见：Compiler Explorer

静态多态（Static Polymorphism）

静态多态的静态是指 object 的类型以及要调用的 function 都是在编译器就决定好的。通常实现静态多态的方式主要包括：

function overloading
operator overloading
templates

// function overloading
double do_oper(int a) // #1
{
    return a * 2;
}
 
double do_oper(double a) // #2
{
    return a * 2;
}
 
auto oper1 = do_oper(5); // #1 is called
auto oper2 = do_oper(5.0); // #2 is called

// operator overloading(already provided by compiler)
auto sum = 1 + 2; // operator+ adds the integers
auto concat = std::string{"1"} + std::string{"2"}; // operator+ concatenates the strings

auto sum_double = do_sum(1.0, 2.0); // double do_sum(double a, double b) is called
// template
template <class T>
T do_sum(T a, T b)
{
    return a + b;
}
 
auto sum_int = do_sum(1, 2); // int do_sum(int a, int b) is called

此外，使用 template 实现静态多态还有一种专门的设计方式：CRTP（curiously recurring template pattern ）其定义方式如下：

template<class Z>
class Y {};
 
class X : public Y<X> {};

通常的设计是在 base class 中，实现一个函数，将 base 强转为 T 对应的 class，调用其对应的 function

example：

#include <iostream>
 
template <class Derived>
struct Base { void name() { (static_cast<Derived*>(this))->impl(); } };
 
struct D1 : public Base<D1> { void impl() { std::cout << "D1::impl()\n"; } };
struct D2 : public Base<D2> { void impl() { std::cout << "D2::impl()\n"; } };
 
int main()
{
    Base<D1> b1; b1.name();
    Base<D2> b2; b2.name();
 
    D1 d1; d1.name();
    D2 d2; d2.name();
}

// output:
D1::impl()
D2::impl()
D1::impl()
D2::impl()

动态多态的性能问题

运行时才能确定真正执行的函数，会带来以下问题：

额外的存储空间（vptr）
额外的重定向 (pointer dereference)
无法 inline 化
cache miss

额外的存储空间与重定向

相比 native 的函数调用，多了一步查表操作例子：https://quick-bench.com/q/E9ZRucuYA6zh7lHeN3wsyGNWUvo 因此，对于不会被用作 base 的 class，不要为其定义 virtual functions，尤其是 virtual deconstructor：Effective C++：Item 7

无法 inline 化

当 virtual function 需要通过 vptr 来调用时，compiler 无法对其进行 inline 优化

class Base
{
public:
    virtual bool doSomething() { return true; }
};
 
class Derived : public Base
{
    bool doSomething() override { return false; }
};
 
Base b;
b.doSomething(); // this can be inlined
 
Base* b1 = new Derived;
b1->doSomething(); // this cannot
delete b1;

cache miss

使用 virtual function 带来的 cache miss 会远大于使用 template 的情况

example:

static void DynamicPolymorphism() {
  std::vector<BaseDP*> ptrs;
  for (int i = 0; i < 5000; i++)
  {
    ptrs.push_back(new DerivedDP);
  }

  // profiling
  for (const auto& ptr : ptrs)
    ptr->process();
  // Make sure the variable is not optimized away by compiler
  // benchmark::DoNotOptimize(created_string);

  for (auto& ptr : ptrs)
    delete ptr;
}

static void StaticPolymorphism() {
  std::vector<BaseSP<DerivedSP>*> ptrs;
  for (int i = 0; i < 5000; i++)
  {
    ptrs.push_back(new BaseSP<DerivedSP>);
  }

  // profilling
  for (const auto& ptr : ptrs)
    ptr->process();

  for (auto& ptr : ptrs)
    delete ptr;
}

使用 cachegrind 和 qcachegrind（mac 上，linux 是 kcachegrind）查看 cache 命中情况： qcache

其他替代 virtual function 的方法

基于 std::variant

std::variant 是 c++17 引入的类型安全的 union 结构。一个 std::variant 实例只能是其定义的一种类型，极少可能会达到 no value 的状态 ([std::variant::valueless_by_exception](https://en.cppreference.com/w/cpp/utility/variant/valueless_by_exception)) 。

用 std::variant 实现多态，需要基于一种 visitor 设计模式，即定义好所有的类型，对每个类型编写对应的 function 实现，在实际调用时基于 variant 的 value 类型选择要执行的 function。

example：

struct Type
{
    Type(int type) : type_(type) { }
    int type_;
};

struct A
{
    int f_impl() const { return 1; }
};

struct B
{
    int f_impl() const { return 2; }
};

/// 定义 variant
using VAR=std::vector<std::variant<A, B>>;
VAR var;
for (int i = 0; i < 1000; ++i)
{
    std::variant<A, B> va;
    if (i % 2)
        va = A();
    else
        va = B();
    var.push_back(va);
}
/// visit with std::visit
int v_total = 0;
struct CallFunc {
    void operator()(const A& a) const { v_total += a.f_impl(); }
    void operator()(const B& b) const { v_total += b.f_impl(); }
};

for (int i = 0; i < 100000; ++i)
    for (auto & v : var)
        std::visit(CallFunc{}, v);

/// visit with holds_alternative
int callFImpl(const std::variant<A, B>& type) {
    if (std::holds_alternative<A>(type)) {
      return std::get<A>(type).f_impl();
    } 

    return std::get<B>(type).f_impl();
}
total = 0;
for (int i = 0; i < 100000; ++i)
    for (auto & v : var)
        total += callFImpl(v);

std::variant 与 virtual function 的比较： variant

性能比较： Quick C++ Benchmarks

基于 concept

主要基于 Replacing CRTP Static Polymorphism With Concepts - Fluent C++ 整理

CRTP 的问题：

多了一层间接的调用语意，可读性比较差，比如下面的代码，需要实现不同的 log 级别输出，以 CRTP 的写法如下：

template <typename TLoggerImpl>
class Logger {
public:
  void LogDebug(std::string_view message) {
    Impl().DoLogDebug(message);
  }
  void LogInfo(std::string_view message) {
    Impl().DoLogInfo(message);
  }
  void LogError(std::string_view message) {
    Impl().DoLogError(message);
  }
private:
 *TLoggerImpl& Impl() { return static_cast<TLoggerImpl&>(*this); }
*  friend TLoggerImpl;
};

template <typename TLoggerImpl>
void LogToAll(Logger<TLoggerImpl>& logger, std::string_view message) {
  logger.LogDebug(message);
  logger.LogInfo(message);
  logger.LogError(message);
}

struct CustomLogger : public Logger<CustomLogger> {
  void DoLogDebug(std::string_view message) const {
    std::cout << "[Debug] " << message << '\n';
  }
  void DoLogInfo(std::string_view message) const {
    std::cout << "[Info] " << message << '\n';
  }
  void DoLogError(std::string_view message) const {
    std::cout << "[Error] " << message << '\n';
  }
};

struct TestLogger : public Logger<TestLogger> {
  void DoLogDebug(std::string_view) const {}
  void DoLogInfo(std::string_view) const {}
  void DoLogError(std::string_view) const {}
};


CustomLogger custom_logger;
LogToAll(custom_logger, “Hello World”);
TestLogger test_logger;
LogToAll(test_logger, “Hello World”);

concept 在 c++ 20 引入，用于为 template 的 type 规定限制条件，以下是上面 Log 功能的 concept 实现。

/// 定义一个 concept
template <typename TLoggerImpl>
concept LoggerLike = requires(TLoggerImpl log) {
  log.LogDebug(std::string_view{});
  log.LogInfo(std::string_view{});
  log.LogError(std::string_view{});
};

/// 定义调用类1
struct CustomLogger {
  void LogDebug(std::string_view message) const {
    std::cout << "[Debug] " << message << '\n';
  }
  void LogInfo(std::string_view message) const {
    std::cout << "[Info] " << message << '\n';
  }
  void LogError(std::string_view message) const {
    std::cout << "[Error] " << message << '\n';
  }
};

/// 定义调用类2
struct TestLogger {
  void LogDebug(std::string_view) const {}
  void LogInfo(std::string_view) const {}
  void LogError(std::string_view) const {}
};

/// 定义调用方法
template <LoggerLike TLogger>
void LogToAll(TLogger& logger, std::string_view message) {
  logger.LogDebug(message);
  logger.LogInfo(message);
  logger.LogError(message);
}

struct CustomLoggerImpl { … };

struct TestLoggerImpl { … };

using CustomLogger = Logger<CustomLoggerImpl>;
using TestLogger = Logger<TestLoggerImpl>;

/// 实际调用
CustomLogger custom_logger;
LogToAll(custom_logger, "Hello World");
TestLogger test_logger;
LogToAll(test_logger, "Hello World");

多态：概念与实现

概念

动态多态（Dynamic Polymorphism）

vtable 与 vptr

静态多态（Static Polymorphism）

动态多态的性能问题

额外的存储空间与重定向

无法 inline 化

cache miss

其他替代 virtual function 的方法

基于 std::variant

基于 concept

Reference