2014-05-pre-Rapperswil mailingのレビュー: N3980-N3989

引き続き、2014-05-pre-Rapperswil mailingをレビューしていく。

N3980: Types Don't Know #

「型はハッシュのことなんざ知ったこっちゃねえんだよ」という挑発的なタイトルの論文

ある型をunorderedコンテナーに対応させるには、ハッシュ値が計算できなければならない。ユーザー提供したクラスは、ユーザーが自力でstd::hashを特殊化してハッシュ値の計算を実装しなければならない。問題は、適切なハッシュの計算というのは、極めて難しい技術であり、そんじょそこらの並のプログラマーは正しく書くことが出来ない（我は書けるなどと豪語するのはバカの証拠である）

これまで、N3333やN3876で、バカでもユーザー定義型をハッシュ対応させられるようにしようという提案が出ていたが、これはどちらも、std::hashに既存の対応した型を放り込んでハッシュ値を生成するのを楽にしようというライブラリであって、汎用性に欠ける。

そこで、ハッシュアルゴリズムをテンプレートで変えられるようにし、また、演算子を定義するかのようにクラスをハッシュ計算に対応させられる新たなライブラリ、std::uhashを提案している。

「型はハッシュの事情など知らぬ」というのは、型はハッシュ値がどのように計算されるかという事情など知ったことではないし、知るべきでもないということだ。型が知っているのは、型のオブジェクトを区別化するための情報だ。ハッシュ値計算に必要な、オブジェクトが等しいか状態にあるかどうかに関わる情報を、ハッシュ値計算に混ぜ込む方だ。ハッシュ値がどのように計算されるかという内部事情を知る必要はない。

N3980では、ハッシュ計算に対応させたいクラスに、friend関数hash_appendを定義させる。そして、hash_appendをADL経由で呼び出す。

class X
{
    int i ;
    std::vector<int> v ;

public :
    template < typename HashAlgorithm >
    friend
    void
    hash_append( HashAlgorithm & h, X const & x ) noexcept
    {
        // unqualified lookupでADLを発動させ、
        // ADL経由で見つからなかった時にstd::hash_appendを発見できるようにするための
        // 小汚いテクニック
        using std::hash_append ; 

        hash_append( h, x.i, x.v ) ;
    }
} ;

このように、std::hash_appendをusing宣言で関数のブロックスコープに引っ張りこんでおいた上で、unqualified lookupでhash_appendを関数呼び出しする。すると、ADLで発見されるhash_appendと、std::hash_appendが等しくオーバーロード解決の候補となり、最適な関数が呼び出される。

クラス定義内でfriend関数定義をしているので、このhash_appendは、ADL経由でしか呼び出すことが出来ない。

実際にハッシュを計算するのは、テンプレート引数HashAlgorithmによって、ハッシュ計算に必要な情報を指示する部分から切り離している。

最終的に、ハッシュ計算はビット列をhashAlgorihmに渡すところにまで落とされる。

さて、hash_appendは、operator ==と密接に関係している。すなわち、

1. x == y ならば、xとyは、hash_appendに同じメッセージを送る
2. x != y ならば、xとyは、hash_appendに異なるメッセージを送る

オブジェクトが等しいならば、同じハッシュ値が計算されて欲しいので、同じ情報が送られなければならない。オブジェクトが等しくないのであれば、異なる情報が送られなければならない。ということだ。

たとえば、vectorを考える。vectorのoperator ==は、size()を比較してから、要素を比較すると定義されている。このため、vectorのhash_appendは、size()をハッシュ計算のメッセージとして送るべきである。

なぜか。もし、size()がハッシュ計算に使われなければ、以下の二つのオブジェクトが、ハッシュ計算では等しいメッセージとして見えてしまう。

std::vector<std::vector<int>> v1{};
std::vector<std::vector<int>> v2{1};

もしsize()をハッシュ計算に使わないと、v1は空なので何もメッセージを送らない。v2は内側のvectorを送るが、内側のvectorは空なので、ハッシュ計算に使うべき情報を送らない。したがって、どちらも同じメッセージになってしまう。

