C++のポリモーフィズムとそのパフォーマンス

モチベーション

この記事は、C++の仮想関数が実は遅いのではないか、もっと早い方法があるのではないかという思いつきから、それの検証結果をまとめたものである。
私はC++が好きだが、その専門家ではないため、もし記事の内容に誤りがあればGithubリポジトリやTwitterなどから教えてほしい。

動的/静的 ポリモーフィズム

C++では、仮想関数で動的ポリモーフィズムを実装できる。

#include <iostream>

class Animal {
  public:
    virtual auto speak() -> void = 0;
};

class Cat : public Animal {
  public:
    auto speak() -> void override {
        std::cout << "meow\n";
    }
};

class Dog : public Animal {
  public:
    auto speak() -> void override {
        std::cout << "bowwow\n";
    }
};

auto speak_virtual(Animal* animal) -> void {
    // (4) 'animal'の構築方法によってCat::speakとDog::speakとが呼び分けられる
    animal->speak();
}

auto park_virtual() {
    auto cat = Cat(); // (1) 'cat' は 'Cat'型
    auto dog = Dog(); // (2) 'dog' は 'Dog'型
    speak_virtual(&cat);  // (3) でも両方 'Animal*' を取り出せる
    speak_virtual(&dog);
}

だが、仮想関数はインライン化による最適化を妨げる。パフォーマンスを上げるなら、できるだけ関数ポインタの使用は避けるべきだ。
上の例の場合、テンプレートを用いると、同じことが静的ポリモーフィズムで実現できる。

#include <concepts>
#include <iostream>

// コンセプト 'Animal' の要件を定義する
template <class T>
concept Animal = requires(T& t) {
// 'Animal' は 'speak' というvoidを返す関数を持たなければならない
    { t.speak() } -> std::same_as<void>;
};

class Cat {
  public:
    auto speak() -> void {
        std::cout << "meow\n";
    }
};

class Dog {
  public:
    auto speak() -> void {
        std::cout << "bowwow\n";
    }
};

// コンセプト 'Animal' を満たす何らかの型を受け付ける
template <Animal T>
auto speak_template(T& animal) {
    animal.speak();
}

auto park_template() {
    auto cat = Cat();
    auto dog = Dog();
    speak_template(cat); // 'Cat' は 'Animal' を満たす
    speak_template(dog); // 'Dog' は 'Animal' を満たす
}

こうすれば、{Cat, Dog}::speakはインライン化が可能で、パフォーマンスの向上が期待できる。

同一の型に代入する

だが、これだけでは仮想関数を置き換えたとは言えない。以下のように、Cat/Dogのインスタンスを一つのvectorに保存する例を考える。

auto speak_virtual2(std::vector<Animal*> animals) -> void {
    for(auto animal : animals) {
        animal->speak();
    }
}

auto park_virtual2() {
    auto animals = std::vector<Animal*>{new Cat, new Dog};
    speak_virtual2(animals);
}

テンプレートを使うと以下のように書きたくなるが、このコードはコンパイルできない。

auto speak_template2(std::vector<Animal>& animal) {
    for(auto animal: animals) {
        animal.speak();
    }
}

auto park_template2() {
    auto animals = std::vector<Animal>{Cat(), Dog()};
}

std::vector<Animal>というのはできない。Animalはあくまでコンセプト(型が満たすべき要件の名前)であり、具体的な型ではないからである。

std::variantを使う

そこで、std::variantを使う。std::variantはunionの強化版みたいなやつである(cpprefjpを読んでほしい)。
すると、上のコードはこのようになる。

using SomeAnimal = std::variant<Cat, Dog>;

auto speak_template2(std::vector<SomeAnimal>& animals) {
    for(auto animal : animals) {
        if(animal.index() == 0) {
            // 'animal' には 'Cat' のインスタンスが入っている
            std::get<0>(animal).speak();
        } else if(animal.index() == 1) {
            // 'animal' には 'Dog' のインスタンスが入っている
            std::get<1>(animal).speak();
        }
    }
}

