Localidade e desempenho da memória

Embora a memória seja frequentemente considerada um pool de armazenamento único e uniforme, a organização física dela e a maneira como a CPU a acessa têm um impacto profundo no desempenho do aplicativo. Entender a localidade da memória é fundamental para escrever código de alto desempenho que usa de maneira eficiente a hierarquia de cache da CPU.

A hierarquia de cache da CPU

Uma CPU móvel moderna é muito mais rápida do que a RAM principal do sistema (DRAM). Para reduzir essa diferença de desempenho, as CPUs usam vários níveis de memória pequena e extremamente rápida, chamados de caches.

Observação: as hierarquias e latências listadas abaixo são exemplos representativos destinados a estabelecer proporções relativas. Esses valores estão sujeitos a mudanças à medida que as arquiteturas de CPU evoluem.

• Cache L1 (nível 1): o menor e mais rápido (~1 ns). Em uma CPU de 3 GHz, isso equivale a cerca de três ciclos de clock.
• Cache L2 (nível 2): maior e um pouco mais lento (~3 a 5 ns ou ~10 a 15 ciclos).
• Cache L3 (nível 3): o maior cache (~10 a 20 ns ou ~30 a 60 ciclos).
• Memória principal (DRAM): a maior e mais lenta (~100 ns ou mais, ou ~300 ciclos ou mais).

Contextualização da latência: o custo de uma paralisação

Para entender o impacto desses números, considere uma CPU superscalar moderna que pode retirar de 4 a 8 instruções por ciclo de clock.

Se a CPU perder todos os caches e precisar esperar 100 ns (300 ciclos) para uma leitura de DRAM:

• Ciclos perdidos: cerca de 300 ciclos.
• Instruções "Desperdiçadas": entre 1.200 e 2.400 instruções que poderiam ter sido executadas se os dados já estivessem em um registro local ou no cache L1.

Quando o código tem uma localidade de memória ruim, a CPU não está necessariamente ocupada com matemática complexa. Ela fica frequentemente "parada", ociosa por milhares de equivalentes de instrução enquanto espera pelo subsistema de memória.

Instruções por ciclo (IPC)

Uma métrica importante para medir essa eficiência é Instruções por ciclo (IPC). O IPC representa quantas instruções a CPU conclui em média durante cada ciclo de clock.

• IPC alto (por exemplo, 3,0 a 5,0): a CPU está funcionando com alta eficiência, provavelmente encontrando a maioria dos dados nos caches ou registros L1/L2.
• IPC baixo (por exemplo, < 0,5): a CPU está com um gargalo grave. Mesmo que a CPU esteja com 100% de "uso" nos monitores do sistema, ela passa a maior parte do tempo esperando a memória, um estado conhecido como paralisação da memória.

A localidade da memória é o principal fator que determina se um loop com uso intenso de dados é executado com IPC alto ou entra em colapso em uma série de paralisações.

Linhas de cache

As CPUs não carregam bytes únicos da memória. Em vez disso, eles carregam blocos de tamanho fixo chamados linhas de cache, que geralmente têm 64 bytes. Quando você acessa uma única variável, a CPU busca todo o bloco de 64 bytes que a contém no cache.

TLB (buffer de substituição antecipada de tradução)

O Android usa memória virtual. Todo acesso à memória exige a tradução de um endereço virtual para um endereço físico. O TLB é um cache especializado que armazena traduções recentes. Uma falha de TLB exige que o kernel percorra as tabelas de páginas na memória principal, o que é uma operação relativamente cara em comparação com um acerto de TLB.

---

Perfil de hardware: Pixel 10 Pro Fold

Para os exercícios a seguir, usamos um dispositivo de hardware Pixel 10 Pro Fold. Este dispositivo tem um SoC Google Tensor G5.

Interrogar o hardware

Para entender o subsistema de memória, primeiro examinamos a configuração da CPU e os parâmetros de cache.

Observação: os comandos a seguir exigem acesso root (adb root).

# Check CPU architecture and core parts
adb shell cat /proc/cpuinfo | grep 'CPU part' | sort -u
# Output:
# CPU part  : 0xd8b
# CPU part  : 0xd8c
# CPU part  : 0xd90

# Check cache line size
adb shell getconf -a | grep CACHE_LINESIZE
# Output:
# LEVEL1_ICACHE_LINESIZE             64
# LEVEL1_DCACHE_LINESIZE             64

Como decodificar peças da CPU

