2017-11-01

C++標準化委員会の文書: P0399R0-P0515R2

[PDF] P0399R0: Networking TS & Threadpools

ネットワークライブラリーはスレッドプールを使いたいがどのようになるのかということを大雑把に説明したスライド資料。

[PDF] P0424R1:Reconsidering literal operator templates for strings

文字列リテラルに対するユーザー定義演算子で文字列を(harT const *, std::size_t)で取れるようにする提案。

template < typename CharT, CharT const * str, std::size_t length >
auto operator "" _udl() ;

auto x = "abcd"_udl ;

[PDF] P0429R2:A Standard flat_map

ソート済みの連続したストレージで実装されるset/mapの実装。flat_set/flat_mapの提案。

既存のset/mapはノードベースのバイナリーツリーによる実装で、これは現代のメモリが凄まじく遅くキャッシュミスが悲惨なことになるアーキテクチャではとても遅い。連続したストレージはキャッシュが聞きやすく、キャッシュが聞いたメモリ領域への読み書きは高速に行える。すると、ソート済みの配列をバイナリサーチする実装のほうが、現実のアーキテクチャでは速度の点で有利だ。

入ってほしい。

P0443R3:A Unified Executors Proposal for C++

実行媒体を表現するexecutorライブラリの提案

P0447R4: Introduction of std::colony to the standard library

歯抜けを許す連続したストレージ上に構築される要素の順序保証のないコンテナー、colonyの提案。

vectorのような連続したストレージ上に構築される要素の順序保証のあるコンテナーを考える。

std::vector v = {1,2,3,4,5} ;
// 中間の要素を削除
v.erase( v.begin()+2 ) ;

このコードは遅い。なぜかというと要素3を削除したあとに、要素3が構築されていたメモリー上に要素4をコピーし、要素4の場所には要素5をコピーして、間を詰めなければならないからだ。vectorでは最後尾以外の要素の削除は遅い。

では要素を詰めなければいいのではないか。eraseを行った後のコンテナーの中身が、{1,2,無効,4,5}となるデータ構造はどうだろうか。要素にアクセスする際は無効になった要素を読み飛ばして無視する。要素2と4の間に要素を挿入すると、無効化されていたストレージに要素が追加される。さらに、位置を指定せずに挿入すると、無効化されているストレージのどこかに要素が追加される。

colonyは要素の順序を保証しないが、中間の要素が定数時間で行える特性を持つコンテナーだ。

なお、リファレンス実装では、無効要素の読み飛ばしは要素ごとに無効フラグを持つのでもなく、ビットマップで無効フラグを持つのでもなく、jump-counting skipfieldと呼ばれる手法を用いるらしい。これによって連続した無効要素を読み飛ばすのがキャッシュ効率よく行えるそうだ。

The Advanced “Jump-Counting” Skipfield Pattern

[PDF] P0461R2: Proposed RCU C++ API

同期処理のためのRCUライブラリの提案。

P0479R2: Attributes for Likely and Unlikely Statements

起こりうる可能性の高さと低さを指定する属性、[[likely]]と[[unlikely]]の提案。

例えば分岐時に実行される可能性の低いブランチに指定することで、コンパイラーの最適化を助けることができる。


if ( is_error )
[[ unlikely]] {
// めったに起こらないエラー
}

GCCとClangは独自拡張として__builtin_expectという同等機能のcompiler intrinsicsを提供している。MozillaやChromiumのような現実のコードでも使用されている。

現実にどのように活用されるかというと、例えばキャッシュを多用するアーキテクチャでは、コードブロックの配置の場所によってキャッシュされるかどうかが変わるので、分岐時により実行される可能性の高いコードをキャッシュされやすい領域に配置することができる。x86では、隣接する複数の命令は内部で単一の命令にまとめられたりするので都合が良い。

[PDF] P0506R2: use string_view for library function parameters instead of const string & / const char *

string_viewを標準ライブラリで文字列を受け取る引数の型として積極的に使っていこうという提案。std::string const &やchar const *で受け取るよりよい。

[PDF] P0514R2:Efficient waiting for concurrent programs

スレッド所有がないmutexとして、atomic_semaphoreの提案。atomic操作にatomic_waitやatomic_notify_oneも追加。そしてcondition_variable_atomicも提案。

[PDF] P0515R2:Consistent comparison

C++における比較をより厳密にするための新しい演算子、operator <=>の提案。

operator <=>(a, b)はa, bの大小関係と等号関係に応じて適切な3値のいずれかを返す。また、strong order, weak order, partial order, strong equality, weak equalityも型で表現する。

これでだいぶ比較がマシになる。今まで同じ演算子にごちゃまぜにしすぎていた。

ドワンゴ広告

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

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

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

1 comment:

abo junghichi said...

> なお、リファレンス実装では、無効要素の読み飛ばしは要素ごとに無効フラグを持つのでもなく、ビットマップで無効フラグを持つのでもなく、jump-counting skipfieldと呼ばれる手法を用いるらしい。これによって連続した無効要素を読み飛ばすのがキャッシュ効率よく行えるそうだ。
読み飛ばしの高速化はキャッシュ効率ではなく分岐予測器への負担の問題のようです。

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0447r4.html#design

It stores and modifies (during insertion and erasure) numbers which correspond to the number of elements in runs of consecutive erased elements, and during iteration uses these numbers to skip over the runs. This avoids the looping branch code necessary for iteration with a boolean skipfield - which is slow, but which also cannot be used due to it's O(random) time complexity.

無効フラグを持つ方法では、読み飛ばす場合と読み込む場合でコードを分岐させねばならず、しかも、上記ベンチマークの様に要素をランダムに削除した場合、読み飛ばしと読み込みもランダムな順番で生じます。
パイプラインフラッシュに15-20クロックほど掛かる昨今のx86プロセッサでは、この様な分岐予測の効かない分岐では15-20倍ほど遅くなります。
一方skip-fieldの場合、読み飛ばす要素の数を「0」と記録することで、無効要素が混ざっている場合とそうでない場合で同じコード
"次の有効要素番号 = 現在の要素番号 + (読み飛ばす要素数) + 1"
が使えます。
このため、無効要素と有効要素の混合で分岐予測が失敗することはなくなります。