Compilações 18% mais rápidas, 0% de comprometimento

A equipe do Android Runtime (ART) reduziu o tempo de compilação em 18% sem comprometer o código compilado ou as regressões de memória de pico. Essa melhoria faz parte da nossa iniciativa de 2025 para melhorar o tempo de compilação sem sacrificar o uso da memória ou a qualidade do código compilado.

Otimizar a velocidade do tempo de compilação é crucial para o ART. Por exemplo, ao compilar just-in-time (JIT), isso afeta diretamente a eficiência dos aplicativos e o desempenho geral do dispositivo. Compilações mais rápidas reduzem o tempo antes que as otimizações entrem em vigor, resultando em uma experiência do usuário mais suave e responsiva. Além disso, tanto para JIT quanto para AOT, as melhorias na velocidade de compilação se traduzem em um consumo reduzido de recursos durante o processo de compilação, beneficiando a duração da bateria e a temperatura do dispositivo, especialmente em dispositivos mais simples.

Algumas dessas melhorias de velocidade no tempo de compilação foram lançadas na versão de junho de 2025 do Android, e as demais estarão disponíveis na versão de fim de ano do Android. Além disso, todos os usuários do Android nas versões 12 e mais recentes estão qualificados para receber essas melhorias por meio de atualizações principais.

Como otimizar o compilador de otimização

Otimizar um compilador é sempre um jogo de compensações. Não é possível aumentar a velocidade sem abrir mão de algo. Definimos uma meta muito clara e desafiadora: tornar o compilador mais rápido, mas sem introduzir regressões de memória e, principalmente, sem prejudicar a qualidade do código produzido. Se o compilador for mais rápido, mas os apps forem executados mais lentamente, falhamos.

O único recurso que estávamos dispostos a gastar era nosso próprio tempo de desenvolvimento para nos aprofundar, investigar e encontrar soluções inteligentes que atendessem a esses critérios rigorosos. Vamos analisar como trabalhamos para encontrar áreas de melhoria e as soluções certas para os vários problemas.

Encontrar otimizações possíveis que valem a pena

Antes de começar a otimizar uma métrica, é preciso saber como medi-la. Caso contrário, você nunca vai saber se houve melhoria ou não. Felizmente, a velocidade do tempo de compilação é bastante consistente, desde que você tome algumas precauções, como usar o mesmo dispositivo para medir antes e depois de uma mudança e garantir que o dispositivo não sofra limitação térmica. Além disso, também temos medições determinísticas, como estatísticas do compilador, que nos ajudam a entender o que está acontecendo nos bastidores.

Como o recurso que estávamos sacrificando para essas melhorias era nosso tempo de desenvolvimento, queríamos poder iterar o mais rápido possível. Isso significa que pegamos alguns apps representativos (uma mistura de apps próprios, de terceiros e o próprio sistema operacional Android) para criar protótipos de soluções. Depois, verificamos que a implementação final valeu a pena com testes manuais e automatizados de forma generalizada.

Com esse conjunto de APKs escolhidos a dedo, acionamos uma compilação manual localmente, recebemos um perfil da compilação e usamos o pprof para visualizar onde estamos gastando nosso tempo.

Exemplo de um gráfico de chama de um perfil no pprof

A ferramenta pprof é muito eficiente e permite fatiar, filtrar e classificar os dados para ver, por exemplo, quais fases ou métodos do compilador estão levando mais tempo. Não vamos entrar em detalhes sobre o pprof em si. Basta saber que, se a barra for maior, isso significa que a compilação levou mais tempo.

Uma dessas visualizações é a "de baixo para cima", em que é possível ver quais métodos estão levando mais tempo. Na imagem abaixo, podemos ver um método chamado Kill, que representa mais de 1% do tempo de compilação. Alguns dos outros métodos principais também serão discutidos mais adiante na postagem do blog.

Visualização de baixo para cima de um perfil

No nosso compilador de otimização, há uma fase chamada Global Value Numbering (GVN). Não é preciso se preocupar com o que ele faz como um todo, mas a parte relevante é saber que ele tem uma chamada de método chamada "Kill" que exclui alguns nós de acordo com um filtro. Isso consome tempo, porque é preciso iterar por todos os nós e verificar um por um. Notamos que, em alguns casos, sabemos com antecedência que a verificação será falsa, independentemente dos nós que estiverem ativos naquele momento. Nesses casos, podemos pular a iteração, reduzindo-a de 1,023% para cerca de 0,3% e melhorando o tempo de execução da GVN em aproximadamente 15%.

