2007-07-31

へんてこりんに再帰したテンプレートパターン

C++のCRTP(Curiously Recurring Template Pattern)の話。

CRTPでは継承クラスの関数を使って基底クラスの関数を実装することができる。

#include <iostream>

template<class T>
class base
{
	const T& get_this() const
	{
		return static_cast<const T&>(*this);
	}

	void p_impl() const
	{
		std::cout << "template<class> class base\n";
	}

public:
	void print() const
	{
		this->p_impl();
		this->get_this().p_impl();
	}
};

class derived : public base<derived>
{
	void p_impl() const
	{
		std::cout << "class derived\n";
	}

	friend class base<derived>;
};

class derived2 : public base<derived2>
{
};

int main(int, char**)
{
	derived().print();
	derived2().print();

	return 0;
};

class derivedのp_impl関数を使ってclass baseのprint関数を実装できるが、上記ソースコードのように基底クラスにp_implを用意しておけばderived2ではp_impl関数が無くても基底クラスのp_implが呼ばれる。

実行結果

template class base
class derived
template class base
template class base

当たり前のことかもしれないけど、CRTPでこのように基底クラスに関数のデフォルト実装を書いておくことができるというのを今日知った。

2007-07-12

マクロの呪いでお先真っ黒

boost_1_34_0のnumeric ublasのソースコードを読んでいると

std::swap_ranges (data_, data_ + (std::max) (size_, a.size_), a.data_);

という感じのstd::maxやstd::minを括弧で囲んだ式をちょくちょく見かける。
それは標準のテンプレート関数なんだけど、なぜこのような変な書き方をしているのだろうか。

そういえば昔、をインクルードするとmin,maxマクロが小文字で定義されていてstd::min, std::maxが使えないという目にあったことがあたった。もしかしてstd::minを括弧で囲むとマクロ展開されないのだろうか。

#include <algorithm>

#define min(a, b) "■■■"

void hoge()
{
	(std::min)(9, 6);
}

cygwinのg++のstl_algobase.hではmin, maxを定義する前にmin, maxを#undefしていた。
min, maxマクロはいろんなところで悪さをしていたのかもしれない。

2007-07-11

sourceforgeのsubversionにimportした

以前、gpuppurのソースコードをsourceforgeのsubversionにimportしようとしたけどsshあたりでうまくいかず断念していた。
昨日再び挑戦したところ、すんなりとimportに成功した。以前使っていたcygwinのsshに不具合でもあったのだろうか。

2007-07-04

vimの補完機能

vimには覚えきれないほど機能があるんで、ときどき
http://vimdoc.sourceforge.net/
を読んで使い方をちまちま覚えてたりする。
今日はかなりいい機能を発見した。
overview->usr_24.txt Inserting quickly->*24.3* Completion
今まで知らなくて損した。
現在のディレクトリにあるファイルやカーソルの前にある単語による補完もできるので
もしかするとvisualstudioのインテリセンスより便利かもしれない。

http://programmer-wanted.capcom.co.jp/
でカプコンが社員を募集しているが、うちの会社もこれぐらいやったらいいんではないだろうか。
本社が近くにあるので、遊びに行ったらソースコードの10行か20行ぐらいは見せて貰えないだろうか(無理か)。

この仕事には、グロテスクなスケジュールを正しく回避することも含まれています。
この仕事ではプロデューサーはいないかもしれません。
この仕事は、遊んでいても休憩しているんだろうなと思われます。
この仕事では先輩から過酷なツッコミを浴びせられる恐れがあります。
この仕事では、いつの間にかハリウッドを顧客にまわす恐れがあります。
最新の開発環境を自宅のPCへ不正コピーしてはいけません。
プログラマーでも自分の担当箇所を理解してもらえない恐れがあります。
社員は18歳以上を対象としておりますが、子供を持つ人が多く含まれます。
この仕事には、特殊すぎて論文にすら教えてもらえない内容が含まれています。
この職場には、麻薬的なお菓子が含まれています。
この職場では、ゲームの対戦相手は個人的に探して下さい。

2007-06-23

