2014-02-post-Issaquahのレビュー: N3920-N3929

前回同様、2014-02-post-Issaquahを引き続きレビューしていく。今回は、N3920からN3929までだ。N3966まであるので、すこし先が見えてきた。

N3920: Extending shared_ptr to Support Arrays, Revision 2

shared_ptrで配列を直接にサポートする拡張案。

現在、shared_ptrで配列へのポインターを扱うには、カスタムデリーターを書いて指定する必要があった。そんな面倒なことをしなくても、shared_ptr<T[]>やshared_ptr<T[N]>を認識して、デリーターを適切に選択してくれるように変更する提案だ。

前回のN3869からの変更点は、特筆すべきでもない細かな文面変更にとどまるようだ。

N3921: string_view: a non-owning reference to a string, revision 7

文字列を、実装の詳細を隠匿して、通過的に扱うためのライブラリ、string_viewの提案の文面案。

文字列を表現する方法として一般的なのが、charなどの文字型の配列と、文字数のペアである。文字列クラスというのは、標準ライブラリにもあるし、また標準ライブラリが目的に合わない場合は、自作されるこのような文字列の実装の詳細を隠して、文字列にアクセスできるラッパークラスが、string_viewだ。

string_viewは、std::basic_stringとほぼ互換のあるメンバーを備えていて、basic_stringのように扱うことができる。

前回の論文からの変更点は、それほど特筆すべきものはない。興味のある読者は、直接論文を読んでもらいたい。

N3922: New Rules for auto deduction from braced-init-list

N3912の提案のための規格の文面案。

[江添フレンドリーとは真逆の存在であるPDF] N3923: A SFINAE-Friendly std::iterator_traits, v3

[PDF注意] N3909によるstd::iterator_traitsをSFINAEフレンドリーにする提案の規格文面案。

[PDFの利用も非推奨扱いにするべき] N3924: Discouraging rand() in C++14, v2

C++11で、新しい乱数ライブラリが導入されたことにより、既存のC時代から受け継いだrand, srand, RAND_MAXと、std::random_shuffleの使用を非推奨扱いにする提案の文面案。

C++11では、より優れた乱数生成と乱数分布のためのライブラリが追加されたので、従来の使いづらく誤用されやすい劣ったrand, srand, RAND_MAXは、規格で使用を推奨しない強いNOTE(注記)を追記する。

std::random_shuffleは、randに依存するオーバーロードがある。また、この関数に独自の乱数生成器を渡す際にも、そのインターフェースが極めて使いづらい。C++11では、新しく設計が洗練されたstd::shuffleが追加されたので、std::random_shuffleもdeprecated扱いにする。

論文では、文面案も示している。

[PDFは採取する必要がない] N3925: A sample Proposal, v4

値の集合の中から、ランダムで標本を採取するアルゴリズム、std::sampleの提案。値がいくつあるかわからなくても正しく採取できる。

もともと、SGI STLにsample, sample_nとして存在したアルゴリズム。提案では、別の名前に分けずに、オーバーロードで切り分ける設計になっている。

そのリファレンス実装も論文に書かれているが、50行程度なので、ここに貼れるほど短い。

// リファレンス実装
template< class PopIter, class SampleIter, class Size, class URNG >
SampleIter
sample( PopIter first, PopIter last
      , SampleIter out
      , Size n, URNG&& g
)
{
    using pop_t = typename iterator_traits<PopIter>::iterator_category;
    using samp_t = typename iterator_traits<SampleIter>::iterator_category;

    return __sample( first, last, pop_t{}
                   , out, samp_t{}
                   , n, forward<URNG>(g)
                   );
}

template< class PopIter, class SampleIter, class Size, class URNG >
SampleIter
__sample( PopIter first, PopIter last, input_iterator_tag
        , SampleIter out, random_access_iterator_tag
        , Size n, URNG&& g
)
{
    using dist_t = uniform_int_distribution<Size>;
    using param_t = typename dist_t::param_type;
    dist_t d{};

    Size sample_sz{0};
    while( first != last && sample_sz != n )
        out[sample_sz++] = *first++;

    for( Size pop_sz{sample_sz}; first != last; ++first, ++pop_sz ) {
        param_t const p{0, pop_sz};
        Size const k{ d(g, p) };
        if( k < n ) out[k] = *first;
    }
    return out + sample_sz;
}


template< class PopIter, class SampleIter, class Size, class URNG >
SampleIter
__sample( PopIter first, PopIter last, forward_iterator_tag
        , SampleIter out, output_iterator_tag
        , Size n, URNG&& g
)
{
    using dist_t = uniform_int_distribution<Size>;
    using param_t = typename dist_t::param_type;
    dist_t d{};

    Size unsampled_sz = distance(first, last);
    for( n = min(n, unsampled_sz); n != 0; ++first ) {
        param_t const p{0, --unsampled_sz } ;
        if( d(g, p) < n ) { *out++ = *first; --n;}
    }

    return out;
}

