Optimiza el rendimiento del CPU con instrumentos

Hola, soy Matt y soy OS Kernel Engineer. Hoy te enseñaré cómo usar Instruments para optimizar el código para los CPU con chip de Apple. El uso eficiente del CPU evita retrasos al procesar grandes volúmenes de datos o responder rápido a las interacciones. Pero predecir el rendimiento del software es difícil por dos razones. Lo primero son las capas de abstracción entre el código fuente de Swift y lo que realmente termina ejecutándose. El código fuente que escribes para tu app se compila en instrucciones de máquina que se ejecutan en un CPU. Pero el código no se ejecuta de forma aislada: Se complementa con código de soporte generado por el compilador, el entorno de ejecución Swift y otras estructuras, que invocan llamadas del sistema de kernel para manejar operaciones en nombre de tu app.

Esto hace que sea difícil conocer el costo de las abstracciones de software de las que depende tu código. La segunda razón por la que es difícil predecir el desempeño del código es cómo el CPU ejecuta las instrucciones recibidas. Dentro de un CPU, sus unidades funcionales trabajan en paralelo para ejecutar instrucciones eficientemente. Para hacer esto, las instrucciones se ejecutarán fuera de orden, dando solo la apariencia de ejecución en orden. Los CPU también se benefician de varias capas de caché de memoria que garantizan un acceso rápido a los datos. Estas características aceleran patrones de codificación comunes, como escaneos lineales o verificaciones defensivas, como salidas anticipadas para condiciones inusuales. Pero algunas estructuras de datos, algoritmos o enfoques de implementación son difíciles de ejecutar para el CPU sin una optimización cuidadosa o una reestructuración significativa. Te mostraré la forma correcta de optimizar tu código para el CPU. Veremos cómo abordar las investigaciones de desempeño, para enfocarnos primero en las aceleraciones potenciales. Para identificar el uso excesivo de CPU en el código, veremos los métodos tradicionales de creación de perfiles. Usaremos Processor Trace para registrar cada Instrucción y medir costos de abstracción del software. Usaremos CPU Counters para analizar los cuellos de botella del CPU y entender cómo microoptimizar nuestro algoritmo. Comencemos por ponernos en la mentalidad adecuada para abordar las investigaciones de desempeño. El primer paso es mantener la mente abierta: Las fuentes de desaceleración pueden ser sorprendentes e inesperadas. Recopila datos para probar suposiciones y verificar que el modelo mental de cómo se ejecuta el código sea preciso.

Considera otras causas de ralentizaciones además del rendimiento del CPU de un solo hilo. Además de ejecutarse en un CPU, los hilos y las tareas también pueden pasar tiempo bloqueados, esperando recursos como archivos o acceso a un estado mutable compartido. La sesión “Visualizar y optimizar la concurrencia en Swift” cubre herramientas para comprender por qué las tareas podrían estar fuera del CPU.

Cuando los hilos no están bloqueados y están en el CPU, es posible que haya una API que se usando incorrectamente, como aplicar una clase de calidad de servicio incorrecta al código. Lee la documentación sobre cómo ajustar el rendimiento del código para obtener más detalles. Pero si el problema es la eficiencia, hay que cambiar el algoritmo y sus estructuras de datos asociadas o la implementación, que es cómo se expresa el algoritmo en el lenguaje de programación. Utilice herramientas para determinar en qué ramas de este árbol debe centrarse primero. Prueba el medidor de CPU integrado de Xcode para detectar si los CPU se usan mucho mientras interactúas con la app. Para analizar los comportamientos de bloqueo entre hilos y qué hilos finalmente los desbloquearán, usa la herramienta System Trace.

Para problemas que afecten la UI o el hilo principal de tu app, usa la herramienta especializada Hangs. En “Análisis de interrupciones con Instruments” se explica cómo confirmar que debe optimizarse el uso de CPU en tu app. Pero incluso con la guía de las herramientas, ten cuidado con los tipos de optimizaciones que implementas. La microoptimización despiadada puede hacer que sea más difícil ampliar el código y razonar sobre él. Y a menudo depende de optimizaciones del compilador que pueden ser frágiles, como vectorización automática. Antes de usar microoptimización intrusiva, busca alternativas que eviten operaciones lentas por completo. Considera por qué se ejecuta el código en primer lugar. Quizás puedas evitar el trabajo y simplemente eliminar el código. Gracias por acompañarnos y... Es broma. Esto suele ser imposible, pero es útil para verificar suposiciones sobre la importancia de los resultados.

