Rendimiento y localidad de la memoria

Si bien la memoria a menudo se considera un único grupo de almacenamiento uniforme, su organización física y la forma en que la CPU accede a ella tienen un profundo impacto en el rendimiento de la aplicación. Comprender la localidad de la memoria es clave para escribir código de alto rendimiento que use de manera eficiente la jerarquía de caché de la CPU.

La jerarquía de caché de la CPU

Una CPU móvil moderna es mucho más rápida que la RAM principal del sistema (DRAM). Para superar esta brecha de rendimiento, las CPU usan varios niveles de memoria pequeña y extremadamente rápida llamada caché.

  • Caché L1 (nivel 1): Es la más pequeña y rápida (~1 ns). En una CPU de 3 GHz, esto equivale a unos 3 ciclos de reloj.
  • Caché L2 (nivel 2): Más grande y un poco más lenta (~3-5 ns o ~10-15 ciclos)
  • Caché L3 (nivel 3): Es la caché más grande (alrededor de 10 a 20 ns o de 30 a 60 ciclos).
  • Memoria principal (DRAM): Es la más grande y lenta (más de 100 ns o más de 300 ciclos).

Pirámide de latencia de la memoria

Contextualización de la latencia: el costo de una detención

Para comprender el impacto de estas cifras, considera una CPU superescalar moderna que puede completar de 4 a 8 instrucciones por ciclo de reloj.

Si la CPU no encuentra los datos en ninguna caché y debe esperar 100 ns (300 ciclos) para una lectura de DRAM, sucede lo siguiente:

  • Ciclos perdidos: Alrededor de 300 ciclos.
  • Instrucciones "Desperdiciadas": Entre 1,200 y 2,400 instrucciones que se podrían haber ejecutado si los datos ya estuvieran en un registro local o en la caché de L1.

Cuando tu código tiene una mala localidad de memoria, la CPU no necesariamente está ocupada con cálculos matemáticos complejos, sino que se "detiene" con frecuencia, permaneciendo inactiva durante miles de equivalentes de instrucciones mientras espera el subsistema de memoria.

Instrucciones por ciclo (IPC)

Una métrica clave para medir esta eficiencia son las instrucciones por ciclo (IPC). El IPC representa la cantidad de instrucciones que la CPU "retira" (completa) correctamente en promedio durante cada ciclo de reloj.

  • IPC alto (p.ej., de 3.0 a 5.0): La CPU se ejecuta con alta eficiencia, y es probable que encuentre la mayoría de sus datos en los registros o las memorias caché L1 y L2.
  • IPC bajo (p.ej., < 0.5): La CPU tiene un cuello de botella grave. Incluso si la CPU está al 100% de "uso" en los monitores del sistema, en realidad se dedica principalmente a esperar la memoria, un estado conocido como detención de memoria.

La localidad de la memoria es el factor principal que determina si un bucle con uso intensivo de datos se ejecuta con un IPC alto o se colapsa en una serie de detenciones.

Líneas de caché

Las CPU no cargan bytes individuales de la memoria. En cambio, cargan bloques de tamaño fijo llamados líneas de caché, que suelen ser de 64 bytes. Cuando accedes a una sola variable, la CPU recupera en la caché todo el fragmento de 64 bytes que la contiene.

Mecánica de la línea de caché

TLB (búfer de anticipación de traducción)

Android usa memoria virtual. Cada acceso a la memoria requiere la traducción de una dirección virtual a una dirección física. El TLB es una caché especializada que almacena traducciones recientes. Un error de TLB requiere que el kernel recorra las tablas de páginas en la memoria principal, lo que es una operación relativamente costosa en comparación con un acierto de TLB.

Perfil de hardware: Pixel 10 Pro Fold

Para los siguientes ejercicios, usamos un dispositivo de hardware Pixel 10 Pro Fold. Este dispositivo cuenta con un SoC Google Tensor G5.

Cómo consultar el hardware

Para comprender el subsistema de memoria, primero examinamos la configuración de la CPU y los parámetros de la caché.

# 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

Partes de la CPU de decodificación

