Otimização elimina o “problema do 33º bit” e já foi integrada ao LLVM; atualizações para GCC e MSVC a caminho

Cybozu Labs e a otimização de divisão por constante em 64 bits

Engenheiros da empresa japonesa Cybozu Labs, focada em software e otimização de processos computacionais, apresentaram uma nova técnica de divisão por constante voltada a processadores de 64 bits. A proposta remove limitações herdadas de algoritmos antigos de 32 bits ao aproveitar a folga de largura disponível nos registos modernos.

A correção já foi incorporada ao LLVM (Low Level Virtual Machine) - projeto open source que inclui o compilador Clang (versão 23.0.0). Já as atualizações para GCC (GNU Compiler Collection) e MSVC (Microsoft Visual C++) seguem em fase de testes.

Por que GCC, Clang e MSVC ainda dependiam de um método de 1994

Mesmo executando em sistemas potentes de 64 bits, compiladores modernos como GCC, Clang e MSVC continuavam a aplicar rotinas de cerca de 30 anos atrás, originalmente ajustadas para CPUs de 32 bits. Desde 1994, a abordagem padrão para dividir por constante nos compiladores tem sido o método de Granlund e Montgomery (método GM).

Nesse método, a divisão é substituída por uma multiplicação por uma “constante mágica” e por deslocamentos de bits. O problema é que, ao lidar com os chamados “divisores de 33 bits”, o método esbarra em limitações que forçam cálculos adicionais e, com isso, reduzem o desempenho em processadores atuais de 64 bits.

Na prática, 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), tornam-se necessários cálculos intermédios com “números mágicos” de 33 bits. Isso cria um caminho crítico mais longo e diminui o paralelismo.

Como a nova transformação elimina o “problema do 33º bit”

A contribuição de Mitsunari Shigeo e Hoshino Takashi está em abandonar a tentativa de simular aritmética de 33 bits e, em vez disso, reescrever diretamente a fórmula usando uma malha de 64 bits. No lugar de uma sequência complexa de instruções de correção, o método usa um modelo matemático direto:

(x⋅(2^64−a ⋅c))//2⁶⁴

Aqui, x é o dividendo estendido para 64 bits, e c é a constante mágica. Em processadores x86-64, emprega-se MULX (Unsigned Multiply Without Affecting Flags), que não altera as flags do processador. Já em ARM/Apple Silicon, utiliza-se UMULH (Unsigned Multiply High), que extrai os 64 bits mais altos do resultado da multiplicação. Essas instruções permitem efetuar a divisão numa única operação, acelerando significativamente a execução.

Menos instruções no ciclo e menor latência

Em comparação, o método GM antigo pode exigir até 9 instruções dentro do ciclo, incluindo somas e deslocamentos, o que alonga o caminho de dependências. Com a nova técnica, a cadeia cai para 3 operações, reduzindo latência e dependências de dados - um ponto particularmente relevante para arquiteturas modernas.

Testes de desempenho em Intel Xeon e Apple M4

Testes de desempenho em Intel Xeon w9-3495X e Apple M4 indicaram aceleração de até 1.67x e 1.98x, respetivamente. No Apple M4, o ganho foi mais forte devido à elevada taxa de processamento das unidades de multiplicação. No Xeon, além do aumento de velocidade, o método também tornou o tempo de execução mais previsível, algo importante em 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 incorporação do novo método em LLVM e GCC tende a acelerar software que lida com grandes volumes de dados, incluindo bases de dados, sistemas criptográficos e análise de tráfego de rede.

Trata-se de uma otimização com impacto prático - e não apenas um resultado académico - que já chegou à indústria. Neste momento, a correção está totalmente integrada ao LLVM, enquanto as atualizações para GCC e MSVC passam pelos testes finais. Isso indica que, num futuro próximo, a maior parte dos programas recompilados com os novos compiladores poderá ganhar aceleração considerável sem qualquer alteração no código-fonte. Além disso, elimina-se um anacronismo histórico nos compiladores e, finalmente, passa-se a explorar a força dos processadores de 64 bits em operações aritméticas básicas, chegando a quase dobrar o desempenho em cenários específicos.