Real Time Ray tracer

最近はCPU上で動作するRay tracerを開発中。
未踏が終わってしばらくした後、とりあえずoctreeを実装してみたけどあまり速くならなかった。各ノードに子ノードへのポインタを持たせないことによってメモリを節約しキャッシュ効率が少し上がるような設計にしたつもりが、結局ノード数が無駄に多くなってしまった。
今は自分で考えたアルゴリズムを実装中。そんな事する前にBVHやkd-treeを実装して勉強したり、自分のアルゴリズムとパフォーマンスを比較できるようにしたほうがいいのかもしれないが。

リアルタイムレイトレといえば、ドイツにあるSaarland大学の研究が凄い。
http://graphics.cs.uni-sb.de/index.html
レイトレ専用チップを開発したり、Quake4をリアルタイムレイトレーサでレンダリングしたりしている。
http://q4rt.de/
リアルタイムレイトレもそこそこ使えるようにはなっているが、やはり現在のGPU+ラスタライズを置きかえるほどには速くない。
上記のQuake4はCore 2 Extreme QX6700でも16fpsぐらいの速さ(画面サイズが256x256で)なのでかなり我慢すれば遊べるかもしれないが、普通のGPUだと安くてより高いfpsが得られる。
gpuppurでそれらに対抗できるようなレンダラを開発するのはかなり難しいけど、いつの日にかリアルタイムレイトレーシングが主流になる日が来ることを信じてこつこつ開発中。
でも、レンダラを作るのはとても楽しい。

もうじきIPAX2007が開催されるわけだが、未踏ユース最終発表会の終わりの言葉のときにIPAの人が是非IPAXに出展して下さい、というような事を言っていたので出ることにした。
申し込みの時,展示する物のみどころを書く欄にてきとうに"ヌルヌルのリアルタイムレイトレーシング"と書いた。後から変更できるらしいので、もっといい言葉を考えてから決めようと考えていた。しかし気がついたときには変更できる期限を過ぎていた。みどころがこんなに短くわかりやすい(?)のは私だけのようだ。

リアルタイム3Dでfpsが一桁ぐらいの状況をカクカク、逆にfpsが30以上のスムーズに表示されている状況をヌルヌルって言うことがあるが、IPAXまでにそんなリアルタイムレイトレーサを作れるだろうか。
とりあえず、表面がヌルヌルしているように見えるレイトレーサはここのdemoプログラムとして用意しておいた。

2007-05-17

データのバックアップと復元のスピード

データのバックアップを取ったり、復元するときの効率について考えてみた。
ハードディスクAから別のハードディスクBへサイズがxのデータをコピーし、その後ハードディスクBからさらに別のハードディスクCへそのデータをコピーすることについて考えてみる。
このときのハードディスクの読み書きするサイズは、
A->Bへのコピーのときはxだけ読み込んでxだけ書き込むので2x,
B->Cへのコピーのときも同様に2xとなる。
合計で4xの大きさの分だけハードディスクを読み書きする。

ここでA->Bへデータを圧縮して書き込み、B->Cへデータを解凍して書き込む場合について考えてみる。
圧縮率がcのとき、A->Bへデータを圧縮して書き込むときの
ハードディスクAから読み込むデータサイズはx、ハードディスクBへ書き込むデータサイズはcxとなる。
次にB->Cへデータを解凍して書き込むときは
ハードディスクBから読み込むデータサイズはcx、ハードディスクCへ書き込むデータサイズはxとなる。
合計で2x+2cx=2(1+c)xだけハードディスクを読み書きすることになる。

ここで圧縮してデータをコピーするときのハードディスクへのアクセス量が、圧縮しないときのアクセス量より小さくなるにはr<1であればよいことがわかる。
非圧縮コピー時のアクセス量に対する圧縮コピー時のアクセス量の比率rは
r=(2(1+c)x)/4x=(1+c)/2
となる。
例えば圧縮率が3/4だとr=7/8
1/2だとr=3/4
1/4だとr=5/8
1/8だとr=9/16
...
c=0のとき、r=1/2だから、圧縮率をどれだけよくしても総ハードディスク読み書き量は半分以下にはならない。