このため、size()をハッシュ値計算に混ぜ込む必要がある。問題は、size()は先に送るか後に送るかということだ。先に送る場合、std::forward_listのようなコンテナは、size()を計算するのにコストがかかるため、コンテナーは後に送るということで統一しようと論文は提案している。

ハッシュ値の計算には、contiguously hashableという概念がでてくる。これは、あるT型の任意の値x, yに対して、x == yならば、memcmp(addressof(x), addressof(y), sizeof(T)) == 0 がtrueとなることである。つまり、x == yならば、xとyは全く同一のビットパターンを持たねばならない。また、パディングビットのような、任意の値を取れるようなビットがあってはならない。

論文では、ある型Tがcontiguously hashableかどうかを調べるtraits、is_contiguously_hashable<T>を提案している。

整数が2の補数表現の環境の場合、intはcontiguously hashableである。

IEEE浮動小数点数は、contiguously hashableではない。なぜならば、0 == -0ではあるが、0と-0のビットパターンは同一ではないからだ。したがって、IEEE浮動小数点数を使う環境では、ハッシュ計算には特別なはからいをしなければならない。

boost::hash_combineとの違いは、hash_appendはビット列をそのまま送り込むのに対し、hash_combineは、個々にハッシュ値を計算し、複数のハッシュ値から、そこそこ使えるハッシュ値を計算するものである。hash_appendの方がハッシュ値計算をネイティブにサポートしている。

hash_appendはVariadic Templatesで実装されていて、引数をいくつも渡せる。

現在、ハッシュ計算としてよく使われているアルゴリズムで、N3980提案で効率的に実装できないものに、CityHashがある。これはCityHashは、後ろから計算していくためである。

とはいっても、CityHashと同等の計算速度や品質をもったアルゴリズムは他にもあるので、CityHashを考える必要はないとしている。

また、このライブラリは、SHA-2などのセキュアなハッシュ値計算に使うためにも転用できる。

pimplにどのように対応するかという問題は、HashAlgorithmをstd::functionでラッパーしてtype erasureすることにより、仮想関数呼び出しで実行時に呼び出し先を決定することができるとしている。

また、unorderedコンテナーのハッシュ計算は、同じ数と値の要素をもつコンテナー同士で同一のハッシュ値を計算する方法は、ないこともないが、どれも一長一短で、汎用的な方法がないため、この提案では規定しないとしている。

この論文を読むのは時間がかかった。

N3981: Removing trigraphs??!

トライグラフを規格から削除する提案。タイトルが面白い。??!はトライグラフで|に置換される。

ある巨大なコードベースに対して、トライグラフ風の文字列を検索した所、

• 923件のトライグラフ置換を防ぐためにエスケープされた?

  string pattern() const { return "foo-????\?-of-?????"; }
  

• 4件のトライグラフが、意図的にテストコードで使われていた。コンパイラーのためのテストコード2件と、boostのプリプロセッサーライブラリのテストコード2件。
• 0件のトライグラフが、意図的にプロダクションコードで使われていた。

明らかに、トライグラフはC++の足かせになっている。

論文は、規格からトライグラフを削除する提案をしていて、そのための文面も提示している。

N3982: Rvalue reference overloads for optional

optionalのメンバー関数、valueとoperator *にref-qualifierがrvalueリファレンス版のオーバーロードを追加する提案。これはむしろ、バグフィクスと言える。

[せっかくやる気になっていたのに忌々しいPDF] Hashing tuple-like types

N3980とは違って控えめな提案。

std::pair, std::tuple, std::arrayをstd::hashに対応させる提案。これにより、tupleなどをunorderedコンテナーに突っ込める。

[嫌気が差すPDF] N3984: Adding attribute reflection to C++.

よくわからない変な提案。TSへの提案のようだが、あまりに違和感を覚える機能のためだろうか。また、どうもサンプルコードに誤りが多い。

どうも論文の記述が詳細ではないので、よく理解しにくいが、この提案は、クラスに、初期化子が書かれたattributeをクラスに付加し、typedefキーワードを使った文法でconstexprインスタンスとして取り出す機能である。typedefキーワードを使った文法は、N3951提案を拡張している。

struct serializable { } ;

struct getter { std::string name ; } ;
struct setter { std::string name ; } ;