Podrías hacer el trabajo más tarde, fuera de la ruta crítica, o solo cuando los resultados sean visibles. De la misma manera, precalcular valores también puede ocultar el tiempo que lleva completar el trabajo. Esto podría incluso implicar la incorporación de valores en el momento de la compilación. Pero estos enfoques podrían consumir energía innecesariamente o ampliar el tamaño de descarga de tu app. Para operaciones repetidas con las mismas entradas, el almacenamiento en caché es otra solución, pero una que a menudo trae su propio conjunto de problemas difíciles, como la invalidación de caché. Una vez que no puedas evitar el trabajo que afecta el rendimiento, necesitarás que el CPU trabaje más rápido. En esto nos centraremos hoy. Prioriza tus esfuerzos de optimización en el código que tendrá el mayor impacto en la experiencia del usuario. Generalmente, se trata de un código en la ruta crítica de alguien que interactúa con tu app, donde notará problemas de rendimiento, pero también pueden ser operaciones que consumen más energía. En esta sesión, nos centraremos en buscar en listas de números enteros porque está en la ruta crítica de mi app.

Mi app ya usa la búsqueda binaria, un algoritmo clásico que usa un conjunto ordenado para encontrar un elemento dividiendo sucesivamente a la mitad el espacio de búsqueda. En este ejemplo, hay 16 elementos en el conjunto y buscamos el elemento que contiene el número 5. Cinco es menor que el elemento en el medio del conjunto, 20, por lo que su elemento debe estar en la primera mitad. Cinco también es menor que el elemento en el medio de la primera mitad, nueve, y debe estar en el primer cuarto. Nos centramos en el elemento coincidente después de comparar con tres, en solo cuatro pasos. Esta es la implementación de búsqueda binaria de una estructura que mi app usa. Es una función independiente que usa la metáfora de encontrar una aguja en un pajar para sus parámetros. Permite buscar una aguja comparable en la colección de pajares. El algoritmo rastrea dos variables: El inicio del área de búsqueda actual en inicio y el número de elementos restantes para buscar en longitud. Mientras quedan elementos por buscar, se comprueba el valor medio del espacio de búsqueda. Si la aguja es menor que el valor, entonces solo reduce a la mitad el espacio de búsqueda, y deja el inicio intacto. Si la aguja es igual, entonces se encontró el elemento y se devuelve el índice medio. Si no, ajusta la posición inicial tras el elemento central y reduce el espacio de búsqueda a la mitad.

Optimizaremos este algoritmo de forma incremental, confirmando en cada paso el progreso comparando el rendimiento de la búsqueda, o la cantidad de búsquedas que se pueden completar cada segundo. No te limites a dar pasos agigantados cada vez que realices un cambio: Las optimizaciones pueden ser difíciles de cuantificar, pero las pequeñas mejoras se sumarán con el tiempo.

Para optimizar de forma continua, escribí una prueba automatizada para medir el rendimiento de la búsqueda. No hace falta una configuración particularmente robusta: solo queremos una estimación del rendimiento. Este bucle repeat-while invoca la función de búsqueda hasta que se cumpla la duración especificada. Uso un intervalo OS signpost en las llamadas de búsqueda para enfocar las herramientas en la parte por optimizar. Y elegí la categoría de puntos de interés ya que Instruments la incluye por defecto. La temporización usa ContinuousClock, que no retrocede y tiene baja sobrecarga, a diferencia de Date. Es un enfoque simple pero efectivo para recopilar datos aproximados sobre el rendimiento del algoritmo. Mi prueba se llama searchCollection y simula cómo mi app usa la búsqueda binaria. Ejecutaremos las búsquedas durante un segundo con un nombre descriptivo para los signpost, en caso de que ejecutemos varias pruebas en una sola grabación. Un bucle dentro del cierre invocará la función de búsqueda binaria para amortizar el costo de verificar el tiempo. Ejecutemos esta prueba con Instruments para analizar el desempeño de la búsqueda binaria en el CPU. Hay dos perfiladores centrados en el CPU para elegir: Time Profiler y CPU Profiler. Time Profiler muestrea periódicamente lo que corre en los CPU del sistema, basado en un temporizador. Aquí, tenemos un trabajo que se realiza en dos CPU. En cada punto de muestra, Time Profiler captura las pilas de llamadas del espacio de usuario de cada hilo que se ejecuta en el CPU.

