Reducción de {fmt}: baja el tamaño del binario a 14 kB y elimina el runtime de C++

 (vitaut.net)
1 puntos por GN⁺ 2024-09-02 | 1 comentarios | Compartir por WhatsApp
  • {fmt} es una biblioteca de formateo para C++ que ha reducido la expansión de templates mediante type erasure; en este experimento, un ejecutable simple con fmt::print se redujo de 75 kB a 14 kB
  • La estructura clave consiste en que format delega en vformat, que no es un template, y en ocultar también el tipo de salida detrás de una API de buffers, lo que permite reducir tanto el tamaño del binario como los tiempos de compilación
  • En aarch64 Ubuntu 22.04 con GCC 11.4.0, el ejecutable stripped de {fmt} 11.0.2 medía 75 kB; al desactivar locale, reducir los tipos incorporados y usar macros de optimización de tamaño, bajó de 71 kB → 31 kB → 27 kB → 23 kB
  • La eliminación del runtime de C++ fue posible al hacer que las excepciones usen abort mediante FMT_THROW, compilar con -fno-exceptions, -nodefaultlibs y -lc, y cambiar el asignador predeterminado de basic_memory_buffer a uno basado en malloc/free
  • El ejecutable final mide 14 kB; considerando que un main vacío en C en el mismo sistema pesa 6 kB, el tamaño que agrega {fmt} es inferior a 10 kB, y ldd tampoco muestra dependencias del runtime de C++

Cómo {fmt} crea binarios pequeños

  • {fmt} formatting library suele generar varias veces menos código por llamada de función que alternativas como IOStreams, Boost Format o tinyformat
  • La clave está en una arquitectura que aplica type erasure en varias capas para reducir la expansión de templates
  • Los argumentos de formateo tienen type erasure mediante format_args
    • La función template format delega el trabajo real en vformat, que no es un template
    • Los iteradores de salida y otros tipos de salida también tienen type erasure mediante una API de buffers separada
  • El uso de templates queda limitado a una capa superior delgada, y esta estructura contribuye a binarios más pequeños y a tiempos de compilación de C++ más rápidos

Tamaño de código cercano a printf y mayor seguridad

  • El programa de ejemplo solo llama a fmt::print("The answer is {}.", 42);
  • El resultado de compilación es mucho más pequeño que con IOStreams y está en un nivel similar al ejemplo con printf
    • Ejemplo de {fmt} en Godbolt: godbolt
    • Ejemplo de printf en Godbolt: godbolt
  • A diferencia de printf, {fmt} ofrece seguridad de tipos en runtime
    • Los errores en la cadena de formato pueden detectarse en tiempo de compilación
    • Incluso si la cadena de formato se decide en runtime, los errores se manejan con excepciones, evitando comportamiento indefinido, corrupción de memoria y posibles caídas
  • Al usar argumentos posicionales (positional arguments), que no encajan bien con los argumentos variádicos de C, una llamada a {fmt} suele ser más eficiente

Tamaño base y eliminación de locale

  • En la optimización del tamaño de la biblioteca de 2020, {fmt} se redujo a menos de 100 kB y a unos 57 kB con -Os -flto
  • Desde entonces, {fmt} pasó a usar el algoritmo Dragonbox, contribuido por Junekey Jeon, para el formateo de números de punto flotante
  • Esta medición toma como referencia el tamaño del ejecutable percibido por el usuario final y se realizó en aarch64 Ubuntu 22.04 con GCC 11.4.0
  • La compilación base de {fmt} 11.0.2 pesa 75 kB después de -Os -flto -DNDEBUG y strip
    • Aunque hubo varios cambios en los últimos 4 años, el tamaño no retrocedió de forma significativa
  • Al desactivar el soporte de locale con FMT_STATIC_THOUSANDS_SEPARATOR, el tamaño del binario baja a 71 kB
    • El formateo de {fmt} es independiente de locale por defecto
    • Locale se puede usar opcionalmente con el especificador de formato L