Los valores de CPU part en /proc/cpuinfo son identificadores hexadecimales para los núcleos de CPU ARM. En el caso del SoC Laguna que se encuentra en el Pixel 10 Pro Fold, estos se asignan de la siguiente manera:

  • 0xd8b: ARM Cortex-A520 (núcleos de eficiencia)
  • 0xd90: ARM Cortex-A720 (núcleos de rendimiento)
  • 0xd8c: ARM Cortex-X4 (núcleo principal)

Esta configuración de 4 + 3 + 1 es común en los SoCs móviles modernos, en los que diferentes clústeres pueden tener diferentes tamaños y latencias de caché.

Tipos de localidad

El diseño de software eficiente se basa en dos tipos principales de localidad:

  1. Localidad espacial: Si se accede a una ubicación de memoria, es probable que pronto se acceda a ubicaciones de memoria cercanas. El recorrido secuencial de un array es el ejemplo clásico. Dado que la CPU carga una línea de caché completa, acceder al siguiente elemento de un array es casi "gratis" si ya está en la línea de caché.
  2. Localidad temporal: Si se accede a una ubicación de memoria, es probable que se vuelva a acceder a la misma ubicación pronto. Los buenos algoritmos reutilizan los datos mientras aún están "activos" en la caché.

Ejercicio práctico: Cómo medir la localidad con simpleperf

En este ejercicio, usaremos simpleperf para supervisar los contadores de rendimiento del hardware mientras ejecutamos dos recorridos diferentes de una matriz de 256 MB.

  1. Recorrido por filas: Accede a los elementos de la matriz en el orden en que se almacenan en la memoria. Esto es compatible con la caché y aprovecha la localidad espacial.
  2. Recorrido por columnas: Salta por la memoria para acceder a los elementos por columna. Esto suele provocar que se pierda la caché y el TLB, lo que obliga a la CPU a detenerse.

1. Ejecuta con Simpleperf

Envía el archivo binario, asegúrate de que sea ejecutable y usa simpleperf stat para medir los eventos de caché y TLB. Usamos el sufijo :u para medir eventos en el espacio del usuario. Estos comandos requieren que adb root acceda a los contadores de PMU de hardware en la mayoría de los 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 columna 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. Medidas de muestra (Pixel 10 Pro Fold)

Los siguientes resultados se midieron en un dispositivo de hardware Pixel 10 Pro Fold:

Métrica Ordenamiento por filas (amigable) Orden de columnas (poco amigable) Diferencia
Tiempo de ejecución 0.83 segundos 68.3 segundos Aproximadamente 82 veces más lento
Instrucciones 5,270 millones 10,200 millones Aprox. 1.9 veces más
Ciclos de CPU 1,200 millones 62,180 millones Aproximadamente 52 veces más
Instrucciones por ciclo (IPC) 4.40 0.16 Eficiencia 27 veces menor
Errores de caché de datos de L1 210 millones 3,369 millones 16 veces más errores
Errores de carga de dTLB 0.13 millones 2,888 millones 22,000 veces más errores

3. Análisis de los resultados

  • La falla de IPC: En la prueba de fila principal, la CPU alcanza un IPC de 4.40, lo que indica que ejecuta de manera eficiente varias instrucciones por ciclo. En la prueba de ordenamiento por columnas, el IPC disminuye a 0.16. Esto significa que la CPU está detenida el 96% del tiempo, esperando que lleguen los datos de la DRAM.
  • El cuello de botella de TLB: La diferencia más drástica se encuentra en dTLB-load-misses. El acceso secuencial (ordenado por filas) permanece dentro de las mismas páginas de memoria, lo que genera muy pocos errores de TLB. Saltar entre columnas (orden de columnas) hace que la CPU haga referencia constantemente a páginas nuevas, lo que sobrecarga el TLB y fuerza costosas búsquedas en la tabla de páginas.
  • Eficiencia de la caché: El recorrido principal de la columna genera 16 veces más errores de caché L1, lo que obliga a la CPU a recuperar datos de la L3 o la DRAM, que son mucho más lentas, de forma constante.

Observación: Si bien ambos recorridos realizaron la misma operación lógica en los mismos datos, el recorrido por columnas fue más de 80 veces más lento. Esta gran diferencia se debe por completo a la forma en que el patrón de acceso interactúa con la realidad física del subsistema de memoria de la CPU.

Seguimiento de punteros en estructuras de datos de Java y Kotlin

