メイン

しーげんご アーカイブ

2004年10月13日

C++ の次はなんなんだ

 余りにもネタが無いので、C++ ベースのプログラミング言語に欲しい機能を列挙。
 プログラミング言語C++第3版 とか読んだ事無いので、既存のものがあっても勘弁。

interface
 純粋仮想クラスだと virtual だから嫌。
 virtual って言えば、最適化で勝手に virtual が解決される事を期待するなら、それを言語仕様で保証して欲しい。そうでなければ 非virtual を明示的に分別したい。
 interface を使いたいのは特にテンプレートだけどね。
interface IBar { /*プロトタイプの列挙*/ };
template< IBar BAR > class CFoo {};
 てな感じ。template 引数が int, typename, class しか無いのが辛い。特定のインターフェースを持ってる事が分ってるなら、それが明記できれば今の分りにくいコンパイルエラーはもっと明快になるし、インテリセンスも使えるようになる。

タイミングに依存しない事を示す const
 名前はいいのが思いつかなかっただけで、const じゃなくていい。ていうか const は色んな意味を持ちすぎてて分りづらい。
 関数って、内部でカウンタを持ってるものとか、デバイス関連とかみたいなタイミングに依存するものと、単純に計算して結果を返すだけのタイミングに一切依存しないものとあるでしょ。
 だから最適化時に関数の呼び出し順序は保存される事になってる。

 特に最近はオブジェクト指向だから、とことんパーツが分離されて効率が良くない。
 極端な話、ポインタと同等なイテレータ(reverse_iteratorみたいの)が外部にあると、いちいち全部メンバ関数呼ばなきゃいけない上に順序が保存されて、それに依存した変数もみんな順序が決定されちゃって、ぜんぜん最適化できないなんて話にもなりかねない。普通イテレータは include するものだからちょっと例えが悪いけど、実際外部に置く事だって出来るわけだし。

 あと、ソースコードが分ってる場合は、インライン展開した時に順序に依存しない事が分るからいいんだけど、全ソース include でプログラムを構成していたらコンパイル速度とかたまったものじゃないよね。
 根本的な解決としては、オブジェクトファイルをもっと柔軟にすべき。プリコンパイル済みヘッダみたいな感じでパースだけした状態にして、いつでもインライン展開出来る状態になってれば万々歳。

struct と class の分別
 struct は名前からしてただの構造体なんだから、クラスのサイズとか保証した方がいいと思う。メンバは 非virtual に限定すべき。明示的な virtual はあってもいいけど、サイズとか変わっちゃうから、それを許可する属性を作って、許可しない限り virtual はコンパイルエラーとか。
 逆に class はデフォルトが virtual。非virtual にしたい場合は明示的に指示する。

virtual なコンストラクタ
 小細工で解決するのは嫌。言語側で持って欲しい。邪道だと思う人は virtual 付けずにコンストラクタ書けばいいんだし。
class base {
public:
    virtual base() { foo(); }
    virtual void foo() { ::std::cout << "base" << ::std::endl; }
};
class over : public base {
public:
    virtual over() : base() {}
    virtual void foo() { ::std::cout << "over" << ::std::endl; }
};
main() { over hoge; } // over を出力

2004年10月15日

C++ の次はなんなんだ その 2

名前つきブロック
foo() {
    named block1 {
        while ( 1 ) named block2 {
            exitfrom block1;
        }
        ::std::cout << "never print" << ::std::endl;
    }
}
 while はループにも名前を付けられるって事を示したかっただけで、コード上の意味は無い。named は冗長だからいらないかも。

template タイプ (またはエイリアス)
template< typename T > typedef ::std::vector< T >  myVec;
 ただ別名が付けられるだけ。略したいなら using しろよってツッコミもアリ。
 class の継承で実現可能だけど、コンストラクタとか operator とか隠滅されるから手軽には出来ない。マクロは namespace 使えないし論外。

動的なクラス名の保持
Expression Template とかで、
CBar bar = (a + b * c) / 2;
みたいな計算式を書くと、template で動的に膨れ上がった、ツリー状のクラスが生成される。bind も同じ現象。
 そのクラス名は不定のため、bar のクラス名を決定する事は出来ない。CBar のコンストラクタを
template< class T > CBar( T value )
としたところで、T を保持しておく機構が無いので、bar を次の演算に使おうにも型が分らない。
 boost の function を使っても、戻り値の型を決めてやらないといけない。次の演算にも ET を連結しようとすると、戻り値の型は function に渡した時の型そのものが必要になるので、やはり分らない。かといって ET の連結を諦めて、そこで ET を解決してしまうと、全要素の演算が発生するので ET の意味が半減する。

