C++ vs. C ; R5G6B5 color pixel transform battle

C++ Advent Calendar 2012 - 22 のC++とCのベンチマークについて気になったので少々書く事に。

the topic based from

• ソフトウエア研究会in秋葉原 - PukiWiki

分り易くて面白い記事なのですが、特にC++とCを比較するベンチマーク部分が少々気に掛かりましたので、とりあえず元記事の「検証3 ビットマップのピクセル処理 (C vs #define vs C++ template)」について触れてみようと思います。

(1) とりあえず試す

元記事のソースを基にビルド可能な必要最小限の変更（main付けたりとか程度）を加えて試してみる。ビルドオプションについてはGCC4.7で有効なO0,O1,O2,O3について試す。

なお、試験環境等は記事の末尾に記載します。また、GCCの最適化オプションについては、末尾のreferencesにGCCのmanの日本語版のリンクを掲載するので「最適化オプション」の項を参考にして下さい。

source (1) ; base codes

• C++ vs. C ; R5G6B5 color pixel transform battle source (1)

result (1) ; base results

• C++ vs. C ; R5G6B5 color pixel transform battle

discussion

C++ は "C より高速"なバイナリーを生成したのか？

• O0に置いてはNO。
• O1に置いてはYES。
• O2に置いてはYES。
• O3に置いてはNO。

ポインターによるマシンネイティブに近い操作に対しデータ構造とアルゴリズムから論理的なプログラミングインターフェースをプログラマーに提供したC++のコードを比較すれば、最適化無しではC++が負けるのもまあ当然。勿論、CでC++がやっているのと同等のインターフェースをプログラマーに提供するライブラリーを作り、それを利用したコードと比べたらゼロオーバーヘッドになるでしょうけれど。

面白いのはO1とO2ですね。O0については素直にC++のライブラリーによる複雑さがCに対して不利になりましたが、O1とO2ではC++コードの方が最適化によりCよりも高速なバイナリーを生成できた様です。

さて、ベンチマークとしてはO3も面白い事に。O3ではO2からさらにループ展開や関数のインライン展開が自動的に行われます。そうすると今度はCの方が圧倒的に高速なバイナリーを出力する結果に。ここまでCが高速化した理由として考えられるのは、test_bitmap_color_transform関数の呼び出し内容が内部のループ含めほぼまるっとmainへとプレーンに展開された可能性がありそうです。一方、O2とO3でほぼ等しいスコアを記録したC++では、標準ライブラリーの複雑さというかデータ構造とアルゴリズムの分離が悪い意味でも上手く機能してしまいコンパイラーがCの単純なコードに対して行った程のインライン展開を出来なかったのでは無いかと推察します。

とりあえず生成されたバイナリーを逆アセンブルして眺めてみましょう。

• master_c.OX
  • c_master.O0.s
  • master_c.O1.s
  • master_c.O2.s
  • master_c.O3.s

test_bitmap_color_transform_pure_c辺りに着目して見ましょう。O0ではCソースと素直に対応する形でJMP/CALLQ/JBEが並んでいるのが分かります。対してO1ではレジスターを効率的に利用したり、ループ初回でループ末尾にJMPしてCMPL/JBEしていたのが除去されてループ末尾でCMP/JNEする様になったりしています。もちろんget_r/get_g/get_b/to_rgbもO0からO1ですっきり。O2ではtest_bitmap_color_transform_pure_cはやたら短くなってMOVZWLからEDX/ECZ/EAXを使いSHL/SHRでちょっとしたレジスター雑技に、O3ではこの関数がループ展開されてベタベタと長くなっています。

ここで、本題の C++ vs. C の前にCマクロ版についても考察して置きましょう。

#define CPPは意味が"無い"のか？

• O0に置いてはNO。
• O1に置いてはNO。
• O2に置いてはYES。
• O3に置いてはYES。

唐突ですが逆アセンブル結果を。

• master_macro_c.OX
  • master_macro_c.O0.s
  • master_macro_c.O1.s
  • master_macro_c.O2.s
  • master_macro_c.O3.s

O0とO1では#define CPPによりtest_bitmap_color_transform_macro_c関数内の処理が全てインライン展開されて居る為にC版、C++版に比べて関数呼び出しコストが極限まで抑えられていてこの最適化レベルでの比較に置いては遥かに高速と言えます。

しかし、O0とO1まではコンパイラーによる最適化ではCPPによるプログラマー手作業のインライン展開に対して非CPP版ではオーバーヘッドがありしたが、O2とO3ではO2の段階で非CPP版と同様のレジスター雑技に最適化されその差が無くなります。よってこの命題「#define CPPは意味が無いのか？」については、少なくともCの範疇のコードを実用的にコンパイルするに置いてはYESと言って良さそうです。

※ちなみに憶測ですが、C++でもCPPによるメタレベルでのインライン展開が意味が無いかと言うと、そうでもない気はします。C++によりコンパイラーが最適化しきれない部分をCPPメタプログラミングで最適化する事はconstexprが実用化されつつあるC++11の現状でも効果のある状況は有り得るかもしれません。

さて、それでは本題。

C++版はC版より高速なバイナリーを生成するのか？

• O0に置いてはNO。
• O1に置いてはYES。
• O2に置いてはYES。
• O3に置いてはNO。

O0については標準ライブラリーの複雑さがそのまま出ているので当然。C++のゼロオーバーヘッドは同等の機能をCで実装するのに対して、なので。ところが面白いのがO1で既にC++の方が高速って事、O2もC++が高速。しかしO3はO2から全く効果が無かった様でC組に負けてしまいました。

例に依って逆アセンブル結果。

• master_fixed.cxx.OX
  • master_fixed_cxx.O0.s
  • master_fixed_cxx.O1.s
  • master_fixed_cxx.O2.s
  • master_fixed_cxx.O3.s

O0のコード量だけが桁違い（109KB、ほかは28KBほど）な時点でまあいろいろお察ししましょう… ・ｗ・；

C++コードではシンボル名がマングルされて _Z31test_bitmap_color_transform_cppRSt6vectorI7pixel_tILi16EESaIS1_EE になっています。この関数直下では boost::for_each （≈ std::for_each）を呼んでいるだけなのでそれほど複雑な事は無く、O0がO1よりも冗長なのは例に依っての程度。ちなみに pixel_t::get_rは _ZNK7pixel_tILi16EE5get_rEv とか。

当然、std::for_eachを呼ぶだけのboost::for_eachすら関数としてそのまま残って呼ばれています。O0ではboost::for_each部分のアセンブリも中で大真面目に受け取ったコンテナーのbeginを呼んで、endを呼んで、それからstd::for_eachを呼んで…その中でもまたソースコードの忠実に冗長なアセンブリーが…と。O1ではboost::for_eachは消えて居ます。

さて、ではどこが最適化されてO0からO1とO2ではC++がCよりも速いコードになったのか、答えはpixel_tの最適化の様です。O0ではpixel_tのメンバー関数がアセンブリーにも存在しますが、O1で既にpixel_tのメンバー関数が見当たりません。そしてCではO2まで最適化されなかったループ内部の処理が、C++ではO1で既にstd::for_eachの中身も比較的すっきりと展開されています。

さらに、O2とO3の主要部分のアセンブリは同等で、ではstd::for_each自体もtest_bitmap_color_transform_cppへ展開され、さらにその展開内容は既にC版のO2でMOVZWL/SHR/SHLなどに最適化されたのともほぼ同様。

ちなみにこの展開されたループ部分ではC++でもCでも実行速度に差は…と、思ったけれど、C++版ではポインターより複雑なstd::vectorのイテレーターを使っている為にそのチェックコードをコンパイラーが省けずにループ前にJEが残るというオーバーヘッドが…。これは今回は現実的にはどうでもよい程度のオーバーヘッドですがちょっと悔しいですね・ｗ・；

しかし、O2においてC++がCより速くなっている理由は、どうやらO2レベルになるとCもC++も主要部分はほぼ同様なアセンブリーに最適化されたとは言え、よく見るとCの主要部分のアセンブリー(master_c.O2.s:0x400820-0x40084E)とC++の主要部分のアセンブリー(master_fixed_cxx.O2.s:0x400FA0-0x400FCA)ではCから生成されたものの方がC++から生成されたものよりも若干だが冗長になってしまっている。この差…かなぁ…。

O3でC++がCに負けた理由はやはりコードの意味から標準ライブラリーの複雑さを大胆にインライン展開できなかった事にありそうです。

(2) …と、思ったけど

(1)ではとりあえず引用元のソースコードをほぼそのまま用いました。しかし、ビットフィールドを用いたらどうなるか？inlineを付けたら？アライメントを指示したら？C++11のfor(:)を使うと？C++11のrvalue referenceも使うと？などなどC++でもCでもソースコードを書くプログラマーレベルでの最適化の予知はまだあります。（何を目的とするコードなのか、ベンチマークであれば何を対象とするのか次第なところではありますが。）

また、現実的にはこの様なR5G6B5のビット操作処理は例えばCPUがまだ200MHzやそこらでDirectXがまだ6とかだった頃でもMMX使ったりは当然実用的には行われて居て（実際その頃にゲーム作りたくて書いたお陰でアセンブラーも基礎は分かるし、その後もSIMDやGPUを応用できる基礎を身に付けられたんだと思っています・ｗ・）、GCCやVC++など一般のPC向けの処理系であれば intrinsics.h からMMXやSSEを使うコード、或いは既に禁忌の古代魔法扱いではありますが昔ながらに__asm{}しても良い訳で…。

確かに C++ vs. C となると標準ライブラリーやBoostなどの有名どころのライブラリーの便利さの上とマシンネイティブに近いCという比較は1つの側面は持ちますが、C++はCのほとんどの仕様を内包し（C99+一部オーバーライド）、インラインアセンブラーもあり（実際インラインよりintrinsics.hや別にオブジェクトを生成するかもしれないけど）、マシンネイティブなコードを出力し、リンクし、がちんこでCPUやメモリー、場合に寄ってはGPUなどとも連携し、或いはハードウェアによってはバスに挿した拡張カードのアドレスを直打ちし…、まあ、とにかくみんなネイティブファミリーだし、必要に応じてC++でもCでもアセンブラーでも適材適所にコード書いてリンクすればいいんだよ！みんなネイティブワールドの仲間たち、オブジェクトコードになればみんないっしょさ！

と、言う訳で(1)書くのに想定以上に時間使っちゃったので本件はここまでで^^;

conclusions

と、ゆーか、C++を使おう！の私見？^^;

C++ と C を比較してどっちが速いバイナリーを生成するか？

同じだけのインターフェースをプログラマーに提供する訳で無ければ単純なコードを書きやすい C の方が速いバイナリーを生成する可能性は十分に有り得る事ではある。
しかし、C++でもCで実装可能な低機能だがシンプルで高速なバイナリーを生成するコードは100%記述可能であり、設計や実装、またライブラリーの選択の幅も広くプログラムの保守性も生産性も向上を期待できるC++を採用しつつ必要に応じてよりネイティブなC互換機能なりアセンブラーなりを応用してプログラミングをすれば通常の用途では間違いなく良いと考えます。

例外は、C++のランタイムをリンクするのも大変なんて極小規模の組み込み用途と、100%マシンリソースとそこで動くコードをプログラマーが掌握したいなんて場合だけじゃないかなぁーと。まあ、対象プラットフォームにC++の"きちんとしたまともな"コンパイラーがあるのか、という現実問題もありますけど…。（一般的なPCではLinux/MacOSX/Windowsにx86_64/x86系では大丈夫、スマフォなんかでARMなんかでもまあ割と、PPCやALPHAもまあ…、しかし組み込みになると騙りまがいの自称C++処理系も実際アリマシテ…・ｗ・；）

spec.

uname -a ; g++ --version | head -n1 ; cat /proc/cpuinfo | grep "model name" | head -n1 ; cat /proc/meminfo | grep "MemTotal"    

Linux LH-MAIN 3.4.11-2.16-desktop #1 SMP PREEMPT Wed Sep 26 17:05:00 UTC 2012 (259fc87) x86_64 x86_64 x86_64 GNU/Linux
g++ (SUSE Linux) 4.7.1 20120723 [gcc-4_7-branch revision 189773]
model name      : AMD Phenom(tm) II X4 940 Processor
MemTotal:        8191384 kB

references

• ソフトウエア研究会in秋葉原 - PukiWiki
• Man page of GCC
• Man page of objdump
• boost/range/algorithm/for_each.hpp - 1.49.0
• (!)PDF http://www.ptlsim.org/papers/x86-64/Opteron-InstructionSet-24594.pdf

SUSE Studio とな？

なにやら楽しいおもちゃを知った・ｗ・

• Welcome – SUSE Studio

どうやら openSUSE 系のマシンイメージをあれこれとカスタマイズして作成できちゃう優れものっぽい！

unboundが…とか一部パッケージについて綺麗に対応しきれない点はあれど、面白いかな。…いやしかしmuninすら無いとか…うううううううううう。

openSUSE Build Service に darkhttpd パッケージを作ってみた

openSUSEでのパッケージの探し方も心得られてきた。

• software.opensuse.org: Search

基本的には↑で探す。そしてどうやら↑はarchlinuxで言うところのAUR、Ubuntuで言うところのPPAとかそんな雰囲気が漂っている。恐らく必要なら私もパッケージをメンテナンスできそうだ。

調べてみると実際どうやら、

• Welcome - openSUSE Build Service

から制御できる様だ。ログインはNovellのアカウントを使う。余談としてNovellのアカウントは昔々Mono絡みで使って居た以来です・ｘ・

さて、このOSBS(長いから略した)については概要は、

• openSUSE:Build Service Tutorial - openSUSE
• openSUSE Build Serviceでパッケージをビルドしてみる - builder

などに断片的な情報はあるのだけど、どうも具体的なところ、そもそもアップロードするファイル構成とかがさっぱり分からない。builderの記事もさすがにほぼ同様とは言え古くなってしまっている。

と、言う訳で、先ずは他人様のリポジトリーがどんな構成になっているか観察してみます。

• Show devel:languages:nodejs / nodejs - openSUSE Build Service

↑は nodejs のプロジェクト。プロジェクトの中身のファイル構成を見ると、どうやらビルドに必要な一式のアーカイブとrpmのspecファイルの様だ。

と、言う訳で早速、OSBSに未登録で私が普段使っていたコマンドライン簡易HTTPDの

• darkhttpd

についてプロジェクトを作成してみました。

• Show home:USAGI-WRP / darkhttpd - openSUSE Build Service

darkhttpdソース配布元のアーカイブを直接アップロードしようと思いましたが、アップロード時にどうやらURLを指示してビルド前に拾わせられる様でしたので、アーカイブのURLを指示して試して見ました。

specファイルについてはnodejsのプロジェクトのspecファイルを参考にしつつ必要最小限はこんな程度かな、という記述に。

specファイルをまともに書き換えSAVEすると、特にUIとしてどうという操作をせずとも勝手にビルドが始まり、少々待ってからプロジェクトのページを表示更新してみるとFinishedへ、それからSucceededへ。

なんともあっさりバイナリーパッケージができてしまったらしい。しかも、

• software.opensuse.org:

既に検索できる様になっていた・ｗ・；

これは openSUSE のなかなかお気に入り要素になるかも。

gistで「そうだ、Fedora17KDEを入れよう・ｘ・ 」を公開

gistに、

ある日のうさぎせんせいのFedoraメモ。もしかしたらこそこそ更新するかも。 はじめてのFedoraでC++環境を整えて素敵な開発ライフを楽しもうかな、そんな事をなぜかふわりと思っているとあるIT系女子へのヒント。

と言った具合の文書を公開しました。

• 『そうだ、Fedora17KDEを入れよう・ｘ・』 ある日のうさぎせんせいのFedoraメモ。もしかしたらこそこそ更新するかも。 はじめてのFedoraでC++環境を整えて素敵な開発ライフを楽しもうかな、そんな事をなぜかふわりと思っているとあるIT系女子へのヒント。

ちょっと興味はあったLinux、でもUbuntuはなんとなく使いたくないんだ。FreeBSDとかGentooとかちょっとまだ怖いし、バイナリパッケージ使いたいし。でもちょっとくらいならシェルとかVimとか使えるのよ？macportsも使うだけなら、Eclipseで簡単なJava開発やAndroid NDKも触ったわ・ｗ・ …Windows？あれはゲーム専用機ね。

そんな謎のLinux初心者向けのFedora17KDEのスタートアップブースターになれば幸いです。

Boost.MultiArray メモ

std::valarrayだと基本的には1次元のデータ構造に対してスライスを考えて多次元要素集合としてアクセスする事になる。Boost.MultiArrayなら基本的には多次元のデータ構造に対して必要ならば1次元のRAWなデータ構造も用いる事ができる。多くの場合は後者の方が扱い易くて助かる。

多次元のBoost.MultiArrayは内部構造としては連続領域が確保されているので、1次元のRAWなデータ構造に直接触れたい場合は、origin()メンバー関数により先頭要素のポインターを取得すれば良い。

目的

Boost.MultiArrayを用いて多次元の要素集合に対しランダムなインデックス値を放り込みたい。

コード

• sample.cxx

#include <boost/multi_array.hpp>
#include <algorithm>
#include <random>
#include <iostream>

int main(){
  using value_type = size_t;
  const size_t dimension = 3;
  using c = boost::multi_array<value_type, dimension>;

  const size_t scaling = 2;
  auto a = c(boost::extents[scaling][scaling][scaling]);

  auto origin_begin = a.origin();
  auto origin_end   = origin_begin + a.num_elements();
  const value_type index_initial = 0;
  std::iota(origin_begin, origin_end, index_initial);

  std::random_device rd;
  std::mt19937_64 rng(rd());
  std::shuffle(origin_begin, origin_end, rng);

  for(const auto& a0: a)
    for(const auto& a1: a0)
      for(const auto& v: a1)
        std::cout << v << " ";
  std::cout << std::endl;
}

実行結果

% g++ -std=c++11 sample.cxx
% ./a.out     
4 7 6 0 3 2 5 1 
% ./a.out 
2 0 1 3 4 6 5 7 
% ./a.out 
4 0 5 7 1 2 6 3

環境

% uname -a && g++ --version | head -n1  
Linux LH-MAIN 3.4.11-2.16-desktop #1 SMP PREEMPT Wed Sep 26 17:05:00 UTC 2012 (259fc87) x86_64 x86_64 x86_64 GNU/Linux
g++ (SUSE Linux) 4.7.1 20120723 [gcc-4_7-branch revision 189773]

References

• MultiDimensional Array Libary - 1.52.0
• 多次元配列 - boostjp
• letsboost::multi_array
• std::random_shuffle, std::shuffle - cppreference.com
• std::iota - cppreference.com
• Pseudo-random number generation - cppreference.com
• valarray - cpprefjp - C++ Library Reference

蛇足

• Boost.MultiArrayは.size()メンバー関数ではコンテナー全体の要素数は得られない。
  • .size() は .shape()[0] を得るもの。
    • .shapre() は次元毎の要素数の配列を得るもの。つまり概形が得られるのでshape。
  • コンテナー全体の要素数は .num_elements() で得られる。
  • .begin()/.end()/.cbegin()/.cend() も概形に基づく1次元内側の要素群を得るもの。
    • N次元の Boost.MultiArray は N 重 for で逐次各次元を辿れる。
  • 全要素を辿るなら .origin() から .origin() + .num_elements() で辿れる。

openSUSE-12.2 + Packman

openSUSEを入れた後、ソフトウェアリポジトリーがやや微妙とか言ってたら「Packmanを追加してあげて！」みたいに教えて頂いて居た事をふと今更思い出した。

• PackMan :: Startseite

実は archlinux から openSUSE に変えた事もあり、しばらくの間は archlinux のパッケージ管理システムである pacman が openSUSE でも使えるの？ほえ？とか思っていた。はっきりいってそれは全く関係無かったらしい・ｘ・

% zypper ar http://packman.inode.at/suse/12.2/packman.repo
 ...

これで openSUSE で生きるのが楽になる、かな？

openSUSE-12.2 に OGLplus を導入

OpenGL3以上のCなAPIをC++らしく扱う為のライブラリーOGLplusをopenSUSE-12.2に導入する。

• OGLplus - a C++ wrapper for OpenGL® version 3 and higher.

zypperに対応したパッケージは無いので普通にソースを拾ってビルドしてインストールする。

OGLplus ソースを拾う

• SourceForge.net: OGLplus - Develop

% git clone git://oglplus.git.sourceforge.net/gitroot/oglplus/oglplus
 ...

GL3/gl3.h を用意する

以下の要求を確認するとGL3/gl3.hが必要との事。

• OGLplus - a C++ wrapper for OpenGL® version 3 and higher.

私自身の管理方法の手前 Makefile を用意したので使いたい方はどうぞ。内容はwgetしてinstallするだけ。

• usagi/GL3 · GitHub

% git clone git@github.com:usagi/GL3.git
 ...
% cd GL3

checkinstall

% sudo su
% checkinstall
 ...
% rpm -i /usr/src/packages/RPMS/x86_64/GL3-20121213-1.x86_64.rpm
% exit

OGLplus を導入

cmake

ビルド用の作業ディレクトリを設け、EXAMPLES抜きでビルドする。EXAMPLESをビルドする場合はGL3/gl3.hに定義される多くについて実際に使用可能なOpenGLのライブラリーがシステムに導入されている必要があり、どこかしらのGLEXTのリンクなどで失敗する可能性が割とよくある。EXAMPLESは必要に応じて個別に参照、ビルドすれば良いだろう。スクリーンショット、ドキュメントも今回は不要のフラグを立てる。

% ls
GL3 oglplus
% mkdir oglplus_build
% cd oglplus_build
% cmake -DOGLPLUS_NO_EXAMPLES=ON -DOGLPLUS_NO_SCREENSHOTS=ON -DOGLPLUS_NO_DOCS=ON ../oglplus
 ...

checkinstall

% sudo su
% checkinstall
 ...
% rpm -i /usr/src/packages/RPMS/x86_64/oglplus_build-20121213-1.x86_64.rpm