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

Otimização resolve o “problema do 33º bit” e já chegou ao LLVM; updates para GCC e MSVC vêm a seguir

Engenheiros da empresa japonesa Cybozu Labs, focada em software e em otimização de computação, apresentaram uma nova forma 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 dos registradores modernos. O patch já foi incorporado ao LLVM (Low Level Virtual Machine) - projeto open source que inclui o compilador Clang (versão 23.0.0). Já as mudanças para GCC (GNU Compiler Collection) e MSVC (Microsoft Visual C++) seguem em fase de testes.

Apesar de o software hoje rodar majoritariamente em máquinas de 64 bits, compiladores atuais (GCC, Clang, MSVC) ainda vinham aplicando rotinas de cerca de 30 anos, originalmente pensadas para 32 bits. Desde 1994, o padrão de divisão por constante nos compiladores tem sido o método de Granlund e Montgomery (método GM), que troca a divisão por uma multiplicação por uma “constante mágica” somada a deslocamentos de bits. O problema é que esse método esbarra em limitações quando encontra “divisores de 33 bits”, o que aciona cálculos extras e derruba o desempenho em CPUs modernas de 64 bits. Na prática, em cerca de 3% dos casos de divisão de inteiros de 32 bits por uma constante (por exemplo, ao dividir por 7, 19 ou 107), são necessárias etapas intermediárias usando “números mágicos” de 33 bits, criando um caminho crítico mais longo e reduzindo o paralelismo.

A inovação de Mitsunari Shigeo e Hoshino Takashi é abandonar a tentativa de “imitar” aritmética de 33 bits e, em vez disso, reescrever diretamente a fórmula numa malha de 64 bits. No lugar de uma sequência de correções com várias instruções, 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, utiliza-se MULX (Unsigned Multiply Without Affecting Flags), que não altera as flags do processador; já em ARM/Apple Silicon, usa-se UMULH (Unsigned Multiply High), que retorna os 64 bits mais altos do resultado da multiplicação. Essas instruções viabilizam realizar a divisão efetivamente em uma única operação, acelerando o cálculo.

Na comparação direta, o método GM antigo pode exigir até 9 instruções dentro de um loop - incluindo somas e shifts - o que alonga o caminho crítico. A técnica nova encurta a cadeia para 3 operações, reduzindo latência e dependências de dados, algo especialmente relevante em microarquiteturas atuais.

Benchmarks em Intel Xeon w9-3495X e Apple M4 indicaram ganhos de até 1.67x e 1.98x, respectivamente. No Apple M4, a melhora foi mais forte por conta da alta capacidade de vazão dos multiplicadores. No Xeon, além do aumento de desempenho, a mudança também tornou o tempo de execução mais previsível - um ponto importante em cargas de servidor. Como exemplo, o desvio-padrão do tempo de execução no Xeon caiu de 0.013 para 0.009 segundos.

Ao entrar no LLVM e no GCC, o método tende a acelerar softwares que lidam com grandes volumes de dados, incluindo bancos de dados, sistemas criptográficos e análise de tráfego de rede.

Trata-se de uma otimização prática, não apenas um resultado acadêmico, e que já começou a ser adotada pela indústria. No momento, o patch está totalmente integrado ao LLVM, enquanto as atualizações para GCC e MSVC estão na etapa final de validação. Na prática, isso significa que, em breve, a maioria dos programas recompilados com esses compiladores novos poderá obter aceleração perceptível sem qualquer alteração no código-fonte. Com isso, remove-se um anacronismo histórico: finalmente a força dos processadores de 64 bits passa a ser explorada também em operações aritméticas básicas, chegando a ganhos quase de duas vezes em cenários específicos.