yohhoyの日記

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

Math.min@浮動小数点数の実装

Java標準ライブラリMath.minメソッドの実装についてメモ。

浮動小数点数型(float, double)に対するminでは、NaN(Not a Number)および負のゼロ(-0.0)を考慮する必要がある。*1

public static double min(double a, double b) {
  if (a != a)
    return a;   // a is NaN
  if ((a == 0.0d) && (b == 0.0d)
      && (Double.doubleToRawLongBits(b) == negativeZeroDoubleBits)) {
    // Raw conversion ok since NaN can't map to -0.0.
    return b;
  }
  return (a <= b) ? a : b;
}

// Use raw bit-wise conversions on guaranteed non-NaN arguments.
private static final long negativeZeroDoubleBits
  = Double.doubleToRawLongBits(-0.0d);

2つのdouble値のうち小さいほうを返します。 つまり、結果は負の無限大に近いほうの値となります。 引数の値が同じ場合は同じ値を返します。 どちらかの値がNaNの場合はNaNを返します。 数値比較演算子とは異なり、このメソッドは負のゼロが厳密には正のゼロよりも小さいと見なします。 一方の引数が正のゼロでもう一方が負のゼロの場合は、負のゼロを返します。

https://docs.oracle.com/javase/jp/10/docs/api/java/lang/Math.html#min(double,double)

一方、整数型(int, long)に対するminは比較演算<=を用いてシンプルに実装される。*2

public static int min(int a, int b) {
  return (a <= b) ? a : b;
}

関連URL

C++ min/maxアルゴリズムの正しい実装

C++標準ライブラリstd::min, std::maxアルゴリズムの動作仕様についてメモ。
問題:C++ min/maxアルゴリズムを「正しく」実装せよ。

template <typename T>
const T& min(const T& a, const T& b)
{
  // どちらのmin実装が正しい?
  return a < b ? a : b;  // #1
  return b < a ? b : a;  // #2
}

template <typename T>
const T& max(const T& a, const T& b)
{
  // どちらのmax実装が正しい?
  return a < b ? b : a;  // #3
  return b < a ? a : b;  // #4
}

答え:#2 と #3

2個の値を比較するmin/maxアルゴリズムでは、値が等価(equivalent)*1なときは1番目の値を返すと規定されている。実装#1や#4ではC++標準ライブラリの仕様違反となる。C++03 25.3.7/p2-3, p5-6より引用。

template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
  const T& min(const T& a, const T& b, Compare comp);

2 Returns: The smaller value.
3 Remarks: Returns the first argument when the arguments are equivalent.

template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
  const T& max(const T& a, const T& b, Compare comp);

5 Returns: The larger value.
6 Remarks: Returns the first argument when the arguments are equivalent.

関連URL

*1:C++標準ライブラリでは a < b が偽かつ b < a が偽のとき、a と b は等価(equivalent)とみなす。

move in accumulateアルゴリズム

C++20標準ヘッダ<numeric>のstd::accumulateアルゴリズム内部実装では、T型のアキュムレータ変数(acc)への累積操作時にstd::move関数適用(右辺値への変換)が規定される。

// C++20仕様の累積演算(1要素あたり)
acc = std::move(acc) + *iterator;
//    ^^^^^^^^^^^^^^
//    右辺値

// C++17仕様の累積演算(1要素あたり)
acc = acc + *iterator;
//    ^^^
//    左辺値

C++17以前の標準ライブラリ仕様では左辺値に対する演算となっていたが、右辺値に変更されたことで(代入右辺の)accオブジェクトに対する破壊的操作が可能となり、より効率的な実装が選択される可能性が広がる。

本ライブラリ仕様変更の提案文書P0616R0では、事前メモリ確保した文字列型に対する累積(連結)操作において大幅な性能改善を報告している。*1

1 Motivation
(snip)

A very simple measurement program showing the difference of using accumulate with strings with or without move show a significant improvement for that case (150 to over 200 times faster with concatenating 10000 short strings, with the additional potential of pre-allocating the whole string size up front when using move). (snip)

同様の改善はinner_product, partial_sum, adjacent_differenceアルゴリズムに対しても適用される。

C++20

C++20 25.10.2/p2より引用(下線部は強調)。