Instruments puede ver esas muestras como un árbol de llamadas o un gráfico de llama en su vista detallada para brindar una aproximación de qué código es importante optimizar. Esto es útil para analizar cómo se distribuye el trabajo en el tiempo o qué hilos están activos al mismo tiempo. Pero el uso de un temporizador para muestrear pilas de llamadas sufre un problema llamado aliasing. El aliasing ocurre cuando el trabajo periódico del sistema coincide con la cadencia del temporizador de muestreo. Aquí, las regiones azules son responsables de la mayor parte del tiempo de CPU, pero las funciones naranjas se ejecutan siempre que el muestreador recopila una pila de llamadas. Esto hace que el color naranja esté excesivamente representado en el árbol de llamadas de Instruments.

Para evitar este problema, podemos usar CPU Profiler. Muestrea los CPU de forma independiente, en función de la frecuencia de reloj de cada CPU. Se prefiere CPU Profiler a Time Profiler para optimizar el CPU; es más preciso y pondera mejor el consumo de recursos.

Estas campanas representan cuándo el contador de ciclos del CPU muestrea la pila de llamadas en ejecución. Los CPU con chip de Apple son asimétricas y algunos funcionarán a una frecuencia de reloj más lenta que otros. Los CPU individuales que escalen su frecuencia se muestrean con más frecuencia, sin el sesgo de Time Profiler frente a los CPU de ejecución más rápida. Usaremos CPU Profiler para averiguar qué partes de mi función de búsqueda binaria consumen más ciclos de CPU. Desde Xcode, lanza Instruments desde una prueba unitaria: haz clic secundario en ella y toca “Profile”. En este caso, seleccionaremos Profile searchCollection.

Se abre Instruments y presenta el selector de plantilla. Elegiré CPU Profiler. En los ajustes de la grabadora, cambiemos al modo diferido para reducir la sobrecarga y comencemos a grabar. El modo inmediato predeterminado para los perfiladores es útil para confirmar la captura de interacciones con la app. Sin embargo, para una prueba automatizada en el mismo equipo que Instruments, queremos minimizar cualquier sobrecarga que puedan agregar nuestras herramientas al esperar hasta que la grabación se detenga para analizarla. A menudo, los documentos nuevos en Instruments pueden ser abrumadores. La ventana está dividida en dos mitades. La parte superior contiene las pistas que muestran la actividad en la línea de tiempo. Cada pista puede contener varias líneas con gráficos para indicar niveles o regiones.

