performance - que - Rendimiento de Delphi: caso contra si

metodo delphi ppt

Question

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

Supongamos que desea comprobar si una variable entera de 32 bits sin signo "MiAcción" es igual a cualquiera de las constantes ACCIÓN1, ACCIÓN2, ..., ACCIÓNn, donde n es, digamos 1000. Supongo que, además de 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 la variante if toma tiempo O (n) para completarse (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 en lo cierto de que el cambio es mucho más rápido?
2. ¿Tengo razón en que el tiempo requerido para encontrar la acción correcta en el caso del interruptor 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 esto exactamente?

Answer 1

1. Sí, el interruptor es O (1) mientras que las cascadas if son O (n)
2. Sí, ver (1)
3. Con una mesa auxiliar

Answer 2

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

1. Tabla de dos niveles, utilizando una tabla para asignar el valor a un índice y usando el índice para seleccionar una dirección de una tabla de salto
2. Salto indirecto a través de la mesa
3. Saltos secuenciales
4. Búsqueda binaria: esto es recursivo, por lo que las hojas de la búsqueda binaria pueden usar cualquiera de 2, 3 o 4.

Utiliza heurísticas como el número de casos, el rango de casos, el número de alternativas distintas (cada alternativa puede implementar un rango de valores diferentes), etc.

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

Answer 3

Siempre es bueno verificar la realidad primero ...

Al compilador de Delphi 2010 parece gustarle mucho probar y ramificar. 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.

El 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

Incluso los casos más complicados se compilarán 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.

... está compilado 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 de este código es que las tablas de salto no funcionan muy bien con las cachés L1 y, debido a esa versión de prueba y salto, pueden ser más rápidas si no hay una gran cantidad de etiquetas de casos presentes.

Una "prueba" para ese razonamiento es el siguiente programa que sí se traduce en una tabla de saltos.

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

Tenga en cuenta que si 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.