Otimize o desempenho da CPU com o Instruments

Olá! Meu nome é Matt. Sou OS kernel engineer. Hoje, vou ensinar como usar o Instruments para otimizar o código para CPUs com o chip Apple Silicon. O uso eficiente dos recursos da CPU pode evitar longos tempos de espera quando o app precisa processar grandes quantidades de dados ou responder rapidamente a uma interação. Mas prever o desempenho do software é difícil por dois motivos. O primeiro são as camadas de abstração entre o código-fonte Swift e o que realmente acaba sendo executado. O código-fonte que você escreve para o app é compilado em instruções de máquina que por fim são executadas em uma CPU. Mas o código não é executado isoladamente: ele é complementado por código de suporte gerado pelo compilador, pelo tempo de execução do Swift e pelos frameworks do sistema. Todos podem invocar o kernel para tratar operações privilegiadas em nome do app.

Isso dificulta saber o custo das abstrações de software das quais seu código depende. O segundo motivo pelo qual o desempenho do código é difícil de prever é a forma como a CPU executa as instruções que recebe. Em uma única CPU, as unidades funcionais trabalham em paralelo para executar instruções com eficiência. Para isso, as instruções serão executadas fora de ordem, dando apenas a impressão de uma execução em ordem. E as CPUs também se beneficiam de várias camadas de caches de memória que garantem acesso rápido aos dados. Esses fatores aceleram exponencialmente os padrões comuns de codificação, como varreduras lineares na memória ou verificações defensivas, como saídas antecipadas para condições raras. Mas a CPU não consegue executar com eficiência alguns algoritmos, estruturas de dados ou abordagens de implementação sem uma otimização cuidadosa ou até mesmo uma reestruturação significativa. Vamos explorar o caminho ideal para otimizar o código visando a CPU. Começaremos revisando como abordar investigações de desempenho, orientados por dados para focar primeiro nas maiores oportunidades de aceleração. Também vamos considerar abordagens tradicionais de criação de perfil, o que é ótimo para identificar o uso excessivo de CPU no código. Para nos aprofundarmos na criação de perfil, usaremos o Rastreamento do Processador para registrar todas as instruções e medir os custos das abstrações de software. Por fim, usaremos o instrumento aprimorado CPU Counters para analisar gargalos de CPU e entender como micro-otimizar nosso algoritmo. Vamos começar adotando a mentalidade certa para conduzir investigações de desempenho. O primeiro passo é manter a mente aberta: as causas da lentidão podem ser surpreendentes e inesperadas. Colete dados para testar suposições e verificar se seu modelo mental de como o código é executado está correto.

Por exemplo, considere outras causas de lentidão além do desempenho da CPU de thread única. Além da execução em uma CPU, threads e tarefas também podem ficar bloqueadas, esperando recursos como arquivos ou acesso ao estado mutável compartilhado. A sessão "Visualizar e otimizar a simultaneidade do Swift" abrange ferramentas para entender por que as tarefas podem estar fora da CPU.

Quando as threads estão desbloqueadas e na CPU, é possível alguma API esteja sendo usada incorretamente, como aplicar a classe de qualidade de serviço errada ao código ou criar implicitamente muitas threads. Para saber mais, leia a documentação sobre como ajustar o desempenho do seu código. Mas se a eficiência é o problema, é preciso mudar o algoritmo e suas estruturas de dados associadas ou a implementação, que é como o algoritmo é expresso na linguagem de programação. Use ferramentas para determinar em quais desvios dessa árvore é preciso focar primeiro. Use o medidor de CPU do Xcode para detectar se as CPUs são muito usadas durante a interação com o app. Para analisar os comportamentos de bloqueio entre threads e quais threads irão desbloqueá-los, use o instrumento Rastreamento do Sistema.

