yohhoyの日記

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

Read-Copy Update @ C++26

C++2c(C++26)標準ライブラリに追加される<rcu>ヘッダについて。Read copy updateの略。

// C++2c
#include <atomic>
#include <mutex>  // scoped_lock
#include <rcu>

struct Data { int m1; /*...*/ };
std::atomic<Data*> data_;
// new確保された初期値が別途設定される前提

void multiple_reader()
{
  // Readerロック取得(ノンブロッキング操作)
  std::scoped_lock rlk(std::rcu_default_domain());
  // 現在の共有データへのポインタ取得
  Data* p = data_.load(std::memory_order_acquire);
  // アドレスloadにはmemory_order_consume指定が想定されていたが、
  // C++20以降はconsume指定はdiscourage扱いとなっている(P0371R1)。
  // acquire指定セマンティクスはconsumeを完全に包含する。
  int m1 = p->m1; 
} // Readerロック解放

void single_writer()
{
  // 新データを作成
  Data* newdata = new Data();
  newdata->m1 = /*...*/; 

  // ポインタをアトミック更新
  Data* olddata = data_.exchange(newdata, std::memory_order_release);

  // 全Readerロック解放後のデータ回収をスケジュールする
  std::rcu_retire(olddata);
  // 内部実装には何らのスケジューラの存在が仮定されている。
  // ポインタはstd::default_delete<Data>経由でdeleteされる。
  // 実装によっては呼出スレッド上にて待機+deleteされる可能性あり。
}

まとめ:

  • プリミティブなスレッド間同期機構として、ユーザ空間RCU(Userspace Read-Copy Update)を提供する。
    • RCU機構で実現される制御はReader-Writerロック*1と似ているが、Readerロック取得はブロッキングされず高いスケーラビリティを持つ。
    • Writerスレッドは共有データを直接書き換えるのではなく、旧データから新データへとコピー&書き換えたのち、“共有データを指すポインタ” が指す先を旧データから新データへとアトミック更新する。
    • 全体としては新旧データが同時に存在する状態となり、以降のReaderロック取得スレッドは新データを参照する。全Readerスレッドが旧データを読取り終わった後に、旧データのメモリ領域を回収(reclaim)しなければならない。
    • RCU機構が直接提供するのは旧データのメモリ解放タイミング制御のみ。
  • RCUドメインstd::rcu_domain
    • Readerロック管理とメモリ回収機構を提供するクラス。Readerロック取得/解放操作のためにLockable要件を満たす。*2
    • rcu_domain::lockは同一スレッド上での再帰的Readerロックをサポートする。*3
    • C++2c標準ライブラリではシステムグローバルなstd::rcu_default_domain()のみが提供される。
  • 下記3パターンの実装方式に対応したAPIが提供される。
    • 侵襲(intrusive) RCU:データ型Tstd::rcu_obj_base<T>から継承*4し、retire()メンバ関数を利用する。
    • 非侵襲(non-intrusive) RCU:std::rcu_retire(p)関数を利用する。
    • 同期(synchronous) RCU:std::rcu_synchronize()関数+手動メモリ解放を行う。
  • 全retire操作の完了待ち:std::rcu_barrier()関数
  • retire操作のメモリ解放処理はカスタマイズ可能。デフォルトstd::default_delete<T>
  • プロダクション品質の実装例として facebook/folly ライブラリが存在する。機能的にはC++2c標準ライブラリの上位互換相当。*5

関連URL

*1:C++標準ライブラリの std::shared_mutex、POSIXの pthread_rwlock_* など。

*2:データ読取り操作を行うRCU保護区間(region of RCU protection)の開始/終了を、std::scoped_lock や std::unique_lock によるScoped Lockイディオムで実現するのために lock/unlock メンバ関数が提供される。

*3:C++標準 std::shared_mutex では再帰的なロック操作をサポートしない。

*4:いわゆるCRTP(Curiously Recurring Template Pattern)継承関係。

*5:P2545R4 "A near-superset of this proposal is implemented in the Folly RCU library."

std::submdspan関数

C++2c(C++26)標準ライブラリに追加される多次元部分ビューstd::submdspanについて。

// <mdspan>ヘッダ
namespace std {
  template<
    class T, class E, class L, class A,
    class... SliceSpecifiers>
  constexpr auto submdspan(
    const mdspan<T, E, L, A>& src,
    SliceSpecifiers... slices) -> /*see below*/;
}