※Expression Template
 divide< add< mult > > みたいな感じで演算式を全てテンプレートに変換してしまう手法。
 配列演算に用いてもテンポラリな配列を必要とせず、線形であれば同じ要素を 2 度読む事も無い。そして配列同士の演算の後、実際に使用するのがたかが数要素なのであれば、ET の解決時に使用する要素だけの演算になる。よって、よく配列演算の最適化に使われる。

2005年01月22日

const 関数

 C++ の次はなんなんだ で書いた「const な関数」だけど、一部の実装であるっぽい。

 gcc の表記 だと、まさに言った通り関数に const をつけるだけでいいみたい。

 他に見つけたのは ptx/C コンパイラってやつの sequent_pure_function プラグマ。恥ずかしながら ptx/C って聞いた事ないからあんま関係ないけど。この中ではどうやら純関数と呼ぶらしい。

2005年10月30日

CGDirectDisplayAPI

 Rb で MouseMove イベントなんかを使うとテリトリーを出た場合に検出出来ない。
 Rb じゃなくても GetMouse() とか GetGlobalMouse() なんかじゃスクリーンの橋にあたった場合にマウスの移動が検出出来ない。

 そんなこんなで探していたら、ありました。

Technical Note 2007:CGDirectDisplayAPI

 日本語で情報提供なんて、アップルやるじゃん。垂直同期待ちまで載ってるし。

 でも、垂直同期って Callback に出来ないのかしら?
 Classic で Game Sprocket 使わない場合はどうやるのかしら?
 と、疑問はまだある。

 <ぼそ>リソースの自動解放と同じ考え方だけど、ディスプレイモードを変更してもアプリケーションが終了すると自動的に戻るなんて、Mac 美しすぎ</ぼそ>

2006年03月13日

VC++ 2005 でプロファイル最適化

 VC++ 2005 Professional 以降はプロファイリングを使用した動的最適化が出来る。
 「ガイド付き最適化のプロファイル」(リンクは MS の解説)でググっても取り扱っているサイトが無さそうだったので持ち上げ型のレビューっぽく VC++ 2005 と一緒に紹介してみる。

 まずは普通にコードを入力。
 コンストラクタでもヒントを表示するようになったのが嬉しい。

コンストラクタの入力

 更に凄いのが、入力中、クラスやマクロがどのように定義されているか逐一表示してくれる「コード定義ウィンドウ」。これに慣れると、もう以前の環境には戻れなくなりそう。
コード定義ウィンドウ

 コードが書き終わったら早速コンパイル。
 このときに表示される「エラー一覧」。VS 2005 ではエラーだけ、警告だけに分けて表示されようになっている。
 このコード#include <tchar.h>を加えると完成。
エラー一覧

 Release でコンパイル、実行したところ、タイムは 2585614 となった。
 さあこれを最適化しよう、といった場合、通常はプロファイラでプロファイルを採ってから、ボトルネックになっている場所を探す。これを人間がやるのではなくコンピュータにやらせよう、というのが今回の動的最適化。

 次は、プロジェクトから [ガイド付き最適化のプロファイル] - [インストルメント] を選択して、再度コンパイル、実行する。
エラー一覧

 これを行うと、実行ファイルのディレクトリに「ソフト名!番号.pgc」といったファイルが作られている。何度も行うと、どんどん番号が増加し、ファイルが作られていく。
 これがプロファイルした結果で、より良く最適化をするには、様々な条件のデータを使って実行し、このファイルを増やしていく。

 今回はデータを 1 種類(固定的な rand 値)しか用意していないので、1 回実行しておしまい。
 この時タイムは著しく下がるが、これはプロファイルを採っているから起こる現象で、気にしない。

 最後に、プロジェクトから [ガイド付き最適化のプロファイル] - [最適化] を選択する事で、プロファイル結果を使ってコンパイルする。これが完成品。

 こいつを実行してみると…タイムは 1754635 となった。約 1.5 倍速に最適化が出来た。

2006年06月05日

スレッドを CPU に張り付ける

 処理そのものに並列性がある場合、SMP(対称型マルチプロセッサ)を有効に使う事は難しくなく、プロセッサの数だけスレッドを立ち上げれば良い。
 けれども、OS が CPU にスレッドを振る過程で、時折同じ CPU に複数のスレッドを振ってしまう事があるらしい。通常、数十〜数百ミリセカンドという短い間隔でタイムスライスしているので、同じ CPU に複数のスレッドを振ってしまったとしても、すぐに振り直されるので問題ない。

 今回はそれすらも許したくない、シビアに速度を要求する場合の話。
 結論から言うと、Windows では SetThreadAffinityMask を使用し、Linux では sched_setaffinity を使用する。

 sched_setaffinity は説明を読めば下位のビットから CPU の個数だけビットが続く事が分るので、すぐに対応出来るはず。
 SetThreadAffinityMask も、まずそのはず。しかし明言はされていないようなので、ビットの途中に利用禁止のプロセッサがあるかもしれないと仮定して、GetProcessAffinityMask で利用可能なマスクを得ておくと完璧。

 なんでこんな事を書いているかというと、Mac OS X で affinity を設定したかったから。
 ところが このメール を読むと、Darwin は affinity を設定出来なさそう。ホントかなあ。

2006年11月27日

コンパイラの癖を知る

 コンパイルした後はコンパイラが吐き出したアセンブリコードを見る習慣を付けよと日々申しておりますが(嘘)、今回はちょっとした癖のお話。

 下のプログラムと Xcode 2.4.1(powerpc-apple-darwin8-gcc-4.0.1) でコンパイルした結果。

void copy1( int bytes, const int * a, int * b )
{
	int count = bytes;

	count /= sizeof(int);
	if ( count > 0 ) printf( "foo\n" );
	
	for ( ; count > 0; count--, a++, b++ )
	{
		*b = *a;
	}
}

void copy2( int bytes, const int * a, int * b )
{
	int count = bytes;

	if ( count > sizeof(int) ) printf( "foo\n" );
	
	for ( count /= sizeof(int); count > 0; count--, a++, b++ )
	{
		*b = *a;
	}
}
_copy1:
……省略……
L4:
	lwz   r0,  0(r30)  ; r0 = *a
	addi  r29, r29, -1 ; count--
	addi  r30, r30, 4  ; a++
	cmpwi cr4, r29, 0  ; cr4 = count > 0
	stw   r0,  0(r31)  ; *b = r0
	addi  r31, r31, 4  ; b++
L8:
	bgt   cr4, L4      ; if (count > 0) goto L4
……省略……

_copy2:
L14:
	lwz  r0,  0(r30) ; r0 = *a
	addi r30, r30, 4 ; a++
	stw  r0,  0(r31) ; *b = r0
	addi r31, r31, 4 ; b++
L13:
	bdnz L14         ; if (--count > 0) goto L14
……省略……

 違いは一目瞭然。
 途中の if (...) printf() のくだりは帯域的な最適化がかかりにくくなるように、わざと count の計算と for() の間に挟んだ物。

 実は Xcode のデフォルトの Release の最適化オプション「最も高速で最小(-Os)」でのみ起こり、-O1 から -O3 では copy1 は copy2 と同じコードを吐く。
 現実にはこのような些細な違いで速度に影響は出てこないが、日頃からコンパイラの出力を見る癖を付けておくと、こういった癖に気づいたり最適化の勉強になったりするはず。

 <独り言>Visual C++ なんかは割と賢く最適化してくれるが、出力を見ているとレジスタが余っているのに極力最小限のレジスタで済まそうとしていて時にイラっと来る事も。</独り言>

2006年12月08日

アフィン変換とBresenham

 ここひと月、というか これ を作ってからアフィン変換に Bresenham のアルゴリズムを使えないか考えている。
 理論上アフィン変換はメモリのコピーだけで、完全にメモリネック。つまりプリフェッチを行う以外に最適化の方法は無い。そして 1 ピクセルずつアクセスしている以上プリフェッチも難しい。(取り出してしまったキャッシュラインは全て処理する、とか考えられるけれども超複雑)
 どころがどっこい素直に書いたアフィン変換の場合、ボトルネックはメモリではなく実は丸め処理にある。そこで丸めずに済む Bresenham の出番というわけ。

 そんなわけで Bresenham の式を一般化しようとしてるんだけれども、中々うまい解が得られない。多分ググれば沢山あるんだろうけど、悔しいので探さない。
 今のところ得られている式はこんな感じ。


x...イテレータ                  (int)
w...イテレートする範囲            (float)
h...イテレートする間に欲しい値の範囲 (float)
b...開始値                      (float)
int(x)  =floor(x)
round(x)=int(x+0.5)

基本的な一次方程式
y = round(ax+b)
  = round(x*(h/w)+b)

// round(x)->int(x+1/2)
  = int(x*(h/w)+b+1/2)

// 通分
  = int(x*(2h/2w)+(2bw/2w)+(w/2w))

// 整数部と小数部を分離 (x*int(2h/2w))
  = x*int(2h/2w)              + int((2bw+w)/2w)
  = x*int(h/w)+int(x*(2h%2w)) + int((2bw+w)/2w)
  = x*int(h/w)                + int({x*(2h%2w)+2bw+w}/2w)

// 整数部と小数部を分離 ((2bw+w)/2w)
  = x*int(h/w)+int((2bw+w)/2w) + int({x*(2h%2w)+(2bw+w)%2w}/2w)
  = x*int(h/w)+int((2b+1)/2)   + int({x*(2h%2w)+(2bw+w)%2w}/2w)

// 最終形態
  = x*int(h/w)+int((2b+1)/2)
    +int({x*int(2h%2w)+int((2bw+w)%2w)}/int(2w))

 ただこれ、イコールで結んじゃってるけれども元の式と同じ値にならない。1 だけ誤差が出る。
 一つ分っているのは w や h が実数の時に int(2h%2w) とかやっちゃうと小数部分が死んでしまうところ。
 精度を保つ必要があるのは 0 <= x < w の間だけなので、下のように分母に w を掛けてしまえば解決する。


y = x*int(h/w)+int((2b+1)/2)
    +int({x*int(2hw%2ww)+int((2bw+w)w%2ww)}/int(2ww))

 解決するんだけれども、w を二乗して更に 2 倍するので(入力値のビット数+1)*2ビットものビット数を用意しなくてはいけない。つまり 32 bit の CPU で処理する場合、入力値は 15 bit 以下である必要がある。

 一般化したプログラムは以下の通り。


//! y = x*int(h/w)+int((2b+1)/2)+int({x*int(2hw%2ww)+int((2bw+w)w%2ww)}/int(2ww))
template<typename T=double, typename INT=int>
struct linear_iterator_round
{
	INT y, dy, ydir;
	INT f, df, flim;
	
	linear_iterator_round( T w, T h, T start_y=0 )
	: y(floor((2.0*start_y+1)*0.5))                     // int((2b+1)/2)
	, dy(floor(h/w))                                    // int(h/w)
	, ydir(w*h != 0)
	, f(fabs(floor(mod((2.0*start_y*w+w)*w, 2.0*w*w)))) // int((2bw+w)w%2ww)
	, df(fabs(floor(mod(2.0*h*w, 2.0*w*w))))            // int(2hw%2ww)
	, flim(fabs(floor(2.0*w*w)))                        // int(2ww)
	{}
	
	static T mod(T a, T b)
	{
		T r = fmod(a, b);
		if ( a<0 != b<0 ) r += b;
		return r;
	}
	
	//! 現在の値を得る
	INT get() const { return y; }

	//! 次の値を計算する
	INT next()
	{
		y += dy;
		f += df;
		if ( f >= flim )
		{
			y += ydir;
			f -= flim;
		}
		
		return y;
	}
};

 これを使うと floor(x+0.5) や round(x) (C99) を連発する場合に比べて 10 倍以上速くなる。

 ただし最近の CPU は浮動小数点数の演算が速い為、これを利用する必要は無い。
 C99 の lrint が使える場合、またはコンパイラの組み込み関数で浮動小数点->整数の変換が出来る場合(cvtxxx や __controlfp+intへのキャスト)はそちらを利用した方が速い。

 floor がなんで遅いかって言うと、多分浮動小数点数から浮動小数点数に変換するから。浮動小数点数を整数レジスタに変換する場合は 1e30 とかって値を正しく変換出来ないけど、floor は変換後も double だから正しく元の値を保持しなくてはいけない。そして x86 や PPC なんかでは丸めた結果を浮動小数点数レジスタへ出力する命令は無いのでソフトウェア処理する羽目になるって寸法。
 追記。ハードウェアで丸める場合も、古いタイプだと丸めモードをいちいち変更しなきゃいけないのが大きい。最近の x86 は丸めモード無しに直接丸める命令がある。

 実用上 32,768 ピクセルを超える事も無いっちゃ無いんだけれども、もうちょっとひねって演算に必要なビット数を節約する方法は無いものかなあ。

2006年12月30日

gcc で混合出力

 プログラムは正しく書いたつもりでも思ったように動かない、最適化の為に細部の挙動まで知りたい、よくそんな時にアセンブラコードを出力する。
 VC++ では /FAs を使えばアセンブラコードとソースコードを織り交ぜて出力してくれるが、gcc には見当たらないので非常に読みづらかったり。

 で、何かそれを実現する方法が無いか探そうと思ったけれども、ppu-gcc/spu-gcc はデバッグオプション(-g)を付けた場合に行数を出力してくれてるようなので、こりゃ自分で書いた方が早いと思い、作ってみた。デバッグ込みで多分 1 時間くらい。

 mas (Mix an Assembler code and Source codes)
 ※現在上のリンクが切れているのでhttp://yoffy.dyndns.org/svn/mas/trunk/からダウンロードしてください。

 使い方としてはこんな感じ:


// hello.c
#include <stdio.h>

int main(int argc, char * argv[])
{
    return printf("Hello World!\n");
}
x86の例(抜粋):

$ gcc -gstabs+ -S hello.c
$ mas hello.s
.globl _main
_main:
        .stabd  46,0,0
;#include <stdio.h>;
;
;int main(int argc, char * argv[])
;{
;    return printf("Hello World!\n");
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        subl    $20, %esp
        call    L3
"L00000000001$pb":
L3:
        popl    %ebx
;}
        leal    LC0-"L00000000001$pb"(%ebx), %eax
        movl    %eax, (%esp)
        call    L_printf$stub
;
        addl    $20, %esp
        popl    %ebx
        leave
        ret
PowerPCの例(抜粋):

$ gcc -g -S hello.c
$ mas hello.s
main:
        .quad   .L.main,.TOC.@tocbase,0
        .previous
        .type   main, @function
.L.main:
.LFB2:
;#include <stdio.h>
;
;int main(int argc, char * argv[])
;{
        stdu 1,-128(1)
.LCFI0:
        mflr 0
.LCFI1:
        std 31,120(1)
.LCFI2:
        std 0,144(1)
.LCFI3:
        mr 31,1
.LCFI4:
        mr 0,3
        std 4,184(31)
        stw 0,176(31)
;       return printf("Hello World!");
        ld 3,.LC1@toc(2)
        bl printf
        nop
        mr 0,3
;}
        mr 3,0
        ld 11,0(1)
        ld 0,16(11)
        mtlr 0
        ld 31,-8(11)
        mr 1,11
        blr

 よくよく考えてみると perl で書いたら正規表現で置換するだけだから、ものの数分で出来た気がする。

 ぐぐってみると、たまに行数付きのフォーマット(.file/.loc)で出力されたプログラムを見つけるんだけれど、ppu-gcc/spu-gcc じゃない普通の gcc でこのフォーマットを出力するにはオプションに何を指定したらいいんだろう?
 Xcode 2.4.1 付属の gcc では -g -S としても .file/.loc が出力されないんだよなあ。

 追記: .stabs/.stabd 形式に対応した ので、Xcode でも ok。

gcc で混合出力(その2)

 前回 gcc で混合出力 で書いたやつの続きで .stabs/.stabd 形式に対応。

 これで大抵の環境でいけるはず。

2007年03月31日

mas が .stabn に対応

 mas (Mix an Assembler code and Source codes) を変更。

  • .stabn に対応。
  • stab.h が無くてもコンパイル出来るようになった。

2009年06月13日

boostを64bit対応でMacにインストール

 前提条件として、bjam (現在の最新はboost-jam-3.1.17-1-macosxx86.tgz) を解凍した boost のフォルダ(ここでは boost_1_39_0)に入れておく。
$ cd boost_1_39_0

$ echo "using darwin : 4.2 : gcc-4.2 ;" >> tools/build/v2/user-config.jam
(gcc-4.2 を使用する場合のみ記述。標準の gcc でいい場合はこの行を飛ばす。)

$ sudo ./bjam --toolset=darwin macosx-version=10.5 architecture=combined address-model=32_64 threading=multi link=static,shared release debug install
 きちんと各環境に対応しているかチェックしてみる。
$ cd /usr/local/lib
$ file libboost_thread-xgcc42-mt-1_39.a 
libboost_thread-xgcc42-mt-1_39.a: Mach-O universal binary with 4 architectures
libboost_thread-xgcc42-mt-1_39.a (for architecture i386):	current ar archive random library
libboost_thread-xgcc42-mt-1_39.a (for architecture ppc):	current ar archive random library
libboost_thread-xgcc42-mt-1_39.a (for architecture x86_64):	current ar archive random library
libboost_thread-xgcc42-mt-1_39.a (for architecture ppc64):	current ar archive random library

About しーげんご

ブログ「きっちん」のカテゴリ「しーげんご」に投稿されたすべてのエントリーのアーカイブのページです。過去のものから新しいものへ順番に並んでいます。

前のカテゴリはさーばです。

次のカテゴリはだうんろーどです。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

Powered by
Movable Type 3.37