Enxugando o {fmt}: reduzindo o binário para 14k e removendo o runtime de C++

• {fmt} é uma biblioteca de formatação em C++ que vem reduzindo a expansão de templates por meio de apagamento de tipos, e neste experimento um executável simples com fmt::print foi reduzido de 75kB para 14kB
• A estrutura central faz format delegar para vformat, que não é template, e também oculta o tipo de saída por meio de uma API de buffer, o que ajuda a reduzir ao mesmo tempo o tamanho do binário e o tempo de build
• Em aarch64 Ubuntu 22.04 com GCC 11.4.0, o executável stripped do {fmt} 11.0.2 tinha 75kB; com locale desativado, redução dos tipos embutidos e macros de otimização para tamanho, caiu para 71kB → 31kB → 27kB → 23kB
• A remoção do runtime de C++ se tornou possível ao tratar exceções com FMT_THROW usando abort, compilar com -fno-exceptions, -nodefaultlibs, -lc e trocar o alocador padrão de basic_memory_buffer por uma implementação baseada em malloc/free
• O executável final ficou com 14kB; considerando que um main vazio em C no mesmo sistema tem 6kB, o tamanho adicional introduzido por {fmt} é inferior a 10kB, e o ldd também não mostra dependência do runtime de C++

---

Como o {fmt} produz binários pequenos

• A biblioteca de formatação {fmt} costuma gerar várias vezes menos código por chamada de função do que alternativas como IOStreams, Boost Format e tinyformat
• O ponto central é uma estrutura que reduz a expansão de templates aplicando apagamento de tipos (type erasure) em várias camadas
• Os argumentos de formatação são apagados em format_args
  • A função template format delega o trabalho real para vformat, que não é template
  • Iteradores de saída e outros tipos de saída também passam por apagamento de tipos via uma API de buffer separada
• O uso de templates fica restrito a uma camada superior e fina, e essa estrutura contribui para binários menores e tempos de compilação em C++ mais rápidos

Tamanho de código próximo ao printf e segurança mais forte

• O programa de exemplo chama apenas fmt::print("The answer is {}.", 42);
• O resultado compilado é bem menor que com IOStreams e fica em nível parecido com o exemplo em printf
  • Exemplo do {fmt} no Godbolt: godbolt
  • Exemplo do printf no Godbolt: godbolt
• Diferentemente do printf, o {fmt} oferece segurança de tipos em tempo de execução
  • Erros na string de formato podem ser detectados em tempo de compilação
  • Mesmo quando a string de formato é definida em tempo de execução, erros são tratados com exceções, evitando comportamento indefinido, corrupção de memória e possíveis falhas
• Ao usar argumentos posicionais (positional arguments), que não se encaixam bem com argumentos variáveis em C, chamadas ao {fmt} em geral são mais eficientes

Tamanho de referência e remoção de locale

• Na otimização de tamanho da biblioteca de 2020, o {fmt} já havia sido reduzido para menos de 100kB, chegando a cerca de 57kB com -Os -flto
• Depois disso, o {fmt} passou a usar o algoritmo Dragonbox, contribuído por Junekey Jeon, para formatação de ponto flutuante
• Desta vez, a medição usa como referência o tamanho do executável percebido pelo usuário final, em aarch64 Ubuntu 22.04 com GCC 11.4.0
• O build de referência do {fmt} 11.0.2, após -Os -flto -DNDEBUG e strip, ficou em 75kB
  • Apesar de várias mudanças nos últimos 4 anos, o tamanho não regrediu de forma relevante
• Ao desativar o suporte a locale com FMT_STATIC_THOUSANDS_SEPARATOR, o tamanho do binário cai para 71kB
  • A formatação do {fmt} é independente de locale por padrão
  • O locale pode ser usado opcionalmente com o especificador de formato L

Redução dos tipos embutidos e o modelo “não pague pelo que não usa”

• Na análise com Bloaty, a formatação de números, especialmente a formatação de ponto flutuante, ocupa uma grande parte do tamanho do binário
  • A formatação de ponto flutuante também usa tabelas, que não aparecem na saída do Bloaty
• A carga fundamental vem do fato de que as funções de formatação precisam conhecer todos os tipos formatáveis
  • Essa abordagem faz sentido para o printf da biblioteca padrão C, mas não é uma exigência para o {fmt}
  • O {fmt} suporta uma API de extensão que permite formatar tipos arbitrários sem conhecer previamente o conjunto completo de tipos
• Em uma implementação experimental, FMT_BUILTIN_TYPES=0 faz com que apenas int receba tratamento especial, enquanto os demais tipos são encaminhados para a API de extensão genérica
  • int é necessário para lidar com largura e precisão dinâmicas
  • Ex.: fmt::print("{:{}}\n", "hello", 10); imprime "hello "
• Essa abordagem oferece um modelo em que você não paga pelos tipos que não usa, mas aumenta um pouco o tamanho do binário por chamada
  • Se ponto flutuante ou outros tipos forem realmente formatados, o código relacionado ainda será incluído no build
