¿La optimización del interruptor para muchos casos garantiza el mismo tiempo de acceso para cualquier caso? (C++)

He visto respuestas aquí para idiomas específicos, sobre switches con más de 5 casos optimizados con tablas de salto para garantizar un tiempo de acceso constante para cualquier caso.
¿Eso es así para C/C++?
¿Es en particular para gcc? para el estudio visual?
En caso negativo, ¿ordenaría los casos por orden de frecuencia de ocurrencia ayuda?¿La optimización del interruptor para muchos casos garantiza el mismo tiempo de acceso para cualquier caso? (C++)

Fuente

2010-01-25 Petruza

Parece que haría que C fuera un "asesino a sueldo" si pudieran optimizar una declaración de conmutación bastante bien ... –

Estaría * muy * sorprendido si el hash fuera más rápido para 6 casos. Tal vez para 25. Claro, una tabla hash probablemente reducirá la varianza en el tiempo de acceso, pero lo hace al agregar una sobrecarga fija. – MSalters

Estoy seguro de que comprende que esto solo importa si las ramas de los conmutadores en realidad no hacen mucho, y si la PC está realmente en el conmutador una fracción de tiempo significativa, como 10% o más. De lo contrario, es básicamente ruido cuántico. –

La norma no garantiza nada acerca de cómo se implementará la instrucción de conmutación. Nunca he visto un compilador producir una tabla hash, aunque algunos producirán una tabla de salto. A menos que mi memoria funcione peor de lo normal, tanto VS como gcc pueden producir tablas de salto cuando las cajas son suficientemente densas (para diferentes valores de "suficiente"). Desafortunadamente, es casi imposible decirlo (o incluso imaginarlo) cuando la ordenación por frecuencia de aparición ayudará: no solo es diferente entre compiladores, sino incluso entre diferentes versiones del mismo compilador.

Fuente

2010-01-25 01:43:31

Lo siento, quise decir tablas de salto. – Petruza

@Pretruza: puedes corregir tu publicación original – peterchen

Esto es lo que el compilador hará por usted. En el caso de GCC usará una tabla de salto.

Fuente

2010-01-25 01:41:37

C y C++ no garantizan nada sobre el tiempo de ejecución de las sentencias de conmutación.
Me temo que no conozco los detalles de implementación para ningún compilador. Probablemente depende de los indicadores de optimización.
casos de clasificación no está garantizada para ayudar, una vez más no se especifica en la norma, y su aplicación pueden o no:
- hacer cosas diferentes de acuerdo a las opciones del compilador
- documento lo que hace
- Garantizar que no se modifique lo que hace en las versiones futuras
- Ignore por completo el orden de los casos en la fuente y vuelva a pedirlos como prefiera. Suponiendo, por supuesto, que los casos son "independientes": no se producen caídas; no hay declaraciones de variables comenzando en un caso y abarcando otro caso; nada más lo he olvidado.

Fuente

2010-01-25 01:45:27

c (y por extensión C++) solamente se enciende tipos de enteros, por lo hashing no es necesario. El compilador generalmente usará un modismo apropiado para la arquitectura para la que está compilando. Esto podría ser un direccionamiento indexado (si se usa un rango pequeño), tablas de salto, o algo completamente diferente.

Fuente

2010-01-25 01:45:37 dmckee

Hashing no es necesario, pero ocasionalmente es posible optimizar un montón de casos enteros usando un hash perfecto como índice en una tabla de salto, básicamente tomando un conjunto de números no consecutivos y asignarlos a un espacio consecutivo más rápido de lo que podría atravesar un árbol de decisión binario. Si eso es una optimización que cualquier compilador-escritor puede ser molestado es otra cuestión ... –

@Steve: Voy a tomar su palabra para ello, pero en las arquitecturas que he sabido lo suficiente como para comentar incluso (bastante viejos estos días) una mesa de salto sería uniformemente más rápida. Incluso una tabla de salto de dos niveles para administrar objetivos dispersos en un rango entero grande. – dmckee

La única excepción que podría obtener sería un hash perfecto para un conjunto de banderas binarias. Es decir. si todos los "valores de casos" son potencias de 2. – MSalters

Para la implementación de gcc ver:

http://old.nabble.com/optimization-of-switch-statements-on-i386-to15366926.html#a15367662

Fuente

2010-01-25 01:52:09

Un hash no parece ser una manera eficaz de poner en práctica un interruptor, ya que tendrá fallos de caché adicional debido a las operaciones de búsqueda.

Fuente

2010-01-25 08:09:24

¿La optimización del interruptor para muchos casos garantiza el mismo tiempo de acceso para cualquier caso? (C++)

Respuesta

Cuestiones relacionadas