Para problemas na interface do usuário ou thread principal do app, use o instrumento especializado Travamentos. A sessão Analisando travamentos com o Instruments contém mais detalhes sobre como confirmar se o uso da CPU pelo app precisa ser otimizado. Mas mesmo com a orientação das ferramentas, cuidado com os tipos de otimização que você implementa. O excesso de micro-otimização pode dificultar a expansão e a legibilidade do código. E isso geralmente depende de otimizações frágeis do compilador, como autovetorização ou eliminação de contagem de referência. Antes de recorrer às micro-otimizações invasivas, busque alternativas que possam evitar completamente as operações lentas. Pergunte-se primeiro por que o código está sendo executado. Talvez você possa evitar esse trabalho e apenas apagar o código. É isso, obrigado por assistir a esta sessão e... brincadeirinha. Falando sério, geralmente isso é impossível, mas é uma boa forma de questionar suas suposições sobre a importância dos resultados do trabalho. Você pode tentar executar o trabalho mais tarde, fora do caminho crítico, ou só quando os resultados forem visíveis para alguém. Da mesma forma, pré-calcular os valores também pode mascarar o tempo necessário para concluir o trabalho. Isso pode até envolver a inserção de valores no momento da compilação. Mas essas abordagens podem consumir energia desnecessariamente ou aumentar o tamanho do download do app. Em operações repetidas com as mesmas entradas, usar o cache é outra solução, mas que geralmente traz seus próprios desafios, como invalidação de cache ou aumento do uso de memória. Depois de esgotar as tentativas de evitar o trabalho quando seu desempenho é perceptível, você precisa que a CPU o faça mais rapidamente. É nisso que vamos focar hoje. Priorize os esforços de otimização no código que terá mais impacto na experiência do usuário. Normalmente, é o código no caminho crítico da interação de alguém com o app, onde problemas de desempenho são notados, mas também podem estar em operações mais longas que consomem energia. Nesta sessão, vamos focar na busca em listas preparadas de números inteiros, pois isso está no caminho crítico do meu app.

Meu app já usa busca binária, um algoritmo clássico que usa uma matriz classificada para encontrar um elemento dividindo sucessivamente ao meio o espaço de busca. Neste exemplo, há 16 elementos na matriz e estamos procurando o elemento que contém o número 5. 5 é menor que o elemento no meio da matriz, 20, então seu elemento deve estar na primeira metade. 5 também é menor do que o elemento no meio da primeira metade, 9, então ele deve estar no primeiro quarto da matriz. Chegamos ao elemento correspondente após comparar com o 3, em apenas 4 etapas. Essa é a implementação de busca binária de um framework usado pelo meu app. É uma função independente que usa a metáfora "encontrar uma agulha no palheiro" para nomear seus parâmetros. Permite buscar a agulha (needle) Comparable no palheiro (haystack) Collection. O algoritmo rastreia duas variáveis: o início da nossa área de busca atual em start e o número de elementos restantes para a busca em length. Enquanto houver elementos restantes para buscar, ele verificará o valor do meio do espaço de busca. Se needle for menor que o valor, o espaço de busca será reduzido pela metade, e start ficará intacto. Se needle for igual, o elemento terá sido encontrado, e o índice do meio será retornado. Caso contrário, a posição inicial precisará ser ajustada para logo após o elemento do meio e o espaço de busca reduzido pela metade.

Vamos otimizar esse algoritmo aos poucos, confirmando a cada etapa que estamos avançando ao comparar a taxa de transferência de busca, isto é, o número de buscas que o algoritmo consegue concluir por segundo. Não se sinta limitado a dar somente grandes saltos toda vez que fizer uma mudança: às vezes é difícil quantificar algumas otimizações, mas pequenas melhorias geram grandes resultados com o tempo.