Debajo de la línea de tiempo, en la vista detallada se resume el rango inspeccionado. Los detalles ampliados se muestran en el lado derecho. Para orientarnos, buscaremos la región donde se estén realizando las búsquedas en la pista de Puntos de interés. Al hacer clic secundario en la región, se ofrece establecer el intervalo de inspección, lo que limita la vista de detalle a solo los datos capturados en el intervalo de signpost. Haz clic en la pista del proceso de prueba para ver el perfil de CPU en la vista detallada. Esta vista muestra un árbol de llamadas de las funciones de prueba, muestreadas por el contador de ciclo de cada CPU. Manteniendo presionada la Opción y haciendo clic en el chevrón junto a la primera función, se expande el árbol hasta donde las muestras divergen, cerca de nuestra búsqueda binaria. Nos centraremos en la función de búsqueda binaria haciendo clic en la flecha junto a su nombre y seleccionando el elemento Focus on Subtree. Cada función se pondera mediante el recuento de muestras multiplicado por el número de ciclos entre cada muestra. Este árbol de llamadas muestra muchos ejemplos tomados en funciones llamadas por búsqueda binaria para tratar con el tipo Collection. Este testigo de protocolo aparece en una cuarta parte de nuestras muestras, aproximadamente. Hay asignaciones e incluso comprobaciones de Array para los tipos de Objective-C. Podemos evitar las sobrecargas de Array y los genéricos si cambiamos a un tipo de contenedor que coincida mejor con el tipo de datos que buscamos. Probemos el nuevo tipo de Lapso. Lapso puede usarse en lugar de Collection cuando los elementos se almacenan contiguamente en la memoria, algo común en muchas estructuras de datos. De hecho, es una dirección base y un recuento. Pero también evita que se escape o se filtre la referencia de memoria fuera de las funciones en las que se usa. Para obtener más información sobre Lapso, consulta “Mejorar el uso y el rendimiento de la memoria con Swift”. La adopción de Lapso solo requiere cambiar el tipo haystack y de retorno a Lapso; el algoritmo en sí no cambia.

Este pequeño cambio hace que la búsqueda sea cuatro veces más rápida. Esta búsqueda binaria aún afecta mi app; quiero ver si la comprobación de límites de Lapso causa sobrecarga. Para profundizar, cambiaremos a una nueva herramienta llamada Processor Trace. A partir de Instruments 16.3, Processor Trace puede recopilar un rastro completo de todas las instrucciones que el proceso de la app ejecuta en el espacio de usuario. Este es un cambio fundamental en la forma de medir el rendimiento del software: No hay sesgos de muestreo y solo un impacto insignificante del 1% en el rendimiento de la app. Processor Trace requiere funciones de CPU especializadas que solo están disponibles en la Mac y el iPad Pro con chip M4 o el iPhone con A18. Antes de continuar, necesitaremos configurar nuestro dispositivo para el rastreo del procesador. En una Mac, activa el ajuste en Privacidad y seguridad y Herramientas para desarrolladores. En el iPhone o iPad, el ajuste está en la sección Desarrollador. Para disfrutar de la mejor experiencia con el rastreo del procesador, intenta limitarlo a solo unos segundos. No es necesario agrupar el trabajo, a diferencia del muestreo con CPU Profiler: Incluso una sola instancia del código que quieres optimizar puede ser suficiente. Ejecutemos Processor Trace en la versión de intervalo de la búsqueda binaria. Nuestra prueba ahora solo necesita algunas iteraciones. Para perfilar esta prueba, haré clic secundario en el ícono de prueba en el medianil del número de línea. Esto muestra el mismo menú que el que usamos antes, pero puede ser más conveniente que cambiar de navegador. Seleccionaré la plantilla Processor Trace y empezaré a grabar.

Processor Trace maneja una gran cantidad de datos, y capturarlos y analizarlos lleva tiempo. Processor Trace configura el CPU para registrar cada decisión de ramificación. El recuento de ciclos y el tiempo actual también se registran para hacer un rastreo del tiempo que se pasa en cada función. A continuación, Instruments usa los archivos binarios ejecutables de la app y la estructura del sistema para reconstruir una ruta de ejecución y anotar las llamadas a funciones con los ciclos transcurridos y las duraciones. Limitamos el tiempo empleado en el rastreo porque, aunque el CPU esté registrando la menor cantidad de información posible, esta puede ser de gigabytes de datos por segundo para una app de varios hilos. Con el documento listo, ampliemos para inspeccionar las llamadas a la función de búsqueda binaria. La búsqueda ahora solo ocupa una parte de toda la grabación, por lo que la veremos en la lista Regions of Interest en la vista detallada, haremos clic secundario en su fila y seleccionaremos Set Inspection Range and Zoom. Para localizar el hilo que está ejecutando la búsqueda binaria, haremos clic secundario en la celda Start Thread y seleccionaremos Pin Thread in Timeline.

Processor Trace agrega un nuevo gráfico de llama de llamada de función a cada pista de hilo, así que arrastraré el divisor del marcador hacia arriba para dejar espacio.

