std::mdspan×空間充填曲線

C++2b(C++23)標準ライブラリの多次元ビューstd::mdspanクラステンプレート（→id:yohhoy:20230303）は、第3テンプレートパラメータLayoutPolicyを介して任意のメモリレイアウトをサポートする。*1

C++2b標準ライブラリは、多次元配列表現としてメジャーな行優先(row major)／列優先(column major)レイアウトstd::layout_right／std::layout_left、これらを汎化したストライドレイアウトstd::layout_strideのみを提供する。一方でstd::mdspanに指定するレイアウトポリシーの表現能力としては、タイル化レイアウト(tiled layout)や空間充填曲線(space-filling curve)といった複雑なメモリレイアウトも表現できる。

空間充填曲線の一種であるヒルベルト曲線(Hilbert curve)の実装例：*2

// C++2b(C++23)
#include <bit>
#include <mdspan>
#include <utility>

struct layout_hilbert {
  template <class Extents>
  class mapping {
  public:
    using extents_type = Extents;
    using index_type = typename extents_type::index_type;
    using rank_type = typename extents_type::rank_type;
    using layout_type = layout_hilbert;

    mapping(const extents_type& e)
      : extents_{e}
    {
      static_assert(extents_type::rank() == 2);
      assert(e.extent(0) == e.extent(1));
      assert(std::has_single_bit(e.extent(0)));
    }
    constexpr const extents_type& extents() const noexcept
      { return extents_; }
    template <class I0, class I1>
    constexpr index_type operator()(I0 i, I1 j) const noexcept
    {
      const index_type N = std::bit_ceil(extents_.extent(0));
      return xy2d(N, j, i);  // x,y=j,i
    }
    constexpr index_type required_span_size() const noexcept
    {
      const index_type N = std::bit_ceil(extents_.extent(0));
      return N * N;
    }
    static constexpr bool is_always_unique() noexcept { return true; }
    static constexpr bool is_always_exhaustive() noexcept { return true; }
    static constexpr bool is_always_strided() noexcept { return false; }
    static constexpr bool is_unique() noexcept { return true; }
    static constexpr bool is_exhaustive() noexcept { return true; }
    static constexpr bool is_strided() noexcept { return false; }
  private:
    // https://en.wikipedia.org/wiki/Hilbert_curve より
    static constexpr index_type xy2d(
      index_type n, index_type x, index_type y)
    {
      index_type rx, ry, s, d = 0;
      for (s = n / 2; s > 0; s /= 2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
      }
      return d;
    }
    static constexpr void rot(
      index_type n, index_type *x, index_type *y,
      index_type rx, index_type ry)
    {
      if (ry == 0) {
        if (rx == 1) {
          *x = n-1 - *x;
          *y = n-1 - *y;
        }
        std::swap(*x, *y);
      }
    }
  private:
    extents_type extents_{};
  };
};

int arr[16] = /*...*/;

// 4x4=16要素がヒルベルト曲線順に配置された2次元ビュー
using MatExts = std::dextents<size_t, 2>;
std::mdspan mat{arr, layout_hilbert::mapping{MatExts{4, 4}}};
// mat[i,j]⇒arr要素順
//   j | 0  1  2  3
// ----+------------
// i=0 | 1  2 15 16
//   1 | 4  3 14 13
//   2 | 5  8  9 12
//   3 | 6  7 10 11

layout_hilbert::mappingクラステンプレートによって、多次元インデクス(i,j)からメモリ領域へのオフセット位置への変換(operator())を定義している。変数mapはCTAD（→id:yohhoy:20230308）によりstd::mdspan<int, std::dextents<size_t, 2>, layout_hilbert>型*3に推論される。

関連URL

• https://github.com/kokkos/mdspan
• std::mdspan - yohhoyの日記
• std::mdspanコンストラクタとCTAD - yohhoyの日記
• https://gist.github.com/yohhoy/9c0edd22e5a2290df6c4485caded83a5

*1:提案文書P0009R18 MDSPAN, §2.6 Why custom memory layouts? 参照。

