En este artículo pretendo explicar el motivo por el cual un switch es mucho más rápido que su homólogo en secuencias if-then-else, para ello analizaremos la implementación del switch.

Índice

Introducción

El switch se basa en una implementación muy eficiente llamada en inglés jump table o tabla de saltos. Esta tabla es un array, donde la entrada i es la dirección de un segmento de código que implementa la acción que el switch debería ejecutar cuando la condición es igual a i. El código realiza una referencia al array dentro de la tabla de saltos usando el índice del switch y determinar así el destino para una instrucción de salto (instrucción jmp en ensamblador).



Esa es la clave que explica el mayor rendimiento de un switch frente a una larga secuencia de if-then-else. Ya que el tiempo necesario para realizar el switch es independiente del número de casos (sentencia case:) que éste tiene.

GCC selecciona qué metodo de traducción aplica al switch dependiendo del número de casos y valores. Las tablas de saltos se usan cuando hay un número determinado de casos (cuatro por ejemplo) y abarcan un número pequeño de valores. Por ejemplo:

Sentencia switch

int switch_eg(int x, int n){
   int result = x;
 
   switch (n) {
 
      case 100:
         result *= 13;
         break;
 
      case 102:
         result += 10;
         /*Fall through*/
 
      case 103:
         result += 11;
         break;
 
      case 104:
      case 106:
         result *= result;
         break;
 
      default:
         result = 0;
   }
 
   return result;
}

Traducción a extended C

int switch_eg_impl(int x, int n) {
   /*Tabla de punteros a código*/
   static void *jt[7] = {
      &&loc;_A, &&loc;_def, &&loc;_B,
      &&loc;_C, &&loc;_D, &&loc;_def,
      &&loc;_D
   };

   unsigned index = n - 100;
   int result;

   if (index > 6)
     goto loc_def;

   /*Rama multidireccional*/
   goto *jt[index];

   loc_def:   /*Default case*/
      result = 0;
      goto done;
   
   loc_C:     /*Case 103*/
      result = x;
      goto rest;
   
   loc_A:     /*Case 100*/
      result = x * 13;
      goto done;
   
   loc_B:     /*Case 102*/
      result = x + 10;
      /*Fall through*/
   
   rest:      /*Finalizar case 103*/
      result += 11;
      goto done;
   
   loc_D:     /*Case 104, 106*/
      result = x * x;
      /*Fall through*/
   
   done:
      return result;
   }

La traducción a extended C muestra la estructura de una tabla de saltos (jt) y cómo se accede a ella.

En este ejemplo, los cases del switch no son contiguos, no existen casos para los valores 101 y 105, y hay casos con varias etiquetas (104 y 106), también hay casos denominados fall through (cases sin sentencia break).

El código ensamblador generado es muy parecido a la versión extended C:

.file   "sw.c"
    .text
    .globl  switch_eg
    .type   switch_eg, @function
switch_eg:
    .LFB0:
    .cfi_startproc
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register 5
    subl    $16, %esp
    movl    8(%ebp), %eax
    movl    %eax, -4(%ebp)
    movl    12(%ebp), %eax
    subl    $100, %eax
    cmpl    $6, %eax
    ja  .L2
    movl    .L7(,%eax,4), %eax
    jmp *%eax
.section    .rodata
    .align 4
    .align 4
.L7:
    .long   .L3
    .long   .L2
    .long   .L4
    .long   .L5
    .long   .L6
    .long   .L2
    .long   .L6
.text
.L3:
    movl    -4(%ebp), %edx
    movl    %edx, %eax
    addl    %eax, %eax
    addl    %edx, %eax
    sall    $2, %eax
    addl    %edx, %eax
    movl    %eax, -4(%ebp)
    jmp .L8
.L4:
    addl    $10, -4(%ebp)
.L5:
    addl    $11, -4(%ebp)
    jmp .L8
