Cuando el compilador te sorprende

 (xania.org)
1 puntos por GN⁺ 2025-12-26 | 1 comentarios | Compartir por WhatsApp
  • Un caso al compilar una función simple de suma de enteros donde se observan las diferencias de optimización entre GCC y Clang
  • GCC realiza una optimización del bucle en la forma x*2 + 1 para sumar dos números a la vez dentro del bucle
  • Clang elimina por completo el bucle y sustituye el cálculo por una fórmula cerrada v(v - 1)/2
  • Con esta transformación, el código pasa de O(n) a O(1) y la simplificación matemática ocurre automáticamente
  • Es un caso que muestra el nivel de optimización inteligente de los compiladores, al punto de sorprender incluso a un autor con más de 20 años trabajando con compiladores

Optimización de bucles en GCC

  • Al escribir una función simple de suma de enteros, GCC genera código eficiente basado en bucles
    • Dentro del bucle usa la instrucción lea edx, [rdx+1+rax*2] para sumar dos números al mismo tiempo
    • Esto corresponde a transformar la operación de sumar x y x+1 en la forma x*2 + 1
  • Si el nivel de optimización se eleva a -O3, procesa el bucle más rápido mediante sumas en paralelo (vectorization)
  • Este enfoque es una forma tradicional de optimización que mantiene el bucle mientras maximiza la eficiencia de las operaciones

Optimización matemática en Clang

  • Al compilar el mismo código con Clang, el bucle desaparece por completo
    • Clang verifica si el valor de entrada es positivo y luego realiza el cálculo con una serie de instrucciones lea, imul y shr
    • Como resultado, lo transforma en (v² - v)/2, es decir, una fórmula cerrada para la suma de enteros
  • Esta transformación elimina el bucle y lo reemplaza por un cálculo en tiempo constante (O(1))
  • El autor describe este resultado como si “hubiera encontrado por sí solo la solución matemática para la suma de enteros”

Proceso de desarrollo de la fórmula

  • Al reconstruir matemáticamente el código ensamblador generado por Clang, se obtiene la siguiente transformación
    • v + ((v - 1)(v - 2) / 2) - 1
    • Al expandirla y simplificarla, se reduce a (v² - v)/2
  • Al final queda en la forma v(v - 1)/2, que coincide con la fórmula de la suma desde 1 hasta v
  • Este proceso se presenta como un ejemplo de cómo el compilador reconoció un patrón matemático y lo optimizó

Funcionamiento inteligente del compilador

  • Se explica que Clang usa esta secuencia específica de instrucciones debido a la prevención de overflow y la forma en que rastrea variables de inducción
  • Aunque la causa exacta del funcionamiento interno no está del todo clara, se menciona como el resultado de la acción combinada de la lógica interna de optimización de Clang
  • El autor describe este resultado como “una experiencia humilde e inspiradora”

Cierre y contexto de la serie

  • Este artículo es la entrada número 24 de la serie ‘Advent of Compiler Optimisations 2025’
  • Explora cómo los compiladores logran simplificación matemática y mejoras de rendimiento mediante la transformación del código
  • El autor enfatiza que “los compiladores todavía me sorprenden”, subrayando el asombro técnico que persiste a pesar de muchos años de experiencia

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-12-26
Comentarios de Hacker News

  • El código que implementa esta función está en ScalarEvolution.cpp y IndVarSimplify.cpp

    • Sorprende y al mismo tiempo da un poco de ansiedad que un solo archivo tenga casi 16,000 líneas de código

  • Este tipo de optimización es realmente interesante
    Las optimizaciones de compilador se dividen, a grandes rasgos, en dos tipos: análisis de flujo de datos y reconocimiento y sustitución de patrones
    La primera suele ser efectiva para la mayoría de los programas, y la segunda es un trabajo acumulativo de patrones con rendimientos cada vez menores
    El ejemplo enlazado es inteligente y divertido, pero en la práctica no tiene mucho valor. En 45 años nunca he escrito un bucle así
    Claro, este tipo de sustitución de patrones sigue siendo importante porque se genera automáticamente a partir de código de alto nivel
    Si soy sincero, puede que solo me esté quejando un poco porque mi optimizer no puede hacer este tipo de optimización

    • En realidad podría ser más valioso de lo que parece. SCEV (Scalar Evolution) de LLVM se usa principalmente para análisis, y también permite otras optimizaciones aparte de los bucles matemáticos
    • No queda claro qué optimización realizó exactamente. Cuando antes hacía compiladores de nicho, recuerdo que me sorprendía ver que el compilador resolvía de forma más inteligente cosas que mis propias optimizaciones escritas a mano

  • Esto es una función llamada Scalar Evolution (SCEV), y en LLVM está implementada de forma bastante compleja

  • Como caso de optimización similar, está el artículo “Do not optimize away”

    • La explicación del inicio de ese artículo está un poco mal. El código suma de 0 a N, pero excluye N, así que en realidad corresponde a N(N-1)/2. Matemáticamente, la suma de 1 a N es N(N+1)/2, así que para excluir el límite superior hay que cambiar N por (N-1)
    • Pienso que el compilador todavía podría optimizar esto. Podría generar por separado una versión con constant folding y otra sin constantes, y bifurcar en tiempo de ejecución

  • Lo realmente genial de esta optimización es que está generalizada (generic)
    No solo reconoce el patrón de “suma de una secuencia finita de enteros”, sino que impresiona que se aplique de forma genérica

  • Parece que el compilador podría agregar más closed forms. Me pregunto si valdría la pena
    Un concepto relacionado es Wilf–Zeilberger pair

  • Una vez más me sorprendió el resultado de que GCC fuera más lento que Clang
    Aunque GCC llevaba 20 años de ventaja, todavía hay casos en los que Clang genera código más rápido
    Antes, al extraer bits, Clang lo resolvía con dos desplazamientos, mientras que GCC hacía tres

    • Entre GCC y LLVM/Clang hay una gran diferencia generacional en tecnología de compiladores. GCC sigue siendo un proyecto impresionante, pero he oído que estructuralmente le cuesta aplicar técnicas modernas de optimización
    • El rendimiento real de ambos compiladores es parecido. Tienen pases de optimización distintos, así que según la situación el resultado cambia
    • Al principio, GCC tenía una arquitectura idealista centrada en la licencia que limitaba su extensibilidad. Ahora eso se ha suavizado bastante, pero el generador de código sigue siendo complejo. En cambio, Clang tiene una estructura más simple y eso facilita implementar optimizaciones. Personalmente, siento que la salida de MSVC o ICC también es bastante buena
    • ¿Era quizá código relacionado con bitfield? GCC es particularmente débil optimizando esa parte

  • Me pregunto si alguien habrá intentado una optimización que sustituya el problema de coloreado de grafos (graph coloring) por una constante

    • El coloreado de grafos es un problema NP-hard, así que es difícil convertirlo en O(1). Si fuera un grafo plano, aplicaría el teorema de los cuatro colores, pero no siempre sale la misma respuesta. Solo quería hablar de teoría de grafos

  • Este es un ejemplo que difumina la frontera entre implementación y especificación
    Creemos que estamos escribiendo una implementación, pero en realidad estamos escribiendo una especie de proxy de la especificación
    Es decir, el compilador crea la ilusión de una máquina imperativa

  • Al principio me sorprendió que Matt no supiera que esto ocurría
    A mí también me impactó cuando en la universidad jugaba con LLVM IR y vi que la recursión se simplificaba a una multiplicación
    Que Matt no lo supiera podría significar que esta optimización solo se aplica a casos simples que él no suele tocar