まとめ:

  • 多次元ビューstd::mdspan(→id:yohhoy:20230303)から部分ビューを取り出す(slice)関数。
  • 第2引数以降のスライス指定子リストにより、各次元のスライス方法(slicing)を指定する。
    • 単一インデクス:単一値。指定次元に対するインデクスを固定し、次元数(rank)を1つ削減する。*1
    • インデクス範囲:開始位置(begin)+終了位置(end)の組。std::pairや2要素std::tuple等により*2、指定次元に対するインデクス範囲を取り出す。
    • ストライド指定範囲:オフセット位置(offset)+要素数(extent)+ストライド(stride)の組。std::strided_sliceにより、指定次元に対してずらし幅指定したインデクス範囲を取り出す。
    • 全選択:タグ値std::full_extent。指定次元をそのまま取り出す。
  • ストライド指定範囲” 用のstrided_slice型は名前付き初期化(→id:yohhoy:20170820)をサポートする。
    • 類似機能を提供するPython/numpyやMatlabFortranと異なり、変換元における終了位置(end)ではなく変換元における要素数(extent)による指定を行う。
    • 例:strided_slice{.offset=1, .extent=10, .stride=3}またはstrided_slice{1, 10, 3}
  • “インデクス範囲” および “ストライド指定範囲” で用いるインデクス値は、通常の値と整数定数の2種類をサポートする。*3
    • 戻り値型mdspan<T,E,L,A>における多次元インデクス型Eの各次元要素数に影響を与える。
    • 通常の値:整数リテラル(literal)*4を含む整数値。指定次元の要素数は実行時(std::dynamic_extent)に決定する。
    • 整数定数:std::integral_constant互換の定数値*5。指定次元の要素数コンパイル時に決定する。
  • レイアウトポリシーLC++標準ライブラリ提供メモリレイアウトのみサポートする。
    • std::layout_right:同ポリシー型を維持できる場合はlayout_rightを利用。それ以外はlayout_strideへ変換。
    • std::layout_left:同ポリシー型を維持できる場合はlayout_leftを利用。それ以外はlayout_strideへ変換。
    • std::layout_stridelayout_strideのまま。
    • ユーザ定義レイアウトポリシーをサポートするには、カスタマイズポイントsubmdspan_mapping関数を実装する。カスタマイズポイント実装は必須要件ではないが、汎用のフォールバック実装は提供されない。
  • 要素型TとアクセスポリシーAは原則維持される。*6

スライス指定の例

int a[15];  // {1, 2, ... 15}
std::ranges::iota(a, 1);

// 3x5要素の2次元ビュー
std::mdspan m0{a, std::extents<size_t, 3, 5>{}};
//  1  2  3  4  5
//  6  7  8  9 10
// 11 12 13 14 15

auto m1 = std::submdspan(m0, 1, std::full_extent);
// [6 7 8 9 10] (5要素1次元)
auto m2 = std::submdspan(m0, std::full_extent, 2);
// [3 8 13] (3要素1次元)
auto m3 = std::submdspan(m0, 1, 2);
// 8 (0次元)

// 2x3要素の2次元部分ビュー
auto m4d = std::submdspan(m0, std::pair{1,2}, std::tuple{1,3});
//  -  -  -  -  -
//  -  7  8  9  -
//  - 12 13 14  -
// Extents = std::dextents<size_t, 2>

// 2x2要素の2次元部分ビュー
auto m5d = std::submdspan(m0,
  std::strided_slice{.offset=0, .extent=3, .stride=2},
  std::strided_slice{.offset=1, .extent=4, .stride=3});
//  -  2  -  -  5
//  -  -  -  -  -
//  - 12  -  - 15
// Extents = std::dextents<size_t, 2>
template <int N>
constexpr auto Int = std::integral_constant<int, N>;

// 2x3要素(静的要素数)の2次元部分ビュー
auto m4s = std::submdspan(m0,
  std::pair{Int<1>,Int<2>}, std::tuple{Int<1>,Int<3>});
//  -  -  -  -  -
//  -  7  8  9  -
//  - 12 13 14  -
// Extents = std::extents<size_t, 2, 3>

// 2x2要素(静的要素数)の2次元部分ビュー
auto m5s = std::submdspan(m0,
  std::strided_slice{.offset=0, .extent=Int<3>, .stride=Int<2>},
  std::strided_slice{.offset=1, .extent=Int<4>, .stride=Int<3>});
