C++ std::strong_orderと浮動小数点数型totalOrder

C++20標準ライブラリのstd::strong_order関数オブジェクト*1は、IEEE 754準拠の浮動小数点数型に対する全順序比較（totalOrder predicate）を実装する。

#include <compare>
#include <concepts>
#include <iostream>
#include <limits>
#include <map>
#include <string>

template<std::floating_point T>
struct totalOrder {
  static_assert(std::numeric_limits<T>::is_iec559);
  bool operator()(T x, T y) const noexcept
    { return std::strong_order(x, y) < 0; };
};

using MapType = std::map<double, std::string, totalOrder<double>>;
// using MapType = std::map<double, std::string>; とすると
// キー比較にはstd::less<double>経由で言語組込の比較演算子<が利用され、
// 負のゼロ(-0.)や各種NaNをキーに用いると予期しない結果をもたらす。

const double qnan = std::numeric_limits<double>::quiet_NaN();
const double snan = std::numeric_limits<double>::signaling_NaN();

MapType m;
m[42] = "42";
m[-0.] = "-0";
m[+0.] = "+0";
m[-qnan] = "-qNaN";
m[+qnan] = "+qNaN";
m[-snan] = "-sNaN";
m[+snan] = "+sNaN";

std::cout
  << m[42] << "\n"     // 42
  << m[-0.] << "\n"    // -0
  << m[+0.] << "\n"    // +0
  << m[-qnan] << "\n"  // -qNaN
  << m[+qnan] << "\n"  // +qNaN
  << m[-snan] << "\n"  // -sNaN
  << m[+snan] << "\n"; // +sNaN

ノート：GCC/libstdc++とLLVM/libcxxの浮動小数点数型totalOrder実装は、NaNペイロード部の比較に関してIEEE 754仕様通りではない気がする（§5.10 d-3-iii）。特殊事情でもない限り浮動小数点数型を辞書型キーに使うべきではないし、totalOrder仕様に依存する処理は好ましくないと思う。

C++20 17.11.6/p1-2より一部引用。

1 The name strong_order denotes a customization point object (16.4.2.2.6). Given subexpressions E and F, the expression strong_order(E, F) is expression-equivalent (16.3.11) to the following:

• (snip)
• Otherwise, if the decayed type T of E is a floating-point type, yields a value of type strong_ordering that is consistent with the ordering observed by T's comparison operators, and if numeric_limits<T>::is_iec559 is true, is additionally consistent with the totalOrder operation as specified in ISO/IEC/IEEE 60559.
• (snip)

2 The name weak_order denotes a customization point object (16.4.2.2.6). Given subexpressions E and F, the expression weak_order(E, F) is expression-equivalent (16.3.11) to the following:

• (snip)
• Otherwise, if the decayed type T of E is a floating-point type, yields a value of type weak_ordering that is consistent with the ordering observed by T’s comparison operators and strong_order, and if numeric_limits<T>::is_iec559 is true, is additionally consistent with the following equivalence classes, ordered from lesser to greater:
  • together, all negative NaN values;
  • negative infinity;
  • each normal negative value;
  • each subnormal negative value;
  • together, both zero values;
  • each subnormal positive value;
  • each normal positive value;
  • positive infinity;
  • together, all positive NaN values.
• (snip)

IEEE 754-2019, 3.4, 5.10より一部引用。

3.4 Binary interchange format encodings
(snip)
In binary interchange formats, all number and NaN encodings are canonical.
(snip)

5.10 Details of totalOrder predicate
For each supported arithmetic format, an implementation shall provide the following predicate that defines an ordering among all operands in a particular format:

• boolean totalOrder(source, source)

totalOrder(x, y) imposes a total ordering on canonical members of the format of x and y:

