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

11 comments:

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"
が使えます。
このため、無効要素と有効要素の混合で分岐予測が失敗することはなくなります。

opbest said...


Excellent post. I was checking continuously this
blog and I am impressed! Extremely helpful information specifically the last part :
) I care for such information much. I was seeking this particular
info for a long time. Thank you and best of luck.

my blog post ==== 오피사이트

(freaky)

majortotositepro said...

I savour, lead to I found exactly what I used to be having a look for. You’ve ended my four day long hunt! God Bless you man. Have a nice day. Bye 메이저사이트

racesitepro said...

I used to be suggested this blog through my cousin. I’m no longer sure whether this submit is written through him as
nobody else understand such detailed approximately my trouble.
You’re wonderful! Thank you! 온라인경마

oncasinositenet said...

I really enjoyed this blog post, thank you for sharing it. I’ll return for more. See you soon! 카지노

totopickpro said...

This paragraph will help the internet visitors for building up new web site or even a weblog from start to end. 토토

oncasinosite said...

It was a very good post indeed. I thoroughly enjoyed reading it in my lunch-time. I Will surely come and visit this blog more often. Feel free to visit my website; 온라인카지노

casinositelink said...

Wow, awesome blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your web site is great, as well as the content!Feel free to visit my website; 온라인카지노

oncasinositenet said...

Very informative and well-written post! The quite interesting and nice topic chosen for the post. thankyou Feel free to visit my website; 바카라사이트

bacarasite said...

Wonderful items from you, man. I’ve have in mind your stuff previous to and you’re just extremely excellent. I actually like what you’ve acquired here, really like what you’re saying and the way in which through which you assert it. You’re making it entertaining and you still care for to keep it smart. I cant wait to read far more from you. That is actually a terrific web site Also visit my website: 온라인카지노

casinoonline said...

Why couldn't I have the same or similar opinions as you? T^T I hope you also visit my blog and give us a good opinion.casino online