質問に対する回答

質問の歴史

C++20以前は、2つの整数またはポインタの算術平均を計算するためには手動での実装が必要であり、通常は単純な式(a + b) / 2を使っていました。しかし、このアプローチは、合計が型が表現できる最大値を超えると未定義の動作を引き起こします。std::midpointはC++20で標準化され、<numeric>ヘッダー内で、符号付き整数のオーバーフローを引き起こすことなく、整数型およびポインタ型の全ドメインにわたって正しい結果を保証する可搬性、constexpr、noexceptなソリューションを提供します。

問題点

符号付き整数のオーバーフローはC++において未定義の動作です。C++20の2補数の義務があってもです。2つの大きな正の符号付き整数（例えば、INT_MAXの近く）を平均化すると、その合計はオーバーフローします。同様に、2つの大きな負の整数の場合、合計はアンダーフローする可能性があります。ポインタの算術もオーバーフローが起きると未定義の動作になりますが、同じ配列内の2つのポインタ間の差はstd::ptrdiff_tに収まることが保証されているため、整数の加算に存在するオーバーフローのリスクが排除されます。検討すべき課題は、加算に伴うオーバーフローを回避しつつ、符号が異なる入力に対しての正確さを維持することを可能にする整数の平均化アルゴリズムの実装です。

解決策

符号付き整数の場合、std::midpointはオーバーフローを避けるために、オペランドを減算の前に無符号の対応する型に変換します。(unsigned_type(a) - b) / 2としつつ、a > bの場合はa - (unsigned_type(a) - b) / 2とすることで平均を計算します。これにより、数値間の半分の距離を計算するために、入力を超える大きさの中間値を決して生成することなく、無符号型の明確に定義された剰余算術を利用します。ポインタの場合、実装は単にfirst + (last - first) / 2を使用し、(last - first)の差は明確に定義され、表現も可能であり、それを2で割ることで次の加算も配列の有効範囲内に留まります。

#include <numeric>
#include <limits>
#include <iostream>

int main() {
    int a = std::numeric_limits<int>::max() - 10;
    int b = std::numeric_limits<int>::max() - 2;
    
    // int naive = (a + b) / 2; // 未定義の動作：オーバーフロー
    int safe = std::midpoint(a, b); // 明確に定義されている：max - 6を返す
    
    int arr[] = {1, 2, 3, 4, 5};
    int* mid = std::midpoint(&arr[0], &arr[4]); // arr[2]を指す
}

実生活の状況

問題の説明

高頻度取引プラットフォームにおいて、システムはUnixエポックからのナノ秒で表された2つの注文タイムスタンプ間の時間的な中間点を計算する必要がありました。市場オープン直前のストレステスト中に、タイムスタンプがINT64_MAXに近づいたとき、従来の計算(t1 + t2) / 2が符号付き整数のオーバーフローによって間欠的にクラッシュを引き起こし、注文マッチングエンジンの優先キューのロジックが破損しました。

検討された異なるソリューション

ソリューション 1: ビルトイン拡張精度型の使用 チームは中間計算のために__int128_tにキャストし、再びキャストバックすることを検討しました。このアプローチは、サポートされているコンパイラ（GCC、Clang、MSVC）で正しい算術を保証します。しかし、厳格なC++17準拠が必要な組込みターゲットへの移植性が欠けており、128ビットのエミュレーションがコスト高の32ビットアーキテクチャにおいて微妙なパフォーマンスの低下を引き起こしました。

ソリューション 2: 無符号算術キャスト 両方のタイムスタンプをstd::uint64_tに変換し、平均を計算し、再び戻すことが提案されました。これは正の値に対してオーバーフローを回避しますが、歴史的なタイムスタンプ（符号付き表現の下での負の値）を扱うときに実装定義された結果を生じさせるため、無符号の変換で負の値が大きな正の値（2の補数のラップアラウンド）を生成し、ゼロを跨ぐ計算において数学的に間違った平均をもたらします。

ソリューション 3: オーバーフローチェックを伴う手動ブランチング オペランドの符号を確認し、条件に応じてa + (b - a)/2またはビット単位の操作を使用するカスタム関数を実装することが検討されました。これにより、正確さが提供されますが、ブランチのオーバーヘッドと複雑さが増します。複数の数値領域（座標、価格、タイムスタンプ）にわたってこのロジックを維持することはDRY原則に違反し、保守エラーのリスクを引き起こしました。

ソリューション 4: C++20 std::midpointの採用 ツールチェーンをC++20にアップグレードし、std::midpointを使用することで、ゼロオーバーヘッドの抽象化が提供され、符号が異なる入力や整数ドメインの限界に近い値を含むすべてのエッジケースを適切に処理しました。

選択されたソリューションと結果

チームはソリューション 4を選択し、計算レイヤをC++20に移行しました。この変更により、運用中のオーバーフローによるクラッシュが排除され、安全な数学ユーティリティのコードベースが200行減少し、ブランチロジックを削除することでキャッシュのローカリティが改善されました。回帰テストは、x86-64上での単純なアプローチと同じパフォーマンスを確認し、コンパイル時定数に対するconstexpr評価の追加的な利点も得られました。

候補者が見落としがちな点

質問 1: なぜ符号付き整数を無符号型にキャストすることは一般的な中間計算には不十分なのですか？

回答無符号算術は2^Nの剰余でラップしオーバーフローを回避しますが、負の符号付き整数を無符号に変換すると大きな正の値になります（例えば、-1はUINT_MAXになります）。無符号算術を通じて正のタイムスタンプと負のタイムスタンプを平均化すると、結果は正しい符号付きの平均ではなく無符号の範囲の中間近くになります。std::midpointは符号を維持し、差が奇数のときに最初の引数に向かって正しく丸められるため、最終結果のために無符号のラップアラウンドに頼ることなく符号ビットを正しく処理します。

質問 2: std::midpointがポインタについて特定のオブジェクトモデルの制約の下で未定義の動作を引き起こすのはどのような場合ですか？

回答 std::midpointは、両方のポインタが同じ配列オブジェクトの要素（または最後の要素の1つ後）を指していることを要求します。ポインタが異なる配列や無関係なメモリを参照している場合、未定義の動作になります。これは、整数の中間点との微妙な違いであり、候補者はしばしばこれが単純な数値平均のように機能すると仮定し、ポインタ演算における厳密なエイリアスやオブジェクトモデルの要件を見逃します。

質問 3: std::midpointは整数と異なり、特にNaN値に関して浮動小数点型についてどのように振る舞いますか？

回答浮動小数点型に対して、std::midpointは合計でのオーバーフローやアンダーフロー（間違って無限大またはゼロを生成する可能性がある）を防ぐために、実装に定義された戦略を使用し、通常はa/2 + b/2と同等です。重要なのは、いずれかの引数がNaNの場合、std::midpointはNaNを返すことです。一方が正の無限大で、もう一方が負の無限大の場合、NaN（不定）を返しますが、整数の中間点は単純にオーバーフローするかラップするだけになります。候補者は、IEEE 754の特別な値の伝播ルールを考慮せずに、単純な算術が行われると仮定することが多いです。