//  -  2  -  -  5
//  -  -  -  -  -
//  - 12  -  - 15
// Extents = std::extents<size_t, 2, 2>
// strided_slice::offset型はsubmdspan適用後の型に影響しない

レイアウトポリシー変換

int a[60] = /*...*/;

// 3x4x5要素の3次元ビュー(LayoutPolicy=layout_right)
std::mdspan m0{a, std::extents<size_t, 3, 4, 5>{}};

auto m1 = std::submdspan(m0, 1, std::full_extent, std::full_extent);
// LayoutPolicy = layout_right (4x5要素2次元)
auto m2 = std::submdspan(m0, 1, std::pair{1,2}, std::full_extent);
// LayoutPolicy = layout_right (2x5要素2次元)
auto m3 = std::submdspan(m0, 1, 0, 2);
// LayoutPolicy = layout_right (0次元)

auto m4 = std::submdspan(m0, std::full_extent, 0, std::full_extent);
// LayoutPolicy = layout_stride (3x5要素2次元)
// 変換後m4の strides[] = {20, 1}
// 3x4x5要素の3次元ビュー, layout_stride = {20, 1, 4}
using Exts3x4x5 = std::extents<size_t, 3, 4, 5>;
std::array strides = {20, 1, 4};
auto mapping = std::layout_stride::mapping{Exts3x4x5{}, strides};
std::mdspan m0s{a, mapping};

auto m5 = std::submdspan(m0s, 0, std::full_extent, 0);
// LayoutPolicy = layout_stride (4要素1次元)
assert(m5.mapping().stride(0) == 1);
// メモリレイアウト的にはlayout_right互換となる
// コンパイル時の型計算ではstridesアクセスできないため
// layout_strideからは常にlayout_strideへと変換される

// 変換コンストラクタによりlayout_rightへ明示変換可能
std::mdspan<int, std::extents<size_t, 4>> m5r{ m5 };
// LayoutPolicy = layout_right (4要素1次元)

関連URL

*1:1次元 mdspan からは 0次元 mdspan(→id:yohhoy:20230309)が生成される。

*2:2要素ペアとしてアクセス可能な型(index-pair-like)を広くサポートする。

*3:“単一インデクス” も整数定数をサポートするが、その効果は通常の値を指定したときと同じ。

*4:戻り値型の決定で利用されるため、std::integral_constant<int,N>::value のように値が型情報にエンコードされていないと、コンパイル時にその値(value)へアクセスできない。

*5:データメンバ value で定数値アクセス可能な型(integral-constant-like)を広くサポートする。

*6:厳密には submdspan 関数適用後 mdspan<T,E,L,A> の要素型 T やアクセスポリシー A は A::offset_policy 型に依存する。通常は A::offset_policy == A として定義されるため、テンプレートパラメータ T, A 型が変化するケースは稀。

GCC -pedanticオプション

GCCコンパイラの -pedantic オプションについてメモ。

pedantic
形容詞
〈侮蔑的〉〔文法・学問的なことなどについて〕重要でない事にこだわり過ぎる、学者ぶった、知識をひけらかす、衒学的な

https://eow.alc.co.jp/search?q=pedantic

GCC 2.95.3マニュアル*1より引用。下線部は後続バージョン(3.0)で削除された内容。

-pedantic
Issue all the warnings demanded by strict ANSI C and ISO C++; reject all programs that use forbidden extensions.

Valid ANSI C and ISO C++ programs should compile properly with or without this option (though a rare few will require `-ansi'). However, without this option, certain GNU extensions and traditional C and C++ features are supported as well. With this option, they are rejected.

`-pedantic' does not cause warning messages for use of the alternate keywords whose names begin and end with `__'. Pedantic warnings are also disabled in the expression that follows __extension__. However, only system header files should use these escape routes; application programs should avoid them. See section 4.35 Alternate Keywords.

This option is not intended to be useful; it exists only to satisfy pedants who would otherwise claim that GCC fails to support the ANSI standard.

Some users try to use `-pedantic' to check programs for strict ANSI C conformance. They soon find that it does not do quite what they want: it finds some non-ANSI practices, but not all--only those for which ANSI C requires a diagnostic.

A feature to report any failure to conform to ANSI C might be useful in some instances, but would require considerable additional work and would be quite different from `-pedantic'. We don't have plans to support such a feature in the near future.

https://gcc.gnu.org/onlinedocs/gcc-2.95.3/gcc_2.html#SEC8

GCC 3.0マニュアル*2より引用(下線部は追加内容)。2024年1月現在の最新版GCC 13.2.0マニュアルでもほぼ同一内容。

-pedantic
Issue all the warnings demanded by strict ISO C and ISO C++; reject all programs that use forbidden extensions, and some other programs that do not follow ISO C and ISO C++. For ISO C, follows the version of the ISO C standard specified by any `-std' option used.

Valid ISO C and ISO C++ programs should compile properly with or without this option (though a rare few will require `-ansi' or a `-std' option specifying the required version of ISO C). However, without this option, certain GNU extensions and traditional C and C++ features are supported as well. With this option, they are rejected.

