2014-08-07

2014-05-pre-Rapperswil-mailingのレビュー: N4030-N4039

さて、5月分の論文集も残すところ後わずか。

N4030: Feature-testing recommendations for C++

C++の新機能が実装によってサポートされているかどうかを確かめる標準のCプリプロセッサーマクロの提案。具体的なマクロ名などは論文を参照。

// N4030提案
#if __cpp_binary_literals
int const packed_zero_to_three = 0b00011011;
#else
int const packed_zero_to_three = 0x1B;
#endif

__cpp_binary_literalsは、実装が二進数リテラルに対応しているかどうかを調べるマクロである。

筆者はCプリプロセッサーを使ういかなる機能にも反対の立場である。

N4031: make_array, revision 1

make_tupleやmake_pairのようなインターフェースで、std::arrayを返すmake_arrayの提案。

これにより、arrayのテンプレート実引数を推定でき、わざわざ手書きする必要がなくなる。

// 面倒
std::array< int, 5 > a = { 1, 2, 3, 4, 5 } 

// 簡単
auto a = std::make_array( 1, 2, 3, 4, 5 ) ;

// 型を明示することもできる
auto b = std::make_array<int>( 1 ) ; 

// array<char const *, 1>
auto c = std::make_array("hello") ;

// array<char, 6> d = { 'h', "e", 'l', 'l', 'o', '\n' } ;
auto d = std::to_array("hello") ;

narrowing conversionは禁止されている。

// エラー、narrwoing conversion
auto a = std::make_array(2, 3U)

なかなか悪くない小粒なライブラリだ。

N4032: Comments on continuations and executors

Anthony Williams本人が自ら、現在提案中の並列処理ライブラリを実装したところ、文面に様々な不備が見つかったとのことで、その不備を列挙して、然るべき修正案などを書いている論文。

executorがabstractクラスなのは不便だ。executorコンセプトを用意して、実行時ポリモーフィックな振る舞いには、別途generic_executor_refのようなtype erasureを使ったラッパーを容易すべきだ。

Scheduled Executorがタイムアウト指定にstd::chrono::system_clockを使うのはいかにもおかしい。std::chrono::steady_cloxkを使うべきだ。そもそも、タイムアウト指定にタイムスタンプを使うというのは、利用例の一部しかカバーできないので、やはり標準のabstract基本クラスと仮想関数を用意して様々な利用例に対応できるようにすべきである。

executorの種類が少なすぎる。executor *で返されるより、generic_executor_refで返すべきだ。その記述も不十分だ。

そのほか、futureに対する拡張案へのコメントが並んでいる。設計の不備、文面の不備を指摘するものが多い。

N4033: synchronized_value<T> for associating a mutex with a value

これもあの有名なAnthony Williamsの論文。T型を自動的にmutexでロックするライブラリ、synchronized_value<T>の提案

値に排他的なロックをかけるにはmutexを使うが、mutexをそのまま使うのは、甚だ面倒である。

int value1 ;
std::mutex m1 ; // value1用のmutex
int value2 ;
std::mutex m2 ; // value2用のmutex

void f()
{
    std::lock_guard<std::mutex> guard(m2) ; // おっと
    value1 = 123 ; // おおっと
} 

上記のコードは、ロックすべきmutexオブジェクトを間違えているのだが、残念ながら、コンパイラーはこれを警告してくれない。

この問題は、ある型のオブジェクトとそのオブジェクトを守るmutexを管理するライブラリがあればいいのだ。そこで、そのようなライブラリを論文著者はすでにDr. Dobb'sの記事として執筆していたが、その設計を手直しして正式に提案している。


std::synchronized_value value ;

void f()
{
    *valule = 123 ;
    int x = *value ;
}

仕組みとしては、synchronized_valueは、T型とmutexをメンバーとして持っている。operator *は、未規定の型を返す。この型は生成時に元のsynchronized_valueのオブジェクトのmutexをロックし、破棄されるときにmutexをアンロックする。また、T型へのリファレンスを返す。その結果、安全に自動的にロック、アンロックした上に、値の読み書きもできる。

これは、値の単発の読み書きをするにはいいが、複数の操作を一括して行うには効率が悪い。そのため、オブジェクトの生存期間の間だけロックし続ける、公に公開されているインターフェースもある。