Processor Trace muestra la ejecución visualmente como un gráfico de llama. Un gráfico de llama es una representación gráfica de los costos y las relaciones de las funciones: el ancho de las barras es el tiempo que tardó la función en ejecutarse y las filas son pilas de llamadas anidadas. Pero la mayoría de los gráficos de llamas tienen datos del muestreo y su costo es solo una estimación basada en un recuento de muestras. El gráfico de llamas de la línea de tiempo de Processor Trace es diferente: muestra las llamadas realizadas en el tiempo exactamente como se habrían ejecutado en el CPU. Los colores de cada barra representan los tipos de binarios de los que proceden: marrón para las estructuras del sistema, magenta para el tiempo de ejecución de Swift y la biblioteca estándar, y azul para el código compilado en el binario de la app o estructuras personalizadas. La primera parte de este rastro muestra la sobrecarga de emitir el signpost, así que acerquémonos al código de búsqueda binaria casi al final del rango. Mantendré presionada la opción, haré clic y arrastraré por la línea de tiempo para ampliar.

Puedo seleccionar cualquier llamada de función de búsqueda binaria de las diez iteraciones y establecer el rango de inspección y el zoom con un clic secundario. Esta es la potencia de Processor Trace: podemos ver todas las llamadas realizadas por una función que se ejecuta durante unos pocos cientos de nanosegundos. Podríamos acercarnos más, pero usemos el resumen de Llamadas a funciones debajo de la línea de tiempo. Se muestra la misma información que en la línea de tiempo, pero como una tabla, con los nombres completos de las funciones que se llaman durante cortos períodos. Ordenaré esta tabla por ciclos.

Mi suposición inicial de que las comprobaciones de límites causaban ralentizaciones era incorrecta. Esta implementación de búsqueda binaria todavía está lidiando con sobrecargas generales de metadatos de protocolo y no puede incluir las comparaciones de números, lo que termina siendo un porcentaje considerable del recuento total de ciclos de la búsqueda. Esto es porque el parámetro genérico Comparable no está especificado para el tipo de elementos usados.

Como mi código está en una estructura vinculada por mi app, el compilador de Swift no puede producir una versión especializada de búsqueda binaria, solo para los tipos pasados por los llamadores.

Cuando esto cause sobrecargas en código de una estructura, deberías agregar la anotación inlinable a la función de la estructura para generar implementaciones especializadas dentro de los binarios ejecutables del cliente de la estructura.

Pero la inserción puede hacer que el código sea más difícil de analizar porque se mezcla con los llamadores. Me gustaría evitar la incrustación en el arnés de prueba, así que para esta función, la especializaré manualmente para el tipo Int usado por la app y la prueba, con un nuevo nombre de función. El código pierde mucha generalidad y se vuelve aproximadamente 1.7 veces más rápido. Tenemos que seguir optimizando porque la búsqueda binaria sigue contribuyendo a la ralentización de la app. Es bastante extraño dedicar tanto tiempo a optimizar una función que periódicamente se vuelve a evaluar y se recopilan más datos ya que es posible que más adelante encuentres otras ineficiencias de código. Nuestra búsqueda binaria especializada de intervalo tampoco muestra ninguna llamada inesperada a una función en Processor Trace, por lo que debemos comprender cómo se ejecuta el código en el CPU para seguir avanzando. Con el instrumento CPU Counters, podemos averiguar qué cuellos de botella tiene el código al ejecutarse en el CPU. Antes de empezar a usar Instruments de nuevo, necesitamos un modelo mental de cómo funciona un CPU. Básicamente, un CPU solo sigue una lista de instrucciones, modifica registros y memoria, e interactúa con dispositivos periféricos.

Cuando un CPU se está ejecutando, tiene que seguir una serie de pasos, que se clasifican en dos fases. La primera es el envío de instrucciones para asegurar que el CPU tiene instrucciones que ejecutar. A continuación, Procesamiento de instrucciones se encarga de ejecutarlas. Las instrucciones se obtienen y decodifican en microoperaciones, más fáciles de ejecutar para el CPU. La mayoría de las instrucciones se decodifican en una única microoperación, pero algunas instrucciones hacen varias cosas, como emitir una solicitud de memoria. Las microoperaciones se envían a unidades de mapa y programación para enrutarlas y despacharlas. Desde allí, la operación se asigna a una unidad de ejecución, o a la unidad de carga y almacenamiento si la operación necesita acceder a la memoria.

