C++プログラムのススメ

つまり、だ。どう考えても飽きっぽくて、新しもの好きで、そのくせ、変なこだわりをもっていたりするような人間が、変な解説をしようという訳のわからんコーナーである。まともな人間はそうそうに立ち去った方がいいと思うよ。事実誤認もあるだろうしね。


7/21 はまり道 〜偏執狂の辿る末路〜

例によって、偏執狂的な省サイズプログラムを作っていた。しかし、/link /nodefaultlibとやったら、リンカに「_memset が無い」と怒られてしまった。しかし、僕はそんな物を使っていないのである。全てWin32SDKですましたはずなのである。grep memset * もやったが、やはりそんなコードは発見できなかった。そこで、アセンブラリストを出力させてみると、ZeroMemoryが_memset呼び出しとなっていた。includeディレクトリをgreすると、ZeroMemoryがmemsetへのdefineされていた。なんやねんな、それ。それってWin32とか、そういう次元ちゃうやん。

おまけに、throwしようとしたら、catchされない例外ハンドラを使うために標準ライブラリが必要だったりして、throwすら使えない状態になってしまった。なんやそれ。

何でthrowか、というと、プログラムをワーカスレッドとウインドウスレッドに分けるとします。ワーカスレッドが動いているときにも、ウインドウのほうには容赦なく終了メッセージが飛んできたりするわけです。もちろん、ユーザーが終了させたい時には直ぐに終了した方がいいのは明らかです。ということは、フラグなんかで終了を通知したりするわけです。ワーカスレッドがフラグを時々見て、終了フラグなら処理をやめると。で、関数の奥深くでキャンセルしたいときは大変やから、時間のかかりそうなところに、if(exit) throw Exception;なんかして、一気に飛ばそう、というわけ。スレッドが開始された場所で、tryしておけば、ちゃんとExitThreadが呼びだせる、というわけです。
しかし、補足されない例外は、最終的にライブラリ関数で処理されるので(標準はabort()だったかな)、つまり、/nodefaultlib /Entry:WinMainと共存できない、というわけです。あ〜あ。


6/27 ウエイト、及びタイマの信用性なぞについて。

さて、ちょっと思うことがあって、Sleep()関数の精度を知りたくなった。

いや、それは正確には正しくない。事の始まりは、WaitForSingleObjectの概要をみていたときのことだ。この関数が待つ対象として、Waitable timerというものが存在した。とりあえず、疑問に思ったのでSetWaitableTimerあたりをみてみると、これが時間の同期を取るものらしい。WaitForSingleObjectのまちかた自体は、Sleepと同じ様な代物なので、代用品として使えそうだ。で、その単位が100ns(!)であるので、こいつはつかえるんで無いかい?というわけで、その使用法を探索しようとしたのである。しかぁし。そもそもたとえば、50μsきっちり休んでるとして、それをどないして計るか、という問題が残るのである。大抵μs単位の精度を持つ時間関数なんて、そんなに無いわけである。

で、まず、timeGetTimeを使った。ところで、NTではtimeGetTimeの精度は10msであり、timeBeginPeriodを使用して、精度を1msまで上げる(本当にあがったのかは知らない)。ここまではよい。ところが、他にも時間の経過を探る関数がある。getTickCountではなく、QueryPerformanceCounterである。QueryPerformanceFrequencyを実行してみると、これが僕のマシンでは1.2MHzあたりを返す。と、すればこれは0.83μ秒の精度があると考えて良いと思う。しかし、まずこれがtimeGetTimeと合わない。Sleep(1000)で一秒休ませると、timeGetTimeでは常に1000を測定できる(単位はms)。しかし、Query...では993〜999であり、どっちが正しいねん、という話になる。

そこで、第三の基準を持ち出すことになる。そもそもWindowsなんかに頼るから間違うのであり、Pentiumの提供するrdtscで、クロックの経過時間を探ればいいのである。あとは、それを267で割れば(PII 266MHzだからね)、μs単位で経過時間り、精度が10nsはある筈である。