*2:ここでは実現可能性を示すことが目的であり、簡単のため2次元ビュー(rank==2)かつ要素数(extent)が2の冪乗となる正方行列のみサポートする。原理的には非正方(non-square)行列や多次元ビュー(rank > 3)へ拡張可能。らしい。https://lutanho.net/pic2html/draw_sfc.html 参照。

*3:エイリアステンプレート std::dextents やデフォルトテンプレート引数を展開した厳密な型は std::mdspan<int, std::extents<size_t, std::dynamic_extent, std::dynamic_extent>, layout_hilbert, std::default_accessor<int>> となる。

0次元std::mdspan

C++2b(C++23)標準ライブラリの多次元ビューstd::mdspanクラステンプレート（→id:yohhoy:20230303）では、0次元(rank-0)ビューをサポートする。

意味論上は “単一変数へのポインタ” に相当する。（´-`）.｡oO（使うことあるか？）

// C++2b(C++23)
#include <cassert>
#include <mdspan>

// 0次元ビュー
using Span0D = std::mdspan<int, std::extents<size_t>>;
static_assert(Span0D::rank() == 0);

int value = 42;
Span0D m0{&value};  // OK
// CTAD利用時は std::mdspan m0{&value};

// 多次元インデクス空間サイズ==1
assert(m0.size() == 1);
assert(m0.mapping().required_span_size() == 1);

// 唯一の有効インデクスはオフセット位置0に対応
assert(m0.mapping()( ) == 0);
assert(m0[ ] == 42);

メモ：std::mdspanの "rank" を「テンソル(tensor)の階数(rank)」相当と考えれば、rank-0＝スカラー(scalar)／rank-1＝ベクトル(vector)／rank-2＝行列(matrix) と自然に解釈できる。（thanks to @onihusube9さん）

N4928(C++2b WD) 24.7.3.1/p1, 24.7.3.5.3.2/p2, 24.7.3.6.3/p1-4より一部引用（下線部は強調）。

1 A multidimensional index space is a Cartesian product of integer intervals. Each interval can be represented by a half-open range [Li, Ui), where Li and Ui are the lower and upper bounds of the ith dimension. The rank of a multidimensional index space is the number of intervals it represents. The size of a multidimensional index space is the product of Ui - Li for each dimension i if its rank is greater than 0, and 1 otherwise.

constexpr reference access(data_handle_type p, size_t i) const noexcept;

2 Effects: Equivalent to: return p[i];

template<class... OtherIndexTypes>
  constexpr reference operator[](OtherIndexTypes... indices) const;

1 Constraints:

• (snip)
• sizeof...(OtherIndexTypes) == rank() is true.

2 Let I be extents_type::index-cast(std::move(indices)).
3 Preconditions: I is a multidimensional index in extents().
[Note 1: This implies that map_(I) < map_.required_span_size() is true. -- end note]
4 Effects: Equivalent to:

return acc_.access(ptr_, map_(static_cast<index_type>(std::move(indices))...));

関連URL

• P0009R18 MDSPAN
• https://github.com/kokkos/mdspan
• std::mdspan - yohhoyの日記
• std::mdspanコンストラクタとCTAD - yohhoyの日記

std::mdspanコンストラクタとCTAD

C++2b(C++23)標準ライブラリに追加される多次元ビューstd::mdspanクラステンプレート（→id:yohhoy:20230303）の、コンストラクタと推論ガイド(deduction guide)による実引数クラステンプレート推論(CTAD; Class Template Argument Deduction)のあれこれ。

mdspan型における次元情報std::extents<I, En...>では、各次元の要素数(En)はコンパイル時定数／実行時動的指定(std::dynamic_extent)のいずれかとなる。ほとんどのCTAD*1では動的サイズ(std::dextents<I, R>)に型推論される。

デフォルトコンストラクタ

動的要素数次元を含む場合のみデフォルト構築可能。

// 2次元ビュー／動的サイズ
using Matrix = std::mdspan<double, std::dextents<size_t, 2>>;
Matrix m1;  // OK: 空(サイズ0x0)の2次元ビュー

// 2次元ビュー／動的+固定サイズNx3
using ViewNx3 = std::mdspan<double, std::extents<size_t, std::dynamic_extent, 3>>;
ViewNx3 m2;  // OK: 空(サイズ0x3)の2次元ビュー

// 2次元ビュー／固定サイズ3x3
using Mat3x3 = std::mdspan<double, std::extents<size_t, 3, 3>>;
Mat3x3 m3;  // NG: コンパイルエラー(ill-formed)

要素数リスト指定コンストラクタ

全次元の要素数リストまたは動的要素数の次元に対する要素数リストを、整数リスト／std::array<I, N>／std::span<I, N>にて指定する。CTAD利用時のインデクス型(mdspan::index_type)は推論ガイドによりsize_tとなる。

// 整数リストによる要素数指定
double *ptr = /*...*/;

// 2次元ビュー／動的サイズ2x3
using Matrix = std::mdspan<double, std::dextents<size_t, 2>>;
Matrix      m1{ptr, 2, 3};  // OK
std::mdspan m2{ptr, 2, 3};  // OK: CTAD

// 2次元ビュー／固定サイズ2x3
using Mat2x3 = std::mdspan<double, std::extents<size_t, 2, 3>>;
Mat2x3 m3a{ptr};        // OK
Mat2x3 m3c{ptr, 2};     // NG: ill-formed
Mat2x3 m3b{ptr, 2, 3};  // OK
Mat2x3 m3d{ptr, 0, 42};  // NG: 未定義動作(UB)
// 固定サイズ次元におけるコンストラクタ引数の不一致は、
// std::extents(OtherIndexTypes...)コンストラクタの
// 事前条件(Preconditions)違反のためUBを引き起こす。

// std::array<I, N>による要素数指定
double *ptr = /*...*/;
std::array<int, 2> exts = {2, 3};

// 2次元ビュー／動的サイズ2x3
using Matrix = std::mdspan<double, std::dextents<size_t, 2>>;
Matrix      m1{ptr, exts};  // OK
std::mdspan m2{ptr, exts};  // OK: CTAD

// std::span<I, N>による要素数指定
double *ptr = /*...*/;
std::vector<int> exts_vec = {2, 3};
std::span<int, 2> exts{exts_vec};

// 2次元ビュー／動的サイズ2x3
using Matrix = std::mdspan<double, std::dextents<size_t, 2>>;
Matrix      m1{ptr, exts};  // OK
std::mdspan m2{ptr, exts};  // OK: CTAD

std::span<int, std::dynamic_extent> exts2{&exts_list[0], 2};
Matrix      m3{ptr, exts2};  // NG: 動的サイズspanは指定不可
std::mdspan m4{ptr, exts2};  // NG: 動的サイズspanは指定不可

固定サイズ／動的サイズ変換

固定サイズから動的サイズへは常に安全に変換可能。動的サイズから固定サイズへはサイズ情報が一致していれば変換可能。

double *ptr = /*...*/;
// 2次元ビュー型
using Matrix = std::mdspan<double, std::dextents<size_t, 2>>;
using Mat3x3 = std::mdspan<double, std::extents<size_t, 3, 3>>;
using Mat4x4 = std::mdspan<double, std::extents<size_t, 4, 4>>;

// 固定サイズ→動的サイズ変換
Mat3x3 src3x3{ptr};
Matrix m1{src3x3};  // OK

// 固定サイズ→固定サイズ変換
Mat4x4 m2{src3x3};  // NG: コンパイルエラー(ill-formed)

// 動的サイズ→固定サイズ変換
Matrix srcmat{ptr, 3, 3};
Mat3x3 m3{srcmat};  // OK
Mat4x4 m4{srcmat};  // NG: 未定義動作(UB)
// 動的サイズ→固定サイズ型変換におけるサイズ不一致は
// 事前条件(Preconditions)違反のためUBを引き起こす。

C配列型からの変換(CTAD)

1次元C配列型のみ直接変換がサポートされる。2次元以上のC配列型からのmdspan構築はコンパイルエラーとなるか、要素アクセス時に未定義動作を引き起こす。配列先頭要素ポインタからの変換は意図しない結果をもたらす。

// 1次元配列からの変換
double arr1d[100] = /*...*/;

// 1次元ビュー／固定サイズ100
using Array100 = std::mdspan<double, std::extents<size_t, 100>>;
Array100    m1{arr1d};  // OK
std::mdspan m2{arr1d};  // OK: CTAD

// 1次元ビュー／動的サイズ100
using ArrayN = std::mdspan<double, std::dextents<size_t, 1>>;
ArrayN      m3{arr1d, 100};  // OK
std::mdspan m4{arr1d, 100};  // OK: CTAD

// 1次元配列要素先頭ポインタから変換(CTAD)
std::mdspan m5{&arr1d[0], 100};  // OK: m4と等価
std::mdspan m6{&arr1d[0]};       // OK: 0次元ビュー(！)
// m6はstd::mdspan<double, std::extents<size_t>>型に推論される

// 2次元配列からの変換
double arr2d[4][4] = /*...*/;

// 2次元ビュー／サイズ4x4(？)
using Mat4x4 = std::mdspan<double, std::extents<size_t, 4, 4>>;
Mat4x4 m1{arr2d};        // NG: ill-formed
Mat4x4 m2{arr2d, 4, 4};  // NG: ill-formed
std::mdspan m3{arr2d};   // NG: ill-formed

std::mdspan m4{arr2d, 4, 4};  // NG
// プログラマの意図に反してm4は「要素型double[4]の2次元ビュー」
// std::mdspan<double[4], std::dextents<size_t, 2>>>型に推論され、
// double[4]型の4要素配列に対する2次元ビュー(4x4=16要素)を構築する。
// 例1: 要素代入 m4[0,0] = 3.14; は型不一致となるためill-formed
// 例2: インデクス位置[0,0～3]以外は範囲外のためUBを引き起こす

// 2次元配列先頭要素ポインタから変換(？)
Mat4x4      m5{&arr2d[0][0]};        // NG
std::mdspan m6{&arr2d[0][0], 4, 4};  // NG
// m6はstd::mdspan<double, std::dextents<size_t, 2>>>型に推論される。
// double[4][4]型をdouble[16]型として扱うため厳密にはUBとなる。
// 詳細は提案文書 P2554R0 を参照。

次元情報指定コンストラクタ(CTAD)

メモリ領域ポインタとstd::extents／std::dextents*2を指定すると、任意の次元数(rank)と要素数(extents)をもつmdspan型を推論可能となる。CTADを用いるメリットは小さいが、第1引数のポインタ型から要素型(mdspan::element_type)が推論される。

double *ptr = /*...*/;

// 2次元ビュー／動的サイズ2x3
using Extents2D = std::dextents<size_t, 2>;
std::mdspan m1{ptr, Extents2D{2, 3}};  // OK

// 2次元ビュー／動的+固定サイズNx3
using ExtentsNx3 = std::extents<size_t, std::dynamic_extent, 3>;
std::mdspan m2{ptr, ExtentsNx3{2}};  // OK

// 2次元ビュー／固定サイズ2x3
using Extents2x3 = std::extents<size_t, 2, 3>;
std::mdspan m3{ptr, Extents2x3{}};  // OK

メモリレイアウト型変換

行優先(row major)std::layout_right／列優先(column major)std::layout_leftレイアウトから汎用ストライドstd::layout_strideレイアウトへは常に安全に変換可能。異種レイアウト間変換においては、マッピングのずらし幅(stride)に互換性があるケースに限って変換可能。
注：std::mdspanは実データに対する「ビュー」にすぎない。例えば行列の転置(transpose)をmdspan型変換のみで実現することはできない。

double *ptr = /*...*/;

// 2次元ビュー／固定サイズ3x3
using Extents3x3 = std::extents<size_t, 3, 3>;
using MatCpp = std::mdspan<double, Extents3x3 /*std::layout_right*/>;
using MatFortran = std::mdspan<double, Extents3x3, std::layout_left>;
using MatStrided = std::mdspan<double, Extents3x3, std::layout_stride>;

// C++/Fortran互換→汎用レイアウト変換
MatCpp     src_cpp{ptr};
MatFortran src_fortran{ptr};
MatStrided m1{src_cpp};      // OK
MatStrided m2{src_fortran};  // OK

// C++⇔Fortran互換レイアウト変換
MatFortran m3{src_cpp};      // NG
MatCpp     m4{src_fortran};  // NG

// 汎用レイアウト→C++/Fortran互換レイアウト変換
std::array<int, 2> strides{3, 1};
std::layout_stride::mapping<Extents3x3> mapping{{}, strides};
MatStrided src_stride{ptr, mapping};
MatCpp     m5{src_stride};  // OK
MatFortran m6{src_stride};  // NG: 未定義動作(UB)
// strides{3,1}のlayout_stride::mapping<Extents3x3>は
// layout_left::mapping<Extents3x3>と互換性がないため、
// 事前条件(Preconditions)違反となってUBを引き起こす。

double *ptr = /*...*/;

// 1次元ビュー／互換レイアウト(stride={1})
using Extents1D = std::extents<size_t, 10>;
using ArrayRow = std::mdspan<double, Extents1D, std::layout_right>;
using ArrayCol = std::mdspan<double, Extents1D, std::layout_left>;
ArrayRow src_row{ptr};
ArrayCol src_col{ptr};
ArrayCol m1{src_row};  // OK
ArrayRow m2{src_col};  // OK
// 次元数1ではlayout_right/layout_leftレイアウトは同一

その他のコンストラクタ(CTAD)

前掲以外のCTADとして、下記の実引数からのmdspan型推論がサポートされる。

• レイアウトマップLayout::mapping
• レイアウトマップLayout::mapping, 要素アクセサAccessor

関連URL

• (PDF)N4928 Working Draft, Standard for Programming Language C++
• P2554R0 C-Array Interoperability of MDSpan
• https://github.com/kokkos/mdspan
• std::mdspan - yohhoyの日記
• https://gist.github.com/yohhoy/452a3c5d9132182f409df49f3b541028

*1:C配列型からの推論ガイドでは固定サイズ1次元ビューへと推論される。第2引数に std::extents 型をとる推論ガイドでは、固定サイズや動的／固定サイズ混在の std::mdspan 型へと推論可能。

*2:std::dextents は std::extents クラステンプレートの別名(alias)として定義される。

std::mdspan

C++2b(C++23)標準ライブラリに追加される多次元ビューstd::mdspanについて。multidimensional spanの略。

// <mdspan>ヘッダ
namespace std {
  template<
    class ElementType,
    class Extents,
    class LayoutPolicy = layout_right,
    class AccessorPolicy = default_accessor<ElementType>>
  class mdspan;
}

まとめ：

• メモリ領域に対して多次元配列風の要素アクセスビューを提供する。
  • 参照先メモリ領域の所有権を管理しない。*1
  • C++20 std::spanの多次元拡張版。
• mdspanコンストラクタと推論ガイド(deduction guide)が多数提供される（→id:yohhoy:20230308）
• mdspanのコピーは定数時間。
  • 多次元ビューサイズがコンパイル時定数ならポインタ1個分、実行時変数なら ポインタ1個＋インデクス値×次元数(rank) 程度のメモリコピー。
• 要素アクセスには多次元[]演算子を利用。*2。
  • 内部的に多次元インデクスからメモリ領域へのオフセット位置へ換算する。
  • 例：m[1, 2], data[i, j, k]
• Extents：多次元ビューのインデクス型I*3、次元数(rank)、各次元の要素数(extent)。
  • インデクス型Iを明示的に指定する（通常はsize_t型）。*4
  • 次元数はコンパイル時定数として与える。
  • std::extents<I, E1, ... En>：次元数N。各次元の要素数はコンパイル時または実行時(std::dynamic_extent)に決定する。両者は混在可能。*5
  • std::dextents<I, R>：次元数R。全次元の要素数が実行時に決定する。
• LayoutPolicy：多次元ビューのメモリレイアウトをカスタマイズ可能。
  • layout_right：行優先(row major)レイアウト。C/C++互換。
  • layout_left：列優先(column major)レイアウト。FortranやMATLAB互換。
  • ユーザ定義クラスによる高度なカスタマイズもサポートする（→id:yohhoy:20230315）。*6
• AccessorPolicy：要素アクセス方法をカスタマイズ可能。
  • 既定動作は通常のメモリアクセスを行う。メモリ領域ポインタptrに対してptr[index]。
  • Atomicな要素アクセス(std::atomic_ref)や、ヘテロジニアスメモリ環境（GPUなど）を想定したカスタマイズポイント。*7
• C++2b(C++23)時点ではmdspanの “部分ビュー/Slicing” 表現は存在しない。
  • C++2c(C++26)以降に向けてsubmdspanがP2630にて継続検討中。
• 1次元ビューstd::spanとは異なり、範囲for文による要素走査はできない。
  • extent(rank)メンバ関数で各次元の要素数を取得し、多次元インデクスによる要素アクセスを行う。

基本的な利用例

// C++2b(C++23)
#include <array>
#include <mdspan>
#include <print>

int a[] = { 1, 2, 3, 4, 5, 6 };

// 2x3要素の2次元ビュー/動的サイズ
int cols = 2, rows = 3;
std::mdspan m1{a, cols, rows};
for (size_t i = 0; i < m1.extent(0); ++i)
  for (size_t j = 0; j < m1.extent(1); ++j)
    std::println("m1[{},{}]=={}", i, j, m1[i, j]);
// m1[0,0]==1  m1[0,1]==2  m1[0,2]==3
// m1[1,0]==4  m1[1,1]==5  m1[1,2]==6

// 3x2要素の2次元ビュー/固定サイズ
using Mat3x2 = std::mdspan<int, std::extents<size_t, 3, 2>>;
Mat3x2 m2{a};
// m2[0,0]==1  m2[0,1]==2
// m2[1,0]==3  m2[1,1]==4
// m2[2,0]==5  m2[2,1]==6

// 列優先3x2要素の2次元ビュー
using FortranMatrix =
  std::mdspan<int, std::dextents<size_t, 2>, std::layout_left>;
FortranMatrix m3{a, 3, 2};
// m3[0,0]==1  m3[0,1]==4
// m3[1,0]==2  m3[1,1]==5
// m3[2,0]==3  m3[2,1]==6

メモリレイアウト

mdspanではレイアウトポリシーLayoutPolicyに従って、多次元インデクスからメモリ領域オフセット位置への変換を行う。同ポリシーはクラステンプレートmapping<Extents>としてレイアウト・マッピング(layout mapping)特性の問合せインタフェースを定義する。

• required_span_size：変換後にアクセスする可能性のあるメモリ領域の範囲（サイズ）を返す。
• is_(always_)unique：一意性。異なる多次元インデクスが同じオフセット位置を指さない。ある要素に対応する多次元インデクスが1つに定まる。
• is_(always_)exhaustive：網羅性。取りうる多次元インデクスに対応する要素位置に “隙間” がない。全次元の要素数の乗算結果がrequired_span_size()に等しい。*8
• is_(always_)strided：各次元のずらし幅(stride)とインデクス値からオフセット位置を算出。例：3次元ビュー(L x M x N)インデクスi,j,kより((i * M) + j) * N + k。

C++標準ライブラリ提供のレイアウトポリシー特性：

ポリシー	unique	exhaustive	strided
layout_right	true	true	true
layout_left	true	true	true
layout_stride	true	(値に依存)	true

std::layout_stride::mapping<Extents>のis_exhaustiveはオブジェクトの値（各次元のずらし幅）に依存する。is_always_exhaustiveはfalse固定。

using Extents = std::extents<int, 2, 3, 4>;
using Mapping = std::layout_stride::mapping<Extents>;
static_assert(not Mapping::is_always_exhaustive());

std::array<int, 3> strides{12, 1, 3};
Mapping mapper{Extents{}, strides};
assert( mapper.is_exhaustive() );
// mapperは3次元インデクス [i,j,k] のうち
// jの次元を連続メモリ配置(strides[1]==1)
// strides{12, 4, 1}はstd::layout_right相当
// strides{1, 2, 6}はstd::layout_left相当

std::array<int, 3> sparse_strides{1, 4, 16};
Mapping sparse_mapper{Extents{}, sparse_strides};
assert( not sparse_mapper.is_exhaustive() );
// sparse_mapperは3次元インデクス [i,j,k] のうち
// i, jの次元末尾にそれぞれ隙間(padding)が存在

// NG: layout_stride変換は常にuniqueであること
std::array<int, 3> bad_strides{1, 1, 1};
Mapping bad_mapper{Extents{}, bad_strides};
// 事前条件(Preconditions)違反により未定義動作

C++2c以降に向けた提案文書P2642では、BLASやLAPACKライブラリがサポートするオーバーアライン(overaligned)・レイアウトに対応したlayout_left_padded, layout_right_paddedが検討されている。*9

関連URL

• P0009R18 MDSPAN
• https://github.com/kokkos/mdspan
• mdspan in C++: A Case Study in the Integration of Performance Portable Features into International Language Standards, arXiv 2020
• Standard Parallelism, CppCon2021
• MDSPAN A Deep Dive Spanning C++, Kokkos & SYCL, CppCon2022
• Why is mdspan::offset_policy needed?, reddit
• ［C++］WG21月次提案文書を眺める（2021年05月） - 地面を見下ろす少年の足蹴にされる私
• ［C++］WG21月次提案文書を眺める（2022年08月） - 地面を見下ろす少年の足蹴にされる私
• ［C++］WG21月次提案文書を眺める（2022年09月） - 地面を見下ろす少年の足蹴にされる私
• https://twitter.com/yohhoy/status/1577475432605429760

*1:std::string_view(C++17)やstd::span(C++20)と同様の設計。

*2:C++2bに向けて採択済み(PDF)P2128R6の利用。std::mdspan のために提案されたC++言語拡張。C++20現在はP1161R3により operator[] 内でのカンマ(,)利用が非推奨(deprecated)とされている。

*3:Mandates: IndexType is a signed or unsigned integer type

*4:https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2553r1.html

*5:提案文書P0009R18 §2.5引用：The fundamental reason to allow expressing extents at compile time is performance.

*6:提案文書P0009R18 §2.6引用："Custom" layouts besides these could include space-filling curves or "tiled" layouts.

*7:https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0367r0.pdf

*8:提案初期は contiguous となっていたが、P2604R0にて exhaustive へと変更された。

*9:C++2b時点でも std::layout_stride を用いてBLASやLAPACK互換メモリレイアウトを表現できる。P2642では専用レイアウト型を用意することで最適化促進を目指している。

ヌル終端文字列のstd::hash計算

C++標準ライブラリのハッシュ計算ファンクタstd::hashを用いてヌル終端文字列のハッシュ計算を行う場合、ポインタ型に対するstd::hash<const char*>特殊化ではなくstd::hash<std::string_view>特殊化を用いる。*1

下記コードにあるh0では、“文字列” からではなくアドレス値からハッシュ計算されてしまう。*2

#include <cassert>
#include <functional>
#include <string_view>

int main()
{
  char str[] = "Hello";

  // NG: 意図に反してアドレス値からハッシュ計算
  std::hash<const char*> h0;
  assert( h0(str) != h0("Hello") );
  // 変数strと文字列リテラルは異なるアドレス値を持つため
  // （非常に高確率で）ハッシュ値も不一致となる

  // OK: string_view経由で文字列のハッシュ計算
  std::hash<std::string_view> h1;
  assert( h1(str) == h1("Hello") );
  // 文字列"Hello"から同一ハッシュ値が算出される
}

おまけ：2つの文字列リテラルが異なるアドレス値を持つかは未規定。*3

std::hash<const char*> h0;
const char* str = "Hello";
assert( h0(str) != h0("Hello") );  // ??

関連URL

• cppreference: std::hash
• cpprefjp: std::hash

*1:セマンティクス上は std::hash<std::string> でも期待通り動作するが、std::string 型の一時オブジェクト構築オーバーヘッドが生じる。C++11/14 時点では std::string_view が提供されないため、選択肢は std::hash<std::string> のみ。

*2:低品質なC++標準ライブラリ実装もしくは偶発的なハッシュ衝突によって、 h0(str) == h0("Hello") となる可能性もゼロではない。こんなところで運を使わない(・ε・ )

*3:C++20 5.13.5/p14: "Whether all string-literals are distinct (that is, are stored in non overlapping objects) and whether successive evaluations of a string-literal yield the same or a different object is unspecified."

static_assert(false, "was wrong");

プログラミング言語C++におけるconstexpr if文とstatic_assert宣言の組合せに関するメモ。

2023年2月会合にてstatic_assert(false)を許容するP2593R1がCWG 2518へと統合され*1、C++言語仕様に対するDefect Reportとして遡及適用される。*2

CWG 2518適用前のC++言語仕様では、下記コードはプログラマの意図に反して関数テンプレートのインスタンス化より前にコンパイルエラーとなる。

#include <type_traits>

template <typename T>
T doubling(T x)
{
  if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T>) {
    // 算術型の場合は2倍した値を返す
    return x * T{2};
  } else {
    // それ以外の型はコンパイルエラー
    static_assert(false);  // NG（CWG 2518適用前）
    // CWG 2518適用後は上記記述でOK
  }
}

CWG 2518未適用C++コンパイラに対する回避策としては、static_assert宣言に「テンプレートパラメータに依存する(depends)が常にfalseを返す」ヘルパ変数always_false_v<T>などを経由した条件式を指定する。

#include <type_traits>

template <typename T>
constexpr bool always_false_v = false;

template <typename T>
T doubling(T x)
{
  if constexpr (std::is_integral_v<T> || std::is_floating_point_v<T>) {
    // 算術型の場合は2倍した値を返す
    return x * T{2};
  } else {
    // それ以外の型はコンパイルエラー
    static_assert(always_false_v<T>);  // OK
  }
}

CWG 2518適用により、static_assert宣言の評価がインスタンス化タイミングに遅延される。オリジナルの提案文書P2593R1 §3.1より一部引用（下線部は強調）。

This sidesteps the question of whether it’s just static_assert(false) that should be okay or static_assert(0) or static_assert(1 - 1) or static_assert(not_quite_dependent_false). anything else. Just, all static_assert declarations should be delayed until the template (or appropriate specialization or constexpr if substatement thereof) is actually instantiated.

If the condition is false, we’re going to get a compiler error anyway. And that’s fine! But let’s just actually fail the program when it’s actually broken, and not early.

P2593R1 Allowing static_assert(false)

関連URL

• CWG 2518. Conformance requirements and #error/#warning
• P2593R1 Allowing static_assert(false)
• (PDF) P1830R1 std::dependent_false
• (PDF) P1936R0 Dependent Static Assertion
• 本の虫: constexpr ifの落とし穴
• cppreference: if statement, static_assert declaration
• cpprefjp: constexpr if文, コンパイル時アサート

*1:https://github.com/cplusplus/papers/issues/1251#issuecomment-1426545462

*2:https://github.com/cplusplus/papers/issues/1366

std::monostateのハッシュ値

C++標準ライブラリの直和データ型std::variant<...>と組み合わせて空の状態を表すstd::monostateオブジェクトでは、std::hashによるハッシュ計算がサポートされる。*1

各C++処理系で算出されるハッシュ値の一覧（括弧内は併記コメント／定数名）：

• GCC: -7777（__magic_monostate_hash）*2
• Clang: 66740831（return a fundamentally attractive random value.）*3
• MSVC: 1729（Arbitrary value）*4

C++20 20.7.8, 20.7.12より引用。

struct monostate{};

The class monostate can serve as a first alternative type for a variant to make the variant type default constructible.

template<class... Types> struct hash<variant<Types...>>;

The specialization hash<variant<Types...>> is enabled (20.14.18) if and only if every specialization in hash<remove_const_t<Types>>... is enabled. The member functions are not guaranteed to be noexcept.

template<> struct hash<monostate>;

The specialization is enabled (20.14.18).

関連URL

• cppreference: std::hash, std::monostate
• cpprefjp: std::hash, std::monostate

*1:std::hash<std::monostate> 特殊化の存在に気づいた勢いだけで書いた虚無記事。本来の目的は std::variant<std::monostate, Types...> 型のハッシュサポート。

*2:https://github.com/gcc-mirror/gcc/blob/releases/gcc-11.1.0/libstdc++-v3/include/std/variant#L1837

*3:https://github.com/llvm/llvm-project/blob/llvmorg-17-init/libcxx/include/__variant/monostate.h#L56

*4:https://github.com/microsoft/STL/blob/79e80412313b86f9d0f382ad91470292ea2c303c/stl/inc/variant#L1723