241 votos

¿Es ' del interruptor ' más rápido que ' si '?

Es una switch instrucción en realidad más rápido que un if afirmación?

Me encontré el siguiente código en Visual Studio 2010 x64 compilador de C++ con la /Ox bandera:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 29)
size_t counter = 0;

size_t testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        switch (counter % 4 + 1)
        {
            case 1: counter += 4; break;
            case 2: counter += 3; break;
            case 3: counter += 2; break;
            case 4: counter += 1; break;
        }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

size_t testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = counter % 4 + 1;
        if (c == 1) { counter += 4; }
        else if (c == 2) { counter += 3; }
        else if (c == 3) { counter += 2; }
        else if (c == 4) { counter += 1; }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    printf("Starting...\n");
    printf("Switch statement: %u ms\n", testSwitch());
    printf("If     statement: %u ms\n", testIf());
}

y se obtuvieron los siguientes resultados:

Instrucción Switch: 5261 de ms
Si la instrucción: 5196 ms

De lo que he aprendido, switch declaraciones aparentemente uso saltar tablas para optimizar la ramificación.

Preguntas:

  1. ¿Qué sería de un básico de salto de la tabla de aspecto, en x86 o x64?

  2. Es este código mediante el uso de un salto de la tabla?

  3. ¿Por qué no hay diferencia de rendimiento en este ejemplo? ¿Hay alguna situación en la que existe es una diferencia considerable del rendimiento?


Desmontaje del código:

testIf:

13FE81B10 sub  rsp,48h 
13FE81B14 call qword ptr [__imp_clock (13FE81128h)] 
13FE81B1A mov  dword ptr [start],eax 
13FE81B1E mov  qword ptr [i],0 
13FE81B27 jmp  testIf+26h (13FE81B36h) 
13FE81B29 mov  rax,qword ptr [i] 
13FE81B2E inc  rax  
13FE81B31 mov  qword ptr [i],rax 
13FE81B36 cmp  qword ptr [i],20000000h 
13FE81B3F jae  testIf+0C3h (13FE81BD3h) 
13FE81B45 xor  edx,edx 
13FE81B47 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B4E mov  ecx,4 
13FE81B53 div  rax,rcx 
13FE81B56 mov  rax,rdx 
13FE81B59 inc  rax  
13FE81B5C mov  qword ptr [c],rax 
13FE81B61 cmp  qword ptr [c],1 
13FE81B67 jne  testIf+6Dh (13FE81B7Dh) 
13FE81B69 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B70 add  rax,4 
13FE81B74 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B7B jmp  testIf+0BEh (13FE81BCEh) 
13FE81B7D cmp  qword ptr [c],2 
13FE81B83 jne  testIf+89h (13FE81B99h) 
13FE81B85 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B8C add  rax,3 
13FE81B90 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B97 jmp  testIf+0BEh (13FE81BCEh) 
13FE81B99 cmp  qword ptr [c],3 
13FE81B9F jne  testIf+0A5h (13FE81BB5h) 
13FE81BA1 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BA8 add  rax,2 
13FE81BAC mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BB3 jmp  testIf+0BEh (13FE81BCEh) 
13FE81BB5 cmp  qword ptr [c],4 
13FE81BBB jne  testIf+0BEh (13FE81BCEh) 
13FE81BBD mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BC4 inc  rax  
13FE81BC7 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BCE jmp  testIf+19h (13FE81B29h) 
13FE81BD3 call qword ptr [__imp_clock (13FE81128h)] 
13FE81BD9 sub  eax,dword ptr [start] 
13FE81BDD imul eax,eax,3E8h 
13FE81BE3 cdq       
13FE81BE4 mov  ecx,3E8h 
13FE81BE9 idiv eax,ecx 
13FE81BEB cdqe      
13FE81BED add  rsp,48h 
13FE81BF1 ret       

testSwitch:

13FE81C00 sub  rsp,48h 
13FE81C04 call qword ptr [__imp_clock (13FE81128h)] 
13FE81C0A mov  dword ptr [start],eax 
13FE81C0E mov  qword ptr [i],0 
13FE81C17 jmp  testSwitch+26h (13FE81C26h) 
13FE81C19 mov  rax,qword ptr [i] 
13FE81C1E inc  rax  
13FE81C21 mov  qword ptr [i],rax 
13FE81C26 cmp  qword ptr [i],20000000h 
13FE81C2F jae  testSwitch+0C5h (13FE81CC5h) 
13FE81C35 xor  edx,edx 
13FE81C37 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C3E mov  ecx,4 
13FE81C43 div  rax,rcx 
13FE81C46 mov  rax,rdx 
13FE81C49 inc  rax  
13FE81C4C mov  qword ptr [rsp+30h],rax 
13FE81C51 cmp  qword ptr [rsp+30h],1 
13FE81C57 je   testSwitch+73h (13FE81C73h) 
13FE81C59 cmp  qword ptr [rsp+30h],2 
13FE81C5F je   testSwitch+87h (13FE81C87h) 
13FE81C61 cmp  qword ptr [rsp+30h],3 
13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
13FE81C69 cmp  qword ptr [rsp+30h],4 
13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
13FE81C71 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C73 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C7A add  rax,4 
13FE81C7E mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C85 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C87 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C8E add  rax,3 
13FE81C92 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C99 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C9B mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CA2 add  rax,2 
13FE81CA6 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CAD jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81CAF mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CB6 inc  rax  
13FE81CB9 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CC0 jmp  testSwitch+19h (13FE81C19h) 
13FE81CC5 call qword ptr [__imp_clock (13FE81128h)] 
13FE81CCB sub  eax,dword ptr [start] 
13FE81CCF imul eax,eax,3E8h 
13FE81CD5 cdq       
13FE81CD6 mov  ecx,3E8h 
13FE81CDB idiv eax,ecx 
13FE81CDD cdqe      
13FE81CDF add  rsp,48h 
13FE81CE3 ret       

Actualización:

Resultados interesantes aquí y aquí. No sé por qué uno es más rápido y uno es más lento, sin embargo.

122voto

Billy ONeal Puntos 50631

Hay varias optimizaciones del compilador puede hacer en un interruptor. No creo que la tantas veces mencionada "salto de la mesa" es muy útil, aunque, como esto sólo funciona cuando la entrada puede ser delimitado de alguna manera.

C Pseudocódigo de un "salto de la tabla" sería algo como esto -- tenga en cuenta que el compilador en la práctica sería necesario insertar alguna forma de si la prueba alrededor de la mesa para asegurarse de que la entrada era válido en la tabla. Tenga en cuenta también que sólo funciona en el caso específico de que la entrada es una carrera de números consecutivos.

Por otra parte, en las modernas Cpu, la caché de la localidad de costo de almacenar el salto de la tabla de frecuencia puede ser mayor que la elide SI las pruebas.

Si el número de sucursales en un switch es muy grande, un compilador puede hacer cosas como utilizar una búsqueda binaria en los valores del interruptor, lo cual (en mi mente) sería mucho más útil de optimización, como lo hace aumentar significativamente el rendimiento en algunos escenarios, es tan general como un interruptor, y no resulta en un mayor tamaño del código generado. Pero a ver que, el código de prueba se necesitaría MUCHO más ramas para ver la diferencia.