struct [[serializable]] X
{
private :
    int index_ ;

public :
    [[ getter{"index"} ]] int index() const { return index_ ; }
    [[ setter{"index"} ]] void set_index( int value ) { index_ = value ; }
} ;

// std::make_tuple( serializable() )  
auto t1 = std::make_tuple( typedef<[[X]]>... ) ;

// std::make_tuple( getter{"index"} ) 
auto t2 = std::make_tuple( typedef<[[&X::index]]>... ) ;

// std::make_tuple( setter{"index"} )
auto t2 = std::make_tuple( typedef<[[%X::set_index]]>... ) ;

このように、クラスやメンバーにattributeを付加し、またtypedefを使って、constexprインスタンスとして取り出すことができる。

また、typedefにはrequires Cという文法で、取り出すattributeをフィルターできる。Cはテンプレート型引数ひとつとり、typedefでattrributeが返されるか否かをboolを返すconstexpr関数である。

struct Bogus { std::string str ; } ;
struct FuckingWhat { std::string str ;} ;
struct this_attribute_is_bullshit { std::string str ; } ;
struct awesome { std::string str ; } ;

template < typename T >
constexpr bool is_awesome
{
    return std::is_same_v<T, awesome> ;
}

struct [[
    Bogus{"Don't mind me."},
    FuckingWhat{"Seriously, I am useless attribute."},
    this_attribute_is_bullshit{"What did you expect huh?"},
    awesome{"I am just awesome."} ]]
X { } ;

/*
    std::make_tuple(
        Bogus{"Don't mind me."},
        FuckingWhat{"Seriously, I am useless attribute."},
        this_attribute_is_bullshit{"What did you expect huh?"},
        awesome{"I am just awesome."}  ) 
*/
auto t = std::make_tuple( typedef<[[X]] >... ) ;

// std::make_tuple( awesome{"I am just awesome."} ) 
auto t = std::make_tuple( typedef<[[X]] requires is_awesome >... ) ;

また、has_attribute<X, A>というtype tratisが追加される。これは、ある型XがattributeとしてA型、もしくはAから派生する型を持っている場合trueを返す。

struct Base { } ;
struct Derived { } ;

struct [[ Derived ]] X { } ;

std::has_attribute_v<X, Base> ; // true
std::has_attribute_v<X, Derived> ; // true

まあ、使い方はいろいろあるだろう。しかし、どうも個人的に、あまりにも文法や意味がわかりにくいコードに思えてならない。

[PDF注意] N3985: A proposal to add coroutines to the C++ standard library (Revision 1)

コルーチンライブラリの提案。Boost.coroutineを土台にしている。

とても重たい論文なので、軽く紹介するだけにとどめるが、std::asymmetric_coroutine<T>とstd::symmetric_coroutine<T>が追加される。

asymmetricなコルーチンとは、コルーチンが呼び出し元を把握していて、特別な操作によって、呼び出し元に実行を返すものである。

symmetricなコルーチンとは、呼び出し元だけではなく、任意のsymmetricなコルーチンに実行を移せる。

[PDFは切り詰められるべき] N3986: Adding Standard support to avoid padding within structures

クラスのパディングを無効にする文法を追加する提案。

C++では、クラスのサイズがいくつになるかは、規定されていない。

以下のようなコードを考える。

struct SomeDataStructure
{
    uint8_t type ;
    uint32_t data ;
} ;

ここで、sizeof(SomeDataStructure)は、1 + 4とはなる保証はない。たとえば、あるアーキテクチャでは、メモリは適切にアラインされていなければならないという制約があるかも知れない。そこで、コンパイラーはパディングと呼ばれる詰め物を挿入して、アラインを合わせようとする。

// このコードはパディングがないものとする
struct SomeDataStructure
{
    uint8_t type ;
    uint32_t : 24 ;
    uint32_t data ;
} ;

また、以下のようなコードを考える。

struct SomeHeader
{
    uint8_t : 4 ;
    uint8_t valid : 1 ;
    uint8_t : 1 ;
    uint8_t id : 2 ;
} ;

この場合、sizeof(FogFrameHeader)が1になる保証はない。なるほど、4 + 1 + 1 + 2は8ビットだが、コンパイラーがパディングを挿入しないという保証は、規格上存在しない。

