最近在做sstable写性能优化的事,涉及到了switch case,作为兴趣,了解了一下switch case在GCC中的优化方法(现在还不清楚,在加-O2时,编译器处理switch是如何做的),可能实际性能影响不大。

GCC优化switch原则:
—对于小于等于4个case的switch,采用二分查找
—对于大部分case不连续的case,采用二分查找
—对于连续的case,采用映射表来处理
—对于大部分连续,少量不连续的case,或是case数值差别不大的case,采用填充冗余case,或是分成几个映射表来处理(不同的编译器做法可能不同)
—对于不是从0开始的case(相差不大时,会进行填充),相差很大时,在做映射表时,要先执行一个减指令,再用映射表来处理
—case顺序无关,GCC会对它进行排序

使用switch注意事项:
(1)case尽量连续,防止填充case
(2)case尽量从0开始,减少一条DEL指令或是填充case
(3)当有3或4个case(1,2,3,4)时,执行频度高的指令可以将其case设为2
(4)尽量避免相差很大的case,可能会完全转化为if…else….
(5)case超过四个时,条目数对性能影响不大,除非过多,超出了CPU cache的大小,
(6)case选项中使用的函数,尽量不要inline,可能导致case中代码过多超出了CPU cache的大小,触发读取内存的操作。

情景1:连续的case,case数目小于等于4.(采用二分查找法)

void switch_case(int data)
{
int ret = 0;
switch(data)
{
case 1:
ret = 1;
break;
case 2:
ret = 2;
break;
case 3:
ret = 3;
break;
case 4:
ret = 4;
break;
default:
ret = 5;
}
}

gcc -S a1.c a1.s

movl %edi, -20(%rbp)
movl $0, -4(%rbp)
movl -20(%rbp), %eax (形参data加入寄存器eax)
cmpl $2, %eax
je .L4 (等于2)
cmpl $2, %eax
jg .L7 (大于2)
cmpl $1, %eax
je .L3 (等于1)
jmp .L2
.L7:
cmpl $3, %eax
je .L5 (等于3)
cmpl $4, %eax
je .L6 (等于4)
jmp .L2
.L3:
movl $1, -4(%rbp)
jmp .L9
.L4:
movl $2, -4(%rbp)
jmp .L9
.L5:
movl $3, -4(%rbp)
jmp .L9
.L6:
movl $4, -4(%rbp)
jmp .L9
.L2:
movl $5, -4(%rbp) (default)
.L9:
leave
.cfi_def_cfa 7, 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
movl %edi, -20(%rbp)
movl $0, -4(%rbp)
movl -20(%rbp), %eax (形参data加入寄存器eax)
cmpl $2, %eax
je .L4 (等于2)
cmpl $2, %eax
jg .L7 (大于2)
cmpl $1, %eax
je .L3 (等于1)
jmp .L2
.L7:
cmpl $3, %eax
je .L5 (等于3)
cmpl $4, %eax
je .L6 (等于4)
jmp .L2
.L3:
movl $1, -4(%rbp)
jmp .L9
.L4:
movl $2, -4(%rbp)
jmp .L9
.L5:
movl $3, -4(%rbp)
jmp .L9
.L6:
movl $4, -4(%rbp)
jmp .L9
.L2:
movl $5, -4(%rbp) (default)
.L9:
leave
.cfi_def_cfa 7, 8
情景2:大于等于5个case,case全部连续整数,case从1开始:(前面填充一个0,采用一个映射表来中转)

