Avanço em compiladores: a otimização da divisão tornou os processadores Apple e Intel quase duas vezes mais rápidos

Оптимизация устраняет «проблему 33-го бита» и уже внедрена в LLVM, с обновлениями для GCC и MSVC на подходе

Quem compila software costuma pensar em “otimização” como algo incremental - alguns pontos percentuais aqui e ali. Mas, desta vez, a mudança vem de um detalhe específico e antigo na forma como compiladores fazem divisão por constante, e o resultado pode ser grande o bastante para ser notado até em aplicações do dia a dia (inclusive em servidores e Macs usados no Brasil).

Engenheiros da empresa japonesa Cybozu Labs, focada em software e otimização de computação, propuseram um novo método de divisão por constante para processadores de 64 bits. A ideia elimina limitações herdadas de algoritmos de 32 bits ao aproveitar a folga de largura dos registradores modernos. O patch já foi integrado ao LLVM (Low Level Virtual Machine) - o conhecido projeto open source que inclui o compilador Clang (versão 23.0.0). Atualizações para GCC (GNU Compiler Collection) e MSVC (Microsoft Visual C++) estão em fase de testes.

Até hoje, compiladores modernos (GCC, Clang, MSVC) continuavam usando algoritmos de cerca de 30 anos, ajustados para processadores de 32 bits, mesmo quando o código roda em máquinas potentes de 64 bits. Desde 1994, o padrão para divisão por constante nos compiladores era o método de Granlund e Montgomery (método GM). Esse método substitui a divisão por uma multiplicação por uma “constante mágica” e deslocamentos de bits. O problema é que ele esbarra em limitações ao lidar com “divisores de 33 bits”, o que gera cálculos extras e reduz desempenho em processadores atuais de 64 bits. Em cerca de 3% dos casos de divisão de números de 32 bits por uma constante (por exemplo, ao dividir por 7, 19 ou 107), são necessários cálculos intermediários com “números mágicos” de 33 bits, criando um caminho crítico longo e limitando o paralelismo.

A inovação de Mitsunari Shigeo e Hoshino Takashi está em abandonar a simulação de aritmética de 33 bits e, em vez disso, transformar diretamente a fórmula usando uma malha de 64 bits. No lugar de uma sequência complexa de instruções de correção, entra um modelo matemático mais direto: (x⋅(2^64−a ⋅c))//2⁶⁴, em que x é o dividendo expandido para 64 bits e c é a constante mágica. Em processadores x86-64, usa-se a instrução MULX (Unsigned Multiply Without Affecting Flags), que não altera as flags do processador; já em ARM/Apple Silicon, entra a UMULH (Unsigned Multiply High), que extrai os 64 bits superiores do resultado da multiplicação. Essas instruções permitem efetuar a divisão em uma única operação, acelerando significativamente os cálculos.

Para comparar, o método GM antigo pode exigir até 9 instruções dentro de um loop, incluindo soma e deslocamentos, o que alonga o caminho crítico. O método novo reduz a cadeia para 3 operações, diminuindo a latência e as dependências de dados. Isso é especialmente relevante em CPUs modernas.

Benchmarks feitos em processadores Intel Xeon w9-3495X e Apple M4 mostraram aceleração de até 1,67x e 1,98x, respectivamente. No Apple M4, o ganho foi mais evidente graças à alta capacidade de throughput das unidades de multiplicação. No Xeon, a técnica também melhorou a previsibilidade do tempo de execução, algo importante para cargas de servidor. Por exemplo, o desvio padrão do tempo de execução no Xeon caiu de 0,013 para 0,009 segundos.

A adoção do novo método nos compiladores LLVM e GCC deve acelerar softwares que lidam com grandes volumes de dados, incluindo bancos de dados, sistemas criptográficos e análise de tráfego de rede.

Não se trata apenas de um resultado acadêmico: é uma otimização prática que já chegou à indústria. No momento, o patch está totalmente integrado ao LLVM, e as atualizações para GCC e MSVC estão na etapa final de testes. Na prática, isso significa que, em breve, a maioria dos programas recompilados com os novos compiladores terá um ganho considerável sem precisar mexer no código-fonte. E, dentro dos compiladores, finalmente some um anacronismo histórico: passa-se a explorar de verdade a potência dos processadores de 64 bits até em operações aritméticas básicas, chegando a quase dobrar o desempenho em cenários específicos.