• Depois de aplicar FMT_BUILTIN_TYPES=0, o binário de exemplo caiu para 31kB
• Em seguida, vestígios restantes relacionados a locale foram removidos em e582d37 e b3ccc2d, e ficou mais claro como desativá-los com a macro FMT_USE_LOCALE, levando o tamanho a 27kB

Escolhas entre velocidade e tamanho, e a remoção do runtime de C++

• Há vários pontos na biblioteca em que se troca tamanho por velocidade
• do_count_digits, que calcula o número de dígitos decimais, usa uma tabela de 256 bytes
  • Mudar essa implementação de forma incondicional pode prejudicar outros casos de uso
  • Já existe uma implementação fallback para casos como constexpr, em que __builtin_clz não pode ser usado
• A macro FMT_OPTIMIZE_SIZE foi adicionada para permitir que o usuário controle o uso da implementação fallback
  • Com esse ajuste e algumas mudanças semelhantes, o tamanho do binário caiu para 23kB
• Para eliminar a dependência da biblioteca padrão C++, exceções podem ser desativadas com FMT_THROW
  • O exemplo usa FMT_THROW(s)=abort() e -fno-exceptions
  • Isso não é recomendado em geral, mas pode ser aceitável em alguns cenários em que a maioria dos erros é detectada em tempo de compilação
• Ao compilar com -nodefaultlibs -lc, a dependência restante do runtime de C++ vem de fmt::basic_memory_buffer
  • Esse buffer é pequeno e alocado na stack, expandindo para memória dinâmica quando necessário
  • Em geral, fmt::print consegue escrever diretamente no buffer de FILE, sem precisar de alocação dinâmica
• Como solução mais geral, o alocador padrão foi trocado por uma implementação baseada em malloc/free no lugar de new/delete
  • Após essa mudança, o binário final ficou em 14kB
  • Como um programa C com main vazio no mesmo sistema ocupa 6kB, o tamanho adicional do {fmt} fica abaixo de 10kB
• A saída de ldd a.out mostra apenas libc.so.6 e o loader, sem qualquer dependência do runtime de C++
• O resultado final mostra que é possível usar o {fmt} de forma mais enxuta em ambientes embarcados e com restrição de memória

[GN⁺]

Comentários no Hacker News

• Isso na verdade parece mais um problema de tendência de comitê, então eu não esperaria que o fmt, sendo uma biblioteca de terceiros, tivesse defaults ruins sem necessidade
  Surpreendentemente, quando esse recurso foi padronizado como std::format no C++20, o comitê não reintroduziu esse erro em várias outras partes do padrão
  Então ainda há um pouco de esperança para quem propõe que não se piore o C++ desnecessariamente só para torná-lo “consistente”

• A quantidade de código necessária para formatação de ponto flutuante é bem chocante
  Vale a pena ler também o projeto Dragonbox [1] linkado, e ele é bastante otimizado até em ramificações quase nunca usadas
  [1] https://github.com/jk-jeon/dragonbox

  • Trabalhando recentemente com Zig, percebi quanto código é necessário para formatação de ponto flutuante
    Normalmente o compilador Zig consegue gerar binários menores que o MSVC no Windows porque não depende do runtime C, mas dessa vez o binário estava estranhamente grande para o que a ferramenta fazia
    Quando abri no Binary Ninja, a maior parte do código era suporte à formatação de ponto flutuante, e ao converter os números de ponto flutuante para inteiros antes da saída ele caiu para o tamanho que eu esperava
  • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
    Estou fazendo experimentos de otimização de tamanho e atualmente consigo reduzir para cerca de 3k em AVR de 8 bits
    Isso incluindo apenas a implementação e a tabela para binary32 de precisão simples; precisão dupla exige bem mais, embora boa parte do crescimento também venha das limitações do AVR
    Em plataformas como x64 pode ficar bem menor, mas ainda assim não dá para dizer que 3k seja pequeno
  • Se você quer que seja rápido, vai precisar de bastante código
    A implementação de referência no fim das contas também é uma implementação de aritmética de precisão arbitrária, mas não é tão ruim assim
    [1] https://research.swtch.com/ftoa
    [2] https://go.dev/src/strconv/ftoa.go
  • O {fmt} tem uma implementação opcional do antigo algoritmo Dragon4, que ocupa menos código, mas é mais lenta
  • Imagino que a maioria dos casos de uso limite a quantidade de casas decimais na saída
    Fico curioso se não seria mais eficiente multiplicar pelo número de casas decimais, converter para inteiro, passar por itoa() e depois inserir o ponto decimal na posição apropriada