.L6:
    movl    -4(%ebp), %eax
    imull   -4(%ebp), %eax
    movl    %eax, -4(%ebp)
    jmp .L8
.L2:
    movl    $0, -4(%ebp)
.L8:
    movl    -4(%ebp), %eax
    leave
    .cfi_restore 5
    .cfi_def_cfa 4, 4
    ret
    .cfi_endproc

Una vez que disponemos del ejemplo representado de 3 formas distintas, profundicemos en el funcionamiento.

En la versión extendida de C se define el array jt que contiene siete entradas, cada una es la dirección de un bloque de código. Dichos bloques de código se definen con etiquetas en el código (loc_A, loc_def etc) e identificadas en el array jt por punteros a código. Para conseguir un puntero a un trozo de código hay que anteponer && a la etiqueta. El operador & crea un puntero para el valor de un dato. Cuando se creó esta extensión de C, los autores crearon el operador && para hacer referencia a la dirección de una porción de código.

El código C tiene cases para los valores 100, 102-104 y 106, pero la variable n puede contener cualquier valor entero. El compilador desplaza el rango a los valores 0-6, restando 100 a n. Creando así una nueva variable que llamaremos index en la versión C del código. Al hacer este desplazamiento facilita las posibilidades de ramificación tratando a index como un valor sin signo (unsigned). Así, se sabrá fácilmente que index está fuera del rango 0-6 cuando sea mayor que 6. Tanto en el código C como ensamblador hay cinco posiciones distintas a las que saltar basandose en el valor de index. Las posiciones son:

Cada una de estas etiquetas identifica el trozo de código a ejecutar en función de valor de index. En las versiones ensamblador y C extendido se compara el index con 6, si es mayor se salta al case por defecto.

El paso clave en la ejecución de una sentencia switch es acceder a una posición de código mediante la tabla de saltos, cosa que pasa en la línea 16 del código C extendido con la sentencia goto que referencia a la tabla de saltos jt. En la versión ensamblador, ocurre algo similar en la línea 21. El cálculo de a qué elemento del array jt se accede está en la línea 20 concretamente .L7(,%eax,4). .L7 es la tabla de saltos, si observamos el contenido

.L7:
    .long   .L3 ; eax = 0
    .long   .L2 ; eax = 1
    .long   .L4 ; eax = 2
    .long   .L5 ; eax = 3
    .long   .L6 ; eax = 4
    .long   .L2 ; eax = 5
    .long   .L6 ; eax = 6
    .text

se aprecia que contiene las distintas etiquetas a las que se saltará posteriormente. Con .L7(,%eax,4) se está accediendo al elemento de índice %eax. Es decir se especifica una localización de memoria indexada por el valor del registro %eax (Que contiene el valor de index).

El * de la línea 21 indica que se trata de un salto indirecto.

En la versión C extendida, se declara la tabla de saltos como un array de siete elementos, cada elemento es un puntero a una sección de código. El encargado de seleccionar los elementos del array es index, y su valor oscila entre 0-6. Hay que destacar, que los valores de index van en correspondencia con los posibles valores de n, 100-106.

Echemos un vistazo a la tabla de saltos:

static void *jt[7] = {
      &&loc;_A, &&loc;_def, &&loc;_B,
      &&loc;_C, &&loc;_D, &&loc;_def,
      &&loc;_D
};

Algunos valores están duplicados, por ejemplo loc_D aparece en la posición 4 y 6 del array. Es lógico ya que para los valores 104 y 106 se debe ejecutar la misma porción del código:

case 104:
case 106:
   result *= result;
   break;

En el caso index = 5 o index = 1 (No existe case para 105 o 101), se saltará al trozo de código etiquetado como loc_def, correspondiente al default del switch. Ahora estamos en condiciones de comprender mejor la estructura de la tabla de saltos en código ensamblador:

.section    .rodata
    .align 4        ; Alinea las direcciones a multiplos de 4 (Un entero ocupa 4B)
    .align 4
