昨日は数論暗号勉強会に参加. 今回はhttpsの脆弱な鍵を運用しているサーバの話と秘匿検索の話. どちらも応用よりの話でいろいろ勉強になった.
昨日は数論暗号勉強会に参加. 今回はhttpsの脆弱な鍵を運用しているサーバの話と秘匿検索の話. どちらも応用よりの話でいろいろ勉強になった.
28日のVCのビット演算→乗算最適化が面白かったので少し試してみた.
int f(int x)
{
return (x << 1) + (x << 2) + (x << 3) + (x << 4);
}
はxを30倍するコードだがどうなるだろう. まずはgcc 4.6.3
f:
lea eax, [0+rdi*4]
lea eax, [rax+rdi*2]
lea eax, [rax+rdi*8]
sal edi, 4
add eax, edi
ret
極めて素直なコード. ではVC2012.
// 64bit imul ecx, 30 mov eax, ecx
// 32bit mov ecx, DWORD PTR _x$[esp-4] mov eax, ecx shl eax, 4 sub eax, ecx add eax, eax
64bitはimul使ってるけど32bitだと30倍をもう一度分解して ((x << 4) - x) * 2に変換してる. おもろいな.
というかなんで64bitと32bitで違うんだと思ったら,
imulに即値が使えるのは64bitだけなのか. 気づいてなかった.
勘違い. imul ecx, ecx, 30(即値は32bit)の意味だった.
FNV hashの定数
昨日のハッシュ関数の中にでてくる定数1677619, 1099511628211は どちらも素数で, 2進数展開したときにハミング重みが小さいように選ばれている.
>>> bin(16777619) '0b1000000000000000110010011' >>> bin(1099511628211) '0b10000000000000000000000000000000110110011'
したがってオリジナルのページではそれぞれ
// v *= 16777619; v += (v << 1) + (v << 4) + (v << 7) + (v << 8) + (v << 24); // v *= 1099511628211ULL; v += (v << 1) + (v << 4) + (v << 5) + (v << 7) + (v << 8) + (v << 40);
なんていう乗算をビットシフトの和に書き換える最適化手法が載っている. というか, そういう最適化が可能なように素数を選んだのだろうが. さて, この処理はどの程度高速化に寄与しているのだろう. VC2012, gcc 4.6.3で試してみた. CPUはi3-2120T, コードはfnv-1a.cpp.
| hash32-mul | hash32-shift | hash64-mul | hash64-shift | |
|---|---|---|---|---|
| VC2012 | 6.55 | 6.58 | 6.54 | 6.55 |
| gcc | 6.58 | 6.53 | 6.62 | 15.97 |
gcc with hash64-shiftだけ遅い理由がわかる? 実はVCではshiftバージョンはご丁寧にもimulを使うコードに変換されていた(だから同じ速度になってる).
mov r10, 1099511628211 .lp ; v ^= x[i]; movzx r8d, BYTE PTR [r9+rcx] inc r9 xor rax, r8 ; v += (v << 1) + (v << 4) + (v << 5) + (v << 7) + (v << 8) + (v << 40); imul rax, r10 cmp r9, rdx jb .lp
gccも32bit versionはimulを使うコードに変換していたが, 64bit版はコードの通りのシフト演算を使っていた.
最近のmulは速いのでそれをわざわざビットシフトと和に書き直すと遅くなることがある. 今回はそれに見事にあたった感じ. これをみるとわざわざ苦労してハミング重みの小さい素数を探す必要もないのかもと思ってしまう.
ちなみにVC2012@i7-2600Kだと3.6clkだった.
文字列に対するhash関数
boostのとVCのとって違うのかなとちょっと気になって調べてみた. まずboost/functional/hash.hpp.
size_t hash(const uint8_t *str, size_t size)
{
size_t seed = 0;
for (size_t i = 0; i < n; i++) {
seed ^= str[i] + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
次にVC2012のやつ(実装はxstddefの_Hash_seq).
// 32bit version
uint32_t hash(const uint8_t *x, size_t n)
{
uint32_t v = 2166136261;
for (size_t i = 0; i < n; i++) {
v ^= x[i];
v *= 16777619;
}
return v;
}
// 64bit version
uint64_t hash(const uint8_t *x, size_t n)
{
uint64_t v = 14695981039346656037ULL;
for (size_t i = 0; i < n; i++) {
v ^= x[i];
v *= 1099511628211ULL;
}
v ^= v >> 32;
return v;
}
これはFNV hashの系列のFNV-1aというやつらしい. いいやつなのかもしれんが, このweb page, 上記単純なコードがどこにあるのか探すのにちょっと苦労した.
gcc 4.6.3はVCと同じだった(tr1/functional_hash.h). VCとgccが同じならそっちを使っとくか(権威主義w).
『山の上の交響楽』(中井紀夫)
この人の本は初めて. とぼけた奇想天外な話の短編集. 「山の上の交響楽」:演奏に1万年かかる交響曲を演奏する楽団. 複数のグループに分かれて一日中演奏し続けている. なぜこんなことしてるのか, 誰が聞いてるのかと問いかけつつ演奏の準備や演奏をする人たちが愛らしい.ヒートテックの下着を買ってみた. すごいあったかい. びっくり.
コンパイラのガイド付き最適化プロファイルオプションメモ
| プロファイルオプション | 最適化オプション | |
|---|---|---|
| VC | /link /LTCG:PGINSTRUMENT | link /LTGC:PGOPTIMIZE |
| gcc | -fprofile-generate | -fprofile-use |
| icc | /Qprof-gen | /Qprof-use |
std::bad_allocが投げられたときのstack traceをとる.
std::set_new_handlerを使うとnewが失敗したときにbad_allocが呼ばれる前のハンドルを登録できるのでそれを使うとよい.
スタックトレースはWindowsならStackWalk64(), Linuxならbacktrace()を使う. そのあたりをラップしたもの(stacktrace.hpp). これを使うとこんな風にstacktraceを表示できる. 実際にはmapファイルを用意しておくべきだろう.
#include <cybozu/stacktrace.hpp>
void putStackTrace()
{
std::cout << "no memory!! " << cybozu::StackTrace();
exit(1);
}
void func()
{
puts("func");
size_t size = 1024 * 1024;
std::vector<double> v;
for (int i = 0; i < 100; i++) {
std::cout << "i=" << i << ", size=" << size << std::endl;
v.resize(size);
size *= 16;
}
}
void g() { func(); }
void h() { g(); }
int main()
try
{
std::set_new_handler(putStackTrace);
h();
} catch (std::exception& e) {
printf("e=%s\n", e.what());
}
もちろん厳密にはbad_allocが投げられたハンドル内でstd::stringなどを使うのは何事か, という問題がある(メモリがないから飛んで来たのに!). まあ実際のところメモリが足りなくなるのはぎりぎりではなくて何か間違えて大きな値が渡されたケースが多いのでそういうときは少々のメモリなら確保できるだろうとく楽観的に思ってる.
気になる場合はアプリが動き始めるときにまず1MBぐらいのメモリを確保しておき, putStackTrace()の中ではそのメモリしか使わないようにするというのがよいだろう.
VC2012で出力ファイル先の変更方法
VC2010ぐらい(覚えていない)からかプロジェクトの[プロパティ]→[リンカー]→[出力ファイル]をいじると
Microsoft.CppBuild.targets(1137,5): warning MSB8012: TargetPath(...) does not match the Linker's OutputFile property value (...). This may cause your project to build incorrectly. To correct this, please make sure that $(OutDir), $(TargetName) and $(TargetExt) property values match the value specified in %(Link.OutputFile).
みたいな警告がでてうっとうしかった. DLLを使ってる場合あちこちのディレクトリごとにコピーするのもなんだし, 複数のexeを同じディレクトリにしたい, RelesaeモードとDebugモードも同じディレクトリにしたい. 普段はコマンドラインで使うことが多いのであんまりまじめに調べてなかったのだけど, いろいろいじって自分なりにようやくやりやすいパターンができたのでメモっておく.
[プロパティマネージャー]を開いてcommon, release, debugのプロパティを用意する. Releaseモードでは一番上にrelease, 次にcommon, あとは既存のプロパティ, Debugモードでは同様に順にdebug, common, 既存としておく. 上にあるプロパティがそれまでの値を上書きする.
たとえばslnファイルと同じディレクトリにbin/を作ってそこにexeをおく. デバッグモードのexeは*d.exeのようにしたいとしよう. そのためにはまずcommon.propsの[共通プロパティ]→[全般]→[出力ディレクトリ]を$(SolutionDir)bin\にする. そうするとexeは全てここに生成される. そしてdebug.propsの[共通プロパティ]→[全般]→[ターゲット名]を$(ProjectName)dにする. こうすればReleaseモードのtagetがtest.exeならDebugモードのexeはtestd.exeになる.
こう設定しておいて新しくプロジェクトを追加したときは上記プロパティを設定すればよい. 共通に定義したいマクロやincludeの場所はcommon.propsに書く.
なお, うっかりdebug.propsなどに先にincludeを指定してしまうとcommon.propsを変更しても反映されない. その場合は継承元の値を使うように設定しなおせばよい.
Xbyakの更新.
XBYAK_NO_OP_NAMEを定義するとand(), or(), xor(), not()を定義しないようにした. 代わりにand_(), or_(), xor_(), not_()を使ってください. これによりgccやclangで-fno-operator-namesを定義しなくてもすませられるようになります.
今までCodeGeneratorのメンバ変数だったeax, ecx, ptrなどをstaticメンバ変数にし, 更にXbyak::util内でconst参照をもたせるようにしました. これによりCodeGeneratorを継承していないクラスからでも
void f(Xbyak::CodeGenerator& as)
{
using namespace Xbyak::util;
as.mov(eax, ptr [ecx + edx});
}
のような記述できるようになります.
SSEの丸め制御
浮動小数点の例外マスクの設定で書いたようにmxcsrの制御はintrinsic関数があるのでそれを使えばできる.
0が直近値への丸め(.5は偶数方向へ), 1が切り捨て, 2が切り上げ, 3がゼロ方向への丸め.
#include <stdio.h>
#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
void put(__m128 x)
{
union di {
__m128 x;
float f[4];
} di;
di.x = x;
printf("%5g %5g %5g %5g\n", di.f[0], di.f[1], di.f[2], di.f[3]);
}
int main()
{
const float a[] = { 1.1f, 1.8f, -2.2f, -2.8f };
__m128 x = _mm_loadu_ps(a);
printf(" ");
put(x);
for (int i = 0; i < 4; i++) {
const int rcMask = 3 << 13;
int cw = _mm_getcsr();
cw &= ~rcMask;
cw |= i << 13;
_mm_setcsr(cw);
printf("%04x ", cw);
/* gccで最適化onだと化けるかも */
put(_mm_cvtepi32_ps(_mm_cvtps_epi32(x)));
}
}
1.1 1.8 -2.2 -2.8
1f80 1 2 -2 -3 // 直近値
3fa0 1 1 -3 -3 // 切り捨て
5fa0 2 2 -2 -2 // 切り上げ
7fa0 1 1 -2 -2 // ゼロ方向
体調が悪いのに人間ドックで更に気分がよろしくない. おいしいものたべてすかっとしたいなあ.
そんなわけでXbyakにfldcw, fstcwを追加
64bit環境でfstcw [eax]がnasmとyasmで違ってたのでまたnasmバグってるのかーと思ったらバグってたのはyasmだった(疑ってすまん>nasm).
nasm(正解)
1 00000000 9B67D938 fstcw word [eax]
yasm(間違い)
2 00000000 679BD938 fstcw word [eax]
fstcwはwait命令(9B) + fnstcw(D9 /7)なので67プレフィクスはfnstcwにつけないといけない. yasmはwait命令に67をつけてしまってるのでfstcw word [rax]と同じ意味になってしまう. ややこしい.
浮動小数点の例外マスクの設定
gcc(というかC99で導入された)feenableexcept()はFPUのcwもSSEのmxcsrもどちらも設定する. それに対してVCにはそんな関数は無い. 代わりに_controlfp_s()を使えばよいのだが, これは32bit環境ではfeenableexcept()と同様に両方のcwを設定するのに対して64bit環境ではSSEのmxcsrしか変更しない. _control87()は64bit環境ではmxcsrをいじるようだし, __control87_2()はご丁寧にも64bit環境では使えなくなってる.
mxcsrは_mm_getcsr()と_mm_setcsr()で取得と設定ができて, この関数はVC/gccどちらも持ってる. しかし64bit VCでfstcw/fldcwってintrinsic命令に無いよなあ. なんでだろう.
cygwinの64bitコンパイラ(mingw64)を初めて使う.
mingw64をいれたあと/usr/x86_64-w64-mingw32/sys-root/mingw/bin/にパスを通さないと動かなかったのだけど, 何か設定間違えてたかな.
で実行してみて初めて気がついたけど, 関数の呼び出し規約は当然Windowsと同じなんだよな. XbyakでLinux用のレジスタ渡しを表すXBYAK64_GCCを定義してしまってたけどXBYAK64_WINにしないといけなかった.
『14歳からの政治』(長谷部尚子)
政治についてやさしく書いた本かと思ったら違って, 中学3年生がいろんな政治家(安倍晋三, 小池百合子, 福島みずほ, ...)にインタビューしたものだった. 6年前のものなので今彼らがどうしているのか比較しながら読むと面白い.
松沢成文, 中田宏のインタビュー, 国会議員と県知事, 市長との問題意識の違いが興味深い. 元市長は昔からゴミ問題に取り組んでいたそうだ. 「与えられた任期の間, 自分の仕事を全力でする」とあるのに任期途中で辞職したのは残念だ. まあ, 途中で止めたり政党を変えたりしてるのはこの人に限ったものではないけど.
「日本を誇りをもてる国にしたい」から今までの「間違った教育」を変えたいそうな. 論理が逆な気がするけど. 変えるべきなのは国じゃないの?