Os valores CPU part em /proc/cpuinfo são identificadores hexadecimais para núcleos de CPU ARM. Para o SoC Laguna encontrado no Pixel 10 Pro Fold, eles correspondem a:

• 0xd8b: ARM Cortex-A520 (núcleos de eficiência)
• 0xd90: ARM Cortex-A720 (núcleos de desempenho)
• 0xd8c: ARM Cortex-X4 (núcleo principal)

Essa configuração 4+3+1 é comum em SoCs móveis modernos, em que diferentes clusters podem ter tamanhos de cache e latências diferentes.

---

Tipos de localidade

Um design de software eficiente depende de dois tipos principais de localidade:

1. Localidade espacial: se um local de memória for acessado, é provável que os locais de memória próximos sejam acessados em breve. O exemplo clássico é o percurso sequencial de matrizes. Como a CPU carrega uma linha de cache inteira, acessar o próximo elemento em uma matriz é quase "sem custo" se ele já estiver na linha de cache.
2. Localidade temporal: se um local de memória for acessado, é provável que o mesmo local seja acessado novamente em breve. Os bons algoritmos reutilizam os dados enquanto eles ainda estão "ativos" no cache.

---

Exercício prático: como medir a localidade com o simpleperf

Neste exercício, vamos usar simpleperf para monitorar contadores de desempenho de hardware enquanto executamos duas travessias diferentes de uma matriz de 256 MB.

1. Travessia por linha principal: acessa os elementos da matriz na ordem em que são armazenados na memória. Isso é compatível com cache e explora a localidade espacial.
2. Transversal principal por coluna: pula pela memória para acessar elementos por coluna. Isso geralmente perde o cache e o TLB, forçando a CPU a parar.

Observação: o simpleperf exige que seu dispositivo esteja executando uma build userdebug ou eng.

1. Executar com Simpleperf

Envie o binário, verifique se ele é executável e use simpleperf stat para medir eventos de cache e TLB. Usamos o sufixo :u para medir eventos no espaço do usuário. Esses comandos exigem que o adb root acesse contadores de PMU de hardware na maioria dos dispositivos.

adb root
adb shell "chmod +x /data/local/tmp/LocalityLab"

Perfil Row-major:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab row"

Perfil de coluna principal:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab col"

2. Exemplos de medições (Pixel 10 Pro Fold)

Os resultados a seguir foram medidos em um dispositivo de hardware Pixel 10 Pro Fold:

Métrica	Row-major (Friendly)	Ordem das colunas (não amigável)	Diferença
Tempo de execução	0,83 segundos	68,3 segundos	~82 vezes mais lento
Instruções	5,27 bilhões	10,2 bilhões	~1,9x mais
Ciclos de CPU	1,20 bilhão	62,18 bilhões	~52 vezes mais
Instruções por ciclo (IPC)	4.40	0,16	Eficiência 27 vezes menor
Erros de cache de dados L1	210 milhões	3.369 milhões	16 vezes mais erros
Falhas de carga do dTLB	0,13 milhão	2.888 milhões	22.000 vezes mais erros

Observação: neste exercício, desativamos explicitamente a vetorização automática de SIMD usando #pragma clang loop vectorize(disable). Isso garante que a diferença de desempenho que medimos seja estritamente devido a gargalos do subsistema de memória (cache e TLB) e não a uma diferença entre a capacidade de processamento de instruções SIMD e escalar.

3. Análise de resultados

• A falha de IPC: no teste de linha principal, a CPU alcança um IPC de 4,40, indicando que está executando várias instruções por ciclo de maneira eficiente. No teste de coluna principal, o IPC cai para 0,16. Isso significa que a CPU fica parada 96% do tempo, aguardando a chegada dos dados da DRAM.
• O gargalo do TLB: a diferença mais drástica está em dTLB-load-misses. O acesso sequencial (linha principal) permanece nas mesmas páginas de memória, resultando em pouquíssimas falhas de TLB. Pular entre colunas (ordem das colunas) faz com que a CPU referencie constantemente novas páginas, sobrecarregando o TLB e forçando caminhadas caras na tabela de páginas.
• Eficiência do cache: a travessia principal da coluna gera 16 vezes mais falhas de cache L1, forçando a CPU a buscar dados constantemente do L3 ou da DRAM, que são muito mais lentos.

Observação:embora as duas travessias tenham realizado a mesma operação lógica nos mesmos dados, a travessia principal da coluna foi mais de 80 vezes mais lenta. Essa grande diferença se deve inteiramente à forma como o padrão de acesso interage com a realidade física do subsistema de memória da CPU.