Para otimizarmos continuamente, escrevi um teste automatizado para medir a taxa de transferência de buscas. Uma configuração simples é suficiente: queremos apenas uma estimativa de desempenho. Esse loop de repeat-while chama o fechamento da busca até que a duração especificada tenha se esgotado. Uso um intervalo de sinalização do sistema operacional nas chamadas para o fechamento de busca para que as ferramentas foquem na parte do teste em otimização. E escolhi a categoria Points of Interest, já que o Instruments a inclui por padrão. A cronometragem em si usa um ContinuousClock que, ao contrário de Date, não pode retroceder e tem baixa sobrecarga. É uma abordagem simples, mas eficaz para coletar dados aproximados sobre o desempenho do algoritmo. Meu teste se chama searchCollection e simula como meu app usa a busca binária. Executaremos as buscas por um segundo com um nome descritivo para as sinalizações, caso realizemos vários testes em uma única gravação. Um loop dentro do fechamento invocará a função de busca binária para amortizar o custo de verificação do tempo. Façamos o teste em um criador de perfil do Instruments para analisar o desempenho da CPU na busca binária. Temos dois criadores de perfil focados na CPU: o Time Profiler e o CPU Profiler. O instrumento Time Profiler mostra periodicamente o que está sendo executado nas CPUs do sistema, com base em um timer. Neste exemplo, temos algum trabalho sendo executado em duas CPUs. Na amostra, o Time Profiler captura as pilhas de chamadas no espaço do usuário de cada thread em execução na CPU.

Assim, o Instruments pode ver essas amostras como uma árvore de chamadas ou um gráfico de chama, fornecendo uma estimativa de qual código é importante na otimização de desempenho da CPU. Isso é útil para analisar a distribuição de trabalho ao longo do tempo ou a simultaneidade de ativação das threads. Mas o uso de um timer para amostragem de pilhas de chamadas sofre com um problema chamado aliasing. Aliasing ocorre quando um trabalho periódico no sistema acontece na mesma cadência que o timer de amostragem. Aqui, as regiões azuis são responsáveis pela maior parte do tempo da CPU, mas as funções laranja sempre são executadas quando o amostrador coleta uma pilha de chamadas. Assim, as funções laranja são injustamente super-representadas na árvore de chamadas do Instruments.

Para evitar esse problema, podemos usar o CPU Profiler. Ele testa CPUs de modo independente, com base na frequência de clock de cada CPU. Prefira o CPU Profiler para a otimização da CPU, pois ele é mais preciso e pondera mais justamente o software que consome recursos da CPU.

Esses sinos representam quando o contador de ciclos da CPU amostra a pilha de chamadas em execução. As CPUs Apple Silicon são assimétricas e algumas operam em uma frequência de clock mais lenta, porém, são mais econômica do que outras. As CPUs individuais que aumentam sua frequência serão amostradas com mais frequência, sem o viés do Time Profiler em relação a CPUs que operam mais rápido. Usaremos o CPU Profiler para descobrir quais partes da minha função de busca binária consomem mais ciclos de CPU. No navegador de testes do Xcode, você pode abrir rapidamente o Instruments com um teste unitário clicando com o botão direito no nome do teste e selecionando Profile. Nesse caso, selecionaremos Profile searchCollection.

Isso abre o Instruments e apresenta o seletor de modelos. Vou escolher CPU Profiler. Nos ajustes do gravador, alteramos para o modo adiado a fim de reduzir a sobrecarga e iniciamos a gravação. O modo imediato padrão para criadores de perfil pode ser útil para confirmar que as interações com o app foram capturadas. Mas para um teste automatizado na mesma máquina que o Instruments, queremos minimizar qualquer sobrecarga gerada pelas ferramentas, aguardando o fim da gravação para analisá-la. Novos documentos no Instruments costumam ser desafiadores. A janela está dividida em duas metades. A parte superior exibe as faixas que mostram a atividade na linha do tempo. Cada faixa pode conter várias raias com gráficos para indicar níveis ou regiões.

