2018-04-23

C++入門書で再帰について解説しようとしたら思わぬ最適化できないコードに出くわした

C++入門書を書き始めて早数カ月、すでに文章量が「江添亮の詳説C++17」の半分近くに達しているが、まだようやくループを説明したところだ。

ループの章を一通り書き終えて、ついでに再帰によってループを実現する方法について軽く触れて章を閉じようと、以下のようなコードを書いた。

void hello()
{
    std::cout << "hello\n"s ;
    hello() ;
}

すると何故かsegmentation faultを起こすではないか。GCCでもClangでも同じ挙動になる。なぜC++コンパイラーはこの程度の末尾再帰を最適化できないのだろうか。

不思議に思って以下のコードも試すと、こちらは問題なく末尾再帰の最適化が行われる。

void hello()
{
    std::cout << "hello\n" ;
    hello() ;
}

違いは文字列だ。今回の入門書では、初心者に簡単にするために、文字列はすべてstd::stringを返すユーザー定義リテラルのoperator "" sを使っているのだ。これにより初心者は、"hello\n"sとかけばstd::stringとして使える。つまり、

auto s = "hello"s ;
s.size() ;

などと書ける。難しいことを一切考えなくてもよい。わたしの本が書き上がって出版されるまでにまだ1年はかかるだろうし、その頃にはC++17が普及している。C++17を使って初心者でも学びやすい記述をすることで、私のC++入門書は初心者にも優しい本になるだろう。そう考えていた矢先に何ということだ。

どうもstd::stringがあると末尾再帰の最適化が行われないらしい。しかしおかしい。一時オブジェクトの寿命はリファレンスにより寿命延長されない場合はfull-expressionの中までのはずだ。したがってこのコードはまだ末尾再帰のはずだ。再帰呼び出し後に何かする必要は何もないはずだ。

不思議に思って以下のコードを試してみたが、やはり末尾再帰の最適化はされていない。

void hello()
{
    {
        std::string s = "hello\n" ;
        std::cout << s ;
    }
    hello() ;
}

これなら一時オブジェクトでもないしブロックスコープを明示的に使っているし問題はないだろうと思ったが、なぜかコンパイラーは末尾再帰の最適化を諦めてしまう。

では関数で包んでしまうというのはどうか。

void hello()
{
    []{ std::cout << "hello\n"s ; }() ;
    hello() ;
}

これはうまくいった。関数で包んだ場合、コンパイラーは末尾再帰を最適化する。

コンパイラーの気持ちはよくわからない。

2018-04-18

2018-04でC++のドラフトに入った変更

C++のドラフトが更新されている。最新版はN4741だ。

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/n4741.pdf

変更点はEditor's Reportに書いてある。

N4740: N4740 Editors' Report -- Programming Languages -- C++

今回入った主要な変更は以下の通り。

P0840R2: Language support for empty objects

[[no_unique_address]]属性の追加。

この属性は、クラスが状態を持たずクラスを表現するためにストレージを割り当てなくてもよいことを意味する。

クラスには、存在すること自体に意味があり、そのオブジェクトに特に意味はないクラスがある。


template<typename Key, typename Value,
         typename Hash, typename Pred, typename Allocator>
class hash_map {
  Hash hasher;
  Pred pred;
  Allocator alloc;
  // ...
public:
  // ...
};

このようなコードで、HashやPredやAllocatorといったクラスが状態を持たないもののみを使用可能だと取り決めた場合、ストレージを割り当てる必要がない。しかし、このような基本クラスや非staticデータメンバーであっても、アドレス可能にするために最低でも1バイトはストレージを割り当てる必要がある。

[[no_unique_address]]はこのようなストレージの確保を必要としない、アドレスを取る必要がない型に使うことで、不必要なストレージの割当を回避することができる。


template<typename Key, typename Value,
         typename Hash, typename Pred, typename Allocator>
class hash_map {
  [[no_unique_address]] Hash hasher;
  [[no_unique_address]] Pred pred;
  [[no_unique_address]] Allocator alloc;
  // ...
public:
  // ...
};

P0962R1: Relaxing the range-for loop customization point finding rules

range-based forはメンバー関数begin/endのいずれか片方を持っている場合は、ADLによるbegin/endの検索を行わない。しかし、たまたまクラスがbegin/endという名前の片方のメンバー関数だけを持っていた場合も、ADLによる検索が行われない。

