All geek questions in one place

Better switch or const table? (built-in SW)

I wonder if, when possible, is a switch or const table more efficient?

For example, what would be better:

switch(input) {
  case 0: value = VALUE_0;
    break;
  case 1: value = VALUE_1;
    break;
  case 2: value = VALUE_2;
    break;
  case 3: value = VALUE_3;
    break;
  case 4: value = VALUE_4;
    break;
  case 5: value = VALUE_5;
    break;
  case 6: value = VALUE_6;
    break;
  default:    
    break;
}

Or something like this:

const uint8_t INPUT_TO_VALUE_TABLE[N_VALUE] = {
    VALUE_0,
    VALUE_1,
    VALUE_2,
    VALUE_3,
    VALUE_4,
    VALUE_5,
    VALUE_6,
}
...
...
value = INPUT_TO_VALUE_TABLE[input];

I showed a dummy example, but I also have code for using a switch that calls different functions or function pointer tables.

The code is for 8-bit micro (I don’t know if it matters for this topic).

+4
source share
6 answers

Well, you should consider disassembling the compiled code to see what is actually being created, but I expect in the second case you will get less code, and there will be less branching.

( switch). - . , :

value = ( input < 6 ) ? INPUT_TO_VALUE_TABLE[input] : default_value;

. gcc -S, 4.6.3, , , . , ; , , .

switch:

switch:

void switch_input( int input ) {
  switch(input) {
  case 0: value = VALUE_0;
    break;
  case 1: value = VALUE_1;
    break;
  case 2: value = VALUE_2;
    break;
  case 3: value = VALUE_3;
    break;
  case 4: value = VALUE_4;
    break;
  case 5: value = VALUE_5;
    break;
  case 6: value = VALUE_6;
    break;
  default: value = VALUE_DEFAULT;
    break;
  }
}

, input , switch.

switch_input:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    cmpl    $6, -4(%rbp)
    ja  .L2
    movl    -4(%rbp), %eax
    movq    .L10(,%rax,8), %rax
    jmp *%rax
    .section    .rodata
    .align 8
    .align 4
.L10:
    .quad   .L3
    .quad   .L4
    .quad   .L5
    .quad   .L6
    .quad   .L7
    .quad   .L8
    .quad   .L9
    .text
.L3:
    movl    $0, value(%rip)
    jmp .L1
.L4:
    movl    $1, value(%rip)
    jmp .L1
.L5:
    movl    $2, value(%rip)
    jmp .L1
.L6:
    movl    $3, value(%rip)
    jmp .L1
.L7:
    movl    $4, value(%rip)
    jmp .L1
.L8:
    movl    $5, value(%rip)
    jmp .L1
.L9:
    movl    $6, value(%rip)
    jmp .L1
.L2:
    movl    $-1, value(%rip)
    nop
.L1:
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

, , , . ; , .

void index_input( int input ) {
  value = ( input < N_VALUE ) ? INPUT_TO_VALUE_TABLE[input] : VALUE_DEFAULT;
}

(, , , .)

index_input:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    cmpl    $5, -4(%rbp)
    jg  .L13
    movl    -4(%rbp), %eax
    cltq
    movl    INPUT_TO_VALUE_TABLE(,%rax,4), %eax
    jmp .L14
.L13:
    movl    $-1, %eax
.L14:
    movl    %eax, value(%rip)
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

C (example.c)

int value;

#define N_VALUE 7

#define VALUE_0 0
#define VALUE_1 1
#define VALUE_2 2
#define VALUE_3 3
#define VALUE_4 4
#define VALUE_5 5
#define VALUE_6 6
#define VALUE_DEFAULT -1

void switch_input( int input ) {
  switch(input) {
  case 0: value = VALUE_0;
    break;
  case 1: value = VALUE_1;
    break;
  case 2: value = VALUE_2;
    break;
  case 3: value = VALUE_3;
    break;
  case 4: value = VALUE_4;
    break;
  case 5: value = VALUE_5;
    break;
  case 6: value = VALUE_6;
    break;
  default: value = VALUE_DEFAULT;
    break;
  }
}

const int INPUT_TO_VALUE_TABLE[N_VALUE] = {
  VALUE_0,
  VALUE_1,
  VALUE_2,
  VALUE_3,
  VALUE_4,
  VALUE_5,
  VALUE_6
};

void index_input( int input ) {
  value = ( input < 6 ) ? INPUT_TO_VALUE_TABLE[input] : VALUE_DEFAULT;
}

(example.s)

gcc -S.

    .file   "example.c"
    .comm   value,4,4
    .text
    .globl  switch_input
    .type   switch_input, @function
switch_input:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    cmpl    $6, -4(%rbp)
    ja  .L2
    movl    -4(%rbp), %eax
    movq    .L10(,%rax,8), %rax
    jmp *%rax
    .section    .rodata
    .align 8
    .align 4
.L10:
    .quad   .L3
    .quad   .L4
    .quad   .L5
    .quad   .L6
    .quad   .L7
    .quad   .L8
    .quad   .L9
    .text
.L3:
    movl    $0, value(%rip)
    jmp .L1
.L4:
    movl    $1, value(%rip)
    jmp .L1
.L5:
    movl    $2, value(%rip)
    jmp .L1
.L6:
    movl    $3, value(%rip)
    jmp .L1
.L7:
    movl    $4, value(%rip)
    jmp .L1
.L8:
    movl    $5, value(%rip)
    jmp .L1
.L9:
    movl    $6, value(%rip)
    jmp .L1
.L2:
    movl    $-1, value(%rip)
    nop
.L1:
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   switch_input, .-switch_input
    .globl  INPUT_TO_VALUE_TABLE
    .section    .rodata
    .align 16
    .type   INPUT_TO_VALUE_TABLE, @object
    .size   INPUT_TO_VALUE_TABLE, 28
INPUT_TO_VALUE_TABLE:
    .long   0
    .long   1
    .long   2
    .long   3
    .long   4
    .long   5
    .long   6
    .text
    .globl  index_input
    .type   index_input, @function
index_input:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    cmpl    $5, -4(%rbp)
    jg  .L13
    movl    -4(%rbp), %eax
    cltq
    movl    INPUT_TO_VALUE_TABLE(,%rax,4), %eax
    jmp .L14
.L13:
    movl    $-1, %eax
.L14:
    movl    %eax, value(%rip)
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE1:
    .size   index_input, .-index_input
    .ident  "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
    .section    .note.GNU-stack,"",@progbits
+6

, , - , . , , , .

, case, . , ​​ .

8- , . , 8- MCU ( ).

+2

, . , input 0 6, :

if (input >= 0 && input < 7) {
    value = INPUT_TO_VALUE_TABLE[input];
}

, .

+1

. , -, .

0

, , CPU (CPE) . , .

0

, . 0, , if :

if ((unsigned)input <= 6) {
   value = INPUT_TO_VALUE_TABLE[input];
}

(since negative values ​​are inputconsidered here as large positive values)

If you do not need a guard, this is most likely the fastest table. If you need it ... it depends.

On some hardware, this trick for checking range with one if(instead of 2) is also useful:

value = (unsigned)(input - min) <= max - min ? table[input] : default_value;

(obviously faster if max and min are constants, or at least max - mincan be pre-calculated)

0
source

Source: https://habr.com/ru/post/1525611/

More articles:


All Articles