Reducción de tipos incorporados y modelo de “no pagar por lo que no se usa”

  • El análisis con Bloaty muestra que el formateo numérico, en especial el formateo de punto flotante, ocupa una gran parte del tamaño del binario
    • El formateo de punto flotante también usa tablas, y esas tablas no aparecen en la salida de Bloaty
  • La carga fundamental surge de que la función de formateo debe conocer todos los tipos formateables
    • Este enfoque encaja con el printf estándar de C, pero no es un requisito indispensable para {fmt}
    • {fmt} admite una API de extensión que permite formatear tipos arbitrarios sin conocer de antemano el conjunto completo de tipos
  • En la implementación experimental, se configura FMT_BUILTIN_TYPES=0 para tratar de forma especial solo a int y enviar el resto de los tipos a la API de extensión general
    • int es necesario para manejar ancho y precisión dinámicos
    • Ejemplo: fmt::print("{:{}}\n", "hello", 10); imprime "hello "
  • Este enfoque ofrece un modelo en el que no se paga por los tipos que no se usan, aunque el tamaño del binario por llamada aumenta ligeramente
    • Si realmente se formatean números de punto flotante u otros tipos, el código relacionado sigue incluyéndose en la compilación
  • Tras aplicar FMT_BUILTIN_TYPES=0, el binario de ejemplo baja a 31 kB
  • Luego se eliminaron restos relacionados con locale en e582d37 y b3ccc2d, y al permitir desactivarlo con mayor claridad mediante la macro FMT_USE_LOCALE, el tamaño quedó en 27 kB