Pointer chasing em estruturas de dados Java e Kotlin

Embora o comparativo de matriz 2D demonstre a localidade espacial em matrizes nativas contíguas, a maior parte do código de apps Android e frameworks é escrita em Java e Kotlin. Em linguagens gerenciadas, variáveis de objeto e elementos de coleção não armazenam objetos inline. Eles armazenam referências (ponteiros) a objetos alocados por heap espalhados pelo heap do ART.

O custo dos gráficos de referência aninhados

Considere um padrão comum em apps Android e serviços do sistema: percorrer coleções aninhadas, como um ArrayList de objetos de estado, cada um contendo um ArrayMap ou ArraySet de listeners ou conexões, cada um apontando para outro registro de estado.

Embora ArrayList, ArrayMap e ArraySet armazenem as matrizes Object[] internas de forma contígua, cada elemento em Object[] ainda é uma referência de heap. Para desreferenciar uma cadeia como process.services.valueAt(i).connections.valueAt(j).client, são necessários cinco carregamentos de memória dependentes sequenciais:

1. Carregue o Object[] de apoio services.
2. Carregue o cabeçalho e os campos do objeto ServiceRecord.
3. Carregue o Object[] de apoio connections.
4. Carregue o objeto ConnectionRecord.
5. Carregue o campo ProcessRecord de destino.

Como o endereço de memória de cada carga depende do valor retornado pela carga anterior, o mecanismo de execução fora de ordem e o pré-buscador de hardware da CPU não podem se sobrepor. Se esses objetos foram alocados em momentos diferentes ou movidos para regiões diferentes durante a coleta de lixo, cada salto corre o risco de uma ausência no cache L1 ou L2.

Primitivos em caixa (ArrayList<Integer>, HashMap<Long, Boolean>) e lambdas genéricos aumentam essa sobrecarga: toda pesquisa de elemento exige uma dereferência de ponteiro extra para desencapsular o valor, e callbacks genéricos Consumer<T> inserem stubs de verificação de tipo de tempo de execução (CheckCast) que adicionam pressão ao cache de instruções (L1-icache).

Diagnóstico de perseguição de ponteiros com simpleperf

Em cargas de trabalho reais de Java e Kotlin (como o processo de travessia de system_server's OomAdjuster, serviço e gráficos de referência de provedor), a busca de ponteiros raramente reduz o IPC até 0,16, como uma verificação sintética de 256 MB de coluna principal, porque parte do conjunto de trabalho se encaixa no cache L2 ou L3. Em vez disso, procure esta assinatura característica em simpleperf:

• IPC baixo (cerca de 0,6 a 0,9): muito abaixo da largura de retirada superescalar da CPU.
• Alto número de interrupções de memória do back-end (raw-stall-backend-mem): geralmente, de 35% a 45% de todos os ciclos da CPU são gastos esperando o preenchimento do cache de dados.
• L1-dcache-load-misses e L1-icache-load-misses elevados: altas taxas de ausência no cache de dados combinadas com ausências no cache de instruções quando loops de travessia ativa pulam métodos virtuais e stubs lambda genéricos.

É possível medir esses contadores em um processo em execução usando simpleperf stat:

adb shell simpleperf stat \
  -e cpu-cycles:u,instructions:u,raw-stall-backend-mem:u,L1-dcache-load-misses:u,L1-icache-load-misses:u \
  -p $(pidof system_server) --duration 10

Melhorar a localidade em código gerenciado

• Substitua coleções encadeadas por matrizes primitivas ou coleções do AndroidX: use primitivos IntArray, LongArray, SparseIntArray ou androidx.collection (IntList, LongLongMap, ScatterMap) para eliminar objetos de wrapper e manter valores contíguos em uma única alocação de matriz.
• Aplanar caminhos de travessia frequentes: se um loop frequente percorrer repetidamente três ou quatro hops em um gráfico de objetos para ler uma única flag booleana ou de número inteiro, eleve ou armazene em cache esse estado em uma matriz simples ou máscara de bits indexada por um ID denso.
• Evite capturar ou usar lambdas genéricos em loops internos apertados: use loops for indexados padrão em listas RandomAccess em vez de forEach ou cadeias de iteradores para evitar alocações de iteradores, despacho megamórfico e sobrecarga de verificação de tipo de tempo de execução.

---

← Threads | ↑ Up | Associações de serviço →