メモ。quadsortのバイナリも見てみよう。
実験環境
kmtr@ubuntu:~/work/2020/0217_quad$ clang --version
clang version 9.0.0-2 (tags/RELEASE_900/final)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
kmtr@ubuntu:~/work/2020/0217_quad$ clang a.c -o a.o -c -O3 -pg -g
kmtr@ubuntu:~/work/2020/0217_quad$ objdump -S -d a.o
まとめ
・quadsortをコンパイルした結果は、レジスタ割り当てがうまくいくと、メモリへの書き込みがかなり減らせそうに見えた。
・「何もしない」がきちんと「何もしない」結果にできた。これはコンパイラが偉い、たぶん。
普通のSWAPを使った実装
なお、普通のSWAPは、
{a,b,c,d} と要素があったら、
sort{a,b} -> sort{b,c} ->sort{c,d}
sort{b,c} -> sort{c,d}
で、ソートできる前提で。
ソースコード
ソースコードはこの部分。
サンプルコード
#define SWAPBY2(val,a,b) \
{\
if ( val[a] > val[b] ) { \
tmp = val[a]; \
val[a] = val[b]; \
val[b] = tmp; \
} \
} \
void stdswap(int *val)
{
int tmp; // shared
SWAPBY2(val,0,1);
SWAPBY2(val,1,2);
SWAPBY2(val,2,3);
SWAPBY2(val,1,2);
SWAPBY2(val,2,3);
}
コンパイル結果
void stdswap(int *val)
{
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: 53 push %rbx
5: 50 push %rax
6: 48 89 fb mov %rdi,%rbx
9: e8 00 00 00 00 callq e <stdswap+0xe>
int tmp; // shared
SWAPBY2(val,0,1);
e: 8b 0b mov (%rbx),%ecx
10: 8b 43 04 mov 0x4(%rbx),%eax
13: 39 c1 cmp %eax,%ecx
15: 7e 27 jle 3e <stdswap+0x3e>
17: 89 03 mov %eax,(%rbx)
19: 89 4b 04 mov %ecx,0x4(%rbx)
SWAPBY2(val,1,2);
1c: 8b 53 08 mov 0x8(%rbx),%edx
1f: 39 d1 cmp %edx,%ecx
21: 7f 24 jg 47 <stdswap+0x47>
23: 89 c8 mov %ecx,%eax
SWAPBY2(val,2,3);
25: 89 d1 mov %edx,%ecx
27: 8b 73 0c mov 0xc(%rbx),%esi
2a: 39 f1 cmp %esi,%ecx
2c: 7f 28 jg 56 <stdswap+0x56>
2e: 89 f2 mov %esi,%edx
SWAPBY2(val,1,2);
30: 89 ce mov %ecx,%esi
32: 39 f0 cmp %esi,%eax
34: 7f 2c jg 62 <stdswap+0x62>
SWAPBY2(val,2,3);
36: 89 f0 mov %esi,%eax
38: 39 d0 cmp %edx,%eax
3a: 7f 30 jg 6c <stdswap+0x6c>
3c: eb 34 jmp 72 <stdswap+0x72>
SWAPBY2(val,1,2);
3e: 89 c1 mov %eax,%ecx
40: 8b 53 08 mov 0x8(%rbx),%edx
43: 39 d1 cmp %edx,%ecx
45: 7e dc jle 23 <stdswap+0x23>
47: 89 53 04 mov %edx,0x4(%rbx)
4a: 89 4b 08 mov %ecx,0x8(%rbx)
4d: 89 d0 mov %edx,%eax
SWAPBY2(val,2,3);
4f: 8b 73 0c mov 0xc(%rbx),%esi
52: 39 f1 cmp %esi,%ecx
54: 7e d8 jle 2e <stdswap+0x2e>
56: 89 73 08 mov %esi,0x8(%rbx)
59: 89 4b 0c mov %ecx,0xc(%rbx)
5c: 89 ca mov %ecx,%edx
SWAPBY2(val,1,2);
5e: 39 f0 cmp %esi,%eax
60: 7e d4 jle 36 <stdswap+0x36>
62: 89 73 04 mov %esi,0x4(%rbx)
65: 89 43 08 mov %eax,0x8(%rbx)
SWAPBY2(val,2,3);
68: 39 d0 cmp %edx,%eax
6a: 7e 06 jle 72 <stdswap+0x72>
6c: 89 53 08 mov %edx,0x8(%rbx)
6f: 89 43 0c mov %eax,0xc(%rbx)
}
72: 48 83 c4 08 add $0x8,%rsp
76: 5b pop %rbx
77: 5d pop %rbp
78: c3 retq
79: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
ポイント
まじめにvalへの書き込みしすぎなのでは？という気がする。
下記のように、ebxレジスタのオフセット位置にデータを書き込む命令がいっぱいある…
47: 89 53 04 mov %edx,0x4(%rbx)
4a: 89 4b 08 mov %ecx,0x8(%rbx)
quadsortを使った実装
ソースコード
ソースコード
void quadswap(int *val)
{
int tmp[4];
if (val[0] > val[1]) {
tmp[0] = val[1];
tmp[1] = val[0];
} else {
tmp[0] = val[0];
tmp[1] = val[1];
}
if (val[2] > val[3]) {
tmp[2] = val[3];
tmp[3] = val[2];
} else {
tmp[2] = val[2];
tmp[3] = val[3];
}
if (tmp[1] <= tmp[2]) {
val[0] = tmp[0];
val[1] = tmp[1];
val[2] = tmp[2];
val[3] = tmp[3];
} else if (tmp[0] > tmp[3]) {
val[0] = tmp[2];
val[1] = tmp[3];
val[2] = tmp[0];
val[3] = tmp[1];
} else {
if (tmp[0] <= tmp[2]) {
val[0] = tmp[0];
val[1] = tmp[2];
} else {
val[0] = tmp[2];
val[1] = tmp[0];
}
if (tmp[1] <= tmp[3]) {
val[2] = tmp[1];
val[3] = tmp[3];
} else {
val[2] = tmp[3];
val[3] = tmp[1];
}
}
}
コンパイル結果
0000000000000080 <quadswap>:
void quadswap(int *val)
{
80: 55 push %rbp
81: 48 89 e5 mov %rsp,%rbp
84: 53 push %rbx
85: 50 push %rax
86: 48 89 fb mov %rdi,%rbx
89: e8 00 00 00 00 callq 8e <quadswap+0xe>
int tmp[4];
if (val[0] > val[1]) {
8e: 8b 33 mov (%rbx),%esi
90: 8b 43 04 mov 0x4(%rbx),%eax
93: 39 c6 cmp %eax,%esi
95: 89 c2 mov %eax,%edx
97: 0f 4d d6 cmovge %esi,%edx
9a: 0f 4f f0 cmovg %eax,%esi
} else {
tmp[0] = val[0];
tmp[1] = val[1];
}
if (val[2] > val[3]) {
9d: 8b 43 08 mov 0x8(%rbx),%eax
a0: 8b 7b 0c mov 0xc(%rbx),%edi
a3: 39 f8 cmp %edi,%eax
a5: 89 f9 mov %edi,%ecx
a7: 0f 4d c8 cmovge %eax,%ecx
aa: 0f 4f c7 cmovg %edi,%eax
} else {
tmp[2] = val[2];
tmp[3] = val[3];
}
if (tmp[1] <= tmp[2]) {
ad: 39 c2 cmp %eax,%edx
af: 7e 0f jle c0 <quadswap+0x40>
val[0] = tmp[0];
val[1] = tmp[1];
val[2] = tmp[2];
val[3] = tmp[3];
} else if (tmp[0] > tmp[3]) {
b1: 39 ce cmp %ecx,%esi
b3: 7e 12 jle c7 <quadswap+0x47>
val[0] = tmp[2];
b5: 89 03 mov %eax,(%rbx)
val[1] = tmp[3];
b7: 89 4b 04 mov %ecx,0x4(%rbx)
ba: 89 f0 mov %esi,%eax
bc: 89 d1 mov %edx,%ecx
be: eb 20 jmp e0 <quadswap+0x60>
val[0] = tmp[0];
c0: 89 33 mov %esi,(%rbx)
val[1] = tmp[1];
c2: 89 53 04 mov %edx,0x4(%rbx)
c5: eb 19 jmp e0 <quadswap+0x60>
val[2] = tmp[0];
val[3] = tmp[1];
} else {
if (tmp[0] <= tmp[2]) {
c7: 39 c6 cmp %eax,%esi
c9: 89 f7 mov %esi,%edi
cb: 0f 4f f8 cmovg %eax,%edi
ce: 0f 4d c6 cmovge %esi,%eax
d1: 89 3b mov %edi,(%rbx)
d3: 89 43 04 mov %eax,0x4(%rbx)
} else {
val[0] = tmp[2];
val[1] = tmp[0];
}
if (tmp[1] <= tmp[3]) {
d6: 39 ca cmp %ecx,%edx
d8: 89 d0 mov %edx,%eax
da: 0f 4f c1 cmovg %ecx,%eax
dd: 0f 4d ca cmovge %edx,%ecx
e0: 89 43 08 mov %eax,0x8(%rbx)
e3: 89 4b 0c mov %ecx,0xc(%rbx)
} else {
val[2] = tmp[3];
val[3] = tmp[1];
}
}
}
e6: 48 83 c4 08 add $0x8,%rsp
ea: 5b pop %rbx
eb: 5d pop %rbp
ec: c3 retq
ポイント
メモリへの書き出しが少ない！
tmp[4]を導入し、それがレジスタに割り当てられることで、val[0..3]への書き出しが少なくなったような！
if (tmp[0] <= tmp[2]) {
c7: 39 c6 cmp %eax,%esi
c9: 89 f7 mov %esi,%edi
cb: 0f 4f f8 cmovg %eax,%edi
ce: 0f 4d c6 cmovge %esi,%eax
d1: 89 3b mov %edi,(%rbx) ☆ val[0] = tmp[2]
d3: 89 43 04 mov %eax,0x4(%rbx) ☆ val[1] = tmp[0]
} else {
val[0] = tmp[2];
val[1] = tmp[0];
}
何もしないが、何もしない！
Beautiful!! 並びかえを実行しない、という部分は本当になにも実行しないようになっている。
if (tmp[1] <= tmp[2]) {
ad: 39 c2 cmp %eax,%edx
af: 7e 0f jle c0 <quadswap+0x40>
val[0] = tmp[0];
val[1] = tmp[1];
val[2] = tmp[2];
val[3] = tmp[3];