.L7:
    .long   .L3      ; case 100 : loc_A
    .long   .L2      ; case 101 : loc_def
    .long   .L4      ; case 102 : loc_B
    .long   .L5      ; case 103 : loc_C
    .long   .L6      ; case 104 : lod_D
    .long   .L2      ; case 105 : loc_def
    .long   .L6      ; case 106 : loc_D
.text

Estas declaraciones dicen que dentro de la sección llamada .rodata (Read-Only Data) debería haber una secuencia de siete palabras long (4-byte) cuyo valor se dá por la dirección de la instrucción asociada a la etiqueta (.L3 etc). La etiqueta .L7 marca el inicio de la asignación de la tabla de saltos. La dirección asociada a esta etiqueta sirve como la base para el salto indirecto en la línea 21.
Tanto en la versión extendida de C, como en ensamblador, el código asociado a las etiquetas (loc_* para extended C y .L* para ensamblador) implementan las distintas ramas del switch. La mayoría calculan un valor para devolver en la variable result (o el registro %eax) y saltan al final de la función (en el código ensamblador se salta a la etiqueta .L8).

El patrón seguido para calcular un resultado no se da para los cases 102 y 103 en el código C. La lógica del programa para estos dos casos en las versiones ensamblador y C extendido es tener dos destinos ditintos para ambos casos (loc_C, loc_B y .L5, .L4 *). Los dos bloques de código convergen en el código que incrementa *result en 11 (etiquetado como rest en C extendido y .L5 en ensamblador)

Comprender todo el código visto requiere examinarlo con detenimiento y paso a paso. Aún así, el objetivo de este artículo era demostrar que el uso de tablas de salto o jump tables permite una forma muy eficiente de implementar ramas multidireccionales. En este ejemplo, el programa puede ramificarse a cinco posiciones distintas de un solo salto, incluso si tuvieramos un switch con cientos de cases, sería manejado con un solo acceso a la tabla de saltos.

La versión ensamblador de arriba corresponde a la compilación para procesadores de 32 Bits, a continuación la versión para 64-Bits:

.file   "sw.c"
.text
.globl  switch_eg
.type   switch_eg, @function
switch_eg:
    .LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -20(%rbp)
    movl    %esi, -24(%rbp)
    movl    -20(%rbp), %eax
    movl    %eax, -4(%rbp)
    movl    -24(%rbp), %eax
    subl    $100, %eax
    cmpl    $6, %eax
    ja  .L2
    movl    %eax, %eax
    movq    .L7(,%rax,8), %rax
    jmp *%rax
    .section    .rodata
    .align 8
    .align 4
.L7:
    .quad   .L3
    .quad   .L2
    .quad   .L4
    .quad   .L5
    .quad   .L6
    .quad   .L2
    .quad   .L6
    .text
.L3:
    movl    -4(%rbp), %edx
    movl    %edx, %eax
    addl    %eax, %eax
    addl    %edx, %eax
    sall    $2, %eax
    addl    %edx, %eax
    movl    %eax, -4(%rbp)
    jmp .L8
.L4:
    addl    $10, -4(%rbp)
.L5:
    addl    $11, -4(%rbp)
    jmp .L8
.L6:
    movl    -4(%rbp), %eax
    imull   -4(%rbp), %eax
    movl    %eax, -4(%rbp)
    jmp .L8
.L2:
    movl    $0, -4(%rbp)
.L8:
    movl    -4(%rbp), %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
.cfi_endproc

Tras analizar y entender cómo se implementa el switch, la razón por la que es más rápido que una sucesión de if-then-else es simple. El factor determinante es la existencia de la tabla de saltos y que solo se requiere de una comparación para determinar a qué sentencia case saltar. Mientras que en una secuencia de if-then-else se requiere la comprobación de todas y cada una de las expresiones que comprenden el if, hasta que se satisfaga alguna o se llegue al final del bloque.

Referencias

Computer Systems: A Programmer’s Perspective »» Ver libro en Amazon