Para responder a sus preguntas específicas:

  1. No sé ensamblador x86, lo siento. :(
  2. Puedo decir que no es el uso de un salto de la tabla -- 4 comparación instrucciones son claramente visibles:

    13FE81C51 cmp  qword ptr [rsp+30h],1 
    13FE81C57 je   testSwitch+73h (13FE81C73h) 
    13FE81C59 cmp  qword ptr [rsp+30h],2 
    13FE81C5F je   testSwitch+87h (13FE81C87h) 
    13FE81C61 cmp  qword ptr [rsp+30h],3 
    13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
    13FE81C69 cmp  qword ptr [rsp+30h],4 
    13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
    

    Un salto de mesa basado en la solución no hace uso de la comparación.

  3. No es suficiente ramas para hacer que el compilador para generar un salto de la mesa, o el compilador simplemente no las genera. No estoy seguro de qué.

EDICIÓN de 2014: se ha discutido en otras partes de las personas familiarizadas con el LLVM optimizador de decir que el salto de la tabla de optimización puede ser importante en muchos escenarios; por ejemplo, en los casos donde hay una enumeración con muchos valores y en muchos casos en contra de los valores en dicha enumeración. Dicho esto, me quedo con lo que he dicho anteriormente, en 2011, muy a menudo, veo a la gente pensar que "si me hacen un interruptor, que va a ser el mismo independientemente de la cantidad de casos que tengo", y eso es completamente falso. Incluso con un salto de la tabla de obtener la indirecta saltar costo y pago de las entradas en la tabla para cada caso; y el ancho de banda de memoria es un Gran problema en hardware moderno.

Escribir el código para mejorar la legibilidad. Cualquier compilador que se precie va a ver un if / else if escalera y se transforma en su equivalente interruptor o viceversa, si sería más rápido para hacerlo.

47voto

Int3 ὰ Puntos 4254

A tu pregunta:

1. ¿qué sería de un básico de salto de la tabla de aspecto, en x86 o x64?

Saltar tabla es la dirección de memoria que contiene el puntero de las etiquetas en algo así como la matriz de estructura. siguiente ejemplo te ayudará a entender cómo saltar la apariencia de la tabla

00B14538  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00  Ø.«.Ø.«.Ø.«.Ø.«.
00B14548  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00  Ø.«.Ø.«.Ø.«.....
00B14558  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00B14568  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

Donde 00B14538 es el puntero al Saltar de la tabla , y el valor como D8 09 AB 00 representa la etiqueta de puntero.

2. este código mediante el uso de un salto de la tabla? No en este caso.

3. por qué no hay diferencia de rendimiento en este ejemplo?

No hay ninguna diferencia de rendimiento debido a que la instrucción para ambos caso se ve mismo, no saltar a la mesa.

4. ¿hay alguna situación en la que existe una significativa diferencia de rendimiento?

Si usted tiene muy larga declaración de si el cheque, en ese caso el uso de saltar tabla reduce el impacto en el rendimiento, sino que viene con el costo de la memoria.

Lema: el Compilador es lo suficientemente inteligente como manejar tal caso :)

31voto

Soren Puntos 6090

El compilador es libre para compilar la instrucción switch como un código que es equivalente a si la instrucción, o para crear un salto de la tabla. Es probable que eligió uno sobre el otro en función de lo que se va a ejecutar más rápido o generar el código más pequeño con un poco dependiendo de lo que usted ha especificado en que las opciones del compilador -- lo peor de los casos será la misma velocidad como si-declaraciones

Yo confiaría en que el compilador para hacer la mejor elección y concentrarse en lo que hace el código más legible.

Si el número de casos se hace muy grande de un salto de la tabla será mucho más rápido que una serie de si. Sin embargo, si los pasos entre los valores es muy grande, el salto de la tabla puede llegar a ser grande, y el compilador puede optar por no generar uno.

13voto

BobTurbo Puntos 228

¿Cómo usted sabe que su equipo no estaba realizando una tarea ajena a la prueba durante la prueba de interruptor de bucle y realizar menos tareas durante el caso de que la prueba de bucle? Los resultados de la prueba no muestra nada como:

  1. la diferencia es muy pequeña
  2. sólo hay un resultado, no una serie de resultados
  3. hay muy pocos casos

Mis resultados:

Yo addded:

printf("counter: %u\n", counter);

a la final, por lo que no sería el de optimizar la distancia del bucle como contador nunca fue utilizado en su ejemplo, así que ¿por qué el compilador de realizar el bucle? De inmediato, el cambio fue siempre ganar incluso con un micro de referencia.