で、これがSleep(100)の結果(pII-266 NT4sp5で実行。なお、他のプロセスは多数存在するが、CPUロードとしてはそんなに大したことはない)。tGtはtimeGetTime。qpCはQueryPerformanceCounter。clkはrdtscを267で割った値。

will wait 100 msec
tGt:100 ms
qpC:94.048519 ms (fq:1193182 / sec)
clk:85120 us(dif:22727095 count)

なぜだぁ?!この15msの違いは、一体どこから来るんだっ。tGtは10msの精度はあるんじゃなかったのか!? sleep==tGt>qpC>clkってのは一体どういうことなんだ?

あ、ひょっとして、「WinNTは暇なときHLTを発行するから、クロック経過を267で割っても1μsとは限らない」のでは‥‥‥ しまった、これでは正確なのがどれか判らぬではないか。tGtとqpCの違いは、NTでtGtがtimeBeginPeriod使っても何故か10msの精度しかないので、精度範囲内ということになってしまったのである。今度は常に全力疾走でtGtの精度が1msのWin98でやってみよ。

というわけで、続く

ちなみにWaitable timerはWin98かNTしか使えないのです。Win95では使えないんですね。まぁ、どうも100ns単位ということだけで、Sleepと同じくらいの精度しかないことが判りつつありますが、すでに目的がずれているので、どうでもよろし。 一応、ソース

7/4 と、いうわけで追加。

全く不思議な事態になってきた。4秒待って見よう。

will wait 4000 msec 
tGt:4000 ms 
qpC:3994.163506 ms (fq:1193182 / sec) 
clk:3989221  us(dif:1065122177 count)

ここではNTだからtGtは無視して(Win98ではtGtがqpCに近くなる)みると、どう考えてもSleep()には10ms位の精度しかないのである。

ちなみに、Sleep(0)は、

tGt:10 ms
qpC:10.047084 ms(fq:1193182 / sec)
clk:1037 us(dif:277071 count)


tGt:0 ms qpC:0.050286 ms(fq:1193182 / sec) clk:44 us(dif:11777 count)

と、大変面白い傾向が出ている。なお、最高でも10msくらいだったをお伝えする。ここで興味深いのはclkとqpCの違いである。なんと、上では9msも出ているかと思えば、下では6μsしか出ていない。ここでqpCとは恐らくタイマ割り込みを最大精度にしたときのカウントであることがまぁ想像される。と、すれば実はこいつもたいしたことが無いのでは‥‥しかしながら、これは精度を10msとする結論に何ら支障を与えない。

結論:Sleep()の精度は10ms。負荷が高い(90%)ときでも10ms。ただしNT。
  tGtは当てにならない。特にNT
  qpCもそんなにあてにならない。
  clkが正確。(よく考えれば、hltしてても大丈夫なはずだ。)

5/31 小さなWindowsアプリの作り方。

ただでさえ膨らみがちなWINDOWsアプリですが、それなりに小さくする方法もあります。ここでは実行サイズのことですけども。もちろん/O1で最適化するのは当然。

まずVC6な向きは、アラインメントが(Win98との絡みで)やたらと大きいので、linkの時に、/link /align:4096 等とします。もちろんスピードは若干落ちますが、それは問題にしません。何なら、/align:16でもよろしい。次に静的なデータを少なくします。たとえば、static char t[1024]というのがあるとすると、それ消すだけで1024byte、実行ファイルが小さくなります。

次はやくざな方法。これはいくらか制限があります。ランタイムライブラリ(Standard C Library)を使わないことと、コマンドライン引数を処理しないこと。WinMainとSDKを中心にすれば、不可能ではないでしょう。MFC?あなた、この話をそもそも根本から誤解してますね。要するに、常駐モノやツールなどでファイルサイズが小さいほうがいい、という目的の物であって、MFCを選択するのでは目的から異なりますな。これは、/link のあとに /entry:WinMain をやればよろしい。僕はこれで、33KBあったファイルを6KBにまで削減しました。ソースコードが8KB強なので、案外小さくなった、という感慨のようなものがあります。

大体1秒毎になにか処理がしたいとしましょう。どう作りますか?

