C++標準乱数ライブラリの、古い提案文書

• N0352 Proposal for Standardization of Random Number Generators in C++

乱数ライブラリに関する、一番最初の提案。1993年。最初は、乱数を生成する方法として、operator()のほかにdraw()という関数が考えられていた。

• N1588 On Random-Number Distributions for C++0x

分布クラスの提案文書。どの分布を入れるかの選定(あとでだいぶ変わった)基準と、各分布法の解説が書かれている。

並列シャッフルの考察

C++14後のParallelism TSで提案されている並列アルゴリズムについての考察。

N3850 Working Draft, Technical Specification for C++ Extensions for Parallelism

この提案にはshuffle()の並列版は予定されていないのですが、そのアルゴリズムを入れることは可能なのかと。Boost.Computeを見てみたら、random_shuffle()の実装が、以下のようになっていました。

template<class Iterator>
inline void random_shuffle(Iterator first,
                           Iterator last,
                           command_queue &queue = system::default_queue())
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;

    size_t count = detail::iterator_range_size(first, last);
    if(count == 0){
        return;
    }

    // generate shuffled indices on the host
    std::vector<cl_uint> random_indices(count);
    boost::iota(random_indices, 0);
    std::random_shuffle(random_indices.begin(), random_indices.end());

    // copy random indices to the device
    const context &context = queue.get_context();
    vector<cl_uint> indices(count, context);
    ::boost::compute::copy(random_indices.begin(),
                           random_indices.end(),
                           indices.begin(),
                           queue);

    // make a copy of the values on the device
    vector<value_type> tmp(count, context);
    ::boost::compute::copy(first,
                           last,
                           tmp.begin(),
                           queue);

    // write values to their new locations
    ::boost::compute::scatter(tmp.begin(),
                              tmp.end(),
                              indices.begin(),
                              first,
                              queue);
}

https://github.com/kylelutz/compute/blob/master/include/boost/compute/algorithm/random_shuffle.hpp

以下のような作りになっていました。

• CPU(メインスレッド)でランダムに並んだインデックスを作っておく
• デバイス(GPU)で、事前に計算しておいたランダムなインデックスに、並列に並び替えを行う。

なので、乱数生成器は並列に特化したものじゃなくてもよさそうなので、従来のmt19937とかをそのまま並列シャッフルに使えそうです。

では先日のVexCLの並列乱数アルゴリズムは何に使うかというと、おそらくランダムな行列を作るのに使うのでしょう。

参照

• C++14の言語拡張まとめ
• C++14 Parallelism TS 並列アルゴリズム

並列乱数アルゴリズムThreefry

GPGPUライブラリであるVexCLで使われている、並列実行でスケールする擬似乱数アルゴリズム。

カウンターベースの乱数生成器(CBRNG : counter-based random number generator)で、暗号論的ではない。

標準の乱数コンセプトに従った実装がほしい場合は、stdfin - Standard Financial C++ librariesにある。

参照

• vex::random::threefry Struct Reference
• Threefry Classes and Typedefs - Random123 Documentation
• Parallel Random Numbers: As Easy as 1, 2, 3

cpprefjp更新：memory完了

<memory>ヘッダのリファレンス作成が完了しました。

• <memory>
• 進捗状況
• ユーティリティライブラリの完成 - cpprefjpマイルストーン

これで、全52ヘッダ中39ヘッダのリファレンスが完成しました。残り13ヘッダです。

cpp-netlibのサーバー機能調査メモ

v0.11.0

• sync_server(server)とasync_serverというのがある。
• sync_serverはシングルスレッドのみ。
• async_serverはプールするスレッド数を指定する。デフォルトは1。
• sync_serverはrun()だけ持っているので、直接はポーリングの設計ができない(io_service::poll()をラップした関数がない)
• poll()したい場合は、sync_serverのコンストラクタでio_serviceオブジェクトへの参照を設定し、sync_serverのlisten()メンバ関数を呼び、外側のio_serviceオブジェクトに対して、poll()メンバ関数を呼ぶ。
• serverが持つio_serviceオブジェクトを取得する方法はない。

C++14 Concurrency TS 並行ハッシュコンテナ

N3732 Value-Oriented Concurrent Unordered Containers

C++14後のConcurrency TSでは、複数スレッドから安全に使えるunordered連想コンテナが予定されています。

提案文書のタイトルにあるように、このコンテナの設計は、「値指向(Value-Oriented)」になっています。これまでのunordered連想コンテナは、検索結果として要素への参照が返ってきましたが、並行プログラミングではそのような挙動は危険なので、参照の代わりに値が返されます。

たとえば、find()関数は以下のようなインタフェースが考えられています。

optional<mapped_type> unordered_map::find(const key type& k) const;

引数としてキーを与えると、対応する要素がoptionalとして返されます。見つからなかったらnulloptが返ります。

その他、Intel TBBやMicrosoft PPLの実装経験に基づいた設計が導入される予定になっています。

参照

• C++14の言語拡張まとめ

C++テンプレートテクニック 第2版 を出します

2009年に出版した書籍『C++テンプレートテクニック』の第2版を出版します。

• C++テンプレートテクニック 第2版 - Amazon.co.jp
• C++テンプレートテクニック 第2版 - SBクリエイティブ

発売日は、2014年4月17日(木)です。

C++テンプレートテクニック

本書は、プログラミング言語C++のテンプレート機能に関する技法を解説した本です。

プログラムをより汎用的にしていくにあたって起きる、様々な問題への解法を提供します。

第2版の更新内容

第2版の主な更新は、C++11への対応です。C++11に追加された機能を使用した各種技法を掲載しています。C++03の技法で今もなお有用なものは残してあります。

第2版では、以下のような変更を行いました：