Abaixo da linha do tempo, a visualização detalhada resume o intervalo da linha do tempo que está sendo inspecionado. Os detalhes adicionais são mostrados no lado direito. Para se orientar, vamos encontrar a região onde as buscas estão acontecendo na faixa Points of Interest. Clicar com o botão direito na região permitirá definir o intervalo de inspeção, limitando a visualização detalhada aos dados capturados no intervalo da sinalização. Podemos clicar na faixa do executor de teste para mostrar o perfil da CPU na visualização abaixo da linha do tempo. Nessa visualização, há uma árvore de chamadas das funções no teste que foram amostradas pelo contador de ciclos de cada CPU. Segurar a tecla Option e clicar na divisa ao lado da primeira função expandirá a árvore até onde as contagens de amostras começam a divergir significativamente, perto da nossa função de busca binária. Vamos focar na nossa função de busca binária clicando na seta ao lado do nome dela e selecionando o item Focus on Subtree. Cada função é ponderada pela contagem de amostras multiplicada pelo número de ciclos entre cada amostra. Essa árvore de chamadas mostra muitas amostras coletadas em funções chamadas pela busca binária para lidar com o tipo Collection. Esse protocol witness está aparecendo em cerca de um quarto de nossas amostras. Há alocações e até verificações do Array para tipos Objective-C. Podemos evitar as sobrecargas do Array e dos genéricos se trocarmos para um tipo de contêiner que combine melhor com o tipo de dados que estamos buscando. Vamos tentar o novo tipo Span. Span pode ser usado no lugar de Collection quando os elementos são armazenados de forma contígua na memória, o que é comum em muitos tipos de estruturas de dados. É, efetivamente, um endereço base e uma contagem. Mas isso também impede que a referência de memória escape ou vaze para fora das funções em que é usada. Para obter mais detalhes sobre Span, confira a sessão "Melhorar o uso da memória e o desempenho com o Swift".

Adotar o Span requer apenas alterar os tipos de haystack e retorno para Span, o algoritmo em si permanece inalterado.

Essa pequena alteração deixa a busca quatro vezes mais rápida. Mas essa versão da busca binária ainda está afetando meu app e eu quero investigar se a verificação de limites de Span está contribuindo para a sobrecarga. Para nos aprofundarmos, vamos usar uma nova ferramenta chamada Rastreamento do Processador. A partir do Instruments 16.3, o Rastreamento do Processador faz um rastreamento completo de todas as instruções executadas pelo app no espaço do usuário. Essa é uma mudança fundamental na forma como você pode medir o desempenho do software: não há viés de amostragem e o impacto no desempenho do app é de apenas 1%. O Rastreamento do Processador requer recursos de CPU especializados, disponíveis apenas no Mac e iPad Pro com M4 ou iPhone com A18. Antes de começarmos, precisamos configurar nosso dispositivo para o rastreamento do processador. Em um Mac, ative o ajuste em Privacidade e Segurança > Ferramentas para Desenvolvedores. No iPhone ou iPad, o ajuste está localizado na seção Desenvolvedor. Para ter a melhor experiência com o Rastreamento do Processador, limite o rastreamento a alguns segundos. Ao contrário da amostragem com o CPU Profiler, você não precisa agrupar o trabalho em lotes: até mesmo uma única instância do código que você deseja otimizar pode ser suficiente. Vamos executar o Rastreamento do Processador na versão Span da busca binária. Nosso teste agora só precisa de algumas iterações. Para criar o perfil, clico com o botão direito no ícone de teste na margem da numeração de linha. Isso mostra o mesmo menu que usamos antes, mas pode ser mais prático do que alternar entre navegadores. Seleciono o modelo Rastreamento do Processador e começo a gravar.

O Rastreamento do Processador lida com muitos dados, então capturá-los e analisá-los pode ser demorado. O Rastreamento do Processador configura a CPU para registrar decisões de desvio. A contagem de ciclos e o horário atual também são registrados para controlar quanto tempo a CPU gasta em cada função. O Instruments usa os binários executáveis do app e do framework do sistema para reconstruir um caminho de execução e anotar chamadas de função com os ciclos decorridos e as durações de tempo. Limitamos o tempo de rastreamento porque, mesmo que a CPU registre o mínimo de informações possível, gigabytes de dados podem ser gerados por segundo em um app multithreaded. Com o documento pronto, vamos dar zoom para inspecionar nossas chamadas de função de busca binária. A busca agora ocupa apenas uma pequena fração da gravação completa, então vamos encontrá-la em Regions of Interest List na visualização detalhada, clicar com o botão direito em sua linha e selecionar Set Inspection Range and Zoom. Para localizar a thread que está executando a busca binária, clicamos com o botão direito na célula Start Thread e selecionamos Pin Thread in Timeline.