range-base forはbegin/end両方のメンバー関数を持つ場合のみADLによる検索を行わないようにする変更。

当然の話だ。

[PDF] P0969R0: Allow structured bindings to accessible members

クラスを構造化束縛する場合、メンバーはpublicでなければならないとされている。


class Three
{
    int a, b, c ;
} ;

void f()
{
    Three t{1,2,3} ;
    auto [a,b,c] = t ; // エラー
}

しかしこれはおかしな話だ。というのも、アクセス指定というのは使った文脈が重要だからだ。


class Three
{
    int a, b, c ;
    friend void f() ;
public :
    Three( int a, int b, int c )
        : a(a), b(b), c(c) { }
} ;

void f()
{
    Three t{1,2,3} ;
    // エラー、friendなのに
    auto [a,b,c] = t ; 
}

構造化束縛でpublicなメンバーに限らず、アクセスできる場所ではアクセスできるようにする変更。

当然すぎる。

P0961R1: Relaxing the structured bindings customization point finding rules

構造化束縛でメンバー関数getが見つかったときに、テンプレートではない場合は、ADLで検索する機能。

これも当然だ。

P0634R3: Down with typename!

文脈上型であることが明らかな場所では依存名にtypenameを付けなくても良くする機能。

template < typename T >
using type = typename T::type ;

と書くかわりに、

template < typename T >
using type = T::type ;

と書ける。他にも様々な文脈上型しか書けない場所でtypenameを省略できる。

P0780R2: Pack expansion in lambda init-capture

ラムダ式の初期化キャプチャーの中でパック展開できる機能。

たとえば、パラメーターパックをstd::moveしつつパック展開して初期化キャプチャーするには以下のように書ける。

template < typename ... Types  >
void f( Types & ... args )
{
    [ ... args = std::move(args) ]
    (){ } ;
}

P0479R5: Proposed wording for likely and unlikely attributes (Revision 5)

分岐先の実行されやすさを指示できる[[likely]], [[unlikely]]属性の追加。

ある分岐先が実行されやすい時、あるいは実行されにくいときがコンパイル時にわかっているときは、その情報をコンパイラーにヒントとして伝えることで、コンパイラーは実行されやすいコードをよりキャッシュに乗りやすいホットな領域に配置したり、コード生成を工夫したりといった最適化ができる。


// めったに起こらないエラーの確認
if ( check_uncommon_error() )
{
    [[unlikely]] ;
    // エラー時の処理
}

