容量チェックをしないpush_back()

C++

（久しぶりすぎて、はてなDiaryの使い方忘れた…）

vector<>::push_back()を使って要素を追加していく場合、push_back()の内部では必要な容量を確保する処理が行われます。

struct T { ... };
vector<T> v;
for (size_t i = 0 ; i < N ; ++i) {
  v.push_back(T{}); // 毎回内部バッファの容量をチェックし、足りなければreallocation
}

多くの要素を追加する場合には、あらかじめreserve()などで適当な容量を確保していなければ、メモリアロケーションやリアロケーションが頻発することになり、非効率的です。

v.reserve(N);
for (size_t i = 0 ; i < N ; ++i) {
  v.push_back(T{}); // 毎回内部バッファの容量をチェックするが、足りているのでreallocationは起こらない
}

ではreserve()すればまったく問題無いかというとそうでもなく、確保済みのメモリ領域に空きがあるかどうかのチェックはどうしても必要になります。
このチェック自体はそれほど重たいものではありませんが、非常に沢山の要素を追加する場合には多少の影響があるようです。


さて、おおよそどの程度の要素が追加されるかあらかじめ予想できる場合、そもそもreserve()とpush_back()のような迂遠なことをしなくても、resize()とdata()を使って値を突っ込んでいけば良いわけです。

v.resize(N);
auto* p = v.data();
for (size_t i = 0 ; i < N ; ++i) {
  p[i] = move(T{}); // 内部バッファの容量チェックは一切行わない
}

…が、どうしてもpush_back()を使いたい！というケースもあると思います。
（「ある」ということにして下さい。後が続かないので。）

そうした場合に簡単に使えるラッパーコンテナを作ってみました。
こんな感じに使えます。

#include "nochecking_sequence.hpp"
using xxcxx::nochecking;

vector<T> v;
v.resize(N);
auto w = nochecking(v);
for (size_t i = 0 ; i < N ; ++i) {
  w.push_back(T{}); // 内部バッファの容量チェックは一切行わない
}

今回は試していませんが、emplace_back()も同じ要領でできると思います。


手元のマシンで小さなオブジェクト（std::stringが１つ入っている程度）を100万回push_backして計測したところ、以下のような結果になりました。

方式 実行時間[sec]
reserve()なし 0.085938
reserve()あり 0.054688
nochecking() 0.046875

…多少は効果があるようですね。

ちなみに、-O3を付けない場合はreserve()に負けてしまいます。ラッパーオブジェクトの生成に時間が掛かるようです。
さらに、push_back()の後からresize()で切り詰める*1と、なぜかreserve()版と同程度の速度まで下がります。何故だろう…。

ソースコードはこちらから参照下さい*2。
https://github.com/kentdotn/cxx-experiment/tree/master/nochecking_container

*1:実際に必要な容量より大目にreserve()しておいた場合など。

*2:せっかくなのでGitHubに手を出してみました。おかしなところがあれば突っ込んで頂けると助かります…

FDIS完成

C++

Herb Sutterのブログ記事を翻訳してみました。
誤訳についてはご勘弁を・・・。

    • -

FDIS完成！ (Trip Report: March 2011 C++ Standards Meeting)

2011年3月25日 Herb Sutter

速報：今日の午後、ISO C++委員会はC++0x標準への最後の技術的な変更を承認した。プログラム言語C++の新しい国際標準は2011年夏に発行される見込みだ。

3月21日から25日にかけて、2011年春のISO C++会議がスペインのマドリッドで開かれた。既に報告したように、この会議のゴールは、最終委員会ドラフト(FCD)に対するNational Bodyからのコメントへの返答を完了すること、最後の技術的変更を受理すること、そして最終国際投票に向けた国際標準最終ドラフト(FIDS)を承認すること、であった。