Sería bastante lento si el CPU tuviera que ejecutar estas fases en serie antes de poder comenzar a buscar nuevamente, por eso los procesadores con chip de Apple están canalizados. Una vez que una unidad termina su trabajo, puede pasar a la siguiente operación, lo que mantiene a cada unidad ocupada.

La canalización y la creación de copias adicionales de las unidades de ejecución favorecen el paralelismo a nivel de instrucción.

Es distinto del paralelismo a nivel de proceso o hilo, donde varios CPU ejecutan diferentes hilos del OS. El paralelismo a nivel de instrucciones permite que un solo CPU aproveche los momentos en los que las unidades podrían estar inactivas y use los recursos de hardware de manera eficiente. El código fuente de Swift no controla directamente este paralelismo, sino que debe ayudar al compilador a generar una secuencia de instrucciones adecuada.

Desafortunadamente, las secuencias de instrucciones paralelizables no son inmediatamente intuitivas debido a la interacción entre unidades en un CPU. Cada flecha muestra dónde se atascan las operaciones en la canalización, limitando el paralelismo disponible. A estos los llamamos cuellos de botella.

Para descubrir qué cuello de botella es relevante, los CPU con chip de Apple pueden contar eventos interesantes en cada unidad y otras características de las instrucciones ejecutadas. El instrumento CPU Counters lee estos contadores para generar métricas de nivel superior a partir de ellos. Este año, agregamos modos preestablecidos para estos contadores para que sean mucho más fáciles de usar. Instruments los usa con una metodología iterativa y guiada para analizar el rendimiento del código, denominada Análisis de cuellos de botella. Usémoslo para descubrir por qué nuestra búsqueda binaria sigue siendo lenta, a pesar de no tener ninguna sobrecarga aparente en las llamadas a funciones. El instrumento CPU Counters se basa en el muestreo de la carga de trabajo, por lo que debemos volver al arnés de prueba que usamos con CPU Profiler para medir el rendimiento nuevamente. Vamos a perfilar la prueba de implementación especializada de Lapso con Instruments.

Seleccionaremos la plantilla CPU Counters.

Ahora hay una configuración guiada con modos seleccionados para medir.

Para obtener más información sobre cada modo, haz clic en el ícono de información junto a la selección de modo. Comencemos a contar.

Este modo inicial de CPU Bottlenecks divide el trabajo realizado por el CPU en cuatro categorías amplias que dan cuenta de todo el rendimiento potencial del CPU. Los instrumentos muestran estas categorías como un gráfico de barras apiladas de colores y una tabla de resumen en la vista detallada. Durante la grabación, Instruments recopilará datos del contador de CPU para los hilos usados en nuestra prueba y los convertirán en porcentajes de cuello de botella. Usaremos los Puntos de Interés para orientarnos, para hacer zoom y seleccionar nuestras búsquedas.

Luego, anclaremos el hilo que ejecuta nuestra implementación de búsqueda binaria a la línea de tiempo.

Al pasar el cursor sobre el carril de cuello de botella, se ve un alto porcentaje de cuellos de botella descartados. En la vista detallada a continuación se muestran las agregaciones métricas en el rango de inspección. Al seleccionar la fila Cuellos de botella descartados se muestra una descripción extendida a la derecha. Instruments también ofrece un comentario encima del gráfico en la línea de tiempo. Al hacer clic en ese comentario se muestran más detalles a continuación. Esto es útil, pero todavía no sé qué parte de la búsqueda es responsable del cuello de botella. Al hacer clic secundario en la celda Discarded Sampling debajo de la columna Suggested Next Mode, se ofrece la opción de perfilar nuevamente la carga de trabajo con un modo diferente. Vamos a probarlo. Este modo es un poco diferente de CPU Bottlenecks. Todavía está recopilando datos del contador, pero también está configurando contadores para activar el muestreo. Los datos de muestra se limitan a la instrucción que genera el trabajo descartado. Para demostrarlo, orientémonos nuevamente con Puntos de interés.

