Converting Binary Floating-Point Numbers to Shortest Decimal Strings: An Experimental Review

Este artigo apresenta uma revisão experimental comparando algoritmos de conversão de ponto flutuante para strings decimais, demonstrando que técnicas modernas como Schubfach e Dragonbox superam significativamente o Dragon4 em velocidade, embora nenhuma das implementações analisadas, incluindo as bibliotecas padrão, garanta consistentemente a geração das strings decimais mais curtas possíveis.

O essencial

Imagine que você tem um computador como uma cozinha super moderna. Dentro dela, os números são guardados de uma forma muito específica e eficiente: em binário (zeros e uns), como se fossem ingredientes pré-medidos em xícaras e colheres padronizadas. Isso é o formato "IEEE 754" que o texto menciona.

O problema é que, quando você quer mostrar esses números para um humano (em um relatório, num log de erro, ou numa planilha), você precisa traduzir essa "xícara binária" para texto decimal (como 3,14 ou 10,5). É como tentar explicar a quantidade de farinha usando apenas palavras, e não xícaras.

Este artigo é um grande teste de corrida para ver quem faz essa tradução mais rápido e de forma mais elegante. Os autores, Jaël Champagne Gareau e Daniel Lemire, colocaram vários "cozinheiros" (algoritmos) para competir.

Aqui está o resumo da história, com analogias simples:

1. O Objetivo: A Tradução Perfeita

O objetivo não é apenas traduzir, mas fazer de duas formas:

• Precisão: O número traduzido deve ser exatamente o mesmo que o original (se você traduzir de volta, deve chegar no mesmo lugar).
• Brevidade: O texto final deve ser o mais curto possível.
  • Analogia: Se o número é 0,00011, escrever "0,00011" (7 caracteres) é ok, mas "1,1e-4" (6 caracteres) é melhor. O ideal é a menor frase possível que ainda conte a história correta.

2. Os Competidores: De Dragões Antigos a Fadas Modernas

O artigo compara várias gerações de algoritmos:

• Dragon4 (O Vovô): Criado em 1990. É como um caminhão de entrega antigo. Funciona, é confiável, mas é lento e gasta muita gasolina (milhares de instruções do processador). Ele faz tudo com "cálculo manual", passo a passo.
• Grisu e Ryū (Os Atuais): São mais rápidos, como carros esportivos dos anos 2010. Usam truques matemáticos inteligentes para pular etapas.
• Schubfach e Dragonbox (Os Super-Heróis): São os campeões atuais (2020-2022). Eles são como carros de Fórmula 1. Conseguem fazer a mesma tarefa em 10 vezes menos tempo e gastam muito menos "combustível" (instruções do processador). Em vez de 1500 passos, eles fazem em cerca de 210.

3. A Grande Surpresa: Ninguém é Perfeito (em tamanho)

Aqui está a parte mais interessante e um pouco frustrante.
Os autores descobriram que, embora os algoritmos modernos sejam incrivelmente rápidos, eles não estão produzindo o texto mais curto possível.

• Analogia: Imagine que você precisa enviar uma mensagem de texto. O algoritmo rápido diz: "Ok, vou enviar a mensagem em 1 segundo!" Mas, ao invés de escrever "Oi", ele escreve "Olá, tudo bem?". A mensagem é correta e rápida, mas não é a mais curta.
• O Problema: Muitos algoritmos focam em encontrar o "número de dígitos" mais curto, mas esquecem de formatar o texto final da maneira mais eficiente. Eles podem usar notação científica quando não precisam, ou adicionar zeros desnecessários.
• O Resultado: Em alguns casos, o texto gerado é 30% mais longo do que o necessário. Isso parece pouco, mas se você estiver enviando milhões de dados (como em um servidor de banco de dados), isso ocupa espaço extra e gasta banda de internet desnecessária.

4. O Teste de Carreira: Hardware e Dados Reais

Os autores não testaram apenas em laboratório. Eles rodaram esses algoritmos em:

• Diferentes "corredores": Processadores da Apple (M4 Max), da AMD (Ryzen) e da Intel, além de servidores na nuvem.
• Diferentes "cargas": Dados sintéticos (números aleatórios) e dados do mundo real (preços de Bitcoin, coordenadas de mapas, dados de meteorologia, pesos de inteligência artificial).

O que eles descobriram?

