在大多数桌面和服务器架构上,分支比间接调用更快,因为它们进行分支预测和/或推测执行。我从未听说过间接调用比单个分支更快的架构。(对于switch()
语句来说,跳转表有多个分支,因此完全是另一回事。)
考虑一下我放在一起的以下微基准。test.c
:
/* test.c */
volatile long test_calls = 0L;
volatile long test_sum = 0L;
void test(long counter)
{
test_calls++;
test_sum += counter;
}
work.c
:
/* work.c */
void test(long counter);
/* Work function, to be measured */
void test_work(long counter, int flag)
{
if (flag)
test(counter);
}
/* Dummy function, to measure call overhead */
void test_none(long counter __attribute__((unused)), int flag __attribute__((unused)) )
{
return;
}
和harness.c
:
#define _POSIX_C_SOURCE 200809L
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
/* From test.c */
extern volatile long test_calls;
extern volatile long test_sum;
/* Dummy function, to measure call overhead */
void test_none(long counter, int flag);
/* Work function, to be measured */
void test_work(long counter, int flag);
/* Timing harness -- GCC x86; modify for other architectures */
struct timing {
struct timespec wall_start;
struct timespec wall_stop;
uint64_t cpu_start;
uint64_t cpu_stop;
};
static inline void start_timing(struct timing *const mark)
{
clock_gettime(CLOCK_REALTIME, &(mark->wall_start));
mark->cpu_start = __builtin_ia32_rdtsc();
}
static inline void stop_timing(struct timing *const mark)
{
mark->cpu_stop = __builtin_ia32_rdtsc();
clock_gettime(CLOCK_REALTIME, &(mark->wall_stop));
}
static inline double cpu_timing(const struct timing *const mark)
{
return (double)(mark->cpu_stop - mark->cpu_start); /* Cycles */
}
static inline double wall_timing(const struct timing *const mark)
{
return (double)(mark->wall_stop.tv_sec - mark->wall_start.tv_sec)
+ (double)(mark->wall_stop.tv_nsec - mark->wall_start.tv_nsec) / 1000000000.0;
}
static int cmpdouble(const void *aptr, const void *bptr)
{
const double a = *(const double *)aptr;
const double b = *(const double *)bptr;
if (a < b)
return -1;
else
if (a > b)
return +1;
else
return 0;
}
void report(double *const wall, double *const cpu, const size_t count)
{
printf("\tInitial call: %.0f cpu cycles, %.9f seconds real time\n", cpu[0], wall[0]);
qsort(wall, count, sizeof (double), cmpdouble);
qsort(cpu, count, sizeof (double), cmpdouble);
printf("\tMinimum: %.0f cpu cycles, %.9f seconds real time\n", cpu[0], wall[0]);
printf("\t5%% less than %.0f cpu cycles, %.9f seconds real time\n", cpu[count/20], wall[count/20]);
printf("\t25%% less than %.0f cpu cycles, %.9f seconds real time\n", cpu[count/4], wall[count/4]);
printf("\tMedian: %.0f cpu cycles, %.9f seconds real time\n", cpu[count/2], wall[count/2]);
printf("\t75%% less than %.0f cpu cycles, %.9f seconds real time\n", cpu[count-count/4-1], wall[count-count/4-1]);
printf("\t95%% less than %.0f cpu cycles, %.9f seconds real time\n", cpu[count-count/20-1], wall[count-count/20-1]);
printf("\tMaximum: %.0f cpu cycles, %.9f seconds real time\n", cpu[count-1], wall[count-1]);
}
int main(int argc, char *argv[])
{
struct timing measurement;
double *wall_seconds = NULL;
double *cpu_cycles = NULL;
unsigned long count = 0UL;
unsigned long i;
int flag;
char dummy;
if (argc != 3 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s COUNT FLAG\n", argv[0]);
fprintf(stderr, "\n");
return 1;
}
if (sscanf(argv[1], " %lu %c", &count, &dummy) != 1) {
fprintf(stderr, "%s: Invalid COUNT.\n", argv[1]);
return 1;
}
if (count < 1UL) {
fprintf(stderr, "%s: COUNT is too small.\n", argv[1]);
return 1;
}
if (!(unsigned long)(count + 1UL)) {
fprintf(stderr, "%s: COUNT is too large.\n", argv[1]);
return 1;
}
if (sscanf(argv[2], " %d %c", &flag, &dummy) != 1) {
fprintf(stderr, "%s: Invalid FLAG.\n", argv[2]);
return 1;
}
wall_seconds = malloc(sizeof (double) * (size_t)count);
cpu_cycles = malloc(sizeof (double) * (size_t)count);
if (!wall_seconds || !cpu_cycles) {
free(cpu_cycles);
free(wall_seconds);
fprintf(stderr, "Cannot allocate enough memory. Try smaller COUNT.\n");
return 1;
}
printf("Call and measurement overhead:\n");
fflush(stdout);
for (i = 0UL; i < count; i++) {
start_timing(&measurement);
test_none(i, flag);
stop_timing(&measurement);
wall_seconds[i] = wall_timing(&measurement);
cpu_cycles[i] = cpu_timing(&measurement);
}
report(wall_seconds, cpu_cycles, (size_t)count);
printf("\n");
printf("Measuring FLAG==0 calls: ");
fflush(stdout);
test_calls = 0L;
test_sum = 0L;
for (i = 0UL; i < count; i++) {
start_timing(&measurement);
test_work(i, 0);
stop_timing(&measurement);
wall_seconds[i] = wall_timing(&measurement);
cpu_cycles[i] = cpu_timing(&measurement);
}
printf("%ld calls, sum %ld.\n", test_calls, test_sum);
report(wall_seconds, cpu_cycles, (size_t)count);
printf("\n");
printf("Measuring FLAG==%d calls:", flag);
fflush(stdout);
test_calls = 0L;
test_sum = 0L;
for (i = 0UL; i < count; i++) {
start_timing(&measurement);
test_work(i, flag);
stop_timing(&measurement);
wall_seconds[i] = wall_timing(&measurement);
cpu_cycles[i] = cpu_timing(&measurement);
}
printf("%ld calls, sum %ld.\n", test_calls, test_sum);
report(wall_seconds, cpu_cycles, (size_t)count);
printf("\n");
printf("Measuring alternating FLAG calls: ");
fflush(stdout);
test_calls = 0L;
test_sum = 0L;
for (i = 0UL; i < count; i++) {
start_timing(&measurement);
test_work(i, i & 1);
stop_timing(&measurement);
wall_seconds[i] = wall_timing(&measurement);
cpu_cycles[i] = cpu_timing(&measurement);
}
printf("%ld calls, sum %ld.\n", test_calls, test_sum);
report(wall_seconds, cpu_cycles, (size_t)count);
printf("\n");
free(cpu_cycles);
free(wall_seconds);
return 0;
}
将这三个文件放在一个空目录中,然后编译构建./call-test
:
rm -f *.o
gcc -W -Wall -O3 -fomit-frame-pointer -c harness.c
gcc -W -Wall -O3 -fomit-frame-pointer -c work.c
gcc -W -Wall -O3 -fomit-frame-pointer -c test.c
gcc harness.o work.o test.o -lrt -o call-test
在 AMD Athlon II X4 640 上,使用 gcc-4.6.3 (Xubuntu 10.04),运行
./call-test 1000000 1
告诉我,单独测试的开销仅为 2 个时钟周期(< 1ns)(未采用分支),而调用第二个函数时,开销仅为 4 个时钟周期(仅超过 1 纳秒),该函数增加test_calls
并将计数器添加到test_sum
.
省略所有优化时(编译时使用-O0
和省略-fomit-frame-pointer
),单独测试大约需要 3 个时钟周期(如果不采用分支,则为 3 个周期),如果采用分支并完成更新两个额外变量的工作,则大约需要 9 个周期.
(两个额外的变量让您很容易看到线束确实做了它应该做的所有事情;它们只是一个额外的检查。我想在第二个函数中做一些工作,这样时间差异会更容易发现。 )
上述解释只对代码已经缓存的情况有效;即最近运行。如果代码很少运行,它就不会在缓存中。但是,测试开销的影响就更小了。缓存效果——例如,如果“附近”代码已经运行(你可以在调用开销测量中看到这一点,其他测试函数代码也倾向于被缓存!)——无论如何都要大得多。(虽然测试工具确实单独产生了初始调用结果,但不要太相信它,因为它不会尝试以任何方式清除任何缓存。)
我的结论是添加
if (flag)
debug_function_call();
任何普通代码都很好:开销几乎可以忽略不计;实际上无关紧要。与往常一样,请考虑整体算法。算法中的任何改进都会产生比担心编译器生成的代码更大的回报。
(由于我一次编写了上面的测试代码,因此其中可能存在一些错误和/或脑残。检查,如果发现任何问题,请在下面告诉我,以便我修复代码。)