yohhoyの日記

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

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

C++

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

関連URL

*1:https://wandbox.org/permlink/6l0UgFuTWECJZ9tM

*2:コンセプト C1 と コンセプト X、コンセプト C2 と コンセプト X の間にはそれぞれ包摂関係が成り立つ。https://wandbox.org/permlink/wpodIgRHXuNiVZI6

*3:C++20標準ライブラリ提供の std::same_as コンセプトは2個の原始制約（→id:yohhoy:20190925）、std::convertible_to コンセプトは2個の原始制約から構成される。

*4:2022年2月現在、C++ Core Guidelines ルールT.31はタイトルのみで説明文は未記述。

std::views::commonレンジアダプタの制約

C++ C++2b

C++20 RangeからC++17互換イテレータペアへの変換にはstd::views::commonレンジアダプタ(range adaptor)を利用する。ただしstd::ranges::basic_istream_viewなどムーブのみ／コピー不可なイテレータからなる一部Rangeは変換できない。*1

#include <sstream>
#include <ranges>
#include <vector>

auto ints = std::istringstream{"0 1 2 3 4"};
auto cv = std::ranges::istream_view<int>(ints)
        | std::views::filter([](int n){ return n % 2 == 0; })
        | std::views::common;  // NG: ill-formed
std::vector<int> vec(cv.begin(), cv.end());

これはstd::ranges::common_view<V>クラステンプレート制約として、対象Viewのイテレータ型(iterator_t<V>)がstd::copyableコンセプトを満たすことを要求するため。C++17互換イテレータではコピー可能・ムーブ可能を要求するが、C++20 Rangeを構成するイテレータはコピー不可・ムーブ可能であればよい。*2

前掲コードのようにRange／Viewからコンテナへ変換したい場合、次期C++2b(C++23)標準ライブラリではstd::views::toレンジアダプタ（→id:yohhoy:20210902）が利用可能となる。

// C++2b(C++23)
#include <sstream>
#include <ranges>
#include <vector>

auto ints = std::istringstream{"0 1 2 3 4"};
auto vec = std::ranges::istream_view<int>(ints)
         | std::views::filter([](int n){ return n % 2 == 0; })
         | std::views::to<std::vector>();
// vec == std::vector<int>{0, 2, 4}

C++20 24.6.4.3, 24.7.13.1, 24.7.13.2より一部引用。

namespace std::ranges {
  template<movable Val, class CharT, class Traits>
    requires default_initializable<Val> &&
             stream-extractable<Val, CharT, Traits>
  class basic_istream_view<Val, CharT, Traits>::iterator {
  public:
    // (snip)
    iterator(const iterator&) = delete;
    iterator(iterator&&) = default;
    iterator& operator=(const iterator&) = delete;
    iterator& operator=(iterator&&) = default;
    // (snip)
  };
}

