Hatena::ブログ(Diary)

ntnekの日記 このページをアンテナに追加 RSSフィード

2013-11-19

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

(久しぶりすぎて、はてな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が1つ入っている程度)を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に手を出してみました。おかしなところがあれば突っ込んで頂けると助かります…

2011-03-26

[] FDIS完成

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ドラフトとなる。そこまで進めば、たぶん3週間くらい掛かるだろうが、私たちはそのFDISをジュネーブのITTFに送り、最後のup/down国際投票を行う。これはこの夏には完了するだろう。

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

品質に関して

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

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

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

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

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

これから

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

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

2011年8月15〜19日:米国インディアナ州ブルーミントン

2012年3月:米国ハワイ州コナ

2012年9月:米国オレゴン州ポートランド

*1:Conceptのことですね。

2010-04-10

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

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

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
{
};

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

続きを読む

Connection: close