私たちはそのゴールに到達した。この会議だけでなく、マドリッドに先んじて行われた会議やその間に必死に作業した皆さんのおかげで、私たち今週の十分早い段階でいくつかの優先度の低い機能を解決するのに着手できるくらい仕事を終えていた。当初予定されていた土曜日を丸一日作業に当てるのではなくて。（つまり、それは休日ではないのだ。ISO C++委員会にとってはいつものことなのは、ほとんど毎日、委員会メンバーの大雑把に半分くらいは、深夜まで技術グループのセッションで特定の課題について作業したり、提案された文面の変更について更新したりレビューしたりして、明るくなった翌日の朝早くからまた作業を開始する）

我々はプロセスのどの段階まで進んだか？

マドリッド時間で金曜日の16時ごろ、委員会はFIDS文書の承認を採択し、我々のホストでありプロジェクトエディターであるPete Beckerに、サブグループ議長であるBjarne Stroustrup, Steve Adamczyk, Alisdair Meredith, Howard Hinnant, Lawrence Crowl, Hans Bohemに、そして私たちをこの地点まで導いてくれた、ここ数年にわたって懸命に働いてきたほかのすべての皆さんに喝采と感謝を送った。

すべての作業が終わったわけではない。プロジェクトエディターはこの会議で承認された変更を作業ドラフトに更新しなければならないし、多数のボランティアからなるレビュー委員会はそれらの編集が間違いないことを確認するためにそれをレビューする。その結果がFDISドラフトとなる。そこまで進めば、たぶん３週間くらい掛かるだろうが、私たちはそのFDISをジュネーブのITTFに送り、最後のup/down国際投票を行う。これはこの夏には完了するだろう。

すべてがうまくいけば、そしてそうなると期待しているが、この国際標準は2011年中には承認・発行され、それ以降、C++ 2011として知られるようになるだろう。

品質に関して

１５年前の最初の時と同様、今回も私たちは第二のC++標準を製作するのに最初に考えていたよりも長い時間を掛けた。これは初期の野心的な機能スコープ*1のためということもあるが、主には品質のためだ。

おそらく私にとって一番心強いのは、この標準は過去にWG21で発行されたFDIS文書の中でも最高の品質であると委員会の古参メンバーの中でも広く受け止められているということだ。そしてまた、最初の標準のFDIS…これは1998年の早い時期の投票のために1997年に承認したのだが…にくらべてずっとよい形のものにできたと確信している。今回は、実質的にすべての機能は少なくともいくつかの出荷済みのコンパイラで実際に実装されているので、設計の混乱や全体的な設計リスクは極めて小さい。これは、C++0xの拡張の大部分を（標準ではない）ライブラリ拡張TR（またはライブラリTR, あるいはTR1）という形で出しておいたことがとりわけ役に立った。これによって、その機能のベンダー実装が早いうちから促され、それらを国際標準に纏め上げる前に委員会が調整（必要であれば破壊的な変更も）することを可能とした。