しかし、このようなコードは、ビット列とその位置が重要なのであって、パディングを挿入してもらいたくないのだ。現実のコードでは、ディスク上のフォーマットや、ネットワークパケットのフォーマット、あるいはメモリを節約するハックなど、ビット列をパディングなしで明示的に指定したい需要が多くある。

このため、主要なC++コンパイラーには、パディングを無効にする独自の機能が提供されている。したがって、パディングを無効にする機能は、標準で存在すべきである。

N3986提案では、既存のビットフィールドの文法を拡張して、-1が指定された場合、次のビットフィールドをアラインせず、すなわちパディングを無効にする意味を持つ。

struct SomeDataStructure
{
    uint8_t type ;
    uint8_t : -1 ;
    uint32_t data ;
} ;

struct SomeHeader
{
    uint8_t : 4 ;
    uint8_t : -1 ;
    uint8_t valid : 1 ;
    uint8_t : -1 ;
    uint8_t : 1 ;
    uint8_t : -1 ;
    uint8_t id : 2 ;
} ;

もし、クラスSの-1ビットフィールドの次のメンバーtがビットフィールドではない場合、そのメンバーのオフセットは、offsetof(S, t) % sizeof(t) == 0を満たす必要がある。

struct S
{
    uint8_t c ;
    char : -1 ;
    uint32_t t ;
} ;

static_assert( offsetof( S, t ) % sizeof(t) == 0, "This shall not be asserted" ) ;

これはTS行きなのかもしれないが、パディングを無効にする機能は、標準で欲しいところだ。

[Yet another goddamn PDF] N3987: Yet another set of C++ type traits.

小粒だが有益な型情報を得るtype traitsを多数追加する提案。

is_default, is_delete, is_extern, is_explicit, is_export, is_final, is_friend, is_inline, is_mutable, is_noexcept, is_override, is_private, is_private_base_of, is_protected, is_protected_base_of, is_public, is_public_base_of, is_thread_local, is_virtual, is_virtual_base_of.

is_defaultとis_deleteは、default化やdeleted定義されたメンバー関数ならばtrueを返す。暗黙にdefault化やdelete定義された特別メンバー関数の場合はどうなるのだろうか。他にも、デストラクターは例外指定を基本クラスから暗黙に受け継ぐ。クラス定義内で定義されたメンバー関数は暗黙にinlineになる。こういう暗黙の型情報はどうなるのだろうか。

論文筆者に問い合わせたところ、明示的であろうが暗黙であろうが、結果には影響を及ぼすべきではないとの回答を得た。論文ではこの問題について明示的に考察していないが、するべきだと思われるので、次の改定版では言及するとのこと。また、暗黙的に指定されたかどうかを調べるis_implicitが必要かもしれないと言っていた。

また、ローカルクラスかどうかを返すis_localや、is_pure_virtual, is_ovberload, is_direct_base_ofなどといったtype traitsも挙げられている。

[PDFだ・・・] N3988: Towards restrict-like aliasing semantics for C++

C++にC99のrestrictの機能を入れるにあたっての議論をまとめた論文。

C99のrestrictを単純にC++に入れられない理由は、thisポインターを経由するクラスメンバーへのアクセス、リファレンスへのrestrict、restrictの有無がオーバーロード解決やテンプレート実引数推定に影響するかどうか、またlambdaキャプチャーなど、C99にはない問題を考える必要があるからである。

しかし、現実の主要なC++コンパイラーを観察すると、すべての主要なコンパイラーは、restrictキーワード、あるいは同等機能を、何らかの方法で実装している。明らかに需要がある。これは標準化が必要だ。

N3989: Technical Specification for C++ Extensions for Parallelism, Working Draft

<algorithm>にタグディスパッチで並列実行版とベクトル実行版を加えるTS(Technical Specification)への提案。

ドワンゴ広告

この記事はドワンゴ勤務中に書いた。これを書いている最中に、筆者の近くの席から、「ああ！　一瞬死んでもらえばいいのか！」という会話が聞こえてきた。実に、プログラマーの会話というのは、文脈を離れると物騒になるものである。

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

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

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