1 common_view takes a view which has different types for its iterator and sentinel and turns it into a view of the same elements with an iterator and sentinel of the same type.
2 [Note: common_view is useful for calling legacy algorithms that expect a range's iterator and sentinel types to be the same. --end note]
3 The name views::common denotes a range adaptor object (24.7.1). (snip)

namespace std::ranges {
  template<view V>
    requires (!common_range<V> && copyable<iterator_t<V>>)
  class common_view : public view_interface<common_view<V>> {
    // (snip)
  };
}

関連URL

*1:std::ranges::istream_view<Val> は std::ranges::basic_istream_view<Val, char> のエイリアステンプレート。(PDF)P2432R1によりC++20 DRとして遡及適用。

*2:現行gcc/libstdc++は難解なエラーメッセージを生成する https://wandbox.org/permlink/qu5Hl1Lbj6fdhQot

コンセプト定義への属性指定

C++

C++20言語仕様では、コンセプト定義に対して属性(attribute)を指定できない。

template <typename T>
[[deprecated("concept")]]  // NG: ill-formed
concept C = /*...*/;

// OK: 変数テンプレート
template <typename T>
[[deprecated("variable")]]
T var = /*...*/;

// OK: 関数テンプレート
template <typename T>
[[deprecated("function")]]
void func(T) { /*...*/ }

// OK: クラステンプレート
template <typename T>
class [[deprecated("class")]] S0 { /*...*/ };

// OK: エイリアステンプレート
template <typename T> struct S1 {};
template <typename T>
using A [[deprecated("alias")]] = S1<T>;

メモ：エイリアステンプレート(alias template)に対するdeprecated属性指定は、GCC／Clangともに機能しない模様… MSVCは期待通り警告C4996が報告される。

C++20 13.1/p1, 13.7.8/p1より一部引用。

1 A template defines a family of classes, functions, or variables, an alias for a family of types, or a concept.

template-declaration:
　　template-head declaration
　　template-head concept-definition
template-head:
　　template < template-parameter-list > requires-clauseopt
template-parameter-list:
　　template-parameter
　　template-parameter-list , template-parameter
requires-clause:
　　requires constraint-logical-or-expression
(snip)

1 A concept is a template that defines constraints on its template arguments.

concept-definition:
　　concept concept-name = constraint-expression ;
(snip)

関連URL

クラステンプレート特殊化型判定

C++

プログラミング言語C++において、与えられた型があるクラステンプレートの特殊化(specialization)か否かを判定する方法。

下記コードは複素数std::complexの特殊化か否かを判定するメタ関数およびコンセプト実装例。

// C++11/14/17: is_complexメタ関数
#include <complex>
#include <type_traits>

template <typename T>
struct is_complex : std::false_type {};
template <typename T>
struct is_complex<std::complex<T>> : std::true_type {};

static_assert( is_complex<std::complex<float>>::value );
static_assert( !is_complex<double>::value );

// C++20: is_complexコンセプト
#include <concepts>
#include <complex>

template <typename T>
concept is_complex = requires (T t) {
  { std::complex{std::move(t)} } -> std::same_as<T>;
  // ムーブのみ可能な型を考慮してrvalueへキャスト
  // コピー可能な型では単にt（lvalue）記述でもよい
};

static_assert( is_complex<std::complex<float>> );
static_assert( !is_complex<double> );

メタ関数バージョンは非型テンプレートパラメータ(non-type template parameter)を含むクラステンプレート（例：std::array, std::span）には利用できない。コンセプトバージョンはコピー／ムーブ不可のクラステンプレート（例：std::atomic, std::counting_semaphore）には利用できない。

関連URL

*1:提案 P2098R1 は2020年5月会合で棄却済み。https://github.com/cplusplus/papers/issues/812 参照。

Math.min＠浮動小数点数の実装

Java

Java標準ライブラリMath.minメソッドの実装についてメモ。

浮動小数点数型(float, double)に対するminでは、NaN(Not a Number)および負のゼロ(-0.0)を考慮する必要がある。*1

public static double min(double a, double b) {
  if (a != a)
    return a;   // a is NaN
  if ((a == 0.0d) && (b == 0.0d)
      && (Double.doubleToRawLongBits(b) == negativeZeroDoubleBits)) {
    // Raw conversion ok since NaN can't map to -0.0.
    return b;
  }
  return (a <= b) ? a : b;
}

// Use raw bit-wise conversions on guaranteed non-NaN arguments.
private static final long negativeZeroDoubleBits
  = Double.doubleToRawLongBits(-0.0d);

2つのdouble値のうち小さいほうを返します。 つまり、結果は負の無限大に近いほうの値となります。 引数の値が同じ場合は同じ値を返します。 どちらかの値がNaNの場合はNaNを返します。 数値比較演算子とは異なり、このメソッドは負のゼロが厳密には正のゼロよりも小さいと見なします。 一方の引数が正のゼロでもう一方が負のゼロの場合は、負のゼロを返します。

https://docs.oracle.com/javase/jp/10/docs/api/java/lang/Math.html#min(double,double)

一方、整数型(int, long)に対するminは比較演算<=を用いてシンプルに実装される。*2

public static int min(int a, int b) {
  return (a <= b) ? a : b;
}

関連URL

*1:https://github.com/openjdk/jdk/blob/jdk-10%2B46/src/java.base/share/classes/java/lang/Math.java#L1556-L1580

*2:https://github.com/openjdk/jdk/blob/jdk-10%2B46/src/java.base/share/classes/java/lang/Math.java#L1501-L1514

C++ min/maxアルゴリズムの正しい実装

C++

C++標準ライブラリstd::min, std::maxアルゴリズムの動作仕様についてメモ。
問題：C++ min/maxアルゴリズムを「正しく」実装せよ。

template <typename T>
const T& min(const T& a, const T& b)
{
  // どちらのmin実装が正しい？
  return a < b ? a : b;  // #1
  return b < a ? b : a;  // #2
}

template <typename T>
const T& max(const T& a, const T& b)
{
  // どちらのmax実装が正しい？
  return a < b ? b : a;  // #3
  return b < a ? a : b;  // #4
}

答え：#2 と #3

2個の値を比較するmin/maxアルゴリズムでは、値が等価(equivalent)*1なときは1番目の値を返すと規定されている。実装#1や#4ではC++標準ライブラリの仕様違反となる。C++03 25.3.7/p2-3, p5-6より引用。

template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
  const T& min(const T& a, const T& b, Compare comp);

2 Returns: The smaller value.
3 Remarks: Returns the first argument when the arguments are equivalent.

template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
  const T& max(const T& a, const T& b, Compare comp);

5 Returns: The larger value.
6 Remarks: Returns the first argument when the arguments are equivalent.

関連URL

*1:C++標準ライブラリでは a < b が偽かつ b < a が偽のとき、a と b は等価(equivalent)とみなす。

move in accumulateアルゴリズム

C++

C++20標準ヘッダ<numeric>のstd::accumulateアルゴリズム内部実装では、T型のアキュムレータ変数(acc)への累積操作時にstd::move関数適用（右辺値への変換）が規定される。

// C++20仕様の累積演算（1要素あたり）
acc = std::move(acc) + *iterator;
//    ^^^^^^^^^^^^^^
//    右辺値

// C++17仕様の累積演算（1要素あたり）
acc = acc + *iterator;
//    ^^^
//    左辺値

C++17以前の標準ライブラリ仕様では左辺値に対する演算となっていたが、右辺値に変更されたことで（代入右辺の）accオブジェクトに対する破壊的操作が可能となり、より効率的な実装が選択される可能性が広がる。

本ライブラリ仕様変更の提案文書P0616R0では、事前メモリ確保した文字列型に対する累積（連結）操作において大幅な性能改善を報告している。*1

1 Motivation
(snip)

A very simple measurement program showing the difference of using accumulate with strings with or without move show a significant improvement for that case (150 to over 200 times faster with concatenating 10000 short strings, with the additional potential of pre-allocating the whole string size up front when using move). (snip)

同様の改善はinner_product, partial_sum, adjacent_differenceアルゴリズムに対しても適用される。

C++20

C++20 25.10.2/p2より引用（下線部は強調）。

template <class InputIterator, class T>
  constexpr T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  constexpr T accumulate(InputIterator first, InputIterator last, T init, 
                         BinaryOperation binary_op);

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = std::move(acc) + *i or acc = binary_op(std::move(acc), *i) for every iterator i in the range [first, last) in order.

C++17以前

C++17 29.8.2/p2より引用。

template <class InputIterator, class T>
  T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  T accumulate(InputIterator first, InputIterator last, T init, 
               BinaryOperation binary_op);

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order.

関連URL

*1:https://wandbox.org/permlink/VJuFbbc1hp37a3AM