为了提供多路分支（multi-way branching ）的能力，编程语言（如C语言）提供了选择语句(Slelection statements)，如if语句和switch语句。但是多重的if-else-if语句在某些情况下执行效率较低，没有switch语句的运行速度快，我们需要灵活选择。
选择语句
C语言中的选择语句包含两种，其语法如下所示：
selection-statement:
if ( expression ) statement
if ( expression ) statement else statement
switch ( expression ) statement
对于测试多个不同条件的情况，可以采用if...else if...else 的格式，也可以采用带有多个case标签的switch语句。
if(test_expression == a)
a();
else if(test_expression == b)
b();
...
...
else if(test_expression == x)
x();
else
fun();
switch ( test_expression ) {
case a:
statement_a;
break;
case b:
statement_b;
break;
...
default:
statement_default;
break;
}
但是两者的运行速度上却有较大的差异。某些情况下，switch-case比if-else的运行速度更快。
实现机制
对于有多个判断条件的if语句，程序在执行时从第一个条件开始进行判断，如果测试条件为真，则执行相应的语句；如果不为真，则继续判断下一个条件。最快的情况下，需要到最后一个分之才能执行完成。对于分之较多的情况，效率尤其低下。
但是，switch语句得益于跳转表(jump table)的实现，可以根据测试条件直接跳转到相应的分支语句上去，不需要逐个对条件进行判断，在case数目很多的情况下也不会降低执行效率。
下面通过一个具体的测试程序对这一特性进行分析。
运行速度测试
这里通过一个包含10个分支的测试程序，对两种不同实现方式的运行速度进行对比和分析。
int test_if_else(int v)
{
if(v == 1)
return v * 13;
else if(v == 2)
return v * 23;
else if(v == 3)
return v * 33;
else if(v == 4)
return v * 43;
else if(v == 5)
return v * 53;
else if(v == 6)
return v * 63;
else if(v == 7)
return v * 73;
else if(v == 8)
return v * 83;
else if(v == 9)
return v * 93;
else if(v == 10)
return v * 103;
else
return 0;
}
对应的switch-case语句如下：
int test_switch_case(int v)
{
switch(v){
case 1:
return v * 13;
case 2:
return v * 23;
case 3:
return v * 33;
case 4:
return v * 43;
case 5:
return v * 53;
case 6:
return v * 63;
case 7:
return v * 73;
case 8:
return v * 83;
case 9:
return v * 93;
case 10:
return v * 103;
default:
return 0;
}
}
通过一个测试程序，调用这两段代码，分别测试它们的运行时长。在测试中，假设各个测试条件出现的概率是相同的；在100000000次调用中，传入的参数是顺序循环出现的，依次执行11个分支。
void run_test()
{
struct timeval start, end;
double elapsed_us = 0;
int i = 0, v = 0;
/* run test with if-else-if */
gettimeofday(&start, NULL);
for(i = 0,v = 0; i<100000000L; i++)
v += test_if_else( i%11 );
gettimeofday(&end, NULL);
elapsed_us = 1000000 * (end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) ;
printf("test_if_else ran %f usec, result = %u\n", elapsed_us, v);
/* run test with switch-case */
gettimeofday(&start, NULL);
for(i = 0,v = 0; i<100000000L; i++)
v += test_switch_case( i%11 );
gettimeofday(&end, NULL);
elapsed_us = 1000000 * (end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) ;
printf("test_switch_case run %f usec, result = %u\n", elapsed_us, v);
}
测试结果及分析
Ubuntu Linux (GCC 4.8.4)
Apple LLVM version 7.0.2 (clang-700.1.81)
从以上测试程序的运行结果可以看出，在编译器各种不同的优化级别下，switch-case都比if-else-if耗时更少。
同时，也可以看到clang在打开编译优化选项的情况下做了更多的优化，运行速度有显著提升。
跳转表（jump table）
从汇编代码也能看出，针对switch-case的跳转表，能够省掉绝大部分的比较操作，直接跳转到相应的执行分支。它首先判断C代码中default的条件是否成立，如果是，则直接返回；否则，则根据索引（switch index）的值直接引用跳转表对应位置的指令。如下所示。
.globl test_switch_case
.type test_switch_case, @function
test_switch_case:
.LFE40:
.cfi_startproc
subl $1, %edi
xorl %eax, %eax
cmpl $9, %edi
ja .L15
movl CSWITCH.5(,%rdi,4), %eax
.L15:
rep_ret
.cfi_endproc
CSWITCH.5:
.long 13
.long 46
.long 99
.long 172
.long 265
.long 378
.long 511
.long 664
.long 837
.long 1030
.ident "GCC: (Ubuntu 4.8.4-2ubuntu~14.04.3) 4.8.4"
.section .note.GNU-stack,"",@progbits
对于if-else-if，则需要从头开始，逐个执行比较操作，一直到匹配到成功的条件。以下是它对应的汇编代码：
.globl test_if_else
.type test_if_else, @function
test_if_else:
.LFB39:
.cfi_startproc
cmpl $1, %edi
je .L3
cmpl $2, %edi
je .L4
cmpl $3, %edi
je .L5
cmpl $4, %edi
je .L6
cmpl $5, %edi
je .L7
cmpl $6, %edi
je .L8
cmpl $7, %edi
je .L9
cmpl $8, %edi
je .L10
cmpl $9, %edi
je .L11
xorl %eax, %eax
movl $1030, %edx
cmpl $10, %edi
cmove %edx, %eax
ret
.L6:
movl $172, %eax
ret
.L3:
movl $13, %eax
ret
.L4:
movl $46, %eax
ret
.L5:
movl $99, %eax
ret
.L7:
movl $265, %eax
ret
.L8:
movl $378, %eax
ret
.L9:
movl $511, %eax
ret
.L10:
movl $664, %eax
ret
.L11:
movl $837, %eax
ret
.cfi_endproc
clang的优化分析
从以上的测试结果还看到一个有趣的现象，在MacOS上运行测试程序时，switch-case和if-else-if的执行速度相当，几乎没有差别。
通过分析产生的汇编代码可以发现，编译器已经将if-else-if优化成跳转表的实现方式了。以下是-O2选项情况下产生的汇编代码：
_test_if_else: ## @test_if_else
.cfi_startproc
## BB#0:
pushq %rbp
Ltmp0:
.cfi_def_cfa_offset 16
Ltmp1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Ltmp2:
.cfi_def_cfa_register %rbp
decl %edi
cmpl $9, %edi
ja LBB0_2
## BB#1: ## %switch.lookup
movslq %edi, %rax
leaq l_switch.table2(%rip), %rcx
movl (%rcx,%rax,4), %eax
popq %rbp
retq
l_switch.table2:
.long 13 ## 0xd
.long 46 ## 0x2e
.long 99 ## 0x63
.long 172 ## 0xac
.long 265 ## 0x109
.long 378 ## 0x17a
.long 511 ## 0x1ff
.long 664 ## 0x298
.long 837 ## 0x345
.long 1030 ## 0x406
总结
通过以上的对比分析，可以发现switch语句在运行速度上比if-else更有优势。但也不是所有的情况都适用，需要对不同的应用场景进行具体分析。
对于switch语句，它：
适用于
- 判断的测试条件针对同一个变量
- 分支较多（大于4个）
- 测试变量的值在一个较小的、连续的范围，跨度不大
不适用于
- 分支数较少（小于4个）
- 测试条件的值分布比较稀疏
- 测试条件不能基于同一个变量的值进行判断
网友评论