std::syncronized_value<std::string> value ;

void f()
{
    std::update_guard< std::string > guard(value) ;

    *guard += "hello" ;
    *guard += "hello" ;

// guardのデストラクターでアンロックされる
}

N4034: Destructive Move

より制約が厳しい、保証された破壊的ムーブをするためのライブラリの提案。

現在のムーブというのは、ムーブ後のオブジェクトを、未規定だが有効な状態にするように義務付けている。つまり、ムーブ後のオブジェクトの状態は定められていないが、通常使えるように使えなければならないということだ。

しかし、クラスの実装によっては、これを無例外保証のまま行うのは難しい。そこで、破壊的ムーブの提案となる。

破壊的ムーブ(destructive move)とは、ムーブ後のオブジェクトは破棄された後であり、利用も、もう一度破棄することも出気ない状態になる。こ無例外ムーブが提供できないクラスでも、無例外破壊的ムーブは提供できるクラスは多い。また、ムーブされた後のオブジェクトはどうせ破棄する場合もある(vectorがその内部バッファーを増やす場合など)

また、破壊的ムーブというのは、単にバイト列のコピーで済ませられる場合もある。そのような条件を満たす型を、trivially destructive movable typeと名付ける。

具体的な提案としては、

template <class T>
void destructive_move(T* to, T* from) noexcept( /* see below */ );

という破壊的ムーブのための関数テンプレートの追加と、is_trivially_destructive_movable<T>という、trivially destructive movableな型かどうかを調べられるtraitsを追加する。destructive_moveは、is_trivially_destructive_movableがtrueの場合、バイト列コピーを行う。また、destructive_moveが特定の型に対してオーバーロードされていた場合は、ADLによって発見され、そちらが呼ばれるようになっている。

また、この配列版、destructive_move_arrayもある。

template <class T>
void destructive_move_array(T* to, T* from, size_t sz)
noexcept(is_nothrow_destructive_movable<T>::value);

リファレンス実装はhttp://halpernwightsoftware.com/WG21/destructive_move.tgzにある。これはBloomberg LPのBDEライブラリで5年以上使われていて、vector操作を劇的に高速化させたとのことである。

[論文フォーマットは暗黙にPDF以外のまともなフォーマットが使われるべき] N4035: Implicit Evaluation of "auto" Variables and Arguments

N3748の改訂版。

以下のようなコードを考える。

matrix A, B ;

auto C = A * B ;

上記のコードで、変数Cの型がなんであるかはわからない。matrix型かもしれないし、違うかもしれない。たとえば、matrixクラスの作者は、最適化のために、計算が実際に必要になるまで遅延させるため、内部的なラッパー型や、Expression Templateの技法を使った複雑な型を返しているかもしれない。

しかし、ここでmatrix型が欲しい場合、いったいどうすればいいのだろうか。

そのため、この論文では、autoを初期化するときに暗黙に型変換される型を、ライブラリ側で指定できる機能と、ユーザー側でその指定された暗黙の型変換を無効にする機能を追加しようと提案している。そのためには、できるだけわかりやすい文法を考えなければならない。

たとえば、matrixクラスは、operator *(Matrix const &, Matrix const &)の結果として、product_exprというラッパークラスを返しているとする。

論文では、いくつかの文法案が提案されている。

using宣言

class product_expr
{
public :
    using auto = matrix ;
} ;

このように記述すれば、auto specifierでは、暗黙にproduct_exprからmatrixに型変換される。型変換は通常通り、product_exprを引数として受け取るmatrixのコンストラクターとか、product_exprからmatrixへの変換関数として実装すればよい。

operator記法


class product_expr
{
public :
    matrix operator auto() { ... }
} ;

この文法の利点は、通常のコンストラクターや変換関数とは独立して、auto specifierのためだけの型変換処理が書けることである。ただし、そういう需要はあまりないのではないかとも思うし、戻り値の型を推定させた場合、何やらわかりにくい。

auto operator auto() { ... }

他にも、decayを特殊化してそれを特別に扱おうという提案もあるが、これは筆者は気に入らないので、わざわざここで紹介しない。

ユーザー側でこの余計なお世話を無効化する方法としては、explicitキーワードを使う文法が提案されている。

explicit auto C = A * B ;

