GCC convierte un switch en un bitset y nadie sabe por qué
Switch Lowering in GCC
El compilador GCC elige entre tabla de saltos, árbol de comparaciones o un bitset para implementar switch. El autor analiza el código fuente de GCC y descubre que la heurística se basa en el número de comparaciones, no de etiquetas case. También muestra que GCC no simplifica casos como dividir el índice antes del salto, y que la optimización con bitset usa una instrucción bt con una constante enigmática.
Si examinamos la representación binaria de 2753205, encontramos que es, de hecho, un bitset. Los bits activados corresponden a los valores ASCII de las etiquetas case, cada valor reducido en 48.
- LarsKrimi
> El switch en sparse_8 podría simplificarse dividiendo x entre ocho antes del salto. Curiosamente, gcc no encuentra esta simplificación.
No podría, porque eso haría que 7 valores de cada caso fueran manejados por llamadas a funciones en lugar del caso default: 0/8 es 0, pero 3/8 también es 0
- rurban
¡Qué vergüenza para clang y gcc! Todavía no implementan hashes perfectos para tablas switch grandes y dispersas. Yo lo hice hace poco para mi compilador de C rcc, y fue solo un día de trabajo. Especialmente beneficioso para el trabajo con unicode. El parche de LLVM fue rechazado hace una década. Gcc tiene varios parches de unicode esperando en ramas, que también necesitarían eso
- p-t
Supongo que el 34 en el de compact_7() debía ser 35, y que edx debía usarse en algún momento en el de bittest() (a menos que me esté perdiendo algo jaja)
- tsukikage
¿Por qué la indirección? ¿Por qué no hacer que la tabla de saltos haga referencia directamente a f0..fX en lugar de saltar a un salto?
- Andi
Recuerdo haber implementado cosas similares en JavaScript (generando código), para Maps y Sets inmutables: ninguna ganancia de rendimiento significativa en los motores modernos. ¡Para expresiones regulares de rangos unicode complejos, la aceleración fue de alrededor de 2x!