Como o Rastreamento do Processador adiciona um gráfico de chama de chamada de função a cada faixa de thread, arrasto o divisor do pino para abrir espaço.

O Rastreamento do Processador mostra a execução visualmente como um gráfico de chama. Um grafo de chama é uma representação gráfica dos custos e relações da função: a largura das barras representa quanto tempo a função levou para ser executada e as linhas representam pilhas de chamadas aninhadas. Mas a maioria dos gráficos de chama usa amostragem e seu custo é apenas uma estimativa baseada na contagem de amostras. O gráfico de chama da linha do tempo do Rastreamento do Processador é diferente: ele mostra as chamadas feitas ao longo do tempo exatamente como teriam sido executadas na CPU. As cores de cada barra representam os tipos de binários de onde elas vêm: marrom para frameworks do sistema, magenta para o tempo de execução do Swift e da biblioteca padrão, e azul para código compilado no binário do app ou em qualquer estrutura personalizada. A primeira parte desse rastreamento mostra a sobrecarga de emitir a sinalização, então vamos dar mais zoom no código de busca binária perto do final do intervalo. Vou manter pressionada a tecla Option, clicar e arrastar pela linha do tempo para dar zoom.

Posso selecionar qualquer chamada de função de busca binária entre as 10 iterações e definir o intervalo de inspeção e o zoom com um clique no botão direito. O Rastreamento do Processador revela todas as chamadas feitas por uma única função que é executada por algumas centenas de nanossegundos. Poderíamos dar mais zoom, mas vamos usar o resumo das chamadas de função abaixo da linha do tempo. São as mesmas informações da linha do tempo, mas em uma tabela, com os nomes completos das funções sendo chamadas por curtos períodos. Vou classificar essa tabela por ciclos.

Minha suposição inicial de que as verificações de limites estavam causando lentidão estava errada. Essa implementação da busca binária ainda sofre com sobrecargas de metadados de protocolo e não consegue alinhar as comparações numéricas, o que acaba representando uma parte significativa do total de ciclos da busca. Isso ocorre porque o parâmetro genérico Comparable não é especializado para o tipo de elemento utilizado.

Como meu código está em um framework vinculado pelo app, o compilador Swift não consegue gerar uma versão especializada da busca binária, apenas para os tipos passados pelos chamadores.

Quando isso causa sobrecarga no código de um framework, você deve adicionar a anotação inlineable à função do framework para gerar implementações especializadas nos executáveis binários do cliente framework. Mas o inlining pode dificultar a análise do código, pois ele se mistura com os chamadores. Quero evitar o inlining no conjunto de testes, então, para essa função, vou especializá-lo manualmente para o tipo Int usado pelo app e pelo teste, com um novo nome de função. O código perde bastante generalidade, mas se torna cerca de 1,7 vez mais rápido. Precisamos continuar otimizando, pois a busca binária ainda está contribuindo para a lentidão no app. É meio estranho gastar tanto tempo otimizando uma única função, já que você vai reavaliar e coletar periodicamente mais dados até perceber que outra parte do código é a responsável pela ineficiência. Nossa busca binária com Span também não mostra chamadas de função inesperadas no Rastreamento do Processador, então precisamos entender como o código está sendo executado na CPU para avançarmos. Com o instrumento CPU Counters, podemos descobrir quais gargalos o código está enfrentando em execução na CPU. Antes de voltarmos a usar o Instruments, precisamos construir um modelo mental de como uma CPU funciona. Em um nível básico, uma CPU apenas segue uma lista de instruções, modifica registradores e a memória e interage com dispositivos periféricos.