template <class InputIterator, class T>
  constexpr T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  constexpr T accumulate(InputIterator first, InputIterator last, T init, 
                         BinaryOperation binary_op);

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = std::move(acc) + *i or acc = binary_op(std::move(acc), *i) for every iterator i in the range [first, last) in order.

C++17以前

C++17 29.8.2/p2より引用。

template <class InputIterator, class T>
  T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  T accumulate(InputIterator first, InputIterator last, T init, 
               BinaryOperation binary_op);

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order.

関連URL

どうしてstd::basic_iosは否定演算子(!)オーバーロードを提供するの?

C++標準ライブラリのI/Oストリーム基底クラステンプレートstd::basic_iosが否定演算子!オーバーロードを提供する理由。本記事の内容はStackOverflowで見つけた質問と回答に基づく。

答え:歴史的理由

標準化前のC++言語仕様では暗黙の型変換に関する仕様が曖昧であり、operator!演算子オーバーロード以外でI/Oストリームから真偽値へと変換する手段がなかったとのこと。つまりif (!s)のような否定形でしか記述できなかったらしい。

C++03

C++03ではoperator void*ユーザ定義変換が追加提供され、if (s)if (!s)のいずれの書き方も可能となった。C++03 27.4.4.3/p1より引用。

operator void*() const;

1 Returns: If fail() then a null pointer; otherwise some non-null pointer to indicate success.

bool operator!() const;

2 Returns: fail().

C++11/14/17/20

operator void*ユーザ定義変換にはプログラマの意図とは異なる動作を引き起こすリスク(→id:yohhoy:20120406)があるためC++11にて削除され、代わりに導入されたexplicit operator bool*1によってif (s)表記がサポートされる。また仮にoperator!オーバーロードが提供されなくとも、if (!s)表記でもexplicit operator boolが利用されるようになる。

C++20現在も後方互換性のためoperator!オーバーロードは提供される。C++20 29.5.5.4/p1-2より引用。

explicit operator bool() const;

Returns: !fail().

bool operator!() const;

Returns: fail().

関連URL

OpenMP 5.2仕様リリース

2021年11月 OpenMP 5.2仕様リリース記事 OpenMP ARB Releases OpenMP 5.2 with Improvements and Refinements より抄訳。

OpenMP仕様バージョン5.2はOpenMP ARB、主要なコンピュータハードウェア/ソフトウェアベンダのグループ、そしてOpenMPコミュニティのユーザによって共同開発されました。改訂仕様は下記の主要な機能追加を含みます:

  • 非構造化データオフロード利用の簡略化。target enter datatarget exit data)におけるmap指示節のデフォルトマップ型は、tofrom)におけるマップ型と同じ振舞いを提供します。
  • ユーザ定義マッパーサポートの拡張。declare mapperディレクティブが追加の修飾句を受け付けるよう拡張されました。
  • メモリアロケータの改善。Fortran側で確保した変数に対してOpenMPアロケータ利用をサポートするためにallocatorsコンストラクトとallocateディレクティブの実行可能形式が追加され、dispatchコンストラクトが追加のendディレクティブをとるよう拡張されました。
  • FortranのPUREプロシージャ利用の改善。PUREプロシージャ*1で許可されるディレクティブが、最適化ヒント(assumption)ディレクティブ、nothingerrorディレクティブ、メタディレクティブ、ループ変形コンストラクトを含むよう拡張されました。
  • スコープコンストラクト利用の改善。scopeコンストラクトにおいてallocateおよびfirstprivate指示節が許可されます。
  • リニア指示節*2の一貫性向上。他の指示節と一致するようlinear指示節が改訂されました。
  • OpenMPディレクティブ構文の改良。より簡潔で一貫性のある構造になります。*3

関連URL

*1:副作用を持たない、いわゆる純粋関数のこと。

*2:OpenMP 4.0で追加されたSIMD化を制御するための指示節。OpenMP 4.5からループ並列化へも適用可能に拡張された。

*3:前バージョンOpenMP 5.1と比べると、OpenMP 5.2仕様書の文書構造が大幅に書き換えられている。(PDF) OpenMP 5.2 is Here! によれば "Large portions of specification now generated from JSON-based database" とのこと。

C++コルーチン送出例外のハンドリング戦略

C++20コルーチンからの例外送出ハンドリングに関するメモ。C++コルーチンライブラリの設計者向け。

