2014-08-25

2014-07 post Rapperswil mailingのレビュー: N4060-N4069

[PDFも変更されるべき] N4060: Changes to vector_execution_policy

Parallelism TSに対する、ベクトル実行の定義を変更する提案。

並列実行とベクトル実行は、ループの個々の繰り返し単位を、順不同で実行するものである。このため、コードが実行される順序という保証がなくなる。また、例外や同期などの処理も行えないという制約がある。

並列実行ポリシー(parallel_execution_policy)とは、スレッド風の実行エージェントよりループを並列に実行するものである。ベクトル実行ポリシー(vector_execution_policy)とは、SIMDやGPUによる実行エージェントによりループを並列に実行するものである。

しかし、現実のアーキテクチャが提供するSIMD命令を考えると、SIMDによる1スレッド内のベクトル実行による実行エージェントとしては、現在のベクトル実行ポリシーの定義は、必要以上に制約が強すぎる。制約というのは、順序の無保証だ。1スレッド内のSIMD命令による並列実行では、先のループ単位の実行が、後のループ単位を追い越さないという保証を与えることができる。

当時、parallelism TSを議論している際には、実行ポリシーを、シーケンシャル、パラレル、ベクトル、パラレル+ベクトルに分類していた。しかし、純粋なベクトル実行に与えられるこの順序保証の需要があるのかどうか不明であったため、標準化委員会は、純粋なベクトルを廃して、パラレル+ベクトルを、ベクトルと称した。これにより、現在のベクトル実行はパラレル実行の制約をさらに強くする形で定義され、GPUなどの実行エージェントもサポートできるようになった。

ところが、Intelが最近、顧客のコードを検証したところ、ベクトル実行の順序保証を活用したコードが、すでに数多く書かれていることが判明した。コードが存在する以上、需要はある。そこで、この論文は、現在のパラレル+ベクトルとなっているベクトルの定義の変更を提案している。また、この変更は、もはやTSを変更する時間的余裕が無いため、TS本体への適用ではなく、TSに対する参考として公開する形をとっている。

提案は二つある。

最小限の変更による提案は、現在のベクトルは、実際にはパラレル+ベクトルなので、vector_execution_policyをparallel_vector_execution_policyに、vecをparvecに改名するものである。

理想の提案は、ベクトル実行を純粋にベクトル実行として、並列実行とは別に、最小限度の制限で定義するものである。

結局、こんなことになったのも、コードが表に出ないからだ。情報が表に出ないからだ。公開されていない情報は、存在しないも同義である。存在しないものには需要があるわけがない。標準化委員会が新機能を設計するにあたって需要を認識できるわけがない。C++は、長年、C++に利害関係を持つものが標準化委員会に参加し、知見を出し、規格に貢献して今の位置に至ったのだ。標準化委員会に参加しないどころか、情報すら表に出さないのでは、その分野は永久に標準化されることはない。

お前ら表にでろ。

[PDFを最小公倍数にするな] N4061: Greatest Common Divisor and Least Common Multiple, v3

最大公約数と最小公倍数を求める関数、gcdとlcmを<numerical>に追加する提案論文の第三版。

ちなみに、constexpr関数であり、さらに任意の整数型に対して使える関数テンプレートとなっている。

実装は短いが、標準でほしい関数ではある。

// 実装例
template< class T >
constexpr auto abs( T i ) -> std::enable_if_t< std::is_integral<T>{}(), T >
{ return i < T(0) ? -i : i; }

template< class M, class N = M >
using common_int_t = std::enable_if_t< std::is_integral<M>{}() and std::is_integral<N>{}()
, std::common_type_t<M,N>
>;

template< class M, class N >
constexpr common_int_t<M,N> gcd( M m, N n )
{ return n == 0 ? abs(m) : gcd(n, abs(m) % abs(n)); }

template< class M, class N >
constexpr common_int_t<M,N> lcm( M m, N n )
{ return m == 0 or n == 0 ? 0 : (abs(m) / gcd(m,n)) * abs(n); }

int main()
{
    gcd( 2, 3 ) ; // 1
    gcd( 10, 15 ) ; // 3

    lcm( 2, 3 ) ; // 6
    lcm( 8455, 99 ) ; // 837045
}

前回の論文からの変更はそれほど特筆するものはないようだ。

[PDFは平行世界に飛ばされるべき] N4063: On Parallel Invocations of Functions in Parallelism TS

Parallerism TSで、sortなどのユーザーの提供する関数オブジェクトを取るアルゴリズムを並列実行した時に、その関数を並列に呼び出せるのかどうかということについて、文面は何も規定していないということを、Hans Boehmが指摘した。この問題を議論するために、論文を書き、Rapperswil会議で議論した結果の改訂版。

