２００７ 代数曲線暗号を巡ってに参加.
暗号からは暫く遠ざかっていたけどぼちぼち身の回りも落ち着いてきたし, 折角自由な環境にいることができるのだからどんどん勉強せねば.
楕円曲線を頂点, 同種写像を辺としてグラフを作り, その上でランダムウォークをして新しい暗号を考える話と匿名認証の話が面白かった.
後者は例えば私がある会社に所属しているという事実のみを, 私の名前を伏せたまま第三者に証明することができる. 効率よいプロトコルのために1/(x+c)Pの形のものがうまく使われていた.
/* サンプル */
int sum(const std::vector<int>& v)
{
int sum = 0;
for (size_t i = 0, n = v.size(); i < n; i++) {
sum += v[i];
}
return sum;
}
を/D_SECURE_SCL=1でコンパイル
.lp:
test eax, eax
je SHORT .exit
mov ecx, DWORD PTR [edi+8]
sub ecx, eax
sar ecx, 2
cmp esi, ecx ; 範囲チェック
jb .ok
.ng:
call __invalid_parameter_noinfo
.ok:
mov eax, DWORD PTR [edi+4]
add ebx, DWORD PTR [eax+esi*4]
add esi, 1
cmp esi, ebp
jb .lp
/D_SECURE_SCL=0でコンパイル
.lp:
add eax, DWORD PTR [ecx]
add ecx, 4
cmp ecx, edx
jne .lp
ちなみにloopじゃなくてaccumelateを使うとiteratorのチェックは入力前に一度だけになるので/D_SECURE_SCL=1でもループ自体は遅くならない.
int sum(const std::vector<int>& v)
{
return std::accumulate(v.begin(), v.end(), 0);
}
#include <stdio.h>
int func(int i)
{
switch (i) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
return 1;
default:
return 0;
}
}
int main(int argc, char *argv[])
{
int sum = 0;
for (int i = 0; i < 10000; i++) {
sum += func(i & argc);
}
printf("sum=%d\n", sum);
return 0;
};
これにたいして通常モードでのコンパイル結果は
.lp:
mov ecx,eax
and ecx,esi
add ecx,0FFFFFFD0h
cmp ecx,16h
ja .default
movzx ecx,byte ptr tbl1[ecx]
jmp dword ptr tbl2[ecx*4] ; match/default
.match:
mov ecx,1
jmp .next
.default:
xor ecx,ecx
.next:
add eax,1
add edx,ecx
cmp eax,2710h
jl .lp:
とテーブル参照でジャンプ. これをPGOモードでコンパイル&実行(オプション無し)すると,
argc == 0が多い(これしかない)という情報をコンパイラに与えることになる. で, 結果は
.lp:
mov eax,ecx
and eax,esi
cmp eax,30h
jge <上記相当の分岐処理>
xor eax,eax
add ecx,1
add edx,eax
cmp ecx,2710h
jl .lp
...
<分岐処理>
となった. つまりfunc()に渡される値が0の時のみ特に高速に動作するようになった.
分岐しないのでパイプラインも乱れない. 凄いなあ.
_main PROC NEAR
mov eax, DWORD PTR _i$[esp-4] ; eax = i
add eax, -48
cmp eax, 22
ja SHORT .Lexit0 ; 範囲外なので0を返す
xor ecx, ecx
mov cl, byte ptr tbl0[eax]
jmp dword ptr tbl1[ecx*4]
.Lexit1:
mov eax, 1
ret 0
.Lexit0:
xor eax, eax
ret 0
tbl1:
DD .Lexit1
DD .Lexit0
tbl0:
DB 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0,
まあ普通だわな. 二個目の方でも
mov eax, DWORD PTR _i$[esp-4]
cmp eax, 50 ; 00000032H
ja SHORT L5
xor ecx, ecx
mov cl, BYTE PTR $L280[eax]
jmp DWORD PTR $L281[ecx*4]
L0:
mov eax, 1
ret 0
L1:
mov eax, 9
ret 0
L2:
mov eax, 6546
ret 0
L3:
mov eax, 4534
ret 0
L4:
mov eax, 4324
ret 0
L5:
xor eax, eax
ret 0
npad 3
$L281:
DD L0, L1, L2, L3, L4, L5
$L280:
DB 0, 1, 2, 3, 5, 5, 5, 5, ..., 4
と素直. gcc 4.2.2だとL?の部分が
.L3:
popl %ecx
movl $1, %eax
popl %ebp
leal -4(%ecx), %esp
ret
.L4:
popl %ecx
movl $9, %eax
popl %ebp
leal -4(%ecx), %esp
ret
.L5:
popl %ecx
movl $6546, %eax
popl %ebp
leal -4(%ecx), %esp
ret
...
ってなっててややもっさり感が(これはmainの特殊事情?).
ところでVCだと成立しないことが分かってるdefaultに__assume(0);を書くと, 範囲外チェックを省く最適化が行われるけどgccだと何だったけ.
あと実際にプログラムを実行した結果を解析して最適化するPGOなら頻度の高いcaseを先にチェックしそうだな(未確認).
<original> n:1025325 bn:1332921 read 1025325 keys lookup_wo 0.633916 key:0.618259 usec lookup 1.028642 key:1.003235 usec <optimized> n:1025325 bn:1332921 read 1025325 keys lookup_wo 0.294019 key:0.286757 usec lookup 0.760556 key:0.741771 useclookup_woで2倍ちょい.
| std::isspace(C++) | isspace(C) | isspace1 | isspace2 | isspace3 | |
|---|---|---|---|---|---|
| Core2 2.6GHz + VC2005(Xp) | 5.22 | 5.22 | 4.66 | 1.91 | 1.78 |
| Core2 1.6GHz + gcc 4.2.2(32bit Linux) | 23.69 | 4.00 | 4.44 | 4.9 | 3.9 |
| Opteron 240 1.4GHz gcc 3.4.6(64bit Linux) | 13.07 | 13.07 | 7.12 | 7.12 | 5.79 |
bool isspace1(char c)
{
const int begin = 0x09;
const int end = 0x0d;
if (c == ' ' || (begin <= c && c <= end)) {
return true;
}
return false;
}
bool isspace2(char c)
{
const int begin = 0x09;
const int end = 0x0d;
if (c == ' ' || (unsigned)(c - begin) <= end - begin) {
return true;
}
return false;
}
char isspace3(char c)
{
static const char tbl[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1
};
return tbl[(unsigned char)c];
}
というわけで
#include <stdio.h>
#include <ctype.h>
int main()
{
int nl = 0, nw = 0, nc = 0, c, prev = 1;
for (;;) {
char buf[8192];
int i;
int readSize = fread(buf, 1, sizeof(buf), stdin);
for (i = 0; i < readSize; i++) {
int c = buf[i];
if (c == '\n') nl++;
int cur = isspace(c);
if (prev && !cur) nw++;
prev = cur;
}
if (readSize < sizeof(buf)) break;
nc += readSize;
}
printf("%d %d %d\n", nl, nw, nc);
}
実行結果
time tanakhさんのC <data >3.090u 0.090s 0:03.18 100.0% 0+0k 0+0io 167pf+0w time 上記C <data >0.560u 0.060s 0:00.61 101.6% 0+0k 0+0io 166pf+0w time wc < data 3209697 10749964 90689245 >1.010u 0.070s 0:01.07 100.9% 0+0k 0+0io 98pf+0wこの時点で既にwcの1.7倍ぐらい速いですね. C++なら
size_t readSize = fread(buf, 1, sizeof(buf), stdin);
の代わりに
size_t readSize = std::cin.read(buf, sizeof(buf)).gcount();
を使ってもいい(若干遅いけど). ただ気をつけないといけないのはC++のisspace()はCに比べてめっちゃ遅い.
なまじ同名なだけにたち悪い.
試しにC版のコードに#include <iostream>を加えるとそちらが使われるんだがその場合は
>1.680u 0.060s 0:01.74 100.0% 0+0k 0+0io 205pf+0wと3倍近く遅くなる. これはlocaleを見るあたりが複雑なためかな(詳しくは未調査). 一般にC++でis***関数は気をつけないと危ないっぽい. asciiのみ前提なら
static inline bool myIsSpace1(char c)
{
if (c == ' ') return true;
if (0x09 <= c && c <= 0x0d) return true;
return false;
}
static inline char myIsSpace2(char c)
{
static const char tbl[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1
};
return tbl[(unsigned char)c];
}
なんかを作った方がよさそうだ(上記URLのHaskellでもそんなことしてるし不公平ではないだろう).