もちろん、WINDOWSですから、VXDなんかで
__int64 o=rdtsc()
__asm{cli;};
while(1) {
_int64 s=rdtsc();
if((s-o)>CPUSPEChz) break;
}
__asm{sti;};

などというコードは御法度です。まじめな解答、またはWindowsのプログラム例題としてはタイマ登録して WM_TIMER メッセージをもらうという話です。ただ、これはwndproc が無い(=ウインドウがない)と使えませんし、終了処理とか、そのあたり面倒です。

他のやり方としては、ワーカスレッドを作成して、Sleep(1000);するという話です。ワーカスレッド自体はwhile(1)としても、Sleepが効きますからマルチスレッド向けです。問題としては、20分毎に何かするというときに、Sleep(20*60*1000);してしまうと、そのスレッドは20分毎にしか終了する機会が与えられないということです。スレッドは自分自身で終了した方が良いのですから、これでは困ります。そのあたり考える必要がありますが。あと、精度の面も。

文字列探索。どうしましょう?

どんなアルゴリズムの本にも、文字列探索のやり方は書いてある。Boyer-Moore法とか、簡略BM法など様々な方法がある。しかし、そんな高尚な理論を披露しなくても充分なことがおおい。まずは一番バカ(率直)な方法

const char *find(const char *str,const char *find)
{ 
	while(*str){
	  if(strncmp(str,find,strlen(find))==0)
		return str;
	  str++;
	}
	return NULL;
}

これが非効率なのは明らかである。find*str回数分(裸の変数名はその長さとして)の比較が生じるからである。しかし、アルゴリズムを云々しなくても、次の改善案はすぐに思いつく。 名付けるなら、先頭文字キャッシュ法である。

const char *find(const char *str,const char *find)
{
	char ch=*find++;
	while(*str){
	  if(*str++ != ch)
		continue;
	  if(strncmp(str,find,strlen(find))==0)
		return str;
	}
	return NULL;
}

これで、アルファベットなら52文字だから一気に52倍速である(実際には分布が均等ではないのでけれども)。そもそも、この種の探索がlog(n)で済むなどと云う話はまぁないのであって、どうあがいても文字列strの数だけ比較を行わねばならないのである(事前にテーブル・木とかを作っている場合は別)。平均比較数は、51/52*str+1/52*str*findである。尤も、アルファベットが均等に分布していないことは考慮に入れねばならないけれど。

あとは、charではなく、short、long、(alpha等なら__int64)で比較を行うというのも手である。但しエンディアンと最後のヌル文字には気を付けねばならない。このとき、(1-1/52^2)*str + (1/52^2)*str*find 回の比較で済む。大抵の32bitマシンでは、メモリのアクセス単位は32bitであるので、charでもlongでも比較自体のコストは変わらない。 よって、比較回数は文字列にn種類の区別があるときに m byte 単位で比較すると、(1-(1/n^m))*str + (1/n^m)*str*findである。理想値、str回の比較にずいぶん近づいたと言える。アルファベットで26パターンとすると、26^4=457K位になるので、strが1MB位なら、str*find項は3〜4となり充分実用となる。こうみると、ずいぶん大きな数でも大丈夫であることが判るのではないだろうか。

まぁ、文字に2種類しか区別がなかったりすると俄然非効率となるのだが、そのあたりの事情はBM法でも同じであるので無視する。これでもまだ簡略BM法を使うのだろうか。って、BM法はO(str/find)であるから、使ったらええんやけど。但し、strlen(str)とやると一気にO(str)だけかかって先頭キャッシュ法とそんなに変わらなくなるので注意。

5/05 STLの盲点など。

 オブジェクトの固まりとして配列を使うのは、C言語でそれが一番容易に実現できるからに過ぎない。であるからSTLとなったときに、その慣習を引きずってstd::vectorを使用する必要などない。多くの場合、std::list、またはstd::dequeで充分事足りるのではないだろうか。そもそも、std::vectorの「ランダムアクセス」よりも、listの「中途挿入速度」が重視されるべきではないかな。まぁ、だからといって、std::list<char>で文字列を表現しようとは思わないが。STLでは、listであっても、listobj[n]という使い方は(非効率的ながら)可能であるし、vectorobj.insert(mendium,5);というのも(大変非効率ながら)可能なのである。あとは、実行時効率だけだ。このあたり、STLは各コンテナの差を隠蔽しすぎているのではないかな、と思うわけです。

