Todos los periódicos y la radio, en unoEscrito por IA a partir de Hacker News · Cómo se hace
Hacker News
Programación · xoranth.net
Switch lowering en GCC
Un artículo de Xoranth's musings repasa cómo GCC traduce las sentencias switch a código máquina: tablas de saltos, árboles de comparaciones, subconjuntos densos y bit tests. Con ejemplos en ensamblador a -O3, deduce las heurísticas que usa el compilador para elegir cada estrategia.
1 medio · MadridPublicada 31 oct, 10:00Actualizada 31 oct, 17:20· Ya no está en portadaEscrita por IA · cómo funciona
El autor parte de un switch compacto con valores 0 a 4, que GCC convierte en una tabla de saltos. Lo mismo ocurre cuando los valores están desplazados una constante (97 a 101): el compilador resta el desplazamiento y usa la tabla. Si los valores están más dispersos, la tabla pierde atractivo. Por experimentación, el autor sitúa el umbral en unas ocho entradas de tabla por cada etiqueta case: con valores separados de siete en siete se genera tabla, con separación de ocho se genera un árbol de comparaciones. Señala además que GCC no simplifica ese último caso dividiendo x entre ocho antes del salto.
Con un valor atípico (case 100 junto a los casos 1 a 5), GCC emite una comparación para el outlier y una tabla de saltos para el subconjunto denso. Con varias etiquetas que llevan al mismo bloque (cuatro valores contiguos por función, hasta 87), GCC opta por comparaciones aunque una tabla de 88 entradas parecería rentable con la regla de ocho por etiqueta. La explicación del autor es que el compilador cuenta comparaciones, no etiquetas: un rango contiguo de cuatro valores se resuelve con dos comparaciones. Con 10 comparaciones, 10 × 8 < 88, así que la tabla no compensa.
El último ejemplo son casos no contiguos con la misma función de destino ('0', '2', '4', '5', '7', '9', 'A', 'C', 'E'). GCC no genera ni cmp en cadena ni tabla, sino un bit test: resta 48, comprueba que el valor está en rango y usa la instrucción bt contra la constante 2753205, que es un bitset donde cada bit a uno corresponde a un valor case menos 48. El autor aclara que todas las optimizaciones salvo esta de bitset se trasladan a clang.
«Switch Lowering in GCC» · puesto 27 · 200 puntos · enviado por signa11
Lo que dicen los comentarios
Los comentarios se centran en detalles del código generado y en lo que falta. Sobre la división entre ocho, se discute que no es válida sin más porque 3/8 también da 0 y se colaría en un caso; otro usuario propone comprobar que el valor es múltiplo de 8 y usar una tabla. Se pregunta por qué la tabla salta a un jmp en lugar de ir directamente a f0..fX, y la respuesta es que falta esa optimización, que se hace en pasadas posteriores. Un usuario lamenta que clang y GCC no usen hashes perfectos para switches dispersos grandes, y otro pide detalles de rendimiento. También hay comentarios sobre predicción de saltos y hardware.
Qué lástima para clang y gcc: siguen sin implementar hashes perfectos para tablas switch grandes y dispersas. Yo lo hice hace poco en mi compilador de C rcc y me llevó un solo día. Es especialmente útil para trabajo con Unicode.
No podría, porque eso haría que siete valores de cada caso se gestionaran con llamadas a función en vez de caer en el caso por defecto: 0/8 es 0, pero 3/8 también es 0.
Todos los valores son divisibles por 8, así que se podría hacer comparando con 40, descartando con un test de los tres bits bajos si no es múltiplo de 8 y saltando después a la tabla.
Esa optimización simplemente falta. Cada jmp a f0..fX es una optimización de un call y un ret, que probablemente se hace en una pasada aparte, cuando el código del switch ya se ha expandido.
Hay sorprendentemente poco sobre cómo alimentar bien al hardware avanzado en ese código: dos o tres constantes en los cálculos de coste, de las cuales una o dos dependen del hardware.
Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.