Seleccionamos la pista del proceso de prueba y vamos a Muestras de instrucciones bajo la línea de tiempo.

Esta no es una pila de llamadas, sino la instrucción exacta que está causando el problema. Podemos abrir Source Viewer haciendo clic en la flecha junto al nombre de la función para mostrar el código fuente que se muestreó porque el CPU siguió la dirección de rama incorrecta. En este caso, las comparaciones que se realizan entre la aguja y el valor medio se predicen erróneamente. Para entender por qué estas líneas fuente son responsables de tantas predicciones erróneas, necesitamos aprender un poco más sobre los CPU.

Los CPU son furtivos y ejecutan instrucciones fuera de orden. Solo parece que las instrucciones se ejecutan secuencialmente gracias a un paso de reordenamiento adicional a medida que se completan las instrucciones. Esto significa que los CPU miran hacia adelante y hacen predicciones sobre qué instrucciones se ejecutarán a continuación. Los predictores de ramificaciones responsables suelen ser precisos, pero pueden tomar caminos equivocados cuando no existe un patrón consistente a partir de una ejecución previa.

El bucle de nuestro algoritmo de búsqueda binaria tiene dos tipos de ramas. La primera condición del bucle usualmente se cumple hasta el final, por lo que se predijo bien y no apareció en el muestreo. Pero la comprobación de la aguja es, en esencia, una ramificación aleatoria, por lo que no sorprende que los predictores tengan problemas con ella.

Reescribí el cuerpo del bucle para evitar ramas difíciles de predecir que afecten el flujo de control. El cuerpo de la sentencia if solo asigna un valor según la condición. Esto permite que el compilador Swift genere una instrucción de movimiento condicional y evite la ramificación a una instrucción diferente. Para regresar de una función o romper un bucle en función de una condición se debe implementar con una rama, por lo que también tuve que eliminar el retorno anticipado. Utilicé aritmética sin verificación para evitar ramificaciones que terminarían el programa. Esta es una de las áreas en las que la microoptimización se vuelve frágil y fácil de interrumpir, además de ser menos segura y comprensible. Cuando realizamos un cambio como este, debemos volver al modo CPU Bottlenecks inicial para verificar cómo impacta al resto de cuellos de botella. Ya recopilé un rastro de nuestra nueva búsqueda binaria sin ramificaciones, que ahora es aproximadamente el doble de rápida que la versión ramificada. Actualmente el procesamiento de instrucciones está casi completamente limitado. Instruments indica que debemos volver a ejecutar la carga de trabajo con el modo de procesamiento de instrucciones.

Ese modo tenía comentarios que recomendaban ejecutar el modo de Muestreo de fallos de caché L1D. Los ejemplos de fallos de caché muestran que acceder a la memoria desde el conjunto es la razón por la que el CPU no puede ejecutar instrucciones de manera eficiente. Aprendamos más sobre los CPU y la memoria para descubrir por qué.

Los CPU acceden a la memoria a través de una jerarquía de cachés que hacen que los accesos repetidos a la misma dirección, o incluso a patrones de acceso predecibles, sean mucho más rápidos. Comienza con las cachés L1 que se encuentran dentro de cada CPU. Estos no pueden almacenar muchos datos, pero ofrecen el acceso más rápido a la memoria. Una caché L2 más lento se ubica fuera de los CPU y proporciona mucho más margen. Y, por último, las solicitudes que omiten ambas cachés y necesitan acceder a la memoria principal se vuelven 50 veces más lentas que la ruta rápida. Estas cachés también agrupan la memoria en segmentos de 64 o 128 bytes llamados líneas de caché: Incluso si una instrucción solo solicita 4 bytes, las cachés extraerán más datos con la expectativa de que las instrucciones posteriores necesitarán acceder a otros bytes cercanos.

Consideremos cómo esto afecta nuestro algoritmo de búsqueda binaria. En este ejemplo, las líneas azules son elementos del conjunto, mientras que las cápsulas grises son líneas de caché en las que operan las cachés del CPU.

