yohhoyの日記

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

AutoClosable#closeメソッドのべき等要件

プログラミング言語Javaのtry-with-resources構文で用いるAutoClosableインタフェース仕様では、closeメソッドのべき等(idempotent)性は要求されない。(実装時には"べき等"が強く推奨される)

void close()
    throws Exception

Closes this resource, relinquishing any underlying resources. This method is invoked automatically on objects managed by the try-with-resources statement.
(snip)
Note that unlike the close method of Closeable, this close method is not required to be idempotent. In other words, calling this close method more than once may have some visible side effect, unlike Closeable.close which is required to have no effect if called more than once. However, implementers of this interface are strongly encouraged to make their close methods idempotent.

https://docs.oracle.com/javase/8/docs/api/java/lang/AutoCloseable.html#close--
void close()
    throws IOException

Closes this stream and releases any system resources associated with it. If the stream is already closed then invoking this method has no effect.

https://docs.oracle.com/javase/8/docs/api/java/io/Closeable.html#close--

関連URL

空っぽの構造体

メンバ変数を1個ももたない空(empty)の構造体は、C++言語ではwell-definedとされるが、C言語ではill-formedとなる。

// C++: OK / C: NG
struct S { };

GCCでは独自拡張として空の構造体を許容するが、標準C++とは異なり構造体サイズが0となることに注意。

// GNU C拡張
struct S {};
printf("%zu", sizeof(struct S));  // 0
// 標準C++
struct S {};
printf("%zu", sizeof(struct S));  // 1

std::mdspan×空間充填曲線

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

C++2b標準ライブラリは、多次元配列表現としてメジャーな行優先(row major)/列優先(column major)レイアウトstd::layout_rightstd::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

*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(使うことあるか?)
2024-02-01追記:C++2c(C++26)標準で追加された、部分ビューを取り出すstd::submdspan関数(→id:yohhoy:20240201)の結果として利用される。

// 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

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>)に型推論される。
2024-05-02:C++2c(C++26)ではP3029R1が採択され、整数リストによる要素数リスト指定CTADにて動的/固定サイズ混在が可能となる(C++23時点では動的サイズ固定)。std::submdspan関数(→id:yohhoy:20240201)へのスライス指定仕様との一貫性向上。

デフォルトコンストラク

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

// 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は指定不可

C++2c:要素数リスト指定コンストラクタ(CTAD)

2024-05-02追記:C++2c以降は要素数リストにおいて整数定数(std::integral_constant互換の定数値)を与えると、対象次元の要素数を固定サイズに推論させることができる。

// C++2c: 整数リストによる要素数指定
double *ptr = /*...*/;

template <int N>
constexpr auto Int = std::integral_constant<int, N>{};

// 2次元ビュー/動的サイズ2x3
std::mdspan m1{ptr, 2, 3};  // OK: CTAD
// 2次元ビュー/固定サイズ2x3
std::mdspan m2{ptr, Int<2>, Int<3>};  // OK: CTAD
// C++2b(C++23)仕様では 動的サイズ2x3 に推論されることに注意

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

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

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::extentsstd::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

*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)レイアウト。FortranMATLAB互換。
    • ユーザ定義クラスによる高度なカスタマイズもサポートする(→id:yohhoy:20230315)。*6
  • AccessorPolicy:要素アクセス方法をカスタマイズ可能。
    • 既定動作は通常のメモリアクセスを行う。メモリ領域ポインタptrに対してptr[index]
    • Atomicな要素アクセス(std::atomic_ref)や、ヘテロジニアスメモリ環境(GPUなど)を想定したカスタマイズポイント。*7
  • C++2b(C++23)時点ではmdspanの “部分ビュー/Slicing” 表現は存在しない。
    • 次期C++2c(C++26)にてmdspanから部分ビューを取り出すsubmdspan関数が追加される(→id:yohhoy:20240201)。
  • 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_exhaustivefalse固定。

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では、BLASLAPACKライブラリがサポートするオーバーアライン(overaligned)・レイアウトに対応したlayout_left_padded, layout_right_paddedが検討されている。*9
2024-06-04追記:2024年3月会合でP2642R6が採択され、C++2c(C++26)標準ライブラリにlayout_left_padded, layout_right_paddedが追加される。

関連URL

*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 を用いてBLASLAPACK互換メモリレイアウトを表現できる。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

*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."