`-pedantic' does not cause warning messages for use of the alternate keywords whose names begin and end with `__'. Pedantic warnings are also disabled in the expression that follows __extension__. However, only system header files should use these escape routes; application programs should avoid them. See section 5.39 Alternate Keywords.

Some users try to use `-pedantic' to check programs for strict ISO C conformance. They soon find that it does not do quite what they want: it finds some non-ISO practices, but not all--only those for which ISO C requires a diagnostic, and some others for which diagnostics have been added.

A feature to report any failure to conform to ISO C might be useful in some instances, but would require considerable additional work and would be quite different from `-pedantic'. We don't have plans to support such a feature in the near future.

Where the standard specified with `-std' represents a GNU extended dialect of C, such as `gnu89' or `gnu99', there is a corresponding base standard, the version of ISO C on which the GNU extended dialect is based. Warnings from `-pedantic' are given where they are required by the base standard. (It would not make sense for such warnings to be given only for features not in the specified GNU C dialect, since by definition the GNU dialects of C include all features the compiler supports with the given option, and there would be nothing to warn about.)

https://gcc.gnu.org/onlinedocs/gcc-3.0/gcc_3.html#SEC11

関連URL

*1:GCC 2.95.3は2.x系の最終バージョン。2001年3月リリース。

*2:GCC 3.0は2001年6月リリース。GCC 2.x系からの大幅な変更・改善が行われている。https://www.gnu.org/software/gcc/gcc-3.0/features.html

関数戻り値の破棄を明示

プログラミング言語C++において、nodiscard属性が指定された関数に対し意図的な戻り値破棄を明示する方法。

まとめ:

  • C++23現在は、方式(3) std::ignoreへの関数戻り値代入が実践的か。*1
  • C++2c(C++26)以降は、方式(4) プレースホルダ識別子_(アンダースコア1文字)への関数戻り値代入がベター。
  • 方式(3), (4)は戻り値オブジェクトの破棄タイミングが異なることに注意。
// 戻り値の破棄をすべきでない関数
[[nodiscard]] int f() { return 42; }

f();  // コンパイラによる警告(warning)
// GCC: ignoring return value of 'int f()', declared with attribute 'nodiscard' [-Wunused-result]
// Clang:ignoring return value of function declared with 'nodiscard' attribute [-Wunused-result]

// 意図的な戻り値破棄を明示
(void)f();          // (1) OK, but...
static_cast<void>(f());  // (2) OK, but...
std::ignore = f();  // (3) OK
auto _ = f();       // (4) OK(C++2c)

各方式の問題点は下記の通り:

  • 方式(1) well-definedだが、現代では利用推奨されないCスタイルキャストを利用している。
  • 方式(2) well-definedだが、冗長な記述となっておりプログラマ意図を読み取りづらい。
  • 方式(3) C++ Core Guildlineでは方式(1),(2)の代替案とされる。Language Lawyer*2による厳密解釈では微妙とのウワサ。*3

関連URL

*1:https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#es48-avoid-casts

*2:https://meta.stackoverflow.com/questions/256510/

*3:P2968R2より引用: "All major open source C++ library implementations provide a suitably implemented std::ignore allowing a no-op assignment from any object type. However, according to some C++ experts the standard doesn’t bless its use beyond std::tie."

std::mdspan AccessorPolicy応用例

C++23標準ライブラリの多次元ビューstd::mdspan(→id:yohhoy:20230303)における、第4テンプレートパラメータAcssesorPolicyを用いた要素アクセスカスタマイズの具体事例。

C++2c(C++26)標準ライブラリ採用が決定している線形代数基本アルゴリズム <linalg> ヘッダでは、mdspan参照先のメモリを書換えずに各要素のスケーリング(std::linalg::scaled)や複素共役(std::linalg::conjugated)変換を行うビューを提供する。適用後の多次元ビュー要素は読み取り専用となる。

#include <mdspan>
#include <linalg>  // C++2c(C++26)

using Vec = std::mdspan<int, std::dextent<size_t, 1>>;
int arr[] = {1, 2, 3};

Vec vec1{ arr };
assert(vec1[0] == 1);
// 要素アクセス vec1[i] はint&型を返す
// &(vec1[i]) == &(arr[i])

// 全要素を2倍した1次元ビュー
auto vec2 = std::linalg::scaled(2, vec1);
assert(vec2[0] == 2 && arr[0] == 1);
// 要素アクセス vec2[i] はint型を返すため
// 要素書き換え vec2[0] = 42; はill-formed

提案文書P1673R13 Wordingより一部引用(クラス宣言は簡略化)。

1 The class template scaled_accessor is an mdspan accessor policy which upon access produces scaled elements. reference. It is part of the implementation of scaled [linalg.scaled.scaled].

template<class ScalingFactor, class NestedAccessor>
class scaled_accessor {
public:
  using element_type = add_const_t<
    decltype(declval<ScalingFactor>() * declval<NestedAccessor::element_type>())>;
  using reference = remove_const_t<element_type>;
  using data_handle_type = NestedAccessor::data_handle_type;
  using offset_policy = /*...*/;

  constexpr scaled_accessor(const ScalingFactor& s, const NestedAccessor& a);
  constexpr reference access(data_handle_type p, size_t i) const;
  // ...
};

1 The scaled function template takes a scaling factor alpha and an mdspan x, and returns a new read-only mdspan with the same domain as x, that represents the elementwise product of alpha with each element of x.

template<class ScalingFactor,
         class ElementType,
         class Extents,
         class Layout,
         class Accessor>
constexpr auto scaled(
  ScalingFactor alpha,
  mdspan<ElementType, Extents, Layout, Accessor> x);

2 Let SA be scaled_accessor<ScalingFactor, Accessor>
3 Returns:

mdspan<typename SA::element_type, Extents, Layout, SA>(
  x.data_handle(), x.mapping(), SA(alpha, x.accessor()))

メモ:<linalg> ヘッダではこのほかに行列転置(std::linalg::transposed)や複素共役転置(std::linalg::conjugate_transposed)変換を行うビューも提供する。行列転置はmdspanの第3テンプレートパラメータLayoutPolicyを利用して実現される。

関連URL

std::views::filter適用後の値書換えには要注意

C++標準ライブラリ提供レンジアダプタstd::views::filter適用後の要素に対する変更操作には十分留意すること。

変更操作により要素がフィルタ条件を満たさなくなる場合、C++ライブラリ仕様上は未定義動作(undefined behavior)を引き起こす。この問題は遅延評価によりフィルタ条件が複数評価されるケースで初めて表面化するため、ライブラリ仕様違反が潜在化するリスクが高い。C++ Ranges難しい(´・ω・)(・ω・`)ネー

