Rendimiento de Delphi: Caso Versus Si

Question

Supongo que podría haber cierta superposición con las anteriores preguntas de SO, pero no pude encontrar una pregunta específica de Delphi sobre este tema.

Supongamos que quiere comprobar si una variable entera de 32 bits sin signo "MiAcción" es igual a cualquiera de las constantes ACTION1, ACTION2, ..., ACTIONn, donde n es - por ejemplo 1000. Supongo que, además de al ser más elegante,

case MyAction of 
    ACTION1: {code}; 
    ACTION2: {code}; 
    ... 
    ACTIONn: {code}; 
end; 

es mucho más rápido que

if MyAction = ACTION1 then 
    // code 
else if MyAction = ACTION2 then 
    // code 
... 
else if MyAction = ACTIONn then 
    // code; 

supongo que el caso de la variante toma O (n) para completar (es decir, para encontrar la acción correcta) si la acción correcta ACTIONi tiene un valor alto de i, mientras que la variante de caso tarda mucho menos tiempo (O (1)?).

1. ¿Estoy correcto que el cambio sea mucho más rápido?
2. ¿Es correcto que el tiempo requerido para encontrar la acción correcta en la caja del conmutador en realidad es independiente de n? Es decir. ¿Es cierto que realmente no demora más verificar un millón de casos que verificar 10 casos?
3. ¿Cómo funciona exactamente?

Answer 1

1. Si el interruptor es O (1) mientras que la cascada si de O (n)
2. Sí, véase (1)
3. Con un branch table

Answer 2

Tenga en cuenta que si el el valor de MyAction es ponderado, se puede obtener un buen rendimiento con la cascada if..else, donde coloca los casos más probables cerca de la parte superior. No estoy diciendo que compita con la declaración caso/cambio en términos de rendimiento cuando se trata de enteros. Pero si un caso no es adecuado (supongamos que tiene cadenas, por ejemplo), coloque sus pruebas de alto porcentaje en la parte superior.

Answer 3

Siempre es bueno comprobar la realidad primera ...

Delphi 2010 compilador parece que le gusta probar y rama mucho. Por ejemplo, el siguiente código simple no se compila en una tabla de sucursal.

var 
    c: (aaa, bbb, ccc); 

begin 
    case c of 
    aaa: sleep(0); 
    bbb: sleep(0); 
    ccc: sleep(0); 
    end; 
end. 

compilador generará el siguiente código:

Project56.dpr.24: case c of 
0040A1C4 0FB6053C0E4100 movzx eax,[$00410e3c] 
0040A1CB 2C01    sub al,$01 
0040A1CD 7208    jb $0040a1d7 
0040A1CF 740F    jz $0040a1e0 
0040A1D1 FEC8    dec al 
0040A1D3 7414    jz $0040a1e9 
0040A1D5 EB19    jmp $0040a1f0 
Project56.dpr.25: aaa: sleep(0); 
0040A1D7 6A00    push $00 
0040A1D9 E86EDAFFFF  call Sleep 
0040A1DE EB10    jmp $0040a1f0 
Project56.dpr.26: bbb: sleep(0); 
0040A1E0 6A00    push $00 
0040A1E2 E865DAFFFF  call Sleep 
0040A1E7 EB07    jmp $0040a1f0 
Project56.dpr.27: ccc: sleep(0); 
0040A1E9 6A00    push $00 
0040A1EB E85CDAFFFF  call Sleep 

aún más complicado casos conseguirán compilado en una serie de prueba y salto. Por ejemplo ...

var 
    c: (aaa, bbb, ccc, eee, fff, ggg, hhh); 

begin 
    case c of 
    aaa: sleep(0); 
    bbb: sleep(0); 
    ccc: sleep(0); 
    hhh: sleep(0); 
    end; 
end. 

... se compila en ...