Implementar otimizações que valem a pena

Abordamos como medir e detectar onde o tempo está sendo gasto, mas isso é só o começo. A próxima etapa é otimizar o tempo gasto na compilação.

Normalmente, em um caso como o de "Kill" acima, analisamos como iteramos os nós e fazemos isso mais rapidamente, por exemplo, realizando ações em paralelo ou melhorando o próprio algoritmo. Na verdade, foi isso que tentamos fazer no início. Só quando não conseguimos encontrar nada para fazer é que tivemos um momento de "Espere um pouco…" e percebemos que a solução era (em alguns casos) não iterar nada. Ao fazer esse tipo de otimização, é fácil se perder nos detalhes.

Em outros casos, usamos algumas técnicas diferentes, incluindo:

• usar heurísticas para decidir se uma otimização não vai produzir resultados que valham a pena e, portanto, pode ser ignorada;
• usar estruturas de dados extras para armazenar em cache dados computados;
• mudar as estruturas de dados atuais para obter supervelocidade
• computação lenta de resultados para evitar ciclos em alguns casos
• use a abstração certa: recursos desnecessários podem deixar o código mais lento;
• evitar perseguir um ponteiro usado com frequência em muitos carregamentos

Como saber se vale a pena fazer as otimizações?

Essa é a melhor parte: você não precisa fazer isso. Depois de detectar que uma área está consumindo muito tempo de compilação e dedicar tempo de desenvolvimento para tentar melhorar isso, às vezes não é possível encontrar uma solução. Talvez não haja nada a fazer, talvez a implementação demore muito, talvez outra métrica seja significativamente prejudicada, talvez a complexidade da base de código aumente etc. Para cada otimização bem-sucedida que você vê neste post, saiba que há inúmeras outras que não deram certo.

Se você estiver em uma situação semelhante, tente estimar o quanto vai melhorar a métrica fazendo o mínimo de trabalho possível. Isso significa, em ordem:

1. Estimativa com métricas que você já coletou ou apenas um palpite
2. Estimativa com um protótipo rápido e simples
3. Implementar uma solução.

Não se esqueça de estimar as desvantagens da sua solução. Por exemplo, se você for usar estruturas de dados extras, quanta memória está disposto a usar?

Análise detalhada

Sem mais delongas, vamos conferir algumas das mudanças que implementamos.

Implementamos uma mudança para otimizar um método chamado FindReferenceInfoOf. Esse método estava fazendo uma pesquisa linear de um vetor para encontrar uma entrada. Atualizamos essa estrutura de dados para ser indexada pelo ID da instrução, de modo que FindReferenceInfoOf seja O(1) em vez de O(n). Além disso, pré-alocamos o vetor para evitar o redimensionamento. Aumentamos um pouco a memória porque tivemos que adicionar um campo extra que contava quantas entradas inserimos no vetor, mas foi um pequeno sacrifício, já que o pico de memória não aumentou. Isso acelerou nossa fase LoadStoreAnalysis em 34% a 66%, o que, por sua vez, melhora o tempo de compilação em cerca de 0,5% a 1,8%.

Temos uma implementação personalizada de HashSet que usamos em vários lugares. A criação dessa estrutura de dados estava levando muito tempo, e descobrimos o motivo. Há muitos anos, essa estrutura de dados era usada apenas em alguns lugares que usavam HashSets muito grandes e foi ajustada para ser otimizada para isso. No entanto, hoje em dia, ele é usado na direção oposta, com apenas algumas entradas e uma vida útil curta. Isso significa que estávamos desperdiçando ciclos ao criar esse enorme HashSet, mas só o usávamos para algumas entradas antes de descartá-lo. Com essa mudança (link em inglês), melhoramos o tempo de compilação em cerca de 1,3% a 2%. Como bônus, o uso da memória diminuiu em cerca de 0,5% a 1%, já que não estávamos usando estruturas de dados tão grandes quanto antes.

Melhoramos cerca de 0,5% a 1% do tempo de compilação transmitindo estruturas de dados por referência para o lambda para evitar que elas sejam copiadas. Isso passou despercebido na análise original e ficou na nossa base de código por anos. Foi graças à análise dos perfis no pprof que percebemos que esses métodos estavam criando e destruindo muitas estruturas de dados, o que nos levou a investigar e otimizá-los.