Elegir entre velocidad y tamaño, y eliminar el runtime de C++

  • Dentro de la biblioteca hay varias partes que sacrifican tamaño para ganar velocidad
  • do_count_digits, que calcula la cantidad de dígitos decimales, usa una tabla de 256 bytes
    • Cambiar esta implementación de forma incondicional podría afectar negativamente a otros casos de uso
    • Ya existe una implementación fallback para casos como constexpr, donde no se puede usar __builtin_clz
  • Se agregó la macro FMT_OPTIMIZE_SIZE para que el usuario pueda controlar si usar la implementación fallback
    • Con este ajuste y algunos cambios similares, el tamaño del binario queda en 23 kB
  • Para eliminar la dependencia de la biblioteca estándar de C++, las excepciones pueden desactivarse con FMT_THROW
    • El ejemplo usa FMT_THROW(s)=abort() y -fno-exceptions
    • En general no se recomienda, pero puede ser aceptable en algunos casos de uso donde la mayoría de los errores se detectan en tiempo de compilación
  • Al compilar con -nodefaultlibs -lc, la dependencia restante del runtime de C++ proviene de fmt::basic_memory_buffer
    • Este buffer es un pequeño buffer asignado en la stack que se expande a memoria dinámica si hace falta
    • fmt::print normalmente puede escribir directamente en un buffer FILE, por lo que no requiere asignación dinámica
  • Como solución más general, se reemplazó el asignador predeterminado basado en new/delete por uno basado en malloc/free
    • Después de este cambio, el tamaño final del binario es 14 kB
    • Como un programa C con main vacío en el mismo sistema pesa 6 kB, el tamaño que agrega {fmt} es inferior a 10 kB
  • El resultado de ldd a.out muestra solo libc.so.6 y el loader; no aparece ninguna dependencia del runtime de C++
  • El resultado final muestra que {fmt} puede usarse con un tamaño menor en entornos embebidos y con restricciones de memoria

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-09-02
Opiniones en Hacker News

  • En realidad, esto es más bien un problema de tendencia de comité, así que no esperaría que fmt, al ser una biblioteca de terceros, tenga necesariamente valores predeterminados incorrectos.
    Sorprendentemente, cuando esta funcionalidad se estandarizó como std::format en C++20, el comité no volvió a introducir este error que existe en muchas otras partes del estándar.
    Así que también hay algo de esperanza para quienes proponen no empeorar innecesariamente C++ con el pretexto de hacerlo “consistente”.

  • Es bastante impactante ver la cantidad de código necesaria para el formateo de punto flotante.
    También vale la pena leer el proyecto Dragonbox [1] enlazado, y está bastante optimizado incluso en ramas que casi no se usan.
    [1] https://github.com/jk-jeon/dragonbox

    • Al trabajar recientemente con Zig, me di cuenta de cuánto código hace falta para formatear punto flotante.
      Normalmente el compilador de Zig no depende del runtime de C en Windows, por lo que puede producir binarios más pequeños que MSVC, pero esta vez el binario era extrañamente grande para lo que hacía la herramienta.
      Lo abrí con Binary Ninja y la mayor parte del código era para soportar formateo de punto flotante; al convertir los números de punto flotante a enteros antes de imprimirlos, el tamaño bajó a lo esperado.
    • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
      Estoy haciendo experimentos de optimización de tamaño, y por ahora se puede reducir a unos 3k en AVR de 8 bits.
      Eso incluye solo la implementación y las tablas para binary32 de precisión simple; la doble precisión requiere bastante más, pero al mismo tiempo buena parte del aumento de tamaño se debe a las limitaciones de AVR.
      En plataformas como x64 podría ser mucho más pequeño, aunque se puede decir que 3k sigue siendo grande.
    • Si quieres que sea rápido, hace falta mucho código.
      La implementación de referencia al final también es una implementación de aritmética de precisión arbitraria, pero no es tan mala.
      [1] https://research.swtch.com/ftoa
      [2] https://go.dev/src/strconv/ftoa.go
    • {fmt} tiene una implementación opcional del antiguo algoritmo Dragon4; el tamaño del código es menor, pero es más lenta.
    • Creo que la mayoría de los casos de uso limitarían la cantidad de decimales a imprimir.
      Me pregunto si sería más eficiente multiplicar por la cantidad de posiciones decimales, convertir a entero, pasarlo por itoa() y luego insertar el punto decimal en la posición correcta.

  • Como principiante en C++, me da curiosidad: ¿el asignador predeterminado de libc++, es decir, la implementación predeterminada de new/delete, hace internamente algo realmente distinto de llamar a malloc/free de libc? Si es así, ¿por qué?

    • No soy muy fuerte en C++, pero new[] intenta llamar al operador new para obtener memoria y luego ejecutar el constructor de cada elemento.
      delete[] intenta ejecutar el destructor de cada elemento antes de liberar la memoria.
      Para que delete[] funcione, C++ tiene que llevar registro del tamaño de la asignación en algún lugar; esa información puede estar cerca de la región asignada o en una estructura separada.
      Si se usa una estructura separada, es menos probable que la información se sobrescriba cuando se escribe mal memoria después del objeto, pero requiere costo de búsqueda y código adicional.
      Una biblioteca de C++ bien hecha hará más cosas, pero con eso uno se puede dar una idea de que new/delete no son lo mismo que malloc/free.
    • ISO C++ no exige que la implementación predeterminada de new/delete llame a malloc()/free().
      Muchas implementaciones lo hacen simplemente porque ya existe y es fácil de usar.
    • Salvo por las sobrecargas de asignación alineada, básicamente no son diferentes.
      Sin embargo, la aplicación puede reemplazar el operator new predeterminado de la biblioteca estándar por una implementación propia incluso en plataformas que no tienen una funcionalidad equivalente a la interposición de símbolos de ELF.
    • La razón principal para cambiarlo por malloc es que new lanza std::bad_alloc, y usar eso obliga a enlazar el runtime de C++.

  • Yo habría esperado que una biblioteca de formateo diseñada para ser pequeña y poder imprimir cadenas y enteros fuera de alrededor de 50 bytes.
    Para una cadena bastan unas 4 instrucciones: comprobar el terminador nulo, imprimir el carácter y saltar dos pasos hacia atrás.
    Para un entero serían unas 20 instrucciones: verificar si es negativo, imprimir '-' e invertir el signo; poner 1000000000 en R1; dividir y guardar el residuo; sumar el ASCII '0'; imprimir el carácter; dividir R1 por 10; usar el residuo como entrada; repetir hasta que R1=0.
    El punto flotante no se usa en muchos programas, así que debería compilarse solo cuando se necesita, y lo mismo para hexadecimal, punteros y relleno con ceros a la izquierda.
    Cuando escribes código para un microcontrolador con 2KB de espacio de código, no metes una biblioteca de formateo de cadenas de 14KB.

    • Esto no es una biblioteca lenta para imprimir enteros y cadenas sin modificadores, sino una biblioteca de formateo con muchas funcionalidades.
      No se puede hacer una biblioteca que al mismo tiempo tenga muchas funciones, sea rápida y además sea pequeña.
    • Diseñar una biblioteca para microcontroladores y diseñar una biblioteca “equivalente” para aplicaciones generales de usuario final difiere en casi todos los puntos importantes.
      No veo muy bien en qué se diferencia esto de una queja general hecha en público, más que algo específico de fmt.
      Solo el código de algoritmos como Dragonbox o Dragon4 ya supera el presupuesto de tamaño, así que que las funciones sean “opcionales” no importa demasiado.
      Y eso es solo una de las aproximadamente 20 funcionalidades que la gente quiere.
    • Entonces creo que lo correcto sería publicar la biblioteca que realmente usas y documentar qué funciones de formateo soporta.
      Así otras personas podrían encontrar formas más inteligentes de meter más funcionalidades.
      Si no, no entiendo bien el punto.
    • No creo que los requisitos de un nicho específico de programación deban influir así en el lenguaje.
      Esos requisitos son válidos, pero deberían resolverlos los compiladores para microcontroladores de especificación mínima, no la especificación del lenguaje.
    • El objetivo principal de esta biblioteca no es ser pequeña, sino construir una biblioteca completa de formateo de cadenas teniendo el tamaño como un objetivo secundario importante.
      Si necesitas que sea extremadamente pequeña a cambio de no soportar ni funciones básicas, claramente hay mejores opciones.
      Si solo tienes 2KB de espacio de código, no deberías usar esto.
      Por suerte, la mayoría de los microcontroladores modernos son mucho más grandes; por ejemplo, el esp32 empieza en 1MB, así que usar una biblioteca de formateo de 14KB es perfectamente razonable.

  • Haciendo un poco de promoción: incluso incluyendo una libc con búfer de salida, se puede tener printf(Hello, World!\n"); en un ejecutable de 1008 bytes: https://github.com/pts/minilibc686
    Claro que compararlo directamente sería comparar peras con manzanas.

    • Eso es porque el compilador lo convierte en fputs.

  • Me parece interesante la parte que dice: “si un programa en C con una función main vacía ocupa 6kB en este sistema, {fmt} ahora solo agrega menos de 10kB al binario”.
    Nunca he hecho una prueba así.

    • Depende mucho de si enlazas la biblioteca de C de forma dinámica o estática, y de cómo se construyeron la aplicación y la biblioteca de C.
      También importa qué biblioteca de C uses, y en menor medida si usas ELF u otro contenedor.

  • Siempre el problema es fmt.
    Es muy gracioso que ahora pase exactamente lo mismo en .NET: si tocas suficientes números, especialmente formateo/parsing de punto flotante y decimal, el linker arrastra un montón de código relacionado con punto flotante y BigInt, y el tamaño del binario crece.

    • Incluso con Native AOT sigo esperando una experiencia tipo Delphi, y por suerte está mejorando poco a poco.

  • Muy interesante.
    Me gustan estas optimizaciones que cambian la forma de pensar.

  • No sé si soy lento, pero me tomó un rato darme cuenta de que el “14k” del título significa 14kB.

    • ¿Qué otra cosa podría significar?
      Al menos históricamente, k es una abreviatura común de kB.