• 第1版の章「Extension Member Function」および「C++0xにおけるテンプレート」を削除
• 新章「コンセプト」を追加。コンセプトに基づく設計(Concept-based Design)について解説しています。
• SFINAEの章を全面見直し。
• 各章に、C++11および最近のBoost事情に合わせた、新たなサンプルおよび解説を追加。

C++14に関しては、多少言及はしていますが、本格的には扱っていません。本書は、ユーザーコミュニティによって十分に使い込まれた、実績のある技法を扱っているからです。

電子書籍版について

どこかの電子書籍ストアで何らかの形式で販売するつもりですが、今のところは未定です。少なくても、書籍版と同時発売にはならないと思います。

書籍執筆においての新たな試み

書籍の第2版というのを出すこと自体が新たな試みでした。5年前の自分と今の自分はやはり違っていて、その差異を埋めつつ改訂を進めるのは、意外と大変でした。改訂期間としては、書籍『C++ポケットリファレンス』の作業が終わる1ヶ月ほど前から始めていたので、ほぼ丸一年かけました。私が関わる書籍では、レビューにバグトラッキングシステムを使っているというのはポケットリファレンスのときに書きましたが、第1版が400チケット程度のレビューだったのに対して、第2版では912件のレビューに対応しました。5年前に比べて、レビュアーの目もいっそう厳しく、いっそう頼もしいものになっていました。

それから今回、「本書推薦の言葉」というのを、4人の方に書いていただきました。第1版を実際に役立てていただいた方、レビュアー、他言語ユーザーの方などにお願いしました。これを導入したのは、いくつか理由があります。

• 著者以外のメッセージを書内に入れてみたかった。読者へのさらなる動機付けのため。
• 本書は比較的ニッチな内容なので、推薦文があることは効果がありそうだと判断した。
• 私たち著者が読んでニヤニヤしたかった。

第1版を読んでいただいた読者の方にとっても、共感できるものがあると思いますので、そちらもお楽しみにしてください。

C++のコンパイルエラー爆発を競うコンテスト

Results of the Grand C++ Error Explosion Competition

少し前に、C++のコンパイルエラーの長さを競うコンテストが開催されていました。

受賞のカテゴリは2つあり、ひとつめは最小コードで最大のコンパイルエラーを出した人、もうひとつは芸術的な評価による受賞です。

最小コードで最大のコンパイルエラー

この部門で優勝したのはEd Hanwayさんという方で、ソースコード量に対して59億倍のコンパイルエラーメッセージを出力したそうです。

それには、自身を2回インクルードするという手法が使われていたそうです。

#include ".//.//.//.//jeh.cpp"
#include "jeh.cpp"

次点として、インクルードに後方参照を使用した、7億9千万倍のコンパイルエラーを出力するコード：

#include "set>.cpp"
#include "set>.cpp"

可変引数テンプレートの再帰を利用した、6億5700万倍のコンパイルエラーを出力するコード：

template<class T,class...>class C{C<T*const,T,C>a;C<T,C>b;};C<int>c;

などがありました。

最高のチート

このコンテストの中では、多くのおもしろい試みが行われて、たとえばC++のダイグラフ拡張を使ったものがありました。検証スクリプトのゼロ除算バグを悪用しようとしたもの、評価スクリプトにパッチを当てて無限のエラーを出力させようとしたものなどもありました。

しかし最高のチートを行った人はこれとは別の方向に行きました。そのコード自体は一つのスペースが入ってるだけのものでしたが、ヘッダ探索のパスが以下のように書かれていたそうです。

/usr/include; perl -e "@c=\"x\"x(2**16); while(1) {print @c}" 1>&2

C++コンパイラがこれを実行すると、シェルコードがサンドボックスを脱出するのだそうです。

最高の驚き

以下のコードは、素朴ではありますが、予期せずコンパイルエラーが爆発します。

template<class T>class L{L<T*>operator->()};L<int>i=i->

Clangは「セミコロンが不足している」と正しく認識してくれますが、その後に無限のテンプレート再帰によってコンパイラがセグメンテーションフォルトになります。 この種の問題を防ぐために、IDEのコード補完に対するニーズを垣間見ることができる・・・そうです。

まだもうちょっとありますが

紹介はこのあたりにしておきます。また来年もやるかもよ、とのことですので、興味がある方は上記ページをウォッチしておくといいと思います。

C++14 complexのconstexpr対応

N3302 Constexpr Library Additions: complex, v2

C++14では、複素数を表すstd::complexクラスのconstexpr対応が行われます。

constexpr化するのは、以下の関数です。

• コンストラクタ
• ゲッター(real, imag)
• 比較演算子
• フリー関数版のゲッター(real, imag)

constexpr化しないのは、以下の関数です。

• セッター(real, imag)
• 算術演算子
• 入出力演算子
• 数学関数

参照

• C++14の言語拡張まとめ

C++14 shared_mutexがshared_timed_mutexに改名

• N3891 A proposal to rename shared_mutex to shared_timed_mutex
• shared_timed_mutex - cpprefjp C++日本語リファレンス

C++14に予定されていたmultiple-readers / single-writerパターンのshared_mutexクラスですが、shared_timed_mutexに名称が変更になりました。このクラスに元々、タイムアウト付きのロック取得関数が含まれていたからです。

// <shared_mutex>ヘッダ

namespace std {
  class shared_timed_mutex;

  template <class Mutex>
  class shared_lock;
}

タイムアウト付きロック取得のないshared_mutexは、以下のペーパーで改めて提案されています。

N3961 A proposal to add shared_mutex (untimed)

これは、C++14には今のところ予定されていません。

参照

• C++14 共有ロック
  • TODO : あとでshared_timed_mutexに直す
• C++14の言語拡張まとめ