もちろん、バグがあることは分かっているし、いつもどおり欠陥レポート(DRあるいはバグ修正とパッチ）の作成を次回以降の数回の会議では継続して行うことになると予想している。しかし、それはより小さなものになるだろうし、最初の標準で５年もひきずったことに比べるとずっと短期間で済むだろうと関係者の多くは自信を見せている。

だがともかく、1997年11月のモーリスタウンでJosse Laijoieが高らかに言ったように、そしてこの午後にBjarne Stroustrupやその他の面々が声をそろえたように、「よし、やり遂げたぜ！」なのだ。

もう一度、個人的に、あるいは電子的にこの標準に貢献してくれたすべての皆さんに、私個人からの感謝の気持ちを表明したい。あなた方が居なければ、私たちは成し遂げることができませんでした。ありがとう。そしてこの瞬間を楽しみましょう！

これから

年に一度はアメリカ国外で会議を開くのが我々の伝統で、これは世界のさまざまな地域に住む人々に参加しやすくするためでもある。来年、以前行ったように、この「アメリカ外」会議はコナで行われる。これは参加を検討している東アジアやオーストラリアの皆さんにはより近い場所だ。

2011年の残りと2011年のISO C++標準会議の開催日時と場所は以下のとおり：

2011年8月15〜19日：米国インディアナ州ブルーミントン
2012年3月：米国ハワイ州コナ
2012年9月：米国オレゴン州ポートランド

*1:Conceptのことですね。

文字エンコードつきの文字列

C++

こういうのはどうだろう：

template <class Encoding, class Char = typename Encoding::char_type, class Traits = std::char_traits<Char>, class Allocator = std::allocator<Char> >
class basic_estring
  : public std::basic_string<Char, Traits, Allocator>
  , public Encoding
{
};

つまり自分の文字エンコーディングが何であるか知っている文字列クラス。

続きを読む

Twitterはじめました

とりあえず道化師さんとCryoliteさんをフォローさせてもらうとして、あと誰がいるのかなー。

…と思ったらなんかnentkでアカウント持ってるみたいだぞ？あれぇ？？
ともかくフォローしてもらってる方はかたっぱしからフォローさせてもらうとして…
http://twitter.com/ntnek/followers

Gates77315さんってどなた？

んー、これ、特に有名人の場合は特に断りいれずにフォローしてよいんだろうけど、
なにかハウスルールみたいなのがあるんかなあ。
とりあえず普段読ませてもらっている方は見つけ次第ぶっこんで行くか…。

和訳：Rvalue References: C++0x Features in VC10, Part 2

C++

Stephan T. Lavavej のRvalue References: C++0x Features in VC10, Part 2の適当な訳です。左辺値と右辺値、無駄なテンポラリが生成される問題、新たな参照「右辺値参照」の特徴と使い方、ムーブセマンティクスの意味と使い方、完全転送パターンの書き方、それらを可能にする仕組みと、これに関する C++0x の新たな文法ルールについて書かれています。

特に前半は、この手の記事としてはこれまでで一番分かりやすく丁寧に解説されていると思います。正直よく分かっていなかったんですけど、これを読んでだいぶスッキリしました。

で、ムーブセマンティクスによるテンポラリの除去が日用品のように使えるようになれば、Linus や Linux カーネル開発者たちが「C++なんてクソ言語は使えねぇ！」と主張する（正当な）理由の一つを崩すことができますね。これを機会にさらにC++の適用分野が広がれば…。

あー、でも、これのおかげで複雑な型推論機構がさらにまた複雑になったから、今度はそのあたりを使いこなせる奴が少ないので使えない、とか言われるのかなあ…。翻訳元のコメント欄をいくつか拾ってみると：

  • で、またみんなが C++ は複雑だって言い出すわけね。誰が使うんだよ…
  • C++って複雑になりすぎて押しつぶされちゃうんじゃない？この先は悲観的だなあ…
  • 複雑すぎて手にあまるんだよ。C++の良いとこだけ抜き出した言語があればいいのに

なんて声がちらほら。ただ同じくコメント欄にあるように、そして記事の中でも書かれているように、使う側からすれば細かいところまでいちいち覚える必要はなくて、ポイントになるパターンだけ覚えれば良いわけですね。それだけであとは STL なり boost なりが上手いこと使ってくれる、と。とはいえ、そういうパターンがただでさえ多いのがC++なわけで、思わず悲観的になる人の気持ちも良く分かります。ええ。

続きを読む

文字コード

C++

επιさんところ
http://blogs.wankuma.com/episteme/archive/2008/12/11/163370.aspx

BSDではwchar_tがEUCだったりSJISだったりできるんじゃないかと思います。

職業柄、大量のテキストをC/C++で捌くことが良くあるんですけど、ほとんどのデータはまだまだSJISだったりするわけです。それをWindowsだけでなくLinuxやBSD上で裁こうとすると、互換性の低いMBCS周りの関数でえっちら処理するのもうざいし、こまめにleadbyteの判定をするのも面倒だしバグの元。

そこで、入力直後に無理やりwchar_tに変換したりすることがあります。これだと（特にLinux/BSDでは）１文字１コードが保証されているので、文字列操作部自体は簡潔に書けます。
このときに内部の文字コードが何になっても本質的には大差ないですけど、元がSJISならSJISのままwchar_tに持っていったほうが余計なテーブル引きがなくなる分だけ高速でしょうし、コード変換にからむトラブルも防げてよい感じです。

文字列リテラルの与え方に関しては相変わらず問題ですけど…。