コンセプト制約式の構成：包摂関係 vs. コンパイル時間

C++20コンセプトでは制約式(constraint-expression)を&&(conjunction)／||(disjunction)で組み合わせることで複雑な制約式を表現できる。一方で制約式が多数の原始制約(atomic constraint)から構成されるケースでは、包摂関係(subsumption relation)判定のための正規化プロセスが複雑になりコンパイル時間に悪影響を及ぼす。

例えばコンセプトX, Y, Zからなるコンセプトの定義方法として、下記2種類が考えられる。コンセプトC1は3個の原始制約から、一見すると記述が冗長なコンセプトC2は2個の原始制約から構成されるため、包摂関係が重要でなければ後者C2の方がC++コンパイラへの負荷が小さい。

template <typename T> concept X = /*(原始制約#1)*/;
template <typename T> concept Y = /*(原始制約#2)*/;
template <typename T> concept Z = /*(原始制約#3)*/;

template <typename T>
concept C1 = X<T> && (Y<T> || Z<T>);
//           ^^^^     ^^^^    ^^^^
//            #1       #2      #3

template <typename T>
concept C2 = X<T> && requires { requires (Y<T> || Z<T>); };
//           ^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//            #1     原始制約#4

コンセプトC1やC2単体利用であれば両者の意味論に差異はない。C1は制約X && Y, X && Z, Y || Zとの間に包摂関係が成り立つが*1、C2ではいずれの包摂関係も成り立たない。*2

// X,Y,Zコンセプトを満たすU型を仮定
template <typename T> requires C1<T>
int f(T) { return 1; }
template <typename T> requires X<T> && Y<T>
int f(T) { return 2; }
assert( f(U{}) == 2 );

template <typename T> requires C2<T>
int g(T) { return 1; }
template <typename T> requires X<T> && Y<T>
int g(T) { return 2; }
// g(U{}) はオーバーロード解決が曖昧

実際にC++2b(C++23)向け提案文書(PDF)P2404R1では、コンパイル時間短縮を目的としてコンセプト定義の変更を行っている。

3.1.1 Avoiding disjunctions
Disjunctions in concepts may slow down compilation times due to added costs in the conversion to disjunctive normal form, so it is desirable to avoid them. As such, this new disjunction should be made into an atomic constraint to avoid this issue. Lost functionality is not a concern in this case, because users are not expected to find it useful to have subsumption between equality_comparable_with<T, U> and convertible_to<const T&, const common_reference_t<const T&, const U&>> or the other similar cases.
Avoiding the disjunctions in this case is easily resolved by forcing the disjunction to be an atomic constraint via a requires expression and nested requirements:
requires {
  requires convertible_to<const T&, const C&> || convertible_to<T&&, const C&>;
}
In this particular case, we have two disjunctions, one for T and one for U. Having a conjunction between atomic constraints is not useful, so the proposed wording will merge them into a single atomic constraint.

提案文書P2304R0およびP2404R1より、common-comparison-supertype-with説明用コンセプト定義を改変引用（メタ関数への引数部は略記）。

// P2304R0
template<class T, class U>
concept common-comparison-supertype-with =
  same_as</*...*/> &&
  (convertible_to</*...*/> || convertible_to</*...*/>) &&
  (convertible_to</*...*/> || convertible_to</*...*/>);

// P2404R1
template<class T, class U>
concept common-comparison-supertype-with =
  same_as</*...*/> &&
  requires {
    requires convertible_to</*...*/> || convertible_to</*...*/>;
    requires convertible_to</*...*/> || convertible_to</*...*/>;
  };

前者のコンセプト定義では10個の原始制約から構成されるのに対し、後者では3個の原始制約（&&に続くrequires式全体で1つの原始制約）から構成される。*3

yohhoyの日記

技術的メモをしていきたい日記

コンセプト制約式の構成：包摂関係 vs. コンパイル時間