• Velocidade: Os algoritmos modernos (Schubfach e Dragonbox) são consistentemente os mais rápidos em quase todos os computadores.
• O "Gargalo" Escondido: À medida que a parte matemática da conversão ficou super rápida, a parte de "escrever o texto" (formatar os dígitos em letras) começou a ser o novo gargalo. É como ter um motor de Ferrari, mas usar pneus de bicicleta.
• 32-bit vs 64-bit: Números menores (32-bit) geralmente são convertidos mais rápido, mas a diferença não é tão grande quanto se esperava em alguns algoritmos modernos.

5. Conclusão: O Que Fazer Agora?

O artigo termina com um conselho para os futuros desenvolvedores:

1. Não pare na velocidade: Já que os algoritmos matemáticos são rápidos, precisamos focar em como formatar a string final para que ela seja realmente a mais curta possível.
2. Use o poder do hardware: Os algoritmos atuais não estão usando todo o poder dos processadores modernos (como instruções vetoriais). Talvez, no futuro, possamos converter vários números de uma vez (em lote) para ganhar ainda mais velocidade.

Em resumo:
A tecnologia de conversão de números evoluiu muito, tornando-se super rápida (de um caminhão lento para um foguete). Mas, na pressa para ser rápido, esquecemos de ser econômicos com o tamanho do texto. O próximo passo da ciência é fazer com que esses "foguete" também sejam "economizadores de combustível", gerando o menor texto possível sem perder a precisão.

Resumo técnico

Resumo Técnico: Conversão de Números de Ponto Flutuante Binários para Strings Decimais Curtas

1. O Problema

A conversão de números de ponto flutuante binários (padrão IEEE 754, tipos float e double) para suas representações em strings decimais é uma operação fundamental em computação, essencial para serialização (JSON, CSV, YAML), logs, telemetria e interfaces gráficas.

O objetivo central não é apenas a precisão (garantir que a string convertida de volta para binário recupere o valor original), mas a otimização do comprimento da string. Existem dois objetivos distintos, muitas vezes confundidos:

1. Mínimo significando decimal: Encontrar o menor inteiro $w$ tal que $w \times 10^q$ represente o valor binário original sem ambiguidade.
2. String impressa mínima: Encontrar a string de caracteres mais curta possível (considerando notação fixa vs. científica, tamanho do expoente, zeros à direita, etc.) que permita a conversão reversa exata.

O artigo destaca que, embora algoritmos modernos sejam rápidos, muitos não produzem a string absolutamente mais curta, gerando saídas até 30% mais longas que o ótimo devido a decisões de formatação herdadas de padrões antigos (como o C). Além disso, a sobrecarga de processamento por valor, quando aplicada a milhões de conversões em massa, cria um gargalo de desempenho significativo.

2. Metodologia

Os autores realizaram uma avaliação empírica abrangente, superando as limitações de benchmarks anteriores (que usavam dados sintéticos, cobriam poucos algoritmos e não mediam o comprimento da string).

• Hardware: Testes executados em diversas arquiteturas modernas, incluindo:
  • x86-64: Processadores Intel (Skylake, Ice Lake, Sapphire Ridge) e AMD (Zen 2 a Zen 5, incluindo o Ryzen 9900X).
  • ARM/AArch64: Apple M4 Max e instâncias AWS Graviton (Neoverse N1, V1, V2).
• Compiladores: Comparação entre GCC (g++) e Clang (clang++) com diferentes níveis de otimização e instruções de arquitetura (x86-64-v1 a v4).
• Conjuntos de Dados:
  • Sintéticos: Dados uniformemente distribuídos (para comparação com trabalhos anteriores).
  • Reais: Dados de malhas 3D, coordenadas geográficas (GeoJSON), preços de Bitcoin, pesos de modelos de ML (MobileNet), dados astronômicos (Gaia) e telemetria meteorológica (NOAA).
• Algoritmos Avaliados: Uma seleção ampla de implementações, desde a clássica Dragon4 (1990) até métodos de ponta como Schubfach, Dragonbox, Ryū, Grisu3, Grisu-Exact, e implementações de bibliotecas padrão (C++ std::to_chars, Swift, Google double-conversion, fmt).
• Métricas:
  • Tempo de execução (nanosegundos por float).
  • Contagem de Instruções (ins/f): Para isolar o custo algorítmico do throughput de microarquitetura.
  • Ciclos por Instrução (ins/c): Para avaliar a eficiência do pipeline da CPU.
  • Comprimento da String: Média de caracteres gerados.