Quando uma CPU está executando, ela tem que seguir várias etapas, que são amplamente categorizadas em duas fases. A primeira é a Entrega de Instruções para garantir que a CPU tenha instruções para executar. Em seguida, o Processamento de Instruções é responsável por executá-las. Na Entrega de Instruções, as instruções são extraídas e decodificadas em micro-operações, que a CPU executa com mais facilidade. A maioria das instruções é decodificada em uma única micro-operação, mas algumas realizam várias tarefas, como fazer uma solicitação de memória e incrementar um valor de índice. Para processar uma micro-operação, ela é enviada para as unidades de mapeamento e programação, que roteiam e despacham a operação. A partir daí, a operação é atribuída a uma unidade de execução, ou à unidade de armazenamento de carga, se ela precisar acessar a memória.

Seria muito lento se a CPU tivesse que executar essas fases em série antes de poder buscar novamente, por isso os processadores Apple Silicon são segmentados. Assim que uma unidade termina o trabalho, ela pode passar para a próxima operação, o que a mantém sempre ocupada.

A segmentação e a duplicação das unidades de execução sustentam o paralelismo no nível de instrução.

É diferente do paralelismo no nível de processo ou thread, que você acessaria com o Swift Concurrency ou Grand Central Dispatch, em que múltiplas CPUs executam diferentes threads do sistema operacional. O paralelismo no nível de instrução permite que uma única CPU aproveite momentos ociosos das unidades para utilizar melhor os recursos de hardware, mantendo todas as partes do pipeline ocupadas. O código-fonte Swift não controla diretamente esse paralelismo, mas deve ajudar o compilador a gerar uma sequência adequada de instruções.

Infelizmente, as sequências de instruções paralelizáveis não são entendidas de imediato devido à interação entre as unidades em uma CPU. Cada seta entre as unidades mostra onde as operações podem ser interrompidas no pipeline, limitando o paralelismo disponível. Chamamos isso de gargalos.

Para descobrir qual gargalo é relevante para nossa carga de trabalho, as CPUs com chip Apple Silicon podem contar eventos interessantes em cada unidade e outras características das instruções executadas. O instrumento CPU Counters lê esses contadores para criar métricas de nível superior a partir deles. Este ano, adicionamos modos predefinidos para esses contadores, tornando-os muito mais fáceis de usar. O Instruments os utiliza em um metodologia guiada e iterativa para analisar o desempenho do código, chamada de análise de gargalos. Vamos usá-lo para saber por que nossa busca binária ainda está lenta, apesar de não haver sobrecargas aparentes de chamadas de função. O instrumento CPU Counters depende da amostragem da carga de trabalho, então, precisamos voltar ao conjunto de testes usado com o CPU Profiler para medir a taxa novamente.

Vamos traçar o perfil de um teste da implementação especializada de Span com o Instruments.

Selecionaremos o modelo CPU Counters.

Agora há uma configuração guiada com modos selecionados para fazer medições.

Se tiver curiosidade sobre o que cada modo faz, consulte a documentação disponível clicando no ícone de informações ao lado da seleção de modo. Vamos começar a contagem.

Esse modo inicial de CPU Bottlenecks divide o trabalho feito pela CPU em quatro categorias amplas que representam todo o potencial de desempenho da CPU. O Instruments mostra essas categorias como um gráfico colorido de barras empilhadas e uma tabela de resumo na visualização detalhada. Durante a gravação, o Instruments coletará dados do contador de CPU para as threads usadas em nosso teste e os converterá em porcentagens de gargalo. Usaremos os Points of Interest para nos orientar, como antes, para dar zoom e selecionar nossas buscas.

Depois fixaremos na linha do tempo a thread que está executando nossa implementação de busca binária.

Passando o mouse sobre a faixa CPU Bottleneck, vemos uma porcentagem alta no gargalo descartado. A visualização dos detalhes abaixo mostra as agregações de métricas no intervalo de inspeção. A seleção da linha Discarded Bottleneck mostra uma descrição na visualização detalhada estendida à direita. O Instruments também apresenta uma observação acima do gráfico na linha do tempo. Clicar nessa observação mostra mais detalhes abaixo. Isso é útil, mas ainda não sei qual parte da busca é responsável pelo gargalo. Clicar com o botão direito na célula Discarded Sampling, na coluna Suggested Next Mode, permite recriar o perfil da carga de trabalho com um modo diferente. Vamos tentar. Esse modo é um pouco diferente de CPU Bottlenecks. Dados ainda estão sendo coletados, mas os contadores estão sendo ajustados para acionar a amostragem. Os dados de amostragem estão limitados à instrução que está gerando trabalho descartado. Para mostrá-los, vamos nos orientar novamente com os Points of Interest.