現代の普通のPCではハードディスクの読み書き速度はCPUやメモリの速度よりかなり遅いので、このようなバックアップ時はハードディスクのアクセスが大きなボトルネックとなる。だから、CPUやメモリをある程度使って圧縮、解凍処理を行い、ハードディスクのアクセス量を減らすと効率が良くなる。

ちなみにいくつかの方法で82MBぐらいのデータを別のハードディスクへコピーしたときの所要時間は以下のようになった。
実験ではCPUがcore2duoT5500、メモリが2GB、windows vistaのマシンを使い、SATAの内臓ハードディスクを外付けケースに入れてUSBで繋いだものから別のUSB接続の外付けハードディスクへのコピーを行った。
windows vistaのシェルで普通にコピペ->110秒(これには所要時間を計算する時間も含まれている)
cygwinからtar+bz2で圧縮してコピー->34秒
cygwinからtar+gzで圧縮してコピー->16秒
http://www.ipmsg.org/tools/fastcopy.html
にあるfastcopyというフリーソフトを使った場合
コピー（全上書き）モードでバッファサイズが128MBで->87秒

ちなみに使用したデータを
tar+bz2で圧縮したとき21MB(c=0.26, r=0.63, 34秒/87秒=0.39)
tar+gzで圧縮したとき24MB(c=0.30, r=0.65, 16秒/87秒=0.18)

この実験では、まだデータを解凍してコピーするときの処理時間の計測はしてない。
やはり圧縮したほうがかなり速い。データの書き込むサイズの減った割合に対して所要時間の減り方が大き過ぎるような気がする。これはどこかで実験方法を間違えたか、ハードディスクにあるキャッシュがかなり効いているためなのか。圧縮率がいいのに所要時間がgzipより長いbzip2はさすがにCPUにかなり負担がかかるようだ。

災害は突然忘れた頃にやって来るので常にデータをバックアップするようにしましょう。

2007-05-12

コード芸人!

id:Ozy:20070509

>酷い日本のソフトウェア産業
近い将来、ソフトウェアの生産性が飛躍的に向上し、世の中のソフトの大半が自動的に生成、保守、管理されるようになり、単なる作業員プログラマがいなくなるときが来るかもしれません。そしてプログラマは新しいソフトの研究開発に集中できるようになると。最近C++言語にはそれを実現する未知の能力があるんじゃないかという気がなんとなくですがします。

>省エネ勉強はどうしようもない
今まで勉強したことの8割は自分の好きな分野のことで、興味の無い分野はあまり勉強していないので、もしかしたら省エネ勉強になってるかもしれません。正直ショートコーディングより、開発時間、実行速度、実行時に必要な資源をショートにするほうが好きです。
今までの経験上、何が役に立ち、何が役に立たないかなんてわかりません。でも、好きな事のほうが勉強が進む。

>真のプロフェッショナル
プログラマは理想のソフトウェア、ソースコードを目指し常に悩み考え続けるべきだと思う。プログラミングで難しいことの一つは、目的を果たす手段を探し出す事と手段が幾つもある内からどれを選ぶかを決定する事です。プログラミングにある程度なれると深く考えなくてもそこそこ最適な手段を選んで書けるようにはなるけど、それでもその方法が本当に最高の手段なのかを常に考えながらコーディングすべきだと思う。そうすることによって、段々と理想のコードに近づいていくんじゃないかと思う。これも真のプロフェッショナルへの道なんじゃなかろうか。

>恥ずかしい思いをしろ
gpuppurのソースコードを公開するのは恥ずかしかった。でもつっこみが少ないってことは、あんまり面白いコードじゃないって事なんだろうか。
2の32乗-1分の1の確率でGPUが爆発してしまうような重大なバグから、コメントに書いたおやじギャグが寒いよという些細なツッコミまでなんでもお待ちしています。

>まあ、なんだ
>つべこべ言わずにコード書けっちゅうの（｀ω´）
今日はコードをあまり書かず、こんなブログを書いてしまいました(´ω｀)