2015-10-26

C++標準化委員会の文書のレビュー: P0030R0-P0039R0

[PDF] P0030R0: Proposal to Introduce a 3-Argument Overload to std::hypot

C++11で追加されたstd::hypotに3引数版のオーバーロードを追加する提案。

std::hypot( x, y )は、\(\sqrt{ x^2 + y^2}\)を、計算過程でオーバーフロー、アンダーフローが発生しない方法で計算する関数だ。

hypotの応用方法として、二次元空間における2点間の距離の計算、\(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\) に使える。

struct point
{ double x, y ; } ;

double dist( point a, point b )
{
    return std::hypot( a.x - b.x, a.y - b.y ) ;
}

しかし、多くの分野では、三次元空間における2点間の距離を計算、、\(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 (z_q - z_2)^2}\)したいことがよくある。hypotは2引数なので、現状では以下のように使わなければならない

struct point
{ double x, y, z ; } ;

double dist( point a, point b )
{
    return std::hypot( a.x - b.x, std::hypot( a.y - b.y, a.z - b.z ) ) ;
}

hypotに3引数版のオーバーロードを追加すると、以下のように書ける。


std::hypot( a.x - b.x, a.y - b.y, a.z - b.z ) ;

論文では、Variadic templatesを利用した任意個の引数を取る汎用的な関数の提案も考えたが、そのような関数の利用例が明らかではないとして、今回の提案では3引数版のみにとどめたという。

P0031R0: A Proposal to Add Constexpr Modifiers to reverse_iterator, move_iterator, array and Range Access

array, reverse_iterator, move_iteratorをconstexprに対応させる提案。

P0032R0: Homogeneous interface for variant, any and optional

現在提案されているvariant, any, optionalには、機能は同じだがメンバー名や引数などが異なるメンバーがあるので、統一を図る。

P0033R0: Re-enabling shared_from_this

現行のenable_shared_from_thisの文面では、挙動が明確に規定されていないコードが存在してしまう。

enable_shared_from_thisは、shared_ptrで管理する型の基本クラスとすることで、shared_from_thisというメンバー関数を追加できる。このメンバー関数を呼び出すと、そのオブジェクトを所有している既存のshared_ptrが返される。以下のように使える。

// CRTPとして使う
struct X : public std::enable_shared_from_this<X>
{ } ;

int main()
{
    auto sp1 = std::make_shared<X>() ;

    // sp1と所有権を共有するshared_ptrが得られる
    auto sp2 = sp1->shared_from_this() ; 
}

ところが、現行の文面では、以下のようなコードの挙動が未定義になってしまう。

int main()
{
  struct X : public enable_shared_from_this<X> { };
  auto xraw = new X;
  shared_ptr<X> xp1(xraw);  // #1
  { // 破棄時にdeleteしないので安全
    shared_ptr<X> xp2(xraw, [](void*) { });  // #2
  }
  xraw->shared_from_this();  // #3
}

shared_from_thisの前提条件として、オブジェクトを所有するshared_ptrのオブジェクトが存在しなければならない。このコードでは、存在している。問題は、複数のshared_ptrが独立して存在しているということだ。ただし、後から構築される#2のオブジェクトのデリーターは何もしないので、このコードは二重にdeleteするという問題はない。すると、このコードは合法なのだろうか。

しかし、合法だとして、この場合はどちらのshared_ptrと所有権を共有するオブジェクトが返るのだろうか。#1だろうか、#2だろうか。

#1が返る場合、#2のshaared_ptrの構築時には、xraw->_weak_thisがアップデートされないことになる。#2が返る場合、アップデートされる。

問題は、shared_from_thisのpostconditionに照らし合わせると、どちらの挙動もweak_ptrがらみのpostconditionを満たせないので、規格上挙動が規定されていない。

さて、既存の実装であるDinkumware, GNU, LLVMの実装は、いずれも#2が_weak_thisをアップデートする挙動になっている。これは設計上意図的なものではない。

一方、Boostの実装では、ユーザーの意見を取り入れた結果、#2は_weak_thisをアップデートしない挙動に意図的にしている。つまり、一番最初に作られたshared_ptrと所有権を共有するshared_ptrを返す。

現在、既存の実装の挙動に依存したコードはなく、Boostの挙動の方が実際の需要があるため、Boostの挙動にあわせる変更を提案している。

また、この提案では、weak_ptrを得るweak_from_thisの追加も提案されている。

P0034R0 – Civil Time

軽量な日付ライブラリの提案。

Boost. Date Timeはあまりにも巨大すぎるし、作者が標準ライブラリに追加することに興味を示していないので、軽量な日付ライブラリを提案している。

このライブラリは、グレゴリオ暦以前の日付はtime_tのオーバーフロー、time_t以上の精度でうるう秒を扱うことは考慮しない。タイムゾーンが使える。

P0035R0: Dynamic memory allocation for over-aligned data

