やっぱり
ほら、やっぱりたとえ話はだめですよ、的な。
ところで、C/C++/Java レベルで普通にできるアルゴリズム以外の最適化って何だろう。
- できるだけキャッシュに乗るように、データの局所性を意識
- 分岐予測ミスができるだけおきないように
そんなもん？あれ、命令セット関係ないな。いや他にもあるはず。
あとまぁ、Pentium 4 の分岐予測ミスのペナルティがでかすぎ。ランダムなデータと逆順に整列されたデータに対して bubble sort をすると逆順にソートされたデータのほうが倍以上速いとか、なんだそれ。でも Pentium M とか AMD 系 CPU とかになるとそこまででもなかったり。
そういや、MSVC++ で getc で一文字ずつ読み込むとすごい遅いなんてことがあって、Linux + glibc ではそんなことは無いんだけど、まぁ、そういう場合は memory mapped file を使うと数百倍以上の高速化ができたりして。行列演算も SIMD でやるという選択肢もあるけど、expression template という手もあるわけで。
まぁ、普通に高速化する分には命令セットがどうとかより libc やら OS やらアルゴリズムの知識が重要なことが多いよ。そういうわけで、senna の nfkc.c を見ていると、trie 使えとか思うわけだ。