• a) If x < y, totalOrder(x, y) is true.
• b) If x > y, totalOrder(x, y) is false.
• c) If x = y:
  • 1) totalOrder(-0, +0) is true.
  • 2) totalOrder(+0, -0) is false.
  • 3) If x and y represent the same floating-point datum:
    • i) If x and y have negative sign, totalOrder(x, y) is true if and only if the exponent of x ≥ the exponent of y
    • ii) otherwise totalOrder(x, y) is true if and only if the exponent of x ≤ the exponent of y.
• d) If x and y are unordered numerically because x or y is NaN:
  • 1) totalOrder(-NaN, y) is true where -NaN represents a NaN with negative sign bit and y is a floating-point number.
  • 2) totalOrder(x, +NaN) is true where +NaN represents a NaN with positive sign bit and x is a floating-point number.
  • 3) If x and y are both NaNs, then totalOrder reflects a total ordering based on:
    • i) negative sign orders below positive sign
    • ii) signaling orders below quiet for +NaN, reverse for -NaN
    • iii) lesser payload, when regarded as an integer, orders below greater payload for +NaN, reverse for -NaN.

Neither signaling NaNs nor quiet NaNs signal an exception. For canonical x and y, totalOrder(x, y) and totalOrder(y, x) are both true if x and y are bitwise identical.

NOTE -- totalOrder does not impose a total ordering on all encodings in a format. In particular, it does not distinguish among different encodings of the same floating-point representation, as when one or both encodings are non-canonical

関連URL

• GCC Bugzilla, Bug 96526 - implement std::strong_order total order on floating point types
• LLVM Phabricator, D110738 Implement the first half of [cmp.alg]: strong_order, weak_order, partial_order.
• Bit patterns of `float` – Arthur O'Dwyer – Stuff mostly about C++
• IEEE 754の十進浮動小数点数の基本
• cppreference: std::strong_order
• cpprefjp: std::strong_order
• nan("is Not-a-Number") - yohhoyの日記
• https://twitter.com/yohhoy/status/1155099962851483648

*1:関数オブジェクトはCPO(Customization Point Object)として定義される。詳細は id:yohhoy:20190403 を参照。

CUDAのメモリアライメント

CUDAアーキテクチャにおける自然なメモリアライメントは 256 バイト。

CUDA提供のメモリ確保関数（cudaMalloc等）は、少なくとも 256 バイト・アライメントされたアドレスを返す。

Size and Alignment Requirement
(snip)
Any address of a variable residing in global memory or returned by one of the memory allocation routines from the driver or runtime API is always aligned to at least 256 bytes.

CUDA C++ Programming Guide, 5.3.2. Device Memory Accesses

関連URL

• CUDA Data Alignment - Lei Mao's Log Book
• gpu - Why are CUDA memory allocations aligned to 256 bytes? - Stack Overflow
• TensorRT: nvinfer1::IExecutionContext, setTensorAddress

インクリメント on 複素数

プログラミング言語Cの次期仕様C2yでは、複素数型(_Complex float/double/long double)に対するインクリメント／デクリメントが正式サポートされる。gcc/Clangでは独自拡張としてサポート済み。

_Complex double c = 41.;
++c;  // OK: C2y
assert(c == 42.);

ノート：複素数のうち実部(real part)が+1.0／-1.0される。C++標準ライブラリの複素数型std::complex<T>は、C言語とは異なりインクリメント／デクリメントをサポートしない。

gcc 14.2/-pedantic指定時の警告メッセージ：

warning: ISO C does not support '++' and '--' on complex types [-Wpedantic]

Clang 18.1.0/-pedantic指定時の警告メッセージ：

warning: ISO C does not support '++'/'--' on complex integer type '_Complex double' [-Wpedantic]

関連URL

• (PDF) N3259 Support ++ and -- on complex values
• (PDF) N3297 How do you add one to something?

std::submdspanとメモリレイアウト変換

C++2c(C++26)多次元部分ビューstd::submdspan（→id:yohhoy:20240201）によるメモリレイアウト変換のチートシート。