Depois selecionamos a faixa do processo de teste e navegamos até Instruction Samples, abaixo da linha do tempo. Isso não é uma pilha de chamadas, mas a instrução exata que está causando o problema. Podemos abrir o Source Viewer clicando na seta ao lado do nome da função para ver o código-fonte que foi amostrado porque a CPU seguiu a direção errada do desvio. Aqui, as comparações feitas entre needle e middleValue estão sendo previstas incorretamente. Para entender por que essas linhas de código-fonte são responsáveis por tantas previsões incorretas, precisamos aprender um pouco mais sobre CPUs.

As CPUs são sorrateiras e executam instruções fora de ordem. Só parece que as instruções são executadas sequencialmente, graças a uma etapa extra de reordenação conforme elas são concluídas. Isso significa que as CPUs olham para frente e fazem previsões sobre quais instruções serão executadas em seguida. Os preditores de desvio responsáveis geralmente são precisos, mas podem tomar caminhos errados quando não há um padrão consistente de execuções anteriores sobre se um desvio será tomado ou não.

O loop em nosso algoritmo de busca binária tem dois tipos de desvio. A primeira condição do loop geralmente é atendida até o final do loop, por isso é bem prevista e não apareceu na amostragem. Mas a verificação de needle é um desvio aleatório, então, não é de se admirar que os preditores tenham dificuldades com ela.

Reescrevi o corpo do loop para evitar desvios difíceis de prever que afetam o fluxo de controle. O corpo da instrução if está atribuindo um valor apenas com base na condição. Isso permite que o compilador Swift gere uma instrução de movimentação condicional e evite o desvio para uma instrução diferente. Retornar de uma função ou interromper um loop com base em uma condição deve ser implementado com um desvio, então precisei remover o retorno antecipado. Usei aritmética não verificada para evitar desvios que encerrariam o programa. Essa é uma das áreas em que a micro-otimização se torna frágil e fácil de ser comprometida, para não dizer menos segura e compreensível. Quando fazemos uma alteração como essa, devemos voltar ao modo inicial de CPU Bottlenecks para verificar como ela afeta o restante dos gargalos. Já coletei um rastreamento da nova busca binária sem desvios, que agora está quase duas vezes mais rápida do que a versão com desvios. Agora está quase completamente limitada pelo Processamento de Instruções. O Instruments indica que devemos executar novamente a carga de trabalho com o modo de Processamento de Instruções.

Esse modo tinha observações que recomendavam a execução do modo de Amostragem de Falhas de Cache L1D. As amostras de falhas de cache mostram que o acesso à memória da matriz é o motivo pelo qual a CPU não consegue executar instruções de modo eficiente. Vamos aprender mais sobre CPUs e memória para descobrir o porquê.

As CPUs acessam a memória usando uma hierarquia de caches que tornam os acessos repetidos ao mesmo endereço, mesmo padrões de acesso ou previsíveis, muito mais rápidos. Tudo começa com os caches L1, que estão localizados dentro de cada CPU. Eles não conseguem armazenar muitos dados, mas oferecem acesso mais rápido à memória. Um cache L2 mais lento fica fora das CPUs e oferece muito mais espaço. Por fim, as solicitações que não encontram nenhum dos caches e precisam acessar a memória principal tornam-se 50 vezes mais lentas. Esses caches também agrupam a memória em segmentos de 64 ou 128 bytes chamados linhas de cache: mesmo que uma instrução solicite apenas 4 bytes, os caches extrairão mais dados com a expectativa de que as instruções subsequentes precisarão acessar outros bytes próximos.