El conjunto comienza completamente fuera de la caché. La primera comparación incorpora una línea de caché y varios elementos en la caché de datos L1. Pero la siguiente comparación tiene un fallo de caché. Las iteraciones siguientes siguen fallando en la caché. Esto continúa hasta que la búsqueda se centra en una región del tamaño de una línea de caché. La búsqueda binaria resulta ser un caso patológico de la jerarquía de memoria del CPU.

Pero si podemos tolerar reordenar los elementos para que sean más amigables con la caché, entonces podemos colocar los puntos de búsqueda en la misma línea de caché. Este diseño se denomina diseño de Eytzinger, en honor a un genealogista austríaco del siglo XVI que organizó los árboles genealógicos de esta manera. Esta no es una optimización general que podamos realizar sin consecuencias significativas. Esto mejora la velocidad de búsqueda a costa de la velocidad de recorrido en orden, lo que hace que esa operación ahora falle en la caché. Vayamos al primer ejemplo de búsqueda binaria para ver cómo reorganizar un conjunto ordenado en diseño Eytzinger. Comenzando con el elemento del medio como raíz, modelaremos la operación de búsqueda binaria como un árbol, donde los puntos medios son nodos descendientes. Un diseño de Eytzinger se organiza como una travesía en anchura de ese árbol.

Los elementos más cercanos a la raíz del árbol están organizados más densamente y es más probable que compartan líneas de caché. Al buscar el número 5, ahora los primeros tres pasos se realizan en la misma línea de caché. Los nodos de hoja se ordenan al final del conjunto, lo que provocará un fallo de caché inevitable.

Grabé un rastro de CPU Bottlenecks de la búsqueda binaria de Eytzinger, que muestra que es dos veces más rápido que la búsqueda sin ramificación. Pero esto resalta algo interesante: técnicamente, aún hay un cuello de botella en el procesamiento de instrucciones. Hicimos que nuestra implementación sea más compatible con la caché, pero la carga de trabajo todavía está inherentemente limitada a la memoria.

Debes monitorear el rendimiento para saber cuándo detenerte y optimizar otro código en tu app, porque nuestra búsqueda ahora ya no afecta el rendimiento de la ruta crítica. Durante este proceso, mejoramos significativamente el rendimiento de la búsqueda. Primero, con CPU Profiler al cambiar de Collection a Lapso, obtuvimos una aceleración significativa.

Luego, con Processor Trace vimos las sobrecargas de los genéricos no especializados. Por último, con algunas microoptimizaciones guiadas por análisis de cuellos de botella, mejoró el desempeño. En general, hicimos que nuestra función de búsqueda sea aproximadamente 25 veces más rápida con Instruments. Para lograr estas aceleraciones, comenzamos con la mentalidad correcta, usando herramientas para confirmar nuestras conjeturas y desarrollar una intuición sobre el costo de las abstracciones. Aplicamos sucesivamente herramientas más detalladas para encontrar sobrecargas inesperadas. Estas fueron tan fáciles de abordar como lo son de pasar por alto, si realmente no se miden. Luego, una vez abordadas las sobrecargas del software, analizamos las optimizaciones centradas en los cuellos de botella del CPU. Nos volvimos más conscientes de las funciones del CPU que se dan por sentadas. Esta orden era importante: tenemos que asegurarnos de que las herramientas centradas en el CPU no se confundan con sobrecargas de tiempo de ejecución de software adicionales.

Para aplicar esto a tus propias apps, recopila datos y sigue las pistas con una mentalidad de rendimiento. Escribe pruebas de rendimiento para que puedas medir repetidamente con estos instrumentos. Proporciona comentarios o haz preguntas sobre el uso de las herramientas en los foros. Mira las sesiones que mencioné anteriormente y la sesión de la WWDC24 sobre el rendimiento de Swift: permitirá construir un modelo mental más preciso de los costos de las potentes abstracciones. Lee la Guía de optimización de CPU con chip de Apple, para comprender mejor cómo los CPU ejecutan tu código. Gracias por acompañarnos y espero que te diviertas usando Instruments para encontrar agujas de optimización en los pajares de tu código.