BinaryPredicate, Compare, BinaryOperationは、実引数を変更してはならないという文面が付け加えられる。これにより、安全に並列に呼び出すことができる。

N4064: Improving Pair and Tuple (Revision 2)

tupleとpairで、以下のようなコードが動かないので、動くように変更する提案。

std::tuple<int, int> pixel_coordinates() 
{
  return {10, -15};  // Oops: Error
}

struct NonCopyable { NonCopyable(int); NonCopyable(const NonCopyable&) = delete; };

std::pair<NonCopyable, double> pmd{42, 3.14};  // Oops: Error

これは当然動いてもいいコードで、実際、このコードが動くようにtupleやpairを実装することが可能である。なぜ動かないのか。

実は、当時ライブラリを設計していた時の議論で、危険な暗黙の型変換を防止するために、必要以上に制約を加えてしまったのだ。

更に調査を進めると、tupleは、TR1の複数のテンプレート仮引数を使う設計から、標準規格のVariadic Templatesを使う実装に変更する際に、極めて重要な規程が抜け落ちてしまっていた。

template <class T1 = unspecified ,
          class T2 = unspecified ,
          ...,
          class TM = unspecified >
class tuple
{
public:
  tuple();
  explicit tuple(P1, P2, ..., PN); // iff N > 0
  […]
};

コメント部分の、"iff N > 0"という制約が、tupleのVariadic Template版の文面を作成する際に、抜け落ちてしまったのだ。

そして、論文では、危険すぎる暗黙の型変換は防ぎつつ初期化が行える、Pefect Initializationというテクニックを紹介している。

#include <type_traits>
#include <utility>

template<class T>
struct A {
  template<class U,
    typename std::enable_if<
      std::is_constructible<T, U>::value &&
      std::is_convertible<U, T>::value
    , bool>::type = false
  >
  A(U&& u) : t(std::forward<U>(u)) {}

 template<class U,
    typename std::enable_if<
      std::is_constructible<T, U>::value &&
      !std::is_convertible<U, T>::value
    , bool>::type = false
  >
  explicit A(U&& u) : t(std::forward<U>(u)) {}
  
  T t;
};

非explicitコンストラクターとexplicitコンストラクターを、SFINAE技法で制約を加えることにより、以下のように、危険な暗黙の型変換は防ぎつつ、自然に初期化ができるようになる。

struct Im{ Im(int){} };
struct Ex{ explicit Ex(int){} };

A<Im> ai1(1); // OK
A<Im> ai2{2}; // OK

A<Im> ai3 = 3;   // OK
A<Im> ai4 = {4}; // OK

A<Ex> ae1(1); // OK
A<Ex> ae2{2}; // OK

A<Ex> ae3 = 3;   // Error
A<Ex> ae4 = {4}; // Error

なぜ複数の引数を取るコンストラクターがexplicitではないとまずいのかということを、以下のような面白いコードで説明している。


#include <tuple>
#include <chrono>
#include <iostream>

using hms_t = std::tuple<std::chrono::hours, std::chrono::minutes, std::chrono::seconds>;

void launch_rocket_at(std::chrono::seconds s)
{
  std::cout << "launching rocket in " << s.count() << " seconds!\n";
}

void launch_rocket_at(hms_t times)
{
  using namespace std;
  launch_rocket_at(get<0>(times) + get<1>(times) + get<2>(times));
}

int main()
{
  using namespace std;
  launch_rocket_at(make_tuple(1, 2, 3)); // #1: ヤバイ
  launch_rocket_at({1, 2, 3});           // #2: もっとヤバイ
  using namespace std::chrono;
  launch_rocket_at(make_tuple(hours(1), minutes(2), seconds(3))); // #3: すっげーわかりやすい
  launch_rocket_at({hours(1), minutes(2), seconds(3)});           // #4: これもわかりやすい
  launch_rocket_at(hms_t{1, 2, 3});                               // #5: これでもいい
}

explicitではないと、暗黙の型変換が仕事をしすぎてしまうので、型による警告ができない。

N4065: make_array, revision 2

arrayを返すmake_arrayの提案

// N4065提案
// std::array< int, 4 >
auto a = std::make_array( 1, 2, 3, 4 ) ;

前回のN4031からの変更点として、型を明示的に指定する場合、make_arrayではなく、array_ofを使うようになった。

// N4031提案
auto a = std::::make_array<long>( 1L, 2L ) ;

// N4065提案
auto b = std::array_of<long>( 1L, 2L ) ;