David Vandevordeは、ライブラリで無効化することも可能であるという例を提示した。

auto C = noeval(A * B) ;

noevalの実装は以下の通り


template <typename T>
struct noeval type
{
    const T& ref;
    noeval type(const T& ref) : ref(ref) {}
    operator T const&() { return ref; }
    using auto= T const&;
} ;

template <typename T>
auto noeval(const T& ref)
{
    return noeval type(ref);
}

ライブラリの無効化のために、まさに提案されているこの機能をもう一度使うとはにくいコードだ。さすがはDavid Vandevorde。

[論文からPDFフォーマットの廃止に向けて] N4036: Towards Implementation and Use of memory_order_consume

2014年2月に、Linus Torvaldsが、GCCのML上で暴れていた。この論文著者とも殺伐とやりあっていた。

gcc archive, author index for February, 2014

Linusの主張はこうだ。

C11/C++11に入ったアトミック操作は使い物にならない。規格がクソすぎるためである。よってLinuxカーネルでは使わない。

規格化されたアトミック操作は保証が弱すぎる。したがって、Linuxカーネルのアトミック操作のすべてを置き換えることはできない。また、Speculative storeのような問題ある最適化を抑制することもできない。そもそもspeculative storeなんて許されるべきではないだろ。コンパイラー屋は、規格を指さして、「でもほら、規格上許されちゃってるんだよねーん」とかほざいているが、規格がぶっ壊れてる。ぶっ壊れたコード生成を正当化するためにクソぶっ壊れた規格を使っている。現実のハードウェアに基づかない規格などクソだ。

結局、問題に対処するために、Linuxカーネルではvolatileを使っている。アトミック操作ではすべての問題ある最適化を抑制できない。すると、volatileかつアトミック型を使わければならない。じゃあ、最初っからvolatileだけでいいじゃねーか。なんでわざわざアトミック型まで使わなきゃなんねーんだよ。

アトミック操作はまだひとつかふたつのプラットフォーム向けにしか実装されていないし、まだ実装経験が浅すぎてどうせバグだらけだ。結局、Linuxカーネルの今のやり方(volatile+インラインアセンブリ)は維持しなければならない。その上で、ひとつかふたつのプラットフォーム向けに標準規格のアトミック操作もつかってみよーかなーなんてなるわけねーだろドアホ。なんでそんなに複雑にしなきゃならねーんだよボケ。

そもそもmemory_order_consumeってクソすぎるだろ。なんだよこのcarries dependencyって概念はよ。コンパイラーが依存順序を完璧に解析できるわけねーだろ。で、明示的にkill_dependency()で依存を断ち切れって? ふざけんじゃねぇぞ。

そもそも、グローバルな最適化なんて糞食らえだ。ソースコードの解析だけですべてが分かると思うな。ソースコードに記述されていない、ハードウェアやモジュールなどの外部の別言語で書かれたライブラリがメモリを操作することだってあるだろうが。ローカルな最適化だけにしておけ。

標準規格はクソ使えないので我々Linuxカーネルではゼッテー使わねー。馬鹿げた机上の空論を捨てて、規格をさっさと直しやがれ。

論文著者は、規格化されたアトミック操作が現実の需要と乖離している理由を、コンパイラーの最適化手法が、7年前の規格化していた時と比べて、格段にアグレッシブになっていること、当時より長い依存チェインが現実に使われていることなどを上げている。

論文では、Linus Torvaldsでも満足する機能を提案しようと、型ベースの制限付き依存チェインとして、value_dep_preserving型指定子を提案している。

この論文を読むのはつかれた。アカデミックバリバリの2カラムのクソレイアウトを利用したクソみたいなtexで書かれたものをPDFで出力した論文で、しかも元のtexのソースコードは公開しないときているので、最高に読みづらかった。仕方がないので紙に印刷して読んだ。そして、背景事情を調べるためにLinusのGCC MLでの発言を追う必要があったので、これまた時間がかかった。

[非PDFドキュメントが欲しい] N4037: Non-Transactional Implementation of Atomic Tree Move

トランザクショナルメモリーを使わずに、lock contentioもできるだけおこさず、要素をあるツリーから別のツリーにムーブするアルゴリズムの考察。2014年のIssaquah会議でそういう課題が出たので考察したらしい。

