引数の数が関数の実行時間に及ぼす影響を調査した話
x86_64の呼び出し規約では、関数の引数は主にレジスタを使って渡すように定義されている。
主に、というのは引数の数が6個まではレジスタ（%edi、%esi、%edx、%ecx、%r8、%r9）を使って渡し、7個以上の場合はスタックに置いて渡す形式となっているからだ。
レジスタとメモリアクセスでは明らかに後者のほうが遅いため、関数の引数が7個以上になると6個以下の関数に比べて実行時間が増加するのでは？と思い検証してみた。
検証環境は以下の通り。
| OS | Gentoo Linux |
| カーネル | Linux 4.9.76-gentoo-r1 |
| コンパイラ | GCC 6.4.0 |
| CPU | Intel Core i7-3770K（3.50GHz） |
検証には以下のコードを用いた。マクロ内でこんな短くて衝突しやすい名前を使うべきではないとか、そもそもマクロを使うべきではないとか、色々とマサカリが怖いですが、良い子の皆さんは真似しないでくださいということでどうかご容赦ください。
#include <stdio.h>
#include <time.h>
#define LOOP_MAX (100000000)
#define TRY_COUNT (100)
void timespec_diff(struct timespec *start, struct timespec *end, struct timespec *diff)
{
if ((end->tv_nsec - start->tv_nsec) < 0) {
diff->tv_sec = end->tv_sec - start->tv_sec - 1;
diff->tv_nsec = 1000000000 + end->tv_nsec - start->tv_nsec;
} else {
diff->tv_sec = end->tv_sec - start->tv_sec;
diff->tv_nsec = end->tv_nsec - start->tv_nsec;
}
}
int func_arg_one(int a)
{
return a + a + a + a + a + a + a + a;
}
int func_arg_two(int a, int b)
{
return a + b + a + a + a + a + a + a;
}
int func_arg_three(int a, int b, int c)
{
return a + b + c + a + a + a + a + a;
}
int func_arg_four(int a, int b, int c, int d)
{
return a + b + c + d + a + a + a + a;
}
int func_arg_five(int a, int b, int c, int d, int e)
{
return a + b + c + d + e + a + a + a;
}
int func_arg_six(int a, int b, int c, int d, int e, int f)
{
return a + b + c + d + e + f + a + a;
}
int func_arg_seven(int a, int b, int c, int d, int e, int f, int g)
{
return a + b + c + d + e + f + g + a;
}
int func_arg_eight(int a, int b, int c, int d, int e, int f, int g, int h)
{
return a + b + c + d + e + f + g + h;
}
#define MEASURE(filename, funcname, ...) \
do { \
FILE *fp = fopen(filename, "w"); \
size_t i, j; \
struct timespec before, after, diff; \
for (i = 0; i < TRY_COUNT; i++) { \
clock_gettime(CLOCK_MONOTONIC, &before); \
for (j = 0; j < LOOP_MAX; j++) { \
funcname(__VA_ARGS__); \
} \
clock_gettime(CLOCK_MONOTONIC, &after); \
timespec_diff(&before, &after, &diff); \
fprintf(fp, "%lld.%.9ld\n", (long long)diff.tv_sec, diff.tv_nsec); \
} \
fclose(fp); \
} while(0)
int main(void)
{
MEASURE("one.dat", func_arg_one, j);
MEASURE("two.dat", func_arg_two, j, j);
MEASURE("three.dat", func_arg_three, j, j, j);
MEASURE("four.dat", func_arg_four, j, j, j, j);
MEASURE("five.dat", func_arg_five, j, j, j, j, j);
MEASURE("six.dat", func_arg_six, j, j, j, j, j, j);
MEASURE("seven.dat", func_arg_seven, j, j, j, j, j, j, j);
MEASURE("eight.dat", func_arg_eight, j, j, j, j, j, j, j, j);
return 0;
}
1個から8個までの引数を取る関数を用意し、各関数は渡された引数を単純に足し算する。この時、引数が8個に満たないものは不足分を最初の引数から足すことにした。つまり、引数が2つの場合は「引数1 + 引数2 + 引数1 + 引数1 + 引数1 + 引数1 + 引数1 + 引数1」している。この計算をLOOP_MAX回繰り返したものを1セットとし、TRY_COUNTセット回の試行を各datファイルに出力する。また、コンパイラによる最適化を抑制するため、コンパイル時に-O0オプションを追加している。
出力された各datファイルの平均値をプロットした図が以下のグラフになる。
引数の数が増えるほど時間が増加する傾向が見れる。しかし、期待した結果とは異なり、引数の数が7個以上であることで特段時間が増加する様子は見て取れなかった。
逆アセンブルして関数を確認すると以下のようになっていた。
00000000000008a4 <func_arg_one>:
8a4: 55 push %rbp
8a5: 48 89 e5 mov %rsp,%rbp
8a8: 89 7d fc mov %edi,-0x4(%rbp)
8ab: 8b 45 fc mov -0x4(%rbp),%eax
8ae: 8d 14 00 lea (%rax,%rax,1),%edx
8b1: 8b 45 fc mov -0x4(%rbp),%eax
8b4: 01 c2 add %eax,%edx
8b6: 8b 45 fc mov -0x4(%rbp),%eax
8b9: 01 c2 add %eax,%edx
8bb: 8b 45 fc mov -0x4(%rbp),%eax
8be: 01 c2 add %eax,%edx
8c0: 8b 45 fc mov -0x4(%rbp),%eax
8c3: 01 c2 add %eax,%edx
8c5: 8b 45 fc mov -0x4(%rbp),%eax
8c8: 01 c2 add %eax,%edx
8ca: 8b 45 fc mov -0x4(%rbp),%eax
8cd: 01 d0 add %edx,%eax
8cf: 5d pop %rbp
8d0: c3 retq
...
0000000000000a2c <func_arg_eight>:
a2c: 55 push %rbp
a2d: 48 89 e5 mov %rsp,%rbp
a30: 89 7d fc mov %edi,-0x4(%rbp)
a33: 89 75 f8 mov %esi,-0x8(%rbp)
a36: 89 55 f4 mov %edx,-0xc(%rbp)
a39: 89 4d f0 mov %ecx,-0x10(%rbp)
a3c: 44 89 45 ec mov %r8d,-0x14(%rbp)
a40: 44 89 4d e8 mov %r9d,-0x18(%rbp)
a44: 8b 55 fc mov -0x4(%rbp),%edx
a47: 8b 45 f8 mov -0x8(%rbp),%eax
a4a: 01 c2 add %eax,%edx
a4c: 8b 45 f4 mov -0xc(%rbp),%eax
a4f: 01 c2 add %eax,%edx
a51: 8b 45 f0 mov -0x10(%rbp),%eax
a54: 01 c2 add %eax,%edx
a56: 8b 45 ec mov -0x14(%rbp),%eax
a59: 01 c2 add %eax,%edx
a5b: 8b 45 e8 mov -0x18(%rbp),%eax
a5e: 01 c2 add %eax,%edx
a60: 8b 45 10 mov 0x10(%rbp),%eax
a63: 01 c2 add %eax,%edx
a65: 8b 45 18 mov 0x18(%rbp),%eax
a68: 01 d0 add %edx,%eax
a6a: 5d pop %rbp
a6b: c3 retq
最適化を抑制しているため、引数を一度メモリ上に保持し、そこから毎回計算しているようだ。このため、引数の個数は関係なく全ての関数でメモリアクセスが発生しているため、期待した結果が得られなかったものと予想できる。
ならばと最適化（-O1）してメモリアクセスが極力発生しないようにし、再検証してみた。逆アセンブルしたコードは以下のとおり。
0000000000000860 <func_arg_one>: 860: 8d 04 fd 00 00 00 00 lea 0x0(,%rdi,8),%eax 867: c3 retq 0000000000000868 <func_arg_two>: 868: 8d 04 be lea (%rsi,%rdi,4),%eax 86b: 8d 04 78 lea (%rax,%rdi,2),%eax 86e: 01 f8 add %edi,%eax 870: c3 retq 0000000000000871 <func_arg_three>: 871: 8d 04 be lea (%rsi,%rdi,4),%eax 874: 8d 04 10 lea (%rax,%rdx,1),%eax 877: 8d 04 78 lea (%rax,%rdi,2),%eax 87a: c3 retq 000000000000087b <func_arg_four>: 87b: 01 fe add %edi,%esi 87d: 01 f2 add %esi,%edx 87f: 01 d1 add %edx,%ecx 881: 8d 04 b9 lea (%rcx,%rdi,4),%eax 884: c3 retq 0000000000000885 <func_arg_five>: 885: 01 fe add %edi,%esi 887: 01 f2 add %esi,%edx 889: 01 d1 add %edx,%ecx 88b: 44 01 c1 add %r8d,%ecx 88e: 8d 04 79 lea (%rcx,%rdi,2),%eax 891: 01 f8 add %edi,%eax 893: c3 retq 0000000000000894 <func_arg_six>: 894: 01 fe add %edi,%esi 896: 01 f2 add %esi,%edx 898: 01 d1 add %edx,%ecx 89a: 44 01 c1 add %r8d,%ecx 89d: 44 01 c9 add %r9d,%ecx 8a0: 8d 04 79 lea (%rcx,%rdi,2),%eax 8a3: c3 retq 00000000000008a4 <func_arg_seven>: 8a4: 01 fe add %edi,%esi 8a6: 01 f2 add %esi,%edx 8a8: 01 d1 add %edx,%ecx 8aa: 44 01 c1 add %r8d,%ecx 8ad: 44 01 c9 add %r9d,%ecx 8b0: 89 c8 mov %ecx,%eax 8b2: 03 44 24 08 add 0x8(%rsp),%eax 8b6: 01 f8 add %edi,%eax 8b8: c3 retq 00000000000008b9 <func_arg_eight>: 8b9: 01 f7 add %esi,%edi 8bb: 01 fa add %edi,%edx 8bd: 01 d1 add %edx,%ecx 8bf: 44 01 c1 add %r8d,%ecx 8c2: 44 01 c9 add %r9d,%ecx 8c5: 89 c8 mov %ecx,%eax 8c7: 03 44 24 08 add 0x8(%rsp),%eax 8cb: 03 44 24 10 add 0x10(%rsp),%eax 8cf: c3 retq
lea命令で計算していて読みづらいが、引数が7個以上の関数（func_arg_seven、func_arg_eight）のみメモリアクセスが発生している。
この状態では実行がすぐに終わってしまうので、LOOP_MAXを10倍（100000000→1000000000）し、先ほどと同様に平均値をプロットしたものが以下のグラフとなる。
引数が7個以上の関数において実行時間が増加する傾向が見て取れるが、今度は引数が5個と6個の場合に実行時間が何故か減少してしまった。引数が1個の時より短いんだけど何これ…
まとめとして、確かに引数の数が増加すると処理時間が増加することがあるが、微々たる差であるため引数を無理に減らすよりも他の部分で最適化をしたほうが建設的であると言える。
無理矢理まとめたけどこれ以上の調査はCPI(?)とかの世界になってきそうなので、僕には無理です。誰かやってください。