変換結果std::mdspan<T,E,L,A>（→id:yohhoy:20230303）のレイアウトポリシーLは、変換元レイアウトマッピングのsubmdspan_mappingカスタマイズポイントにより下記ルールにて導出される：

• layout_left, layout_rightのとき
  1. レイアウト互換ならば、layout_{left,right}を維持
  2. レイアウト互換ならば、layout_{left,right}_paddedに変換（降格）
  3. layout_strideに変換（降格）
• layout_left_padded, layout_right_paddedのとき
  1. 変換元が0次元（→id:yohhoy:20230309）のとき、layout_{left,right}_paddedを維持*1
  2. レイアウト互換ならば、layout_{left,right}に変換（昇格）*2
  3. レイアウト互換ならば、layout_{left,right}_paddedを維持
  4. layout_strideに変換（降格）
• layout_strideのとき
  1. layout_strideを維持

ノート：C++2c標準ライブラリ提供メモリレイアウト型は、その型情報として layout_LR ＞ layout_LR_padded ＞ layout_stride の順で強い制約条件を表す（LR := left／right）。

関連URL

• P2630R4 Submdspan
• (PDF)P2642R6 Padded mdspan layouts
• cpprefjp: std::submdspan

*1:レイアウトとしては layout_{left,right} 型に昇格可能だが、他メモリレイアウト型における変換元=0次元の挙動に揃えたと考えられる。

*2:この変換条件を満たすのは、変換先=1次元以下かつ要素連続配置が保証されるケースに限られる。

構造化束縛 in 条件式 @ C++26

プログラミング言語C++の次期標準C++2c(C++26)から、if/while/for/switch構文の条件式(condition)部に構造化束縛(structured binding)を記述できる。

// C++2c
if (auto [a, b] = func()) {
  // 関数戻り値からbool型への変換結果がtrueとなるときに限り
  // 戻り値オブジェクトから変数a, bへの分割代入が行われる
}
// 下記コード動作と等価
auto r = func();
if (r) {
  auto [a, b] = r;
  // ...
}

またC++2c採択済み提案文書P2497R0により、std::to_chars／std::from_chars関数の各戻り値型std::to_chars_result／std::from_chars_resultにbool型への変換（→id:yohhoy:20121110）が追加され、構造化束縛による結果取得と変換成功判定ec == errc{}を簡素に記述できるようになる。*1

#include <charconv>

char buf[8];
char* last = buf + sizeof(buf);

// C++17/20/23
if (auto [ptr, ec] = std::to_chars(buf, last, 42); ec == std::errc{}) {
  // ...
}

// C++2c
if (auto [ptr, ec] = std::to_chars(buf, last, 42)) {
  // ...
}

Clang 6.0.0以降は独自拡張として本機能をサポート*2しているが、戻り値オブジェクトの条件評価と分割代入の評価順がC++2c言語機能と異なることに注意。

// Clang独自拡張: 下記コード動作と等価
auto r = func();
if (auto [a, b] = r; r) {
  // ...
}

関連URL

• P0963R3 Structured binding declaration as a condition
• P2497R0 Testing for success or failure of <charconv> functions
• (PDF) P2761R3 Structured binding declaration as a condition
• D39284 Allow conditions to be decomposed with structured bindings
• https://twitter.com/yohhoy/status/1809146730400628872

*1:本来はC++23時点で採択予定だったようだが、手続き上の問題でC++2cに遅延したとのこと。https://github.com/cplusplus/papers/issues/1454

*2:https://github.com/llvm/llvm-project/blob/llvmorg-6.0.0/clang/include/clang/Basic/DiagnosticSemaKinds.td#L417-L419

R.I.P. <strstream>ヘッダ

C++2c(C++26)標準ライブラリでは、ようやく <strstream> ヘッダが削除される。同ヘッダはC++ ISO標準化されたC++98当初から非推奨(deprecated)とされていた。