3. Contribuições Principais

1. Avaliação Empírica Sistemática: O primeiro estudo a comparar algoritmos modernos em uma ampla gama de hardware (x86 e ARM) e datasets reais, incluindo tanto números de 32 quanto 64 bits.
2. Caracterização de Comprimento de String: Demonstração de que nenhum algoritmo testado produz consistentemente a string mais curta possível. A maioria otimiza o significando, mas falha na formatação final (ex: uso excessivo de notação científica ou zeros desnecessários).
3. Métricas de Nível de Instrução: Introdução de medições de instruções por float e ciclos por instrução, revelando que a diferença de desempenho entre algoritmos é dominada pelo número de instruções executadas, não apenas pela velocidade do hardware.
4. Reavaliação de Práticas de Benchmarking: Identificação de falhas em benchmarks anteriores que ignoravam dados do mundo real e o comprimento da saída.

4. Resultados Chave

• Desempenho e Velocidade:

  • Algoritmos modernos (Schubfach e Dragonbox) são até 10 vezes mais rápidos que a clássica Dragon4.
  • Schubfach e Dragonbox executam cerca de 210 a 310 instruções por conversão, comparado a 1500–5000 instruções da Dragon4.
  • Schubfach tende a ser o mais rápido em datasets com strings curtas (como malhas 3D), enquanto Dragonbox compete de perto ou supera em outros cenários.
  • Ryū é consistente e correto, mas geralmente um pouco mais lento que Schubfach e Dragonbox.
  • Implementações de bibliotecas padrão (como std::to_chars do C++ e fmt) são significativamente mais lentas que os algoritmos de ponta, executando mais instruções.

• Comprimento da String (Eficiência de Dados):

  • Nenhuma implementação testada gerou consistentemente a string mais curta.
  • Em alguns casos (ex: dataset mesh), as saídas eram 30% mais longas que o mínimo teórico.
  • Algoritmos como std::to_chars seguem regras estritas do padrão C (ex: expoentes com pelo menos dois dígitos, sinal positivo obrigatório), o que infla o tamanho da string. Algoritmos como Ryū e Dragonbox preferem notação científica mesmo quando a notação fixa seria mais curta, mas ainda assim não alcançam o ótimo global.

• Impacto do Hardware e Compilador:

  • A escolha do algoritmo tem um impacto maior no desempenho do que a arquitetura da CPU ou o compilador.
  • Processadores com maior paralelismo aritmético (como Apple M4 Max e AMD Zen 5) obtêm melhores taxas de instruções por ciclo (IPC).
  • O uso de instruções avançadas (AVX-512, FMA) trouxe ganhos marginais ou nulos para conversões de valores únicos, sugerindo que esses algoritmos não exploram bem a vetorização.

• 32-bit vs 64-bit:

  • A conversão de 32-bit é geralmente mais rápida em termos de floats processados por segundo, mas a conversão de 64-bit gera mais caracteres totais por segundo devido ao maior tamanho médio das strings.

5. Significado e Conclusões

O artigo conclui que, embora a eficiência algorítmica tenha melhorado drasticamente nas últimas três décadas (redução de milhares para centenas de instruções), ainda há espaço para otimização:

1. Geração de Strings: À medida que a conversão matemática (cálculo do significando) se torna extremamente rápida, a etapa final de formatação da string (gerar os caracteres ASCII) tornou-se um gargalo significativo, consumindo até 34% do tempo de execução em alguns casos.
2. Otimização de Saída: Há uma lacuna entre "calcular o significando mínimo" e "imprimir a string mínima". Futuras pesquisas devem focar em backends unificados que garantam a string mais curta possível, independentemente do algoritmo de conversão matemática usado.
3. Vetorização: Como a conversão de um único float não se beneficia muito de instruções SIMD, o próximo salto de desempenho pode vir de algoritmos de conversão em lote (batch), que convertem múltiplos floats simultaneamente para explorar melhor a vetorização moderna.

Em suma, o trabalho fornece um novo padrão de referência para a comunidade, demonstrando que a escolha do algoritmo e a atenção ao formato de saída são tão críticas quanto a escolha do hardware para aplicações que lidam com grandes volumes de dados numéricos.