void switch_case(int data)
{
int ret = 0;
switch(data)
{
case 1:
ret = 1;
break;
case 2:
ret = 2;
break;
case 3:
ret = 3;
break;
case 4:
ret = 4;
break;
case 5:
ret = 5;
break;
default:
ret = 6;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void switch_case(int data)
{
int ret = 0;
switch(data)
{
case 1:
ret = 1;
break;
case 2:
ret = 2;
break;
case 3:
ret = 3;
break;
case 4:
ret = 4;
break;
case 5:
ret = 5;
break;
default:
ret = 6;
}
}
gcc -S a1.c a1.s

mov -20(%rbp), %eax
movq .L8(,%rax,8), %rax (变址寻址: .L8 + rax,8是什么意思??)
jmp %rax
.section .rodata
.align 8
.align 4
.L8: (映射表)
.quad .L2 (填充0)
.quad .L3
.quad .L4
.quad .L5
.quad .L6
.quad .L7
.text
.L3:
movl $1, -4(%rbp)
jmp .L10
.L4:
movl $2, -4(%rbp)
jmp .L10
.L5:
movl $3, -4(%rbp)
jmp .L10
.L6:
movl $4, -4(%rbp)
jmp .L10
.L7:
movl $5, -4(%rbp)
jmp .L10
.L2:
movl $6, -4(%rbp)
.L10:
leave
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
mov -20(%rbp), %eax
movq .L8(,%rax,8), %rax (变址寻址: .L8 + rax,8是什么意思??)
jmp
%rax
.section .rodata
.align 8
.align 4
.L8: (映射表)
.quad .L2 (填充0)
.quad .L3
.quad .L4
.quad .L5
.quad .L6
.quad .L7
.text
.L3:
movl $1, -4(%rbp)
jmp .L10
.L4:
movl $2, -4(%rbp)
jmp .L10
.L5:
movl $3, -4(%rbp)
jmp .L10
.L6:
movl $4, -4(%rbp)
jmp .L10
.L7:
movl $5, -4(%rbp)
jmp .L10
.L2:
movl $6, -4(%rbp)
.L10:
leave

情景3:大于等于5个case,大部分不连续,(真充case,构成连续的case)

void switch_case(int data)
{
int ret = 0;
switch(data)
{
case 1:
ret = 1;
break;
case 4:
ret = 2;
break;
case 9:
ret = 3;
break;
case 20:
ret = 4;
break;
case 24:
ret = 5;
break;
default:
ret = 6;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void switch_case(int data)
{
int ret = 0;
switch(data)
{
case 1:
ret = 1;
break;
case 4:
ret = 2;
break;
case 9:
ret = 3;
break;
case 20:
ret = 4;
break;
case 24:
ret = 5;
break;
default:
ret = 6;
}
}

movq .L8(,%rax,8), %rax
jmp %rax
.section .rodata
.align 8
.align 4
.L8:(填充的映射表)
.quad .L2
.quad .L3
.quad .L2
.quad .L2
.quad .L4
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L5
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L6
.quad .L2
.quad .L2
.quad .L2
.quad .L7
.text
.L3:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
movq .L8(,%rax,8), %rax
jmp
%rax
.section .rodata
.align 8
.align 4
.L8:(填充的映射表)
.quad .L2
.quad .L3
.quad .L2
.quad .L2
.quad .L4
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L5
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L2
.quad .L6
.quad .L2
.quad .L2
.quad .L2
.quad .L7
.text
.L3:

情景4:不从0开始的case(相差比较大),会先执行一条减法指令

void switch_case(int data)
{
int ret = 0;
switch(data)
{
case 11:
ret = 1;
break;
case 12:
ret = 2;
break;
case 13:
ret = 3;
break;
case 14:
ret = 4;
break;
case 15:
ret = 5;
break;

default:
  ret = 6;

}
}

movl $0, -4(%rbp)
movl -20(%rbp), %eax
subl $11, %eax (减去11)
cmpl $4, %eax
ja .L2
mov %eax, %eax
movq .L8(,%rax,8), %rax
jmp *%rax
.section .rodata
.align 8
.align 4
.L8:
.quad .L3
.quad .L4
.quad .L5
.quad .L6
.quad .L7
.text

oceanbase中有段这样的代码(压缩整数大小):

int get_int_byte(int64_t int_value)
{
  int ret = 0;
  if( int_value >= -128 && int_value <= 127 )
  {
    ret = 1;
  }
  else if( int_value >= (int16_t)0x8000 && int_value <= (int16_t)0x7FFF )
  {
    ret = 2;
  }
  else if( int_value >= (int32_t)0x80000000 &&
    int_value <= (int32_t)0x7FFFFFFF)
  {
    ret = 4;
  }
  else
  {
    ret = 8;
  }
  return ret;
}


  switch(get_int_byte(int_value))
  {
  case 1:
    cell_meta.type_ = ObCellMeta::TP_INT8;
    break;
  case 2:
    cell_meta.type_ = ObCellMeta::TP_INT16;
    break;
  case 4:
    cell_meta.type_ = ObCellMeta::TP_INT32;
    break;
  case 8:
    cell_meta.type_ = ObCellMeta::TP_INT64;
    break;
  }

如果整数大部分是一个字节就可以放得下的话(int8频度最高),可以这样改


int get_int_byte(int64_t int_value)
{
  int ret = 0;
  if( int_value >= -128 && int_value <= 127 )
  {
    ret = 1;
  }
  else if( int_value >= (int16_t)0x8000 && int_value <= (int16_t)0x7FFF )
  {
    ret = 0;
  }
  else if( int_value >= (int32_t)0x80000000 &&
    int_value <= (int32_t)0x7FFFFFFF)
  {
    ret = 2;
  }
  else
  {
    ret = 3;
  }
  return ret;
}

 switch(get_int_byte(int_value))
  {
  case 0:
    cell_meta.type_ = ObCellMeta::TP_INT16;
    break;
  case 1:
    cell_meta.type_ = ObCellMeta::TP_INT8; (INT8 对应1,二分查找,首先被找到)
    break;
  case 2:
    cell_meta.type_ = ObCellMeta::TP_INT32;
    break;
  case 3:
    cell_meta.type_ = ObCellMeta::TP_INT64;
    break;
  }

Comments

2012-06-21