No Such Blog or Diary

2^n で割ったあまりを求めるには 2^n -1 との AND をとる方が一般には速い．んで，コンパイラもそこらへんがわかっているので AND 演算に置き換えてくれるのだが…　以下の二つのプログラム

int main(int argc, char *argv[])
{
    int k = 0;
    for(int i = 0; i < 100000000; i++){
        k = k % 4;
    }
    return k;
}

と

int main(int argc, char *argv[])
{
    int k = 0;
    for(int i = 0; i < 100000000; i++){
        k = k % 4U;
    }
    return k;
}

では後者のほうが３倍くらい速くなる（倍率は環境によるかもしれないけど）．両者のアセンブリコードを比べると

	xorl	%edx, %edx
	movl	$99999999, %ecx
	jmp	L6
	.p2align 4,,7
L5:
	andl	$-4, %eax
	subl	%eax, %edx
	decl	%ecx
	movl	%edx, %eax
	js	L10
L6:
	testl	%edx, %edx
	movl	%edx, %eax
	jns	L5
	leal	3(%edx), %eax
	andl	$-4, %eax
	subl	%eax, %edx
	decl	%ecx
	movl	%edx, %eax
	jns	L6
L10:
	leave
	ret

と

	xorl	%ecx, %ecx
	movl	$99999999, %edx
	.p2align 4,,15
L5:
	movl	%ecx, %eax
	andl	$3, %eax
	decl	%edx
	movl	%eax, %ecx
	jns	L5
	leave
	ret

のようになっており(gcc3.4.4)，後者のほうが分岐が無いし速いのは当たり前．とりあえず問題点は「符号付の剰余は負数のときにめんどくさい」という点にある．その面倒な処理が分岐を必要として遅くなってしまうと．

ということで，負数なんて知らんという場合には明示的に符号なしであることを指定しておくべし．

よくわからないけど Raw Input 使うのに必要そうなので必要なことだけ調べてみたり．とりあえず Top-Level Collections Opened by Windows for System Use やら Hardware IDs for HID Devices やらにより，RowInputDeviceの登録に必要な情報がとりあえず判明．

Device Type 	Usage Page 	Usage ID
Mouse           0x01             0x02
Keyboard        0x01             0x06

しかし，これらを RAWINPUTDEVICE 構造体に入れて RegisterRawInputDevices してもパラメータが違うとエラーが返ってる…　なぞだ．とりあえず http://www.usb.org/developers/hidpage/ とか http://www.usb.org/developers/docs/ とかを眺めようか？

をしようと思ったら Row Input の API を叩けば良いらしい．これ使って入力がどのキーボードからきたかに応じてレイアウトを切り替えればキーボードごとにレイアウトを変えて使えそうだが…　できるかどうかよくわからん．

とりあえず自分のスロットを消費完了．決勝問題のサイズが大きく read 関数で一度に読みきれなかったため転送ミスで間違った答え連発…　これに気づいて修正するのに３０分を無駄にしてしまった．けどまあ，そのあとは順調に答えが出たので今回のプログラムはそれなりにうまく出来ていたらしい．結局全部で５００台１０００CPUぐらいは占有して計算できたので去年に比べればだいぶ進歩したかなと．戦略を間違えたのでいい答えが出たかはよくわからんが，とにかくあとは結果まち．

usleep がキャンセルポイントになっているであろうと思い込んでいたら実はキャンセルポイントになっていない環境があることに気づいた．ということで，pthread_testcancel() をループ中に叩き込みまくる羽目に．美しくないプログラムだなぁ．

とりあえず，プログラムの連続稼動はあきらめて各問題で再起動させることにして…　あとはファイルサイズがどの程度か気になるけど全員に読ませることにして…　仕掛けは出来上がったので後はグリッド上でテストしよう．どうでもいいけど障害多すぎて練習時間削られてるのは非常に痛い．