待望のオーバーアライメントしてくれる確保関数の提案。

C++の現行規格では、確保関数はオーバーアライメントする必要はない。例えば、floatのアライメントが4バイトで、SIMD命令の都合上、floatの配列を16バイトアライメントしたいとする。以下のようなコードを書いても、16バイトアライメントされる保証はない。

class alignas(16) float4 {
 float f[4];
};
float4 *p = new float4[1000];

C++の規格上は4バイトアライメントされれば十分なのだ。オーバーアライメントは規格上必須ではない。

シグネチャは以下のようになる。

namespace std {
    enum class align_val_t: size_t;
}
void* operator new(std::size_t size, std::align_val_t alignment);
void* operator new(std::size_t size, std::align_val_t alignment,
   const std::nothrow_t&) noexcept;
void operator delete(void* ptr, std::align_val_t alignment) noexcept;
void operator delete(void* ptr, std::align_val_t alignment,
   const std::nothrow_t&) noexcept;
void* operator new[](std::size_t size, std::align_val_t alignment);
void* operator new[](std::size_t size, std::align_val_t alignment,
   const std::nothrow_t&) noexcept;
void operator delete[](void* ptr, std::align_val_t alignment) noexcept;
void operator delete[](void* ptr, std::align_val_t alignment,
   const std::nothrow_t&) noexcept;

P0036R0: Unary Folds and Empty Parameter Packs (Revision 1)

folding expressionに空のパラメーターパックを指定した時のフォールバックを、operator &&, operator ||, operator , だけに留める提案。

デフォルトで0が変えるとまずい場合がある。

P0037R0: Fixed_Point_Library_Proposal

固定少数点ライブラリの提案。

template < class ReprType, int Exponent >
class fixed_point ;

ReprTypeは内部でつかう整数型で、Exponentは、ビットを指定された数だけシフトする。fixed_pointの精度は、pow(2, Exponent)であり、最小値と最大値は、pow(2, Exponent)にstd::numeric_limites<ReprType>::min()/max()を掛けた値になる。

Exponentを指定するのは面倒だ。固定少数は、基数ビット数と少数ビット数を記述することで指定できる。プログラマーの多くはこの記述方法を好む。

そこで、fixed_pointのエイリアスが用意される。

template <unsigned IntegerDigits, unsigned FractionalDigits = 0, bool IsSigned = true>
    using make_fixed ;

template <unsigned IntegerDigits, unsigned FractionalDigits = 0>
    using make_ufixed ;

例えば、8bitの符号なしの固定少数で、基数と少数のビット数にそれぞれ4ビット割り当てたい場合は、

make_ufixed<4, 4> value{ 15.9375 } ;

32bit、符号あり、基数が2ビット、少数が29ビットにしたい場合は、

make_fixed<2, 29> value { 3.141592653 } ;

固定少数と組み込みの整数型は相互に明示的に変換できる。

丸め誤差は発生する。

make_ufixed<4, 4>(.006) == make_ufixed<4, 4>(0)

このコードは丸められた結果trueとなり得る。

整数に普通に使える演算子は固定少数にもオーバーロードされていて普通に使える。シフト演算子と比較演算子以外では、二項演算子は固定少数同士や、固定少数と他の演算型を組み合わせてオペランドに取れる。

組み合わせが同じ固定少数型ではない場合、簡単なプロモーション風のルールによって、戻り値の型が決定される。

  1. どちらの実引数も固定少数の場合、大きなサイズの型が選ばれる。どちらか片方が符号付きならば、符号付きになる
  2. どちらかの実引数が浮動小数点数型の場合、結果の型は入力と同じかそれ以上大きい、最小の浮動小数点数型になる
  3. どちらかの実引数が整数型の場合、結果は他方の固定少数型になる

make_ufixed<5, 3>{8} + make_ufixed<4, 4>{3} == make_ufixed<5, 3>{11};  
make_ufixed<5, 3>{8} + 3 == make_ufixed<5, 3>{11};  
make_ufixed<5, 3>{8} + float{3} == float{11};  

提案では、このプロモーションルールの理由を、挙動を簡単に推測できるためとパフォーマンス上の理由から、各ルールについて以下のように説明している。

  1. 固定少数のみが使われていた場合に、最小の計算のみが行われることを保証する。
  2. 型を混ぜた演算のプロモーションルールをまねた。固定少数の範囲から外れるようなexponentを持つ値も作り出せるようにし、浮動小数点数から整数へのコストのかかる変換を避ける
  3. 入力として与えられた固定少数型を維持する。処理に重要なのは意図的に固定少数型である

シフト演算子は右辺に整数型を取り、オーバーフロー、アンダーフローしない新しい型を返す。

比較演算子は、プロモーションルールにしたがって入力を共通の型に変換した上で、比較して、結果をtrueかfalseで返す。