前回の論文からの変更に、特筆すべきものはないようだ。

[PDFはdefect] N3926: LWG Issue 2168 is NAD

Library issue 2168はNAD(Not A Defect、問題ではない)と結論する論文。

26.5.8.22 p1では、uniform_real_distributionは、\(a \leq x < b\) の範囲に分布する乱数を生成するとある。

26.5.8.22 p2では、uniform_real_distribution( RealType a = 0.0, RealType b = 1.0 ) ;とあり、\( a \leq b \) かつ \(b - a \leq \verb=numerix_limits<RealType>::max()=\) でなければならないとしている。

この文面では、aとbの差が表現可能ではない場合（最もわかりやすい例はa == b）では、26.5.8.22を満たせないではないか。なぜ半開区間なのか。

まず、この文面はもともと\(a < x < b\)だった。しかし、プログラマーというものは、統計学者や数学者と違い、閉区間ではなく、半開区間を好むものであるので、\(a \leq x < b\)に修正された。issue 2168はこの背景をしらずに追加されたというのがまず一点。

\(a \neq b\)である理由は、\(1 / (b - a)\)を計算する必要があるためである。したがって、\(a \neq b\)である引数を与えるのは、利用者側の責任であるとのことだ。

ただし、\(a \neq b\)が要求されるのは、operator ()を呼び出した時だ。uniform_real_distributionのオブジェクトを\(a = b\)の条件で初期化しても、問題はない。

N3927: Definition of Lock-Free

C++ Standard Library Active Issues 2075を解決するための文面案。

Library issue 2075は、規格の以下の文面を問題としている。

1.10 [intro.multithread] p2

Implementations should ensure that all unblocked threads eventually make progress.

C++の実装は、ブロックされていないスレッドは、いずれ実行が進むことを保証したほうがよい。

ちょっとまて。これを文字通り解釈して保証しようとすると、大変なことになるぞ。アトミック操作にロックフリー程度の保証では実現できないぞ。アトミック操作は、一部のスレッドの実行が進むことを保証するだけだからだ。

そもそも、実行が進む(make progress)とはどういう意味だ。「ブロックされていないスレッド」には、現在ロックされているスレッドは含まれないのか（そうであれば、アトミック操作がロックフリーであるだけで十分なはずだが）

29.4 [atomics.lockfree] p2で、ロックフリー(Lock-free)という用語が使われているが、ロックフリーなる用語の定義がないぞ。そして、議論の結果、どうやらC++規格の文面で使われているロックフリーという用語は、一般的なロックフリーとは意味が異なるものであるぞ。

この問題を解決するために、「ロックフリー」という言葉を定義することにした。文面案は以下の通り

Executions of atomic functions that are either defined to be lock-free (29.7 [atomics.flag]) or indicated as lock-free (29.4 [atomics.lockfree]) are lock-free executions.

ロックフリーと規定されている、もしくはロックフリーであると示唆されているアトミック関数の実行はロックフリー実行である。

If there is only one unblocked thread, a lock-free execution in that thread shall complete. [Note: Concurrently executing threads may prevent progress of a lock-free execution. For example, this situation can occur with load-locked store-conditional implementations. This property is sometimes called obstruction-free. —end note]

When one or more lock-free executions run concurrently, at least one should complete. [Note: It is difficult for some implementations to provide absolute guarantees to this effect, since repeated and particularly inopportune interference from other threads may prevent forward progress, e.g. by repeatedly stealing a cache line for unrelated purposes between load-locked and store-conditional instructions. Implementations should ensure that such effects cannot indefinitely delay progress under expected operating conditions, and that such anomalies can therefore safely be ignored by programmers. This property is sometimes called lock-free outside this International Standard. —end note]

ブロックされていないスレッドがひとつだけ存在する場合、そのスレッド内におけるロックフリー実行は完了しなければならない。[注：平行に実行されているスレッドはロックフリー実行を妨げるかもしれない。たとえば、load-locked store-conditionalな実装をしている場合におこる。このような特徴を、時に、obstruction-freeと言う。注終わり]

ひとつかそれ以上のロックフリー実行が平行に実行する場合、少なくとも、ひとつは完了するべきである。[注：一部の実装では、この効果を完全に保証するのは難しい。というのも、他のスレッドからの連続して特に間の悪い干渉が、実行の進展を妨げるかもしれないからである。例えば、load-lockedとstore-conditional命令の間で、キャッシュラインを奪い合う場合。実装は、通常の実行の条件下において、このような効果が、永久に実行の進展を妨げないように保証すべきである。それにより、余りの異常な条件は、プログラマーは安全に無視できる。このような特徴を、時に、この国際規格の範疇の外では、ロックフリーと呼んでいる。注終わり]