C++コルーチン言語仕様では、コルーチン送出例外ハンドリングのカスタマイズポイントとしてpromise_type::unhandled_exception関数を規定する。プログラマが記述したコルーチン本体処理に対して、C++コンパイラは下記のようなコード展開を行う(一部は簡略化)。

/* コルーチンの展開後コード */ {
  promise_type _promise;
  try {
    co_await _promise.initial_suspend();
    /* コルーチン本体処理 */
  } catch (...) {
    _promise.unhandled_exception();  // ★
  }
  co_await _promise.final_suspend();
}

C++コールチンライブラリ設計者の選択肢としては、3種類の例外ハンドリング戦略が考えられる。

  • [A] コルーチンの呼出元(caller)/再開元(resumer)にそのまま例外伝搬させる。ジェネレータ(generator)などの同期型コルーチン向け。
  • [B] コルーチンの戻り値型オブジェクトに例外保持しておき、値の読み取りタイミングで例外再スローする。並行タスクや非同期I/Oなどの非同期コルーチン向け。
  • [C] 例外送出=プログラム異常終了(std::terminate)。

それぞれの例外ハンドリングにおけるpromise_type::unhandled_exception実装イメージは下記の通り。

// [A] 再スロー
void unhandled_exception()
{
  throw;  // 現在の例外を再スロー
  // コルーチン処理と呼出元は同一スレッドの前提。
  // コルーチンの呼出元(caller)/再開元(resumer)に
  // コルーチン内部から送出された例外が伝搬する。
}

// [B] 例外保持
void unhandled_exception()
{
  ep_ = std::current_exception();
  // コルーチン処理と値の取出操作は別スレッドの可能性あり。
  // メンバ変数 std::exception_ptr ep_; に格納しておき、
  // コルーチン計算結果の取出操作メンバ関数の実装にて
  // 値を返す代わりに std::rethrow_exception(ep_); を実行。
}

// [C] プログラム停止
void unhandled_exception()
{
  std::terminate();
}

選択肢[A]の動作は、C++20統合前のC++コルーチン拡張Coroutine TSに対するP0664R6 Issue#25にて明言されている。

25. Allow unhandled exception escape the user-defined body of the coroutine and give it well defined semantics

The proposed resolution is to eliminate the undefined behavior in the following manner:

  • Allow an exception to escape p.unhandled_exception() and, in that case, consider the coroutine to be at the final suspend point. Reminder: when a coroutine is at the final suspend point, the coroutine can only be destroyed and a call to member function done() of the coroutine handle associated with that coroutine returns true.
  • Eliminate possibility of an exception being thrown from evaluation of an expression co_await p.final_suspend() by stating that final_suspend member function of the coroutine promise and await_resume, await_ready, and await_suspend members of the object returned from final_suspend shall have non-throwing exception specification.

This resolution allows generator implementations to define unhandled_exception as follows:

void unhandled_exception() { throw; } 

With this implementation, if a user of the generator pulls the next value, and during computation of the next value an exception will occur in the user authored body it will be propagate back to the user and the coroutine will be put into a final suspend state and ready to be destroyed when generator destructors is run.

P0664R6 C++ Coroutine TS Issues

関連URL

コルーチン×ラムダ式キャプチャ=鼻から悪魔

C++20 コルーチンとキャプチャありラムダ式の組合せは、キャプチャ変数の生存期間(lifetime)切れによる未定義動作(undefined behavior)を引き起こすリスクが高く、原則として併用すべきでない。

要約:ラムダ式でキャプチャした変数はコルーチン中断時にコルーチンフレーム*1に退避されない。キャプチャ変数はコルーチンフレームに退避されない。大事なことなので二回言いました。

C++20現在は標準コルーチンライブラリを提供しないため*2、ここでは次期C++2b(C++23)向け提案(PDF)P2168R3std::generator<T>を用いたコード例示を行う。
2022-08-01追記:C++2b向けに後継提案文書(PDF)P2502R2が採択され、<generator>ヘッダとstd::generator導入が決定している。id:yohhoy:20220801 参照。

#include <iostream>
#include <generator>  // P2168R3