符号付きと符号なしの固定少数のオーバーフローは、未定義の挙動となる。符号なしの整数型のオーバーフローの挙動が規定されている基本型とは異なる。

// オーバーフローの例
make_fixed<4, 3>(15) + make_fixed<4, 3>(1)

アンダーフローが発生して精度が失われることは許容されている。


make_fixed<4, 3>(15) + make_fixed<4, 3>(1) ;

この結果は7になるが、これは許容されている。

ただし、すべてのビットがアンダーフローによって失われた場合、その値は「フラッシュされた」状態になり、未定義の挙動となる。

固定少数の精度を上下させるpromote/demote関数がある。これは、基数部と小数部のビット数をそれぞれ、2倍、1/2倍する。

// make_fixed< 4, 4 >
promote( make_fixed< 2, 2 >(1) ) ;
// make_fixed< 2, 2 >
promote( make_fixed< 4, 4>(1) ) ;

オーバーフローを防ぐために精度を上げつつ計算する関数が用意されている。

単項演算子としては、trunc_reciprocal, trunc_square, trunc_sqrt, promote_reciprocal, promote_square

二項演算子としては、trunc_add, trunc_subtract, trunc_multiply, trunc_divide, trunc_shift_left, trunc_shift_right, promote_add, promote_sub, promote_multiply, promote_divide

trunc_は、入力よりも大きくはない結果を返すが、exponent部分をオーバーフローを避けるために変更される。

promote_は、オーバーフローとアンダーフローが起きないほど十分に大きな型を結果として返す

_multiplyと_squareは、64bit型には提供される保証がない。

_multiplyと_squareは、入力が最小負数である場合、未定義の挙動となる。

_squareは符号なし型を返す

_divideと_reciprocalは、ゼロ除算チェックは行わない

trunc_shift_は、最初の入力と同じ型を返す。

関数はまだ追加される余地がある。

P0038R0: Flat Containers

Boost.ContainerにあるFlat Associative Container(flat_map, flat_set, flat_multimap, flat_multiset)の追加。

フラット連想コンテナーとは、従来の連想コンテナーであるmapやsetのように、キーと対応する値をもっていて、キーによって値を高速に検索できる特性を持つ。従来のノードベースの連想コンテナーと違い、連続したストレージ上に要素が確保される。

実装方法は2つある。ひとつは要素を常にキーでソート済みにしておくこと。もうひとつはヒープ構造を用いること。Boostの実装はソートを使っている。ヒープを使った実装はキャッシュのローカル性を保ちやすいので、理論上優れた実装であるとされ、会議では関心が高かったが、実装経験が少ないため、さらなる検証が必要であるとしている。

P0039R0: Extending raw_storage_iterator

raw_storage_iteratorを改良する提案。

raw_storage_iteratorにムーブ代入演算子を追加し、ムーブに対応させる。

raw_storage_iteratorを作るのは面倒なので、factory関数を追加する。

template<class T>
auto make_storage_iterator( T&& iterator)
{
 return raw_storage_iterator<std::remove_reference<T>::type, decltype(*iterator)>( std::forward<T>(iterator));
}

raw_storage_iteratorの目的は、主にplacement newで使うためだが、placement newの文法はraw_storage_iteratorをサポートしていない。これを直接サポートする。

template<class T, class U>
void* operator new(size_t s, raw_storage_iterator<T,U> it) noexcept
{
 return ::operator new(s, it.base() );
}

template<class T, class U>
void operator delete ( void* m, raw_storage_iterator<T,U> it) noexcept
{
 return ::operator delete(m, it.base() );
}

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。来月は有給を取りまくる必要のある事情がある。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

3 comments:

  1. オーバーフローの例とアンダーフローの例が同じだったり、promoteとdemoteに誤りがある様に見受けられます。

    ReplyDelete
  2. hypotが地味に面白そうですね。
    arrayがconstexpr対応っていうのは良対応ですね。
    固定少数ライブラリですけど、最近半精度少数が流行ってるそうですがちゃんとした規格がないように思います。その対応として使えるものになるのでしょうか?
    コンテナですけど、早くリングバッファ入らないですかね。ちょっと使いたい用途があるので期待してマース。それと検索の都合でよくmapを使うのですが、これがフラットになるとバイナリ探査が使えてもっと早くなるとかそういうことにはならないんでしょうかねぇ??ヒープって検索に向いてたかちょっと失念してるんですけど、Mapには検索速度重視で設計してほしいです。フラットにするんだったら、インデックスドリンクドリストなんかも効率と微妙に相反してたりしますかね??
    あと、地味に日付ライブラリには期待してます。自分で書くとめちゃくちゃめんどくさいので。

    ReplyDelete
  3. 最近(?)流行りのGPGPU、OpenCLや3Dグラフィックスなどで使用されるhalfは浮動小数点です。
    16bit浮動小数点はIEEE754標準で規格化されています。
    P0037R0は固定小数点なので異なります。

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.