auto park_template2() {
    auto animals = std::vector<SomeAnimal>{Cat(), Dog()};
    speak_template2(animals);
}

これで仮想関数と同じことができるようになった。

だが待ってほしい、speak_virtual2とspeak_template2を見比べてみると、speak_template2には拡張性がないことがわかる。動物の種類が増えた場合、speak_virtual2はそのまま動くが、speak_template2はelse if節を増やさなければならない。これはちょっといただけない。この問題の解決策の一つは、std::visitである。

std::visitを使う

詳しいことは例によってcpprefjpを見てもらうとして、std::visitを使うとspeak_template2は以下のように書き直せる。

auto speak_template2(std::vector<SomeAnimal>& animals) {
    for(auto animal : animals) {
        std::visit([](auto animal) { animal.speak(); }, animal);
    }
}

これでspeak_template2を書き直さなくても良くなった、めでたしめでたし... と言いたいが、この方法には問題がある。それは、std::visitが遅いということだ。
将来は変わるかもしれないが、現時点(clang 15.0.3)の実装では、std::visitは内部で関数ポインタのリストを作る。これでは、仮想関数のときと何も変わらない。後述するベンチマークでも、std::visitは仮想関数と同じくらいのパフォーマンスしか出ないことがわかっている。よって、別の方法を考えなければならない。

std::visitを使わない

別の方法として私が用意したのは、この関数である。

template <class V, size_t index = 0>
auto visit(V& variant, auto visitor) -> auto{
    if constexpr(index < std::variant_size_v<V>) {
        if(index == variant.index()) {
            return visitor(std::get<index>(variant));
        }
        return visit<V, index + 1>(variant, visitor);
    }

    // unreachable
    return decltype(visitor(std::get<0>(variant)))();
}

愚直にif-elseをネストしていくものだ。私はコンパイラがこの再帰関数をswitch文のような形に最適化してくれることを期待してこの関数を書いた。実際にコンパイラはこれを最適化できるのか、ベンチマークを行った。

ベンチマーク

ベンチマークは、以下のプログラムで行った: gist
このプログラムは、bench.shを実行すると、計測を行い、結果をcsvで出力する。
計測環境は以下のとおり:

> uname -srmpio
Linux 6.0.8-gentoo x86_64 Intel(R) Core(TM) i5-6300U CPU @ 2.40GHz GenuineIntel GNU/Linux
> clang++ --version
clang version 15.0.3
Target: x86_64-pc-linux-gnu
Thread model: posix
...
> g++ --version
g++ (Gentoo 11.3.0 p4) 11.3.0
...

結果は以下のようになった。なお、自作visit/std::visit/仮想関数の値は計算にかかった時間[ms]であり、この値が小さいほどスコアが高い。

この表からclang++ -O2とg++ -O2の行をそれぞれ抜き出してプロットすると、以下のグラフのようになった。 グラフ中のrecursive-ifとは自作visit関数のことである。
さて、際立っているのは、clangのrecursive-ifとgccのrecursive-ifである。前者は圧倒的に早いが、後者は圧倒的に遅い。
前者が早いことから、clangは自作visitを想定どおりに最適化していると予想される。
一方、後者については、その計算時間がクラス数に対してべき級数的に増加していることから、gccは自作visitをそのまま再帰関数としてコンパイルしたことが予想される。
これらの傾向は-O3フラグをつけても変わらないため、clangはこの関数を最適化できるが、gccはできない、という結論になった。
その他の方法、std::visitや仮想関数については、どれも似たような値が出ている。それを確かめるため、縦軸の最大値を2500に固定したグラフも用意した。 若干gccのstd::visitが早い気もするが、どれも同じようなものと言っていいだろう。

まとめ

最適化が効くコンパイラを使うなら、自作visitの方法を使うのが最も早いことがわかった。逆に、そのようなコンパイラを使えないなら、仮想関数から乗り換えてもあまり効果はなさそうである。