El otro problema con su código es:

switch (counter % 4 + 1)

en su interruptor de bucle, frente a

const size_t c = counter % 4 + 1; 

en el caso de bucle. Diferencia muy grande si usted arreglar eso. Creo que poner la instrucción dentro de la instrucción switch provoca el compilador en el envío del valor directamente en los registros de la CPU en lugar de ponerlo en la pila primero. Este es, por tanto, en favor de la instrucción switch y no equilibrada de la prueba.

Ah, y creo que usted también debe restablecer el contador de entre las pruebas. De hecho, usted probablemente debería ser el uso de algún tipo de número aleatorio en lugar de +1, +2, +3, etc, ya que probablemente optimizar algo allí. Por número aleatorio, me refiero a un número basado en la hora actual, por ejemplo. De lo contrario, el compilador podría girar a ambos de sus funciones en una larga operación matemática y no molestarse con cualquiera de los bucles.

He modificado Ryan, el código sólo lo suficiente para asegurarse de que el compilador no podía entender las cosas antes de que el código se había quedado:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 26)
size_t counter = 0;

long long testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;

        switch (c)
        {
                case 1: counter += 20; break;
                case 2: counter += 33; break;
                case 3: counter += 62; break;
                case 4: counter += 15; break;
                case 5: counter += 416; break;
                case 6: counter += 3545; break;
                case 7: counter += 23; break;
                case 8: counter += 81; break;
                case 9: counter += 256; break;
                case 10: counter += 15865; break;
                case 11: counter += 3234; break;
                case 12: counter += 22345; break;
                case 13: counter += 1242; break;
                case 14: counter += 12341; break;
                case 15: counter += 41; break;
                case 16: counter += 34321; break;
                case 17: counter += 232; break;
                case 18: counter += 144231; break;
                case 19: counter += 32; break;
                case 20: counter += 1231; break;
        }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

long long testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;
        if (c == 1) { counter += 20; }
        else if (c == 2) { counter += 33; }
        else if (c == 3) { counter += 62; }
        else if (c == 4) { counter += 15; }
        else if (c == 5) { counter += 416; }
        else if (c == 6) { counter += 3545; }
        else if (c == 7) { counter += 23; }
        else if (c == 8) { counter += 81; }
        else if (c == 9) { counter += 256; }
        else if (c == 10) { counter += 15865; }
        else if (c == 11) { counter += 3234; }
        else if (c == 12) { counter += 22345; }
        else if (c == 13) { counter += 1242; }
        else if (c == 14) { counter += 12341; }
        else if (c == 15) { counter += 41; }
        else if (c == 16) { counter += 34321; }
        else if (c == 17) { counter += 232; }
        else if (c == 18) { counter += 144231; }
        else if (c == 19) { counter += 32; }
        else if (c == 20) { counter += 1231; }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    srand(time(NULL));
    printf("Starting...\n");
    printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
    printf("counter: %d\n", counter);
    counter = 0;
    srand(time(NULL));
    printf("If     statement: %lld ms\n", testIf()); fflush(stdout);
    printf("counter: %d\n", counter);
} 

conmutador: 3740
si: 3980

(resultados similares a través de varios intentos)

También he reducido el número de casos/ifs 5 y la función de interruptor aún así ganó.

5voto

Bill Forster Puntos 3298

Voy a responder 2) y hacer algunos comentarios generales. 2) No, No se puede saltar de mesa en la asamblea código que has publicado. Un salto de la tabla es una tabla de salto destinos, y uno o dos instrucciones para saltar directamente a un indexadas ubicación de la tabla. Un salto de la tabla tendría más sentido cuando hay muchas posibilidades de cambiar los destinos. Tal vez el optimizador sabe que simple, si más lógica es más rápido, a menos que el número de destinos es mayor que un cierto umbral. Intente su ejemplo de nuevo con decir 20 posibilidades en lugar de 4.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X