Si bien la comparativa de la matriz 2D demuestra la localidad espacial en arrays nativos contiguos, la mayor parte del código de la aplicación para Android y el framework está escrito en Java y Kotlin. En los lenguajes administrados, las variables de objeto y los elementos de colección no almacenan objetos de forma intercalada, sino que almacenan referencias (punteros) a objetos asignados al montón y dispersos en el montón de ART.

El costo de los gráficos de referencia anidados

Considera un patrón común en las apps para Android y los servicios del sistema: recorrer colecciones anidadas, como un ArrayList de objetos de estado, cada uno de los cuales contiene un ArrayMap o un ArraySet de objetos de escucha o conexiones, cada uno de los cuales apunta a otro registro de estado.

Aunque ArrayList, ArrayMap y ArraySet almacenan sus arrays internos Object[] de forma contigua, cada elemento de ese Object[] sigue siendo una referencia de montón. La desreferenciación de una cadena como process.services.valueAt(i).connections.valueAt(j).client requiere cinco cargas de memoria dependientes secuenciales:

  1. Carga el respaldo de Object[] services.
  2. Carga el encabezado y los campos del objeto ServiceRecord.
  3. Carga el respaldo de Object[] connections.
  4. Carga el objeto ConnectionRecord.
  5. Carga el campo de destino ProcessRecord.

Dado que la dirección de memoria de cada carga depende del valor que devuelve la carga anterior, el motor de ejecución fuera de orden y el captador previo de hardware de la CPU no pueden superponerlas. Si esos objetos se asignaron en diferentes momentos o se trasladaron a diferentes regiones durante la recolección de elementos no utilizados, cada salto corre el riesgo de un error de caché L1 o L2.

Los tipos primitivos empaquetados (ArrayList<Integer>, HashMap<Long, Boolean>) y las expresiones lambda genéricas agravan esta sobrecarga: cada búsqueda de elementos requiere una desreferencia de puntero adicional para desempaquetar el valor, y las devoluciones de llamada genéricas Consumer<T> insertan stubs de verificación de tipo en tiempo de ejecución (CheckCast) que agregan presión a la caché de instrucciones (L1-icache).

Cómo diagnosticar la búsqueda de punteros con simpleperf

En las cargas de trabajo de Java y Kotlin del mundo real (como el proceso de recorrido de system_server, los gráficos de referencia de servicios y proveedores de OomAdjuster), el seguimiento de punteros rara vez reduce el IPC a 0.16 como un análisis sintético de 256 MB orientado a columnas, ya que parte del conjunto de trabajo cabe en la caché de L2 o L3. En su lugar, busca esta firma característica en simpleperf:

  • IPC bajo (alrededor de 0.6 a 0.9): Muy por debajo del ancho de retiro superescalar de la CPU.
  • Paradas de memoria de backend altas (raw-stall-backend-mem): A menudo, entre el 35% y el 45% de todos los ciclos de CPU se dedican a esperar a que se complete el llenado de la caché de datos.
  • L1-dcache-load-misses y L1-icache-load-misses elevados: Altas tasas de errores de caché de datos combinadas con errores de caché de instrucciones cuando los bucles de recorrido activos saltan entre métodos virtuales y stubs de lambda genéricos.

Puedes medir estos contadores en un proceso en ejecución con 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

Mejora de la localidad en el código administrado

  • Reemplaza las colecciones con conversión boxing por arrays primitivos o colecciones de AndroidX: Usa primitivos IntArray, LongArray, SparseIntArray o androidx.collection (IntList, LongLongMap, ScatterMap) para eliminar objetos wrapper y mantener los valores contiguos dentro de una sola asignación de array.
  • Aplanar las rutas de acceso frecuentes: Si un bucle frecuente recorre repetidamente tres o cuatro saltos en un gráfico de objetos para leer una sola marca booleana o de números enteros, eleva o almacena en caché ese estado en un array plano o una máscara de bits indexada por un ID denso.
  • Evita capturar lambdas genéricas o de captura en bucles internos ajustados: Usa bucles for indexados estándar en listas RandomAccess en lugar de cadenas de iteradores o forEach para evitar asignaciones de iteradores, despacho megamórfico y sobrecarga de verificación de tipo en tiempo de ejecución.

← Threads | ↑ Arriba | Vinculaciones de servicios →