// 必ず成功するはずの初歩的なチェック
if ( sanity_check() )
{
    [[likely] ;
    // 通常の処理
}

P0905R1: Symmetry for spaceship

比較演算子としてoperator <=>が追加されたが、"a <=> b"が合法であるならば、"b <=> a"も合法であり、かつその結果も自然なものになるように規定する変更。

[PDF] P0754R2: version

何もしないヘッダーファイル<version>の追加。このヘッダーファイルはコンパイラーによって定義される実装依存の定義済みマクロなどを定義ささせるのに使われる。そのような定義済みマクロを使うには、何らかの標準ヘッダーを#includeしなければならず、そのような軽量ヘッダーとして追加された。

P0355R7: Extending to Calendars and Time Zones

<chrono>にカレンダー機能を追加する。ユーザー定義リテラルによりコード中でも読みやすくなる。

int main()
{
    auto date = 2018y/April/18 ;

    // 2018-04-18
    std::cout << date << "\n" ;

    // 2018-04-19
    date += 1 ;
    std::cout << date << "\n" ;
    
    // 2018-03-25
    date -= 25 ;
    std::cout << date << "\n" ;
    
}

日付処理が簡単にできるようになる。

[PDF] P0122R7: span : bounds - safe views for sequences of objects

spanライブラリの追加。これは連続したストレージ上の配列を扱うストレージを所有しないライブラリだ。

ロシア、Telegramをブロックするために180万ものIPアドレスをブロック

Russia Bans 1.8 Million Amazon and Google IPs in Attempt to Block Telegram

ロシアはインスタントメッセージングサービスのTelegramをブロックするため、AmazonやGoogleの所有する約180万ものIPアドレスをブロックした。

以下がそのIPアドレスの範囲で、1835008個のIPアドレスになる。


52.58.0.0/15
18.196.0.0/15
18.194.0.0/15
18.184.0.0/15
35.156.0.0/14
35.192.0.0/12

Telegramの創始者は以下のような声明を出したそうだ。

Telegram: Contact @durov

過去24時間でTelegramはロシアのISPによってBANされた。理由は我々が暗号鍵をロシアの諜報機関に提出するのを拒んだためだ。我々にとってこれは容易い選択であった。我々は顧客に対し100%のプライバシーを約束しており、約束を守れぬのであればむしろ消えるべきであるからだ。」

BANにもかかわらず、ユーザーの利用率は極端に落ちていない。これはロシア人は政府の検閲に対抗するために日常的にVPNやプロクシーを使っているためである。また我々はサードパーティのクラウドプロクシーサービスを使うことで部分的にユーザーにサービスを提供し続けている。

ロシアのTelegramユーザーの皆さんの協力に感謝する。また政治的検閲に与しなかったApple, Google, Amazon, Microsoftにも感謝する。

ロシアはTelegramユーザーの7%を占めている。ロシア市場を失ったとしても、他の地域でのユーザーの増加がこの穴を数ヶ月以内に埋めるであろう。しかし、ロシアのユーザーにサービスを提供し続けることは個人的にも重要だ。

ロシアとその他の地域におけるインターネットの自由を守るために、私はsocks5プロクシーとVPNを提供する個人や団体にbitcoinを寄付することにした。私はこの運動のために今年数百万ドルを喜んで寄付するし、私に続く者が出てきてほしい。私はこれをデジタル抵抗軍を呼ぶ。電磁的自由とその進展に対する草の根活動だ。

一方、日本では出版社が両手を上げて、緊急避難によるIPアドレスのブロックに賛同している。日本もロシアや中国と同じ道を辿りつつある。隷属への道は近い。

2018-04-07

江添ボドゲ会@4月15日

connpass: 江添ボドゲ会@4月15日

江添ボドゲ会、今月は4月15日。

ゴールデンウィークあたりに鍋会もしたい。

2018-04-05

入門書の文章量が増える問題

C++17の参考書を書き終えた今、この世に必要なのはC++の入門書だ。そこでC++の入門書を苦しみながら書いているのだが、一つ問題がある。文章量が多いということだ。

今書いているC++の入門書は、まだ本の序盤までしか書いていない。C++のソースコードのコンパイルと実行方法、ビルドシステム、そしてようやく条件分岐を半分ぐらい書いた。後は付録としてプリプロセッサーを解説した。その程度だ。

しかし、wcで現行を単一のHTMLファイルに変換した結果を大雑把に計算すると、今書きかけのC++入門書が"2335 7876 178578"に対し、完成したC++17本が"8280 31208 639671"だ。まだ条件分岐までしか書いてないというのに少し分量が多くないだろうか。

考えてみると、文章量が多くなるのも無理はない話だ。初心者の気持ちに寄り添って書いている結果、「整数と浮動小数点数を演算すると結果は浮動小数点数になる」と書けば済む程度のところを、

  1. 整数と浮動小数点数を演算するとどうなるのだろうか?
  2. 確かめてみよう。
  3. ソースコード
  4. 実行結果
  5. なるほど、整数と浮動小数点数を演算すると浮動小数点数になることがわかる

などという冗長な書き方をしているためだ。これでは文章量が増えるのも当然だ。

しかし、冗長ではない書き方をするとなると、結果的にリファレンスマニュアルのような無味乾燥とした記述が続く。それで入門できる人間は、規格書とか私が昔書いたC++11/14コア言語を読めばC++を学べるはずだ。

とはいえ、文章量が多いとそれだけ読むのに労力がかかり、ただでさえ人間の脳に負担を強いる全く新しいプログラミング言語の習得に、長文を読むという追加の負担を強いることになる。

この問題をどうすればいいのだろう。Bjarne StroustrupのC++入門書があまりにも長大で鈍重で悪書の見本のような参考書であるとかつてあざ笑ったが、これは笑えない由々しき問題だ。このペースで書き続けると鈍器として凶器転用可能な重量を持つ入門書ができあがってしまう。

ドワンゴ広告

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

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

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