• Como iniciante em C++, tenho curiosidade: o alocador padrão do libc++, ou seja, a implementação padrão de new/delete, faz algo diferente de simplesmente chamar malloc/free da libc internamente? Se sim, por quê?

  • Não sou tão forte em C++, mas new[] tenta chamar o operador new para obter memória e depois executar o construtor de cada elemento
    delete[] tenta executar o destrutor de cada elemento antes de liberar a memória
    Para delete[] funcionar, C++ precisa rastrear o tamanho da alocação em algum lugar, e essa informação pode ficar perto da região alocada ou em uma estrutura separada
    Se usar uma estrutura separada, fica menos provável que um overwrite incorreto na memória após o objeto destrua essa informação, mas isso exige custo de consulta e código extra
    Uma biblioteca C++ de verdade faz mais coisas, mas isso já dá uma ideia de por que new/delete não são iguais a malloc/free
  • A ISO C++ não exige que a implementação padrão de malloc()/free() seja chamada por new/delete
    Muitas implementações fazem isso apenas porque já existe e é fácil de usar
  • Tirando overloads de alocação alinhada, na prática não é diferente
    Só que a aplicação pode substituir o operator new padrão da biblioteca por uma implementação própria, mesmo em plataformas sem um mecanismo equivalente à interposição de símbolos ELF
  • O motivo principal para trocar por malloc é que new lança std::bad_alloc, então usá-lo exige linkar com o runtime de C++

• Eu esperava que uma biblioteca de formatação projetada para ser pequena e capaz de imprimir strings e inteiros tivesse algo como 50 bytes
  Strings precisariam de algo como 4 instruções: checar terminador nulo, emitir caractere e fazer um desvio de duas etapas para trás
  Inteiros precisariam de algo como 20 instruções: checar negativo, emitir '-', inverter o sinal, carregar 1000000000 em R1, dividir e guardar o resto, somar ASCII '0', emitir caractere, dividir R1 por 10, usar o resto como entrada e repetir até R1=0
  Ponto flutuante não é usado em muitos programas, então deveria ser compilado só quando necessário, assim como hexadecimal, ponteiros e preenchimento com zeros à esquerda
  Ao escrever código para microcontroladores com 2 KB de espaço de código, você não vai colocar uma biblioteca de formatação de strings de 14 KB

  • Isso não é uma biblioteca lenta de saída de inteiros e strings sem modificadores, e sim uma biblioteca de formatação cheia de recursos
    Não dá para ao mesmo tempo fazer uma biblioteca com muitos recursos, rápida e pequena
  • Projetar uma biblioteca para microcontroladores e projetar uma biblioteca “equivalente” para aplicações normais de usuário final são coisas diferentes em praticamente todos os pontos importantes
    Nem entendo muito bem em que isso difere de uma reclamação genérica feita em público, e não algo específico sobre fmt
    Só o código de algoritmos como Dragonbox ou Dragon4 já estoura o orçamento de tamanho, então os recursos “opcionais” nem importam tanto
    E esse é só um entre talvez uns 20 recursos que as pessoas querem
  • Nesse caso, talvez o certo fosse publicar a biblioteca que você realmente usa e documentar quais recursos de formatação ela suporta
    Aí outras pessoas talvez conseguissem descobrir como colocar mais recursos de forma mais inteligente
    Caso contrário, não entendo muito bem qual é o ponto
  • Não acho que requisitos de um nicho específico de programação devam influenciar a linguagem dessa forma
    Esses requisitos são válidos, mas isso é algo que deveria ser resolvido por compiladores para microcontroladores de especificação mínima, não pela especificação da linguagem
  • O objetivo principal desta biblioteca não é ser pequena, e sim ser uma biblioteca completa de formatação de strings, tendo tamanho como um objetivo secundário importante
    Se você quer algo extremamente pequeno mesmo abrindo mão de recursos básicos, certamente há opções melhores
    Se você só tem 2 KB de espaço de código, não deveria usar isso
    Felizmente, a maioria dos microcontroladores modernos tem bem mais do que isso e, por exemplo, o esp32 começa em 1 MB, então usar uma biblioteca de formatação de 14 KB é perfeitamente razoável

• Só para fazer um pouco de propaganda: dá para fazer printf(Hello, World!\n"); em um executável de 1008 bytes, mesmo incluindo uma libc com buffer de saída: https://github.com/pts/minilibc686
  Claro que, numa comparação direta, isso é comparar maçãs com laranjas

  • Isso é porque o compilador converte isso em fputs

• Achei interessante a parte que diz “se um programa C com uma função main vazia tem 6kB nesse sistema, o {fmt} agora adiciona menos de 10kB ao binário”
  Nunca fiz esse tipo de teste

  • Isso varia bastante dependendo de você linkar a biblioteca C dinamicamente ou estaticamente, e de como a aplicação e a biblioteca C foram compiladas
    Qual biblioteca C você usa também importa, e usar ELF ou outro contêiner também influencia um pouco

• O problema é sempre o fmt
  É muito engraçado que, se você mexe com números o suficiente, especialmente com formatação/parsing de ponto flutuante e decimal, o linker acaba puxando muito código relacionado a ponto flutuante e BigInt e o binário cresce — e agora exatamente a mesma coisa acontece no .NET

  • Ainda espero uma experiência tipo Delphi no Native AOT, e felizmente isso está melhorando aos poucos

• Muito interessante
  Adoro esse tipo de otimização com mudança de perspectiva

• Talvez eu seja lerdo, mas demorei um pouco para perceber que “14k” no título queria dizer 14kB

  • Fico pensando no que mais poderia significar
    Pelo menos historicamente, k é uma abreviação bem comum para kB