論文では、バランスも何もないバイナリツリーのみを考察している。

論文自体は、あまりC++らしくない。ただ、C++会議でそのような条件を満たすアルゴリズムが現在存在しないので今後の課題として設定されたので、その道の専門家であるPaul McKenneyが考察したようだ。

N4038: Proposal for Unbounded-Precision Integer Types

C++の標準ライブラリに無限精度整数型の提案。

プログラミングにおいて、C++の基本型の整数型が表現しきれないほど大きな数値を扱う需要はよくある。特に、暗号用途には必須だ。C++用のそのようなライブラリは、多数ある。Javaはそのようなライブラリを標準で持っている。C++にも無限精度整数型が必要だ。

無限精度整数型(Unbounded-Precision Integer Type)とは言うものの、現実的には、有限のコンピューターリソース上に実装される以上、当然、有限の精度を持つ。ここでいう無限精度とは、ハードコードされた上限がなく、システムのリソース以外に桁数に制限を加えるものがないことを言う。

提案では、無限精度整数型であるstd::integer型と、無限精度ビット列型であるstd::bitsが提案されている。

std::integer型は、既存の組み込みの整数型と組み合わせて使うことができ、また組み込みの整数型がサポートしている演算はすべて同じ文法でサポートする。また、その他にも無限精度整数型を必要とする分野で需要ある演算をサポートする。需要あるすべての演算を網羅することはできないので、必要な演算を実装できる基本的な演算を提供する。abs, sqr, sqrt, pow, mod, mulmod powmod, gcd, lcmあたりだ。is_zero, is_oddがあるのも興味深い

また、integer型のメンバー関数のsizeとcapacityは、内部ストレージを再確保せずに表現できる10進桁数の上限を返す。reserveも桁数を取る。

現在表現している値を表現できる規模に内部ストレージを縮小するshrink_to_fitもある。

get_data_proxyというメンバー関数もあり、これは内部ストレージを直接見たり操作したりできる。

ちなみに、ドワンゴ社内では、競技プログラミングに使えるとの意見が多かった。

N4039: Default executor

現在提案中の並列実行ライブラリには、デフォルトのexecutorがない。デフォルトのexecutorはあるべきである。しかし、何をデフォルトにすればいいのか議論は付きない。タスクごとにスレッドを作るexecutorはわかりやすいが、一般的に、スレッドプールよりコストがかかる、しかし、スレッドプールでは、タスクがブロックされてしまうことがある。

論文は結論を出さず、それぞれのexecutorの利点、欠点を挙げるだけにとどまっている。

ドワンゴ広告

最近、ドワンゴのオフィスが入っている歌舞伎座タワーの7FのコンビニがICE BOXを置くようになったので、食べ過ぎないように鋼鉄の意思を要求されてつらい。

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

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

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

3 comments:

Anonymous said...

とりあえず、多倍長整数を歓迎いたします。
スレッドプールについては、デッドロックしてもハンドルさえ握っていればリスタートはそんなに難しくないと思いますので個人的にはスレッドプール型が好みです。
個人的にはプライオリティキューとスレッドプールの組み合わせが最強だと思ってるので、そういう方向に流れてほしいかな。
autoの扱については手を付けるべきではないですね。そもそも設計時にそこも考慮して返す型を選択するべきで、手を抜くために変な仕様を入れないでほしい。
ミューテックスのロック失敗してデッドロックするのはさすがに間抜けなのでクラスにミューテックスオブジェクトとバリューをセットにする案は合理的に思います。あとは寿命の管理をPG側にもいじれるようにしてほしい。

Anonymous said...

ツリーからあるツリーへ要素をムーブするには、要素のメモリ独立性が必要です。ツリーを作るときは通常ブロックでメモリを確保して使いますが、それではフリーした時に全部解放してしまうので、まぁ、要素単位でニューするしかないと思いますよ。
おっそいので現実的ではないですが、手法としてはアリじゃないでしょうか。
まぁ、必要になった時に必要な回数Newして都度解放。って感じです。
ListTreeって感じになるんでしょうか。

Anonymous said...

// array d = { 'h', "e", 'l', 'l', 'o', '\n' } ;

// array d = { 'h', 'e', 'l', 'l', 'o', '\0' } ;
ではないでしょうか