Project56.dpr.24: case c of 
0040A1C4 0FB6053C0E4100 movzx eax,[$00410e3c] 
0040A1CB 2C01    sub al,$01 
0040A1CD 720C    jb $0040a1db 
0040A1CF 7413    jz $0040a1e4 
0040A1D1 FEC8    dec al 
0040A1D3 7418    jz $0040a1ed 
0040A1D5 2C04    sub al,$04 
0040A1D7 741D    jz $0040a1f6 
0040A1D9 EB22    jmp $0040a1fd 
Project56.dpr.25: aaa: sleep(0); 
0040A1DB 6A00    push $00 
0040A1DD E86ADAFFFF  call Sleep 
0040A1E2 EB19    jmp $0040a1fd 
Project56.dpr.26: bbb: sleep(0); 
0040A1E4 6A00    push $00 
0040A1E6 E861DAFFFF  call Sleep 
0040A1EB EB10    jmp $0040a1fd 
Project56.dpr.27: ccc: sleep(0); 
0040A1ED 6A00    push $00 
0040A1EF E858DAFFFF  call Sleep 
0040A1F4 EB07    jmp $0040a1fd 
Project56.dpr.28: hhh: sleep(0); 
0040A1F6 6A00    push $00 
0040A1F8 E84FDAFFFF  call Sleep 

La causa más probable motivo de dicho código es que las tablas de salto no juegan muy bien con cachés L1 y debido a que la versión de prueba y salto puede ser más rápida si no hay una gran cantidad de etiquetas de casos presentes.

Una "prueba" para ese razonamiento es el siguiente programa que hace se traduce en una tabla de salto.

var 
    b: byte; 

begin 
    case b of 
    0: sleep(0); 
    1: sleep(0); 
    2: sleep(0); 
    3: sleep(0); 
    4: sleep(0); 
    5: sleep(0); 
    6: sleep(0); 
    7: sleep(0); 
    8: sleep(0); 
    9: sleep(0); 
    10: sleep(0); 
    11: sleep(0); 
    12: sleep(0); 
    13: sleep(0); 
    14: sleep(0); 
    15: sleep(0); 
    16: sleep(0); 
    17: sleep(0); 
    18: sleep(0); 
    19: sleep(0); 
    20: sleep(0); 
    end; 
end. 

Project56.dpr.12: case b of 
0040A178 0FB6C0   movzx eax,al 
0040A17B 83F814   cmp eax,$14 
0040A17E 0F8728010000  jnbe $0040a2ac 
0040A184 FF24858BA14000 jmp dword ptr [eax*4+$40a18b] 
... 
Project56.dpr.14: 1: sleep(0); 
0040A1EB 6A00    push $00 
0040A1ED E85ADAFFFF  call Sleep 
0040A1F2 E9B5000000  jmp $0040a2ac 
Project56.dpr.15: 2: sleep(0); 
0040A1F7 6A00    push $00 
0040A1F9 E84EDAFFFF  call Sleep 
0040A1FE E9A9000000  jmp $0040a2ac 
Project56.dpr.16: 3: sleep(0); 
0040A203 6A00    push $00 
0040A205 E842DAFFFF  call Sleep 
0040A20A E99D000000  jmp $0040a2ac 
... 

Barry podría darnos una respuesta definitiva a esa pregunta. Solo estoy probando y divagando.

Answer 4

El compilador se traducirá una declaración de caso en una de:

1. tabla de dos niveles, utilizando una tabla para correlacionar el valor de un índice, y utilizando el índice para seleccionar una dirección de una tabla de saltos
2. salto indirecta a través de la mesa
3. secuencial salta
4. la búsqueda binaria - esto es recursivo, por lo que las hojas de la búsqueda binaria puede utilizar cualquiera de 2, 3 o 4.

Se utiliza heurísticas, tales como el número de casos, el rango de los casos, el número de alternativas distintas (cada alternativa puede implementar una gama de diferentes valores), etc.

La intuición para la declaración de caso es que es una operación O(1).