代替機能として下記C++標準ヘッダが提供するクラス群を利用する。*1

• <sstream>
  • stringstream, istringstream, ostringstream, stringbuf
• <spanstream> ［C++23以降］
  • spanstream, ispanstream, ospanstream, spanbuf

関連URL

• P2867R2 Remove Deprecated strstreams From C++26
• ［C++］WG21月次提案文書を眺める（2023年05月） - 地面を見下ろす少年の足蹴にされる私
• c++ - Why was std::strstream deprecated? - Stack Overflow
• strstream - How will std::spanstream usually be used in C++? - Stack Overflow

*1:本文中では <strstream> ヘッダ提供機能に対応する basic_xxxstream<char>, basic_xxxbuf<char> エイリアス名だけを列挙している。

struct.pack/unpack関数フォーマットにはメモリレイアウトを指定する

Python言語のstructモジュールでは、フォーマット指定先頭文字(@/=/<>/!)にてメモリレイアウト指定を明示すべき。

パック(pack)／アンパック(unpack)フォーマット文字列の省略時デフォルトのメモリレイアウトは、Pythonプログラマの期待に反する可能性が高い。

By default, C types are represented in the machine’s native format and byte order, and properly aligned by skipping pad bytes if necessary (according to the rules used by the C compiler). This behavior is chosen so that the bytes of a packed struct correspond exactly to the memory layout of the corresponding C struct. Whether to use native byte ordering and padding or standard formats depends on the application.

Alternatively, the first character of the format string can be used to indicate the byte order, size and alignment of the packed data, according to the following table:

Character	Byte order	Size	Alignment
@	native	native	native
=	native	standard	none
<	little-endian	standard	none
>	big-endian	standard	none
!	network (= big-endian)	standard	none

If the first character is not one of these, '@' is assumed.

Byte Order, Size, and Alignment

デフォルト動作（@相当）ではC/C++コンパイラの構造体メモリレイアウトに従うため、型指定子の配置順によって意図しないパディング挿入が行われるケースがある。64bitプロセッサ／Native Endian＝Little Endian環境での実行結果。

import struct
from binascii import b2a_hex 
printhex = lambda s: print(b2a_hex(s, ' '))

a, b = 0x12345678, 0x123456789abcdef0

printhex(struct.pack('@Iq', a, b))
# b'78 56 34 12 00 00 00 00 f0 de bc 9a 78 56 34 12'
printhex(struct.pack('=Iq', a, b))
# b'78 56 34 12 f0 de bc 9a 78 56 34 12'
printhex(struct.pack('<Iq', a, b))
# b'78 56 34 12 f0 de bc 9a 78 56 34 12'
printhex(struct.pack('>Iq', a, b))
# b'12 34 56 78 12 34 56 78 9a bc de f0'

printhex(struct.pack('@qI', b, a))
# b'f0 de bc 9a 78 56 34 12 78 56 34 12'
printhex(struct.pack('=qI', b, a))
# b'f0 de bc 9a 78 56 34 12 78 56 34 12'
printhex(struct.pack('<qI', b, a))
# b'f0 de bc 9a 78 56 34 12 78 56 34 12'
printhex(struct.pack('>qI', b, a))
# b'12 34 56 78 9a bc de f0 12 34 56 78'

@指定メモリレイアウトの結果は、一般的なC/C++コンパイラの構造体メモリレイアウトと整合する。*1

#include <stdint.h>

struct S1 {
  uint32_t m1;  // +0: 4byte
  // (padded: 4byte)
  uint64_t m2;  // +8: 8byte
};

struct S2 {
  uint64_t m1;  // +0: 8byte
  uint32_t m2;  // +8: 4byte
};

*1:構造体 S2 ではメンバ変数 m2 に後続して4byteパディングが挿入されるが、structモジュールは末尾パディングを自動挿入しない。