Aceleramos a fase que grava a saída compilada armazenando em cache os valores computados, o que resultou em uma melhoria de cerca de 1,3% a 2,8% no tempo total de compilação. Infelizmente, a contabilidade extra foi demais, e nosso teste automatizado nos alertou sobre a regressão de memória. Depois, analisamos o mesmo código novamente e implementamos uma nova versão que não apenas resolveu a regressão de memória, mas também melhorou o tempo de compilação em mais 0,5% a 1,8%. Nessa segunda mudança, tivemos que refatorar e reimaginar como essa fase deveria funcionar para eliminar uma das duas estruturas de dados.

Temos uma fase no nosso compilador de otimização que incorpora chamadas de função para melhorar o desempenho. Para escolher quais métodos serão inline, usamos as duas heurísticas antes de fazer qualquer cálculo e as verificações finais depois de fazer o trabalho, mas logo antes de finalizar o inline. Se algum deles detectar que a inclusão in-line não vale a pena (por exemplo, se muitas instruções novas forem adicionadas), não vamos incluir a chamada de método in-line.

Movemos duas verificações da categoria "verificações finais" para a categoria "heurística" para estimar se uma inlining será bem-sucedida ou não antes de fazermos qualquer computação demorada. Como essa é uma estimativa, ela não é perfeita, mas verificamos que nossas novas heurísticas cobrem 99,9% do que era inline antes, sem afetar o desempenho. Uma dessas novas heurísticas era sobre os registros DEX necessários (melhoria de ~0,2% a 1,3%), e a outra sobre o número de instruções (melhoria de ~2%).

Temos uma implementação personalizada de um BitVector que usamos em vários lugares. Substituímos a classe BitVector redimensionável por uma BitVectorView mais simples para determinados vetores de bits de tamanho fixo. Isso elimina algumas indireções e verificações de intervalo de tempo de execução e acelera a construção dos objetos de vetor de bits.

Além disso, a classe BitVectorView foi transformada em modelo no tipo de armazenamento subjacente (em vez de sempre usar uint32_t como o antigo BitVector). Isso permite que algumas operações, como Union(), processem o dobro de bits em plataformas de 64 bits. As amostras das funções afetadas foram reduzidas em mais de 1% no total ao compilar o SO Android. Isso foi feito em várias mudanças [1, 2, 3, 4, 5, 6]

Se fôssemos falar em detalhes sobre todas as otimizações, ficaríamos aqui o dia todo! Se você tiver interesse em mais otimizações, confira outras mudanças que implementamos:

• Adição de contabilidade para melhorar os tempos de compilação em cerca de 0,6% a 1,6%.
• Calcule os dados de forma lenta para evitar ciclos, se possível.
• Refatorar o código para pular o trabalho de pré-computação quando ele não for usado.
• Evite algumas cadeias de carregamento dependentes quando o alocador puder ser facilmente acessado em outros lugares.
• Outro caso de adição de uma verificação para evitar trabalho desnecessário.
• Evite ramificações frequentes no tipo de registro (núcleo/FP) no alocador de registros.
• Verifique se algumas matrizes são inicializadas no tempo de compilação. Não use o clang para isso.
• Limpar alguns loops. Use loops de intervalo que o clang pode otimizar melhor, porque ele não precisa recarregar os ponteiros internos do contêiner devido a efeitos colaterais do loop. Evite chamar a função virtual "HInstruction::GetInputRecords()" no loop usando o "InputAt(.)" inline para cada entrada.
• Evite funções Accept() para o padrão de visitante, aproveitando uma otimização do compilador.

Conclusão

Nossa dedicação em melhorar a velocidade de compilação do ART resultou em melhorias significativas, tornando o Android mais fluido e eficiente, além de contribuir para uma melhor duração da bateria e temperatura do dispositivo. Ao identificar e implementar otimizações com diligência, demonstramos que é possível obter ganhos substanciais no tempo de compilação sem comprometer o uso da memória ou a qualidade do código.

Nossa jornada envolveu a criação de perfis com ferramentas como o pprof, a disposição para iterar e, às vezes, até mesmo abandonar caminhos menos produtivos. Os esforços coletivos da equipe do ART não apenas reduziram o tempo de compilação em uma porcentagem significativa, mas também estabeleceram as bases para avanços futuros.

Todas essas melhorias estão disponíveis na atualização de fim de ano do Android de 2025 e para o Android 12 e versões mais recentes com as atualizações principais. Esperamos que essa investigação do nosso processo de otimização forneça insights valiosos sobre as complexidades e as recompensas da engenharia de compiladores.