生成するビット幅を指定可能なrandom_deviceクラスを書いた

64ビット版メルセンヌ・ツイスターはいつ使うか」に関連して、64ビットのシードを作れるように、生成する整数型を指定できるrandom_deviceクラスを書きました。

Boost.Randomの実装をコピペしてきてちょっと変えただけです。

インタフェース:

// <shand/random/random_device.hpp>
namespace shand {
   template <class UIntType>
   class random_device {
     using result_type = UIntType;

     explicit random_device(const std::string& token = implementation-defined);
     result_type operator()();

     template <class Iterator>
     void generate(Iterator first, Iterator last);
   };

   using random_device_32 = random_device<std::uint32_t>;
   using random_device_64 = random_device<std::uint64_t>;
}

標準やBoost.Randomのものと違うのは、以下の点:

  • クラステンプレートになっている
  • テンプレートパラメータとして、生成する整数型をとる
  • entropy()メンバ関数がない
    • 有意義な結果は誰も返せないので、必要ないと判断した。

mt19937_64のシードを作るために、64ビット版random_device型であるrandom_device_64を使えます。

#include <iostream>
#include <cstdint>
#include <random>
#include <shand/random/random_device.hpp>

int main()
{
    shand::random_device_64 seed_gen;
    std::mt19937_64 engine(seed_gen());

    for (int i = 0; i < 10; ++i) {
        std::uint64_t result = engine();
        std::cout << result << std::endl;
    }
}

出力例:

3893701729893995308
10711700309771701362
17929754974751635565
17553023603653786827
13502565356887369052
10931010143106186937
4547535530895765923
153507564072994118
1189766131898797718
5246883299549427354

64ビット版メルセンヌ・ツイスターはいつ使うか

C++11標準ライブラリとBoost.Randomには、32ビット版メルセンヌ・ツイスターmt19937と64ビット版のmt19937_64があって、64ビット版をいつ使えばいいかよくわからなかったのでメモ。

What is the advantage of using mt19937_64 over its 32 bit variant? - StackOverflow

  • 64ビット版は、より大きな幅(64ビット)のシードを持つことができる。
    • これによって、乱雑さがさらに増す。
  • CPUの64ビット命令を使うので、64ビットマシンなら速く動作して、32ビットマシンなら遅い。
  • sizeofはどちらも同じ。

ただし、random_deviceクラスは32ビット(unsigned int)の値を作るので、それをそのままシードとして使う場合は、64ビットシードにはならない。その実装詳細であるWindowsCryptGenRandom() APIUNIX系OS/dev/urandom自体は64ビットで読み込める。

シード生成の問題があるため、C++11とBoost 1.55.0時点では、ターゲット環境が64ビットならmt19937_64は高速に動作するので、そちらを使う。という、高速化のみに注目した選定基準でいいのかもしれない。

リンクディレクトリの指定

CMake 2.8で検証

  • link_directories相対パスを指定するのは廃止された。絶対パスでリンクディレクトリのパスを通す必要がある。
  • link_directories環境変数のパスを使って指定する場合は、link_directories($ENV{MYPROJECT_ROOT}/libs)のように、環境変数$ENV{}で囲んで指定する。

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

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

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

並列シャッフルの考察

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の並列乱数アルゴリズムは何に使うかというと、おそらくランダムな行列を作るのに使うのでしょう。

参照

並列乱数アルゴリズムThreefry

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

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

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

参照

cpprefjp更新:memory完了

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

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

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

v0.11.0

  • sync_server(server)とasync_serverというのがある。
  • sync_serverはシングルスレッドのみ。
  • async_serverはプールするスレッド数を指定する。デフォルトは1。
  • sync_serverrun()だけ持っているので、直接はポーリングの設計ができない(io_service::poll()をラップした関数がない)
  • poll()したい場合は、sync_serverコンストラクタio_serviceオブジェクトへの参照を設定し、sync_serverlisten()メンバ関数を呼び、外側の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++テンプレートテクニック 第2版 を出します

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

発売日は、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版を読んでいただいた読者の方にとっても、共感できるものがあると思いますので、そちらもお楽しみにしてください。