久しぶりに懐かしのWin32 API(not MFC)プログラミング.
Visual Studio Exress 2012 for Windows Desktopは最初から64bitバイナリ作れるのがいい. リソースエディタがあるとうれしいな.
64bit環境ではmanifestのprocessorArchitecture='x86'を'amd64'にしないといけなかったとか, GetWindowLongじゃなくてGetWindowLongPtrでDWL_DLGPROC(WIN64じゃ定義されてない)じゃなくてDWLP_DLGPROCを使うとか. いろいろはまった.
『生き抜くための数学入門』(新井紀子)
中学生～高校生を想定した本. 数学的な構え, 論理的に考える訓練の重要性を説く.
円周率が3.14...の話や負の数同士の掛け算, そもそも掛け算って何, 無限大の話, 筆算の話と基本的なところで鋭い問題提起が沢山. 素晴らしい.
「円周率が約3なんて言ってちゃ, 日本もおしまいですよね」と言っていた新聞記者に著者は 「円周率って何ですか? どうして円周率は3.から始まるんだと思ういます?」と切り返すとその記者は絶句したそうな.
後半は駆け足ながらもグラフの近似式からsin, cosのテイラー展開を通って「博士の愛した数式」にまでたどりつく.
最終章の論理の限界の話は興味深かった. 人間は非常に限定された論理しか使ってないというのが調べられてるそうな. ちょっと調べてみよう.
gccで簡単に21000を全桁表示する方法.
#include <stdio.h>
int main() {
printf("%.f\n", 0x1p1000);
}
実行結果は
gcc t.cpp && ./a.out 107150860718626732094842504906000181056140481170553360744\ 375038837035105112493612249319837881569585812759467291755\ 314682518714528569231404359845775746985748039345677748242\ 309854210746050623711418779541821530464749835819412673987\ 675591655439460770629145711964776865421676604298316526243\ 86837205668069376
いろいろいじっていて気がついた. ちょっと面白い. gccはできるだけ正確に%fを出力しようとするようだ(今まで何か表示されてるけど適当だろうと思ってました. m(__)m). VCではdoubleの精度以降は0になる(まあ普通).
0x1p1000というやや見慣れない記法はC99で導入されている16進浮動小数点定数. 仮数部が1で指数部が1000なので21000を表す.
"%f"ではなく"%.f"なら値が整数のときは小数点以下を表示しない.
double(64bit)なら21023までだが, gccはlong doubleも使えるので"%.Lf", 0x1p16383L(=216383)まで可能. がんばってるなあ.
個人情報保護法と越境データ問題──津田大介の「メディアの現場」より
Tカードの問題って, 日本が国としてどうプライバシーを考えるかという姿勢に関わってるのだなあ.
日本は個人情報保護法の過剰反応問題に過剰反応して、利活用の時代と称して、理論的基礎の欠如、哲学の不在という根本的問題をスルーしてきました。
常に省庁間での協議が必要になってしまいます。意思決定の機動力もなければ方針の統一もありません。交渉過程における高度な政治的妥協など臨機応変な国益保護は全く期待できません。
このあたりの問題はこれに限らずよく聞く. 縦割り行政を越えた動きというのはどうしたらできるのだろう.
Hotmailのパスワードは先頭16文字だけが認証に使われる
16文字より長いときに文句が出るならええんとちゃうか. slashdotなんかたとえば30文字のパスワードに変更すると何も文句言わないくせに勝手に先頭20文字に切り捨てていて, 次回ログイン時に30文字入力するとパスワードエラーで弾かれる. 入力し間違えたかと数回やるとパスワードロックで1日操作できない. 気がつかないと次の日パスワード変更してまたはまる.
先日用事で未来館のそばを通ったら, なんとなく行ってみたくなったので来てしまった.
そしたら少し前にyoutubeの「フカシギの数え方」おねえさんといっしょ！みんなで数えてみよう！が話題になっていたが,
なんとその本家がここにあった. しかも, かなり大きめのブースでいろんな映像を見せながら解説してる.
湊真一氏が1993年に開発したZDDという集合の集まりのデータ処理アルゴリズムがもとになって一大プロジェクト(湊離散構造処理計プロジェクト)が走ってる.
それの紹介の一環だった. すごいなあ. いろんな分野に応用できそうということで勉強してみよう.
# cf. 「フカシギの数え方」の問題を解いてみた.
他にはこれまた少し前に話題になった2012年度イグノーベル賞の, 煩い人を発話を困難にさせるSpeechJammerの原型(だと思う. パネルにこれがヒントになって産総研の人が…と書かれてたので)もあった.
確かに早口言葉をしゃべろうとするとうまういえない. 他にも音声に関する錯覚の展示もあって新鮮だった. 実演コーナーや解説の方はボランティアの人が多く感じられた.
とまあ他にも楽しいが展示があって常時展は素晴らしかったのだが, 特別展示の企画展『科学で体験するマンガ展』～時を超える夢のヒーロー～は…. 私ぐらいの年代をターゲットにしてそうなので, 敢えて「未来館の企画展は行ってはならない」という自分の掟を破って入ってみたが, やっぱりがっかり感が.
ドラえもんの「コエカタマリン」を体験できるコーナー. 「未来」館だし当然「自分がしゃべった言葉がでる」と思ったら, コラー, エー, オイなど決められた4種類ぐらいのものしか認識しないのに 認識精度が悪い. しかも反応パターンも事前に決まったのが表示されるだけ. 落書き銃も銃で直接画面に書けるのではなく, 対象を選択するだけ. そのあとは手元のタッチパネルで選ぶってEXPO'85ですと言われても違和感なさそうな. 「アトムと一緒に空をこえよう」はgoogle earthにアトムをオーバーレイしただけ?
夏休みが終わったとは言え休日だったのにがらがらなのもさもありなん.
gitの説明で, 複数のbranchの絵が出てくるとすぐ混乱する(というか拒絶反応を起こす)のは極度の方向音痴と関係あるのだろうか. 状態が複数あるやつは自分がどこにいるのか分からなくなる.
家の近くでも, 「キャンピングカーが止まってるところで右折」という覚え方なのでたまにその持ち主が旅行に出かけてると通りすぎてしまう.
しばらく前も「民主党議員のポスターのところで左折」だったのが, ある日, 国民の～に変わっていて(略.
# いや, 冗談じゃなくて.
もちろんそんな動くものを目印に設定するのが間違ってるに決まってるのだが, 何故か記憶と行動が上書きされない. 困ったなあ.
『たったひとつの冴えたやり方』(ジェイムズ・ティプトリー・ジュニア 浅倉久志訳)
海外のSFってあんまし読んだことないと言ったら, @shuyoさんが薦めてくれた中の一冊. まずタイトルがかっこいい. 川原由美子(知らなかった)の挿絵もかわいらしい. 少女が一人でこそっと宇宙船に乗って探検する楽しい導入. しかしそこからは思いもつかないラスト. 「グッドナイト，スイートハーツ」の主人公のラストの選択も渋い. どちらも記録用のカセットの描写が時代を感じる.
『ジョナサンと宇宙クジラ』(ロバート・F・ヤング 伊藤典夫編・訳)
こちらも@shuyoさんお薦め. 宇宙に漂う超巨大クジラといえば『フェイダーリンクの鯨』(野尻抱介)が楽しかった. 主人公が伝説のクジラに遭遇して攻撃する直前に中断, 脱出できなくなる最初の数ページ. 豪快な展開だなあ. おもろいからいいけど. どこか能天気な主人公を見倣いたい.
ロバート・F・ヤングって聞いたことあるようなと思ったら「たんぽぽ娘」の著者だった. そちらは読んだことある.
『ジェノサイド』(高野和明)
コンゴの内戦に送り込まれた傭兵, 難病の治療薬を特殊なソフトを使って開発する大学院生が徐々に交錯する. 大学院生の助っ人が優秀な韓国の学生という設定は新鮮. 内戦での子どもの虐殺などの描写は強烈. いろんな要素がてんこ盛りでおなかいっぱいなところもあるけどよくまあ調べて考えて書いたなあと感心. 読書中は先が気になってしかたなかった.
『虐殺器官』(伊藤計劃)
暗殺を命じられて様々な内戦地域に送り込まれる主人公. 感情調整された主人公の悩みが主題の一つ. 『ジェノサイド』と似たところもあるけどこちらは描写がとても静か. ただあまりに淡々としすぎて生々しさが薄れ(これは意図的なものだろうけど), そういう悩みとか感情がコントロールされる部分とかが人ごとっぽくてせまってくるものが少なかった. 言語についてのある面白いアイデアはもう少し踏み込んで欲しかった感も.
memmem vs. mie::findStr
memmemなんてGNU拡張の関数があったのか. 知らなかったな.
で, 先日のプロシンやx86/x64最適化勉強会3で話したstring.hppと速度比較してみた(string_test.cpp).
いつもの通り, 約130MBの日本語ファイルからの文字列探索にどのぐらいかかったか.
| 検索文字 | memmem | mie::findStr | 速度比 |
|---|---|---|---|
| a | 0.85 | 1.04 | 0.82 |
| ab | 4.30 | 0.51 | 8.36 |
| jit | 4.50 | 0.48 | 9.47 |
| 1234 | 4.48 | 0.51 | 8.85 |
| です | 6.06 | 1.25 | 4.83 |
| cybozu | 4.42 | 0.51 | 8.68 |
| これは | 6.41 | 1.14 | 5.64 |
| static_assert | 4.42 | 0.48 | 9.30 |
| 0..0 | 5.12 | 0.52 | 9.93 |
| AB..Z | 4.53 | 0.47 | 9.67 |
mie::findStrはmemmemの8～9倍速いようだ.
プロシン補足その3
発表したときに, rankの実装で海外のライブラリとの比較は?という質問がでていたのでやってみた(rank_test.cpp). 田中哲朗さんにライブラリいくつか紹介していただいた. ありがとうございます.
比較したのはbitあたり1/4の追加メモリが必要なSBV2と追加メモリが1/8のSBV6. marisa-trie 0.2.0, sux-0.7, sdsl-0.9.10.
suxはSSEのpopcntを使ってなかった. sdslはいろんなオプションがあるようでまだよく分かってない. 2048bit単位のテーブルを使うのもあるようだ.
大きなサイズのところでは大体私のやつのほうが速いように見えるけど正しいオプションを設定すればsdslの方が速いのかも. そもそも私はまだselectを実装してないのでフェアでもなんでもない. これは単なるスナップショットということで.
| table size | SBV2 | SBV6 | marisa | sux | sdsl |
|---|---|---|---|---|---|
| 1MiB | 15.39 | 21.74 | 44.75 | 19.97 | 12.44 |
| 4MiB | 19.13 | 24.58 | 47.75 | 27.81 | 14.91 |
| 16MiB | 26.39 | 26.61 | 55.26 | 32.20 | 17.06 |
| 64MiB | 30.98 | 38.74 | 70.82 | 50.83 | 34.22 |
| 256MiB | 57.42 | 83.58 | 128.35 | 108.95 | 72.39 |
| 512MiB | 60.20 | 84.38 | 144.66 | 121.84 | 81.54 |
| 1GiB | 68.83 | 87.84 | 152.00 | 132.07 | 91.08 |
| 2GiB | 70.08 | 96.31 | 164.25 | 136.33 | 102.96 |
| 4GiB | 73.65 | 94.52 | - | 141.11 | 113.78 |
if elseとテーブルジャンプ
その2の追加ベンチマーク(switch.cpp).
test(op, op);
je(".lp0");
cmp(op, 1);
je(".lp1");
cmp(op, 2);
je(".lp2");
jmp(".lp3");
のようなif elseを重ねたタイプと
jmp(ptr [tbl + op * sizeof(size_t)]);
というテーブル引き1回で分岐するタイプと比較してみた.
| i3 2120T gcc | Sandy Bridge VC11 | Xeon X5650 gcc | core2 duo | |||||
|---|---|---|---|---|---|---|---|---|
| op | if else | tbl jmp | if else | tbl jmp | if else | tbl jmp | if else | tbl jmp |
| 0 | 3.43 | 2.82 | 1.82 | 1.82 | 2.62 | 2.62 | 2.75 | 3.02 |
| 1 | 5.11 | 2.88 | 2.71 | 1.87 | 3.48 | 4.35 | 2.74 | 2.90 |
| 2 | 6.72 | 3.13 | 3.62 | 2.04 | 4.35 | 4.36 | 4.84 | 2.99 |
| 3 | 8.34 | 4.23 | 4.55 | 2.79 | 5.23 | 4.35 | 5.82 | 2.99 |
cmpを何度もしないといけないop = 3のような後ろの方ならテーブル引きが速いだろうとは思ったけどop = 0の一発目のやつでも速度は互角なのは意外だった(数値はぶれるので有効数字2桁は無い).
で, もともとの疑問に答えるにはその2の表のnoJmpと上の表のtbl jmpを比べる必要がある. 見にくいのでもう一度並べてみる.
| i3 2120T gcc | Sandy Bridge VC11 | Xeon X5650 gcc | core2 duo | |||||
|---|---|---|---|---|---|---|---|---|
| op | noJmp | tbl jmp | noJmp | tbl jmp | noJmp | tbl jmp | noJmp | tbl jmp |
| 0 | 2.10 | 2.82 | 1.10 | 1.82 | 1.75 | 2.62 | 1.92 | 3.02 |
| 1 | 3.44 | 2.88 | 1.83 | 1.87 | 2.61 | 4.35 | 1.84 | 2.90 |
| 2 | 3.48 | 3.13 | 1.83 | 2.04 | 2.61 | 4.36 | 3.01 | 2.99 |
| 3 | 3.42 | 4.23 | 1.83 | 2.79 | 2.61 | 4.35 | 2.81 | 2.99 |
おお, ほとんど変わらんではないか.
少し間が開いたけどプロシン補足その2
『ビューティフルコード』の8章ではWindowsの画面描画関数bitbltに関する話題がある. その関数は長方形のデータ転送をする関数で引数にラスタオペレーションコードopを持つ. これは転送元(src)と転送先(dst)をどう論理演算するかを指定する命令で, 0に塗るとかandにするとかを指定できる. ざっくり言うとこんな感じ:
for (int y = 0; y < cy; y++) {
for (int x = 0; x < cx; x++) {
*dstPtr = f(*dstPtr, *srcPtr, op);
...
}
// 注:switchの中身は適当
uint32_t f(uint32_t src, uint32_t dst, unit32_t op)
{
switch (op) {
case 0: return 0;
case 1: return src;
case 2: return dst ^ src;
case 3: return src | dst;
...
}
}
ここでは1ピクセルuint32_tと書いたけど実際は8, 16, 24などいろいろあるだろう.
ナイーブに実装するとswitch文がループの一番奥になってしまうので遅すぎる. 当時は高速化のためにopに応じた動的コード生成をしていたらしい.
最近のCPUはそういうループの中のswitchも結構高速に実行されるんじゃないかしらと@nothingcosmosさんに聞かれたのでベンチマークしてみた(switch.cppのbitblt_noJmpとbitblt_jmp1). アセンブラはコンパイラに最適化させないために使ってる.
gccはgcc-4.6.3. いずれも64bit OS. opは上記関数fのopに対応. noJmpはopに関する分岐をループの外で行い, jmp1はループの中で行う.
たとえばop = 0のnoJmpは
L("@@");
mov(ptr [dst], eax);
add(dst, 4);
add(src, 4);
sub(n, 1);
jnz("@b");
こうなっていてループの中はopは参照しない. jmp1は
L("@@");
test(op, op);
je(".lp0");
cmp(op, 1);
je(".lp1");
cmp(op, 2);
je(".lp2");
jmp(".lp3");
align(16);
L(".lp0");
mov(ptr [dst], eax);
jmp(".next");
align(16);
L(".lp1");
mov(eax, ptr [src]);
mov(ptr [dst], eax);
jmp(".next");
ループ毎にif (op == 0) else if (op == 1) else if (...)を実行する.
| i3 2120T gcc | Sandy Bridge VC11 | Xeon X5650 gcc | core2 duo | |||||
|---|---|---|---|---|---|---|---|---|
| op | noJmp | jmp1 | noJmp | jmp1 | noJmp | jmp1 | noJmp | jmp1 |
| 0 | 2.10 | 5.13 | 1.10 | 2.75 | 1.75 | 2.63 | 1.92 | 2.80 |
| 1 | 3.44 | 6.71 | 1.83 | 3.62 | 2.61 | 3.48 | 1.84 | 3.65 |
| 2 | 3.48 | 8.40 | 1.83 | 4.58 | 2.61 | 4.35 | 3.01 | 6.36 |
| 3 | 3.42 | 8.37 | 1.83 | 4.59 | 2.61 | 5.22 | 2.81 | 5.48 |
i3 2120T以外はcmpが一つ増える毎に1clk増えるような感じ. 本当はテーブル引き分岐でのテストもすべきだが諸般の事情で後日できれば(4日参照). これを見ると昔みたいに「ループ毎にswitchなんて論外」というわけでもないんだなあとちょっと感慨深い.
#もちろんそんなことをしてるとループアンロールとかその他いろいろな最適化ができないのでいいわけないのだが.