#include <iostream>
#include <ranges>
#include <vector>

bool is_odd(int x) { return x % 2 != 0; }

std::vector vec1 = { 1, 2, 3, 4, 5, 6 };
std::vector vec2 = vec1, vec3 = vec1;

for (int& e: vec1 | std::views::filter(is_odd) | std::views::reverse) {
  e += 10;  // OK: 条件is_odd(e)は維持される
  std::cout << e << ' ';
}
// 15 13 11 を出力

for (int& e: vec2 | std::views::filter(is_odd) | std::views::reverse) {
  e += 1;  // NG: 条件is_odd(e)を満たさないためUB
  std::cout << e << ' ';
}
// GCC/Clang: SEGV発生

// 上記例から reverse, filter 適用順を入れ替え
for (int& e: vec3 | std::views::reverse | std::views::filter(is_odd)) {
  e += 1;  // NG: 本来はUBだが...
  std::cout << e << ' ';
}
// GCC/Clang: 6 4 2 を出力

C++20 24.7.4.3/p1より引用。

Modification of the element a filter_view::iterator denotes is permitted, but results in undefined behavior if the resulting value does not satisfy the filter predicate.

関連URL

Living Dead/Zombie in C++ Standard

プログラミング言語C++標準規格の索引(Index)に紛れ込むリビングデッド。🧠👀🧟*1

brains
  names that want to eat your, [zombie.names]

living dead
  name of, [zombie.names]

https://github.com/cplusplus/draft/commit/e844e0f45550eb0bf11ea262e4abd8a5403f47d4

関連URL