文字列リテラルをcharのarrayにするto_arrayに変更はない。

// N4065提案
// std::array< char, 6 >
auto a = std::to_array("hello") ;

実装例がGitHubに上がっている。

Factory function of std::array

N4066: Delimited iterators (Rev. 3)

ostream_iteratorにはデリミターを指定できる。ただし、このデリミターは、実際にはサフィックスというべきである。

std::vector<int> v = { 1, 2, 3 } ;

std::copy( v.begin(), v.end(), std::ostream_iterator<int>( std::cout, ", " ) ;

このコードを実行した結果の出力は、"1, 2, 3, "となる。

この論文は、正しくデリミターとして働く、つまり要素の間にしかデリミターを出力しない、ostream_joinerというライブラリを提案している。上記コードでostream_iteratorの代わりに使うと、"1, 2, 3"となるクラスだ。

N4067: Experimental function etc.

標準ライブラリに対する拡張TSである、N4023: Working Draft, C++ Extensions for Library Fundamentalsでは現在、std::functionなど、標準規格の標準ライブラリを直接参照している。これはTSをサードパーティが実装するのに都合が悪い。そのため、function, promise, packaged_taskと同等のものを、std::experimental名前空間に存在させるための文面変更案。

N4068: Toward More Expressive Iterator Tags

Rapperswil会議で、N3976で提案されている多次元配列ビューを議論したところ、この論文で提案されているイテレーターの一部は、random access iteratorであると自称しながらも、実はforward iteratorの要件すら満たしていないことが指摘された。

これは、現在のイテレーターカテゴリーの要件が粒度が荒すぎるのが問題である。もっと細かい要件に分割して、要件を組み合わせて指定できるべきである。そのための方法としては、議論ではコンセプトが最適であるという方向で一致したが、とりあえずイテレータータグで対応する提案。

論文で提案されている細かい粒度のイテレータータグは以下の通り。

struct referene_tag { } ;

*iterがプロクシーではなく、実際にvalue_type&であり、その値はイテレーターによりキャッシュされたものではないこと。

struct lvalue_tag { } ;
struct rvalue_tag { } ;

*iterが変更可能なlvalue、もしくはrvalueであること(両方であることもあり得る)

struct equality_comparable_tag { } ;

iter1 == iter2がwell-formedであること

struct multipass_tag { } ;

iter1 == iter2であれば、++iter1 == ++iter2、かつ、&*iter1 == &*iter2であること

struct decrementable_tag { } ;

--iterがwell-formedであること。

struct random_move_tag { } ;

iterが任意の距離を移動でき、less-than comparableであること

さらに、これらのタグをまとめて指定できるbasic_iterator_tagを以下のように定義する。

template < typename ... Tags >
struct basic_iterator_tag { } ;

すると、既存のイテレータータグは、以下のように定義できる。

    typedef basic_iterator_tag<lvalue_tag> output_iterator_tag;

    typedef basic_iterator_tag<rvalue_tag, equality_comparable_tag>
              input_iterator_tag;

    typedef basic_iterator_tag<reference_tag,
                               lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag>
              forward_iterator_tag;

    typedef basic_iterator_tag<reference_tag,
                               lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag,
                               decrementable_tag>
              bidirectional_iterator_tag;

    typedef basic_iterator_tag<reference_tag,
                               lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag,
                               decrementable_tag,
                               random_move_tag>
              random_access_iterator_tag;

これを使えば、例えばvector<bool>のイテレータータグは以下のように定義できる。

    typedef basic_iterator_tag<lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag,
                               decrementable_tag,
                               random_move_tag>
              vector_bool_iterator_tag;

ドワンゴ広告

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

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

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

3 comments:

  1. 公開されていない情報は存在しないも同義と信じているのなら、現実の需要と乖離した使えない標準を垂れ流し続ければ良いのでは?
    本気で標準化しようと努力せず、結果がついてこないのを他人のせいにしたがる人にぴったりだと思います。

    ReplyDelete
  2. 個人的には、タプルの変更を歓迎ですね。
    最近タプル使ったコードをよく書くので簡素になるならそれもいいです。
    タプルのアラインメントを構造体並の保障にしてほしいというのが最近の願望です。
    まぁ、ライブラリのないもののコードも書けませんのでぜひVCEEにパラレリズム入ってほしいですね。
    改良は偉い人に任せてフレームワーカーとしてコード書きたいと思います。

    ReplyDelete
  3. そもそも※1の人は何に腹を立ててるんだろうか。
    本気で標準化するには調査員が各企業を訪ねて回れとでもいうのだろうか。標準化を望む側が必要な情報を提供するのが筋だと思うが。

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.