Vamos considerar como isso afeta o nosso algoritmo de busca binária. Neste exemplo, as linhas azuis são elementos na matriz, enquanto as cápsulas cinzas são as linhas de cache nas quais os caches da CPU operam.

A matriz começa completamente fora do cache. A primeira comparação traz uma linha de cache e vários elementos para o cache de dados L1. Mas a próxima comparação resulta em uma falha de cache. E as iterações subsequentes continuam resultando em falhas de cache. Isso continua até que a busca se concentre em uma região do tamanho de uma linha de cache. A busca binária acaba sendo um caso patológico para a hierarquia de memória da CPU.

Mas se pudermos reorganizar os elementos para favorecer o cache, então poderemos colocar os pontos de busca na mesma linha de cache. Esse é o layout Eytzinger, em homenagem a um genealogista austríaco do século XVI que organizava árvores genealógicas dessa maneira. Essa não é uma otimização geral que podemos fazer sem consequências significativas. Isso acelera a busca, mas compromete a velocidade da travessia em ordem, fazendo com que essa operação cause falhas no cache. Vamos voltar ao primeiro exemplo de busca binária para mostrar como reorganizar uma matriz classificada em um layout Eytzinger. Começando com o elemento do meio como raiz, modelaremos a operação de busca binária como uma árvore, onde os pontos médios são nós descendentes. Um layout Eytzinger é organizado como a travessia em largura dessa árvore.

Os elementos mais próximos da raiz são organizados de modo mais denso e são mais propensos a compartilhar linhas de cache. Buscar novamente o 5 agora inclui as três primeiras etapas na mesma linha de cache. Os nós folha são classificados no final da matriz, o que resultará em uma falha de cache inevitável.

Gravei um rastreamento de CPU Bottlenecks da busca binária com Eytzinger, que mostra que ela é duas vezes mais rápida do que a busca sem desvios. Mas este exemplo destaca algo interessante. Ela ainda está tecnicamente limitada pelo Processamento de Instruções. Tornamos nossa implementação mais amigável ao cache, mas a carga de trabalho ainda é limitada pela memória.

Você deve monitorar o desempenho para saber quando parar e otimizar outros códigos no app, pois nossa busca agora não afeta mais o desempenho do caminho crítico. Durante esse processo, melhoramos significativamente a taxa de busca. Primeiro, com o CPU Profiler, conseguimos uma aceleração significativa ao trocar de Collection para Span.

Em seguida, o Rastreamento do Processador nos mostrou as sobrecargas de genéricos não especializados. E, por fim, aumentamos significativamente o desempenho com algumas micro-otimizações, guiadas pela Análise de Gargalo. No geral, tornamos nossa função de busca cerca de 25 vezes mais rápida com o Instruments. Para ganhar essas acelerações, começamos com a mentalidade certa, usando ferramentas para confirmar nossos palpites e desenvolver uma intuição sobre o custo das abstrações. Fomos aplicando ferramentas cada vez mais detalhadas para identificar sobrecargas inesperadas. Essas questões eram tão fáceis de resolver quanto de ignorar, se você não as mede de fato. E depois de resolver as sobrecargas de software, passamos a focar em otimizações voltadas para gargalos na CPU. Ficamos mais conscientes, e talvez mais empáticos, em relação aos recursos da CPU que são dados como certos. Essa ordem foi importante: temos que garantir que as ferramentas voltadas à CPU não sejam confundidas por sobrecargas extras do tempo de execução do software.

Para aplicar isso aos seus próprios apps, colete dados e siga as pistas com o foco no desempenho. Escreva testes de desempenho para que você possa medir repetidamente com esses instrumentos. Faça comentários ou perguntas nos fóruns sobre como usar as ferramentas. Confira as sessões que mencionei anteriormente e a sessão da WWDC24 desempenho do Swift, que ajudarão a criar um modelo mental mais preciso dos custos das poderosas abstrações do Swift. E para entender melhor como as CPUs executam código, leia o "Guia de Otimização para CPUs com chip Apple Silicon" Agradeço sua participação. Divirta-se usando o Instruments para encontrar agulhas de otimização no seu palheiro de código.