// NG: キャプチャありコルーチンラムダ式
void f(int n)
{
  // (1) co_yield式により クロージャ型::operator() はコルーチンとなる。
  // またラムダ式内部からは「関数fのローカル変数n」へは直接アクセスできず、
  // 「クロージャオブジェクトのメンバ変数として保持されたn」に自動変換される。
  auto gen = [n]() -> std::generator<int> {
    // (3) std::generatorのpromise_type定義よりコルーチン本体実行前の
    // 初期サスペンドポイント(initial_suspend)にて実行を中断する。

    // (6) 「メンバ変数として保持されたn」は生存期間が終了しているため、
    // 下記for文において変数名nへのアクセスが未定義動作を引き起こす!
    for (int i = 0; i < n; i++) {
      co_yield i;
    }
  }();
  // (2) IILE(Immediately-Invoked Lambda Expression)イディオムを用いて、
  // ローカル変数nをキャプチャしたクロージャオブジェクトを即時評価する。

  // (4) この時点でラムダ式によるクロージャオブジェクトは破棄済みとなり、
  // 同メンバ変数として保持されたnの生存期間もまた終了している。

  // (5) 範囲for文によりgen.begin()が呼び出されてコルーチン再開する。
  for (int i: gen) {
    std::cout << i;
  }
}

// OK: キャプチャ無しコルーチンラムダ式
void g(int n)
{
  // (1) 変数キャプチャでなはく引数ありラムダ式として定義する。
  // ラムダ式内部では「コルーチンフレームで保持されるn」へアクセスする。
  auto gen = [](int n) -> std::generator<int> {
    // (3) 初期サスペンドポイント(initial_suspend)にて中断される。
    // 引数nはコピーされてコルーチンフレーム上に格納される。

    // (6) コルーチンフレームで保持されるnへアクセスする。
    for (int i = 0; i < n; i++) {
      co_yield i;
    }
  }(n);
  // (2) IILEイディオムにより変数nを実引数として渡す。

  // (4) この時点でラムダ式によるクロージャオブジェクトは破棄済み。

  // (5) 範囲for文によりgen.begin()が呼び出されてコルーチン再開する。
  for (int i: gen) {
    std::cout << i;
  }
}

ラムダ式キャプチャに関するこの振る舞いは、キャプチャ動作はラムダ式によるクロージャオブジェクト生成時に1回だけである一方、コルーチンラムダ式クロージャ型のoperator())は複数回呼び出されうる*3という差異に起因する。例えば Move-only 型を前者でムーブキャプチャした場合、後者で同オブジェクトをコルーチンフレームへとコピー退避することができない。*4

メモ:次期C++2b(C++23)で導入されるP0847R7 "Deducing this" 機能(→id:yohhoy:20211025)を使っても、本問題は未解決もしくは仕様規定が曖昧に思える。*5
2022-10-05追記:根本的な解決策ではないがReddit関連スレッドにて、[n](this auto self){ ... }ラムダ式中でnの代わりにself.nと記述する方法が紹介されている。

例えば facebook/folly C++ライブラリでは、キャプチャありコルーチンラムダ式を安全に呼び出すためのfolly::coro::co_invokeヘルパ関数を実験的に提供する。*6

Lambdas
You can implement a lambda coroutine however you need to explicitly specify a return type - the compiler is not yet able to deduce the return type of a coroutine from the body.

IMPORTANT: You need to be very careful about the lifetimes of temporary lambda objects. Invoking a lambda coroutine returns a folly::coro::Task that captures a reference to the lambda and so if the returned Task is not immediately co_awaited then the task will be left with a dangling reference when the temporary lambda goes out of scope.

Use the folly::coro::co_invoke() helper when immediately invoking a lambda coroutine to keep the lambda alive as long as the Task.

https://github.com/facebook/folly/blob/main/folly/experimental/coro/README.md#lambdas

関連URL

*1:C++言語仕様上はコルーチンフレーム(coroutine frame)ではなく coroutine state が正式名称。本文中ではより一般的な “コルーチンフレーム” を用いた。

*2:C++20時点では言語仕様へのコルーチン導入と、コルーチンライブラリ作成者向けの低レイヤ・ライブラリのみが提供される。

*3:本文中コードはIILEイディオムによりコルーチンは1回しか呼び出されないが、C++構文上で1回のみ呼び出し/複数回呼び出しの可能性を判別できない。例えばRust言語では型システムにより両者を判別可能。

*4:https://www.reddit.com/r/cpp/comments/qmes0e/a_capturing_lambda_can_be_a_coroutine_but_you/hj9b352/

*5:https://twitter.com/yohhoy/status/1458091760777900037

*6:https://github.com/facebook/folly/blob/main/folly/experimental/coro/Invoke.h