ところで、配列って初期化できるでしょ。広域でも、局地でも。
char data[]={100,7,5,66,32};
とか。別段言うこともない。構造体でもできたはずだ。 でも、これのSTL版は、
std::list<char> data={100,7,5,66,32};
とはならない。コンパイルできない。これは、初期化を阻んでいるとしか思えない。何でだろ。多分、アレだね。コンパイラが初期化方法を知らないからだね。だからといって、デフォルトコンストラクタ
std::list<char> data(100,7,5,66,32);
も使えない。charには任意の引数をもつコンストラクタは存在しないから。結局どうしょうもないわけだ。つまり、STLはC++の標準ライブラリだから、C++の礼儀作法に則りクラスメンバにして、そのクラスのコンストラクタで初期化しなさい、と言うことだと受け取ったわけです。


4/28 リストコントロール?大きな口たたけんなぁ。

実は、結構リストコントロールのレポートビューって使いたいコントロールなのだ。そのわりに、SDKは言うに及ばず、MFCも結構面倒くさい。非常に使いづらい。学習しづらい。このあたり、GTK--とかの方が非常に良くできている。テンプレートもあるしね。

Windowsのリストコントロールが非常に理解しがたいのは、大アイコン表示と、小アイコン表示、詳細表示、一覧表示、というエクスプローラ標準の4つの表示方法全てを、単一のコントロールとして実装しているところにある。そのため、内部データの管理方法が非常にややこしくなっている。それはとりもなおさず、設定が面倒くさいと言うことに他ならない。他の表現方法用の関数がいろいろあって、それが小石を隠す森の役目を果たしてくれる。MSDNのMFCヘルプは殆ど役に立たなかった。仕方なく、Win32SDKのヘルプ(英語版)をひもといているところである。これが、MSDNの「リストコントロールのつかいかた」などより断然わかりやすくできているから(SDKなので面倒くさいけど)、やっぱりラッパーのマニュアルのさらに翻訳版ともなると、精度が落ちるのは仕方がないのか。あるいはMFC自体、便利なSDKという扱いで、SDKでクラスの果たす役割、関数のもつ意味、操作方法などがある程度わかっている前提があるのでは、と思ってしまう次第である。

文字列を表す方法がいくつあるか、ご存じでしょうか。まずは、char *。標準ですな。で、これがMBCS対応になると、unsigned char*とかになるときがある。で、wchar_t *。UNICODE文字列ですな。で、CString。MFC謹製の文字列クラス。あとは、string , wstringなどがある。STLに付随してくる物で、実体は、basic_string<char>と、basic_string<wchar_t>のtypedefであるが。 問題は、それぞれ扱いが殆ど異なると言うところで。 さらに使われる範囲も。結局最大公約数である、古き良きsprintfchar *を使う次第となるわけである。

4/26 日本語処理にはまる。

日本語処理といっても、UNICODEのHan-Unificationと包摂基準が‥‥とか言うつもりは更々ない。日欧混合文・禁則処理である。Windowsはやっぱり洋物であるから、禁則処理なんかマトモに考えていない。このあたり、たまぁに全然考えてないアプリは、'、'が平気で行頭に来たりする。考えなしに作ると、「'、'だけで90文字くらいあるときどうするんだ」とかいう問題が発生する。至極面倒くさい問題なのだ。ただひたすら面倒くさい。さらに、英文のプロポーショナル化とか、日欧フォント混合文等、さらにその禁則処理など、考えるだけでぞっとする。ベースラインのちがいから、ワードラップ、日英間の1/4スペース、フォントサイズ比、追い出し、追い込み、ぶら下がり。ハイフナイズ、etc、etc。このあたりをつつくと、ろくな物が出てこない。費用対効果が著しく低いのだ。おとなしく口をつぐむことにしよう。究極的には、日本語のワードラップというのも存在するのであるが。