En Android 17, las apps que se segmenten para el SDK 37 o versiones posteriores recibirán una nueva implementación de MessageQueue en la que la implementación no tiene bloqueos. La nueva implementación mejora el rendimiento y reduce los fotogramas perdidos, pero puede interrumpir los clientes que reflejan los campos y métodos privados de MessageQueue. Para obtener más información sobre el cambio de comportamiento y cómo mitigar su impacto, consulta la documentación sobre el cambio de comportamiento de MessageQueue. En esta entrada de blog técnica, se proporciona una descripción general de la rearquitectura de MessageQueue y cómo puedes analizar los problemas de contención de bloqueo con Perfetto.

El Looper controla el subproceso de IU de cada aplicación para Android. Extrae trabajo de una MessageQueue, lo envía a un Handler y repite el proceso. Durante dos décadas, MessageQueue usó un solo bloqueo de monitor (es decir, un bloque de código synchronized) para proteger su estado.

Android 17 introduce una actualización importante en este componente: una implementación sin bloqueo llamada DeliQueue.

En esta publicación, se explica cómo los bloqueos afectan el rendimiento de la IU, cómo analizar estos problemas con Perfetto y los algoritmos y las optimizaciones específicos que se usan para mejorar el subproceso principal de Android.

El problema: Contención de bloqueo e inversión de prioridad

La función MessageQueue heredada funcionaba como una cola de prioridad protegida por un solo bloqueo. Si un subproceso en segundo plano publica un mensaje mientras el subproceso principal realiza el mantenimiento de la cola, el subproceso en segundo plano bloquea el subproceso principal.

Cuando dos o más subprocesos compiten por el uso exclusivo del mismo bloqueo, se denomina contención de bloqueo. Esta contención puede causar una inversión de prioridad, lo que genera bloqueos de IU y otros problemas de rendimiento.

La inversión de prioridad puede ocurrir cuando se hace esperar a un subproceso de alta prioridad (como el subproceso de la IU) por un subproceso de baja prioridad. Considera esta secuencia:

1. Un subproceso en segundo plano de baja prioridad adquiere el bloqueo MessageQueue para publicar el resultado del trabajo que realizó.
2. Un subproceso de prioridad media se vuelve ejecutable y el programador del kernel le asigna tiempo de CPU, lo que interrumpe el subproceso de prioridad baja.
3. El subproceso de IU de alta prioridad finaliza su tarea actual y trata de leer desde la cola, pero se bloquea porque el subproceso de baja prioridad mantiene el bloqueo.

El subproceso de prioridad baja bloquea el subproceso de IU, y el trabajo de prioridad media lo retrasa aún más.

Cómo analizar la contención con Perfetto

Puedes diagnosticar estos problemas con Perfetto. En un registro estándar, un subproceso bloqueado en un bloqueo de monitor entra en el estado de suspensión, y Perfetto muestra un segmento que indica el propietario del bloqueo.

Cuando consultes los datos de seguimiento, busca segmentos llamados "monitor contention with…" seguidos del nombre del subproceso que posee el bloqueo y el sitio de código en el que se adquirió el bloqueo.

Caso de éxito: Jank del selector

Para ilustrarlo, analicemos un registro en el que un usuario experimentó tirones mientras navegaba a la página principal en un teléfono Pixel inmediatamente después de tomar una foto en la app de la cámara. A continuación, vemos una captura de pantalla de Perfetto que muestra los eventos que provocaron la pérdida del fotograma:

• Síntoma: El subproceso principal del Launcher no cumplió con el plazo del fotograma. Se bloqueó durante 18 ms, lo que supera el plazo de 16 ms requerido para la renderización de 60 Hz.
• Diagnóstico: Perfetto mostró que el subproceso principal estaba bloqueado en el bloqueo MessageQueue. Un subproceso “BackgroundExecutor” era propietario del bloqueo.
• Causa raíz: BackgroundExecutor se ejecuta en Process.THREAD_PRIORITY_BACKGROUND (prioridad muy baja). Realizó una tarea no urgente (verificar los límites de uso de la app). Al mismo tiempo, los subprocesos de prioridad media usaban tiempo de CPU para procesar datos de la cámara. El programador del SO interrumpió el subproceso de BackgroundExecutor para ejecutar los subprocesos de la cámara.

Esta secuencia hizo que el subproceso de IU del Launcher (alta prioridad) se bloqueara indirectamente por el subproceso de trabajador de la cámara (prioridad media), lo que impedía que el subproceso en segundo plano del Launcher (prioridad baja) liberara el bloqueo.

Cómo consultar registros con PerfettoSQL

Puedes usar PerfettoSQL para consultar datos de seguimiento en busca de patrones específicos. Esto es útil si tienes una gran cantidad de registros de dispositivos o pruebas de usuarios, y buscas registros específicos que demuestren un problema.

Por ejemplo, esta consulta encuentra la contención de MessageQueue que coincide con los fotogramas descartados (lag):

INCLUDE PERFETTO MODULE android.monitor_contention;
INCLUDE PERFETTO MODULE android.frames.jank_type;

SELECT
  process_name,
  -- Convert duration from nanoseconds to milliseconds
  SUM(dur) / 1000000 AS sum_dur_ms,
  COUNT(*) AS count_contention
FROM android_monitor_contention
WHERE is_blocked_thread_main
AND short_blocked_method LIKE "%MessageQueue%" 

-- Only look at app processes that had jank
AND upid IN (
  SELECT DISTINCT(upid)
  FROM actual_frame_timeline_slice
  WHERE android_is_app_jank_type(jank_type) = TRUE
)
GROUP BY process_name
ORDER BY SUM(dur) DESC;

En este ejemplo más complejo, une los datos de registro que abarcan varias tablas para identificar la contención de MessageQueue durante el inicio de la app:

INCLUDE PERFETTO MODULE android.monitor_contention; 
INCLUDE PERFETTO MODULE android.startup.startups; 

-- Join package and process information for startups
DROP VIEW IF EXISTS startups; 
CREATE VIEW startups AS 
SELECT startup_id, ts, dur, upid 
FROM android_startups 
JOIN android_startup_processes USING(startup_id); 

-- Intersect monitor contention with startups in the same process.
DROP TABLE IF EXISTS monitor_contention_during_startup; 
CREATE VIRTUAL TABLE monitor_contention_during_startup 
USING SPAN_JOIN(android_monitor_contention PARTITIONED upid, startups PARTITIONED upid); 

SELECT 
  process_name, 
  SUM(dur) / 1000000 AS sum_dur_ms, 
  COUNT(*) AS count_contention 
FROM monitor_contention_during_startup 
WHERE is_blocked_thread_main 
AND short_blocked_method LIKE "%MessageQueue%" 
GROUP BY process_name 
ORDER BY SUM(dur) DESC;

Puedes usar tu LLM favorito para escribir consultas de PerfettoSQL y encontrar otros patrones.

En Google, usamos BigTrace para ejecutar consultas de PerfettoSQL en millones de registros. Al hacerlo, confirmamos que lo que observamos de forma anecdótica era, de hecho, un problema sistémico. Los datos revelaron que MessageQueue la contención de bloqueo afecta a los usuarios en todo el ecosistema, lo que justifica la necesidad de un cambio arquitectónico fundamental.

Solución: Concurrencia sin bloqueos

Abordamos el problema de MessageQueue contención implementando una estructura de datos sin bloqueo, que usa operaciones de memoria atómicas en lugar de bloqueos exclusivos para sincronizar el acceso al estado compartido. Una estructura de datos o un algoritmo no tienen bloqueos si al menos un subproceso siempre puede avanzar, independientemente del comportamiento de programación de los demás subprocesos. Por lo general, esta propiedad es difícil de lograr y no suele valer la pena buscarla para la mayoría del código.

Las primitivas atómicas

El software sin bloqueo a menudo se basa en primitivas atómicas de lectura-modificación-escritura que proporciona el hardware.

En las CPU ARM64 de generaciones anteriores, las operaciones atómicas usaban un bucle de carga vinculada/almacenamiento condicional (LL/SC). La CPU carga un valor y marca la dirección. Si otro subproceso escribe en esa dirección, el almacenamiento falla y el bucle vuelve a intentarlo. Debido a que los subprocesos pueden seguir intentando y tener éxito sin esperar a otro subproceso, esta operación no requiere bloqueo.

ARM64 LL/SC loop example
retry:
    ldxr    x0, [x1]        // Load exclusive from address x1 to x0
    add     x0, x0, #1      // Increment value by 1
    stxr    w2, x0, [x1]    // Store exclusive.
                            // w2 gets 0 on success, 1 on failure
    cbnz    w2, retry       // If w2 is non-zero (failed), branch to retr

(ver en Compiler Explorer)

Las arquitecturas ARM más recientes (ARMv8.1) admiten extensiones grandes del sistema (LSE), que incluyen instrucciones en forma de Compare-And-Swap (CAS) o Load-And-Add (que se muestran a continuación). En Android 17, agregamos compatibilidad con el compilador de Android Runtime (ART) para detectar cuándo se admite LSE y emitir instrucciones optimizadas:

/ ARMv8.1 LSE atomic example
ldadd   x0, x1, [x2]    // Atomic load-add.
                        // Faster, no loop required.

En nuestras comparativas, el código de alta contención que usa CAS logra una aceleración de aproximadamente 3 veces en comparación con la variante LL/SC.

El lenguaje de programación Java ofrece primitivas atómicas a través de java.util.concurrent.atomic, que se basan en estas y otras instrucciones especializadas de la CPU.

La estructura de datos: DeliQueue

Para quitar la contención de bloqueo de MessageQueue, nuestros ingenieros diseñaron una nueva estructura de datos llamada DeliQueue. DeliQueue separa la inserción de Message del procesamiento de Message:

1. La lista de Messages (pila de Treiber): Es una pila sin bloqueos. Cualquier subproceso puede insertar nuevos Messages aquí sin contención.
2. La cola de prioridad (min-heap): Es un heap de Messages que se controla y es propiedad exclusiva del subproceso Looper (por lo tanto, no se necesita sincronización ni bloqueos para acceder a él).

Enqueue: Envío a una pila de Treiber

La lista de Messages se mantiene en una pila de Treiber [1], una pila sin bloqueo que usa un bucle de CAS para actualizar el puntero de encabezado.

public class TreiberStack <E> {
    AtomicReference<Node<E>> top =
            new AtomicReference<Node<E>>();
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = top.get();
            if (oldHead == null) return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }
}

Código fuente basado en Java Concurrency in Practice [2], disponible en línea y publicado en el dominio público

Cualquier productor puede enviar nuevos Messages a la pila en cualquier momento. Es como sacar un número en la fila de una carnicería: tu número se determina según la hora a la que llegaste, pero el orden en el que recibes la comida no tiene que coincidir. Como es una pila vinculada, cada Message es una subpila. Puedes ver cómo era la cola de Message en cualquier momento haciendo un seguimiento del encabezado y realizando iteraciones hacia adelante. No verás ningún Message nuevo insertado en la parte superior, incluso si se agregan durante tu recorrido.

Dequeue: Transferencia masiva a un min-heap

Para encontrar el siguiente Message que debe controlar, el Looper procesa los nuevos Messages de la pila de Treiber recorriendo la pila desde la parte superior y realizando iteraciones hasta que encuentra el último Message que procesó anteriormente. A medida que Looper recorre la pila, inserta Messages en el min-heap ordenado por fecha límite. Dado que el Looper posee exclusivamente el heap, ordena y procesa los Messages sin bloqueos ni operaciones atómicas.

Al recorrer la pila, el Looper también crea vínculos desde los Message apilados hasta sus predecesores, lo que forma una lista doblemente vinculada. La creación de la lista vinculada es segura porque los vínculos que apuntan hacia abajo en la pila se agregan a través del algoritmo de pila de Treiber con CAS, y los vínculos que apuntan hacia arriba en la pila solo se leen y modifican con el subproceso Looper. Luego, estos vínculos se usan para quitar Messages de puntos arbitrarios en la pila en un tiempo O(1).

Este diseño proporciona una inserción de O(1) para los productores (hilos que publican trabajo en la cola) y un procesamiento amortizado de O(log N) para el consumidor (el Looper).

El uso de un heap mínimo para ordenar los Messages también aborda una falla fundamental en el MessageQueue heredado, en el que los Messages se mantenían en una lista vinculada de forma individual (con raíz en la parte superior). En la implementación heredada, la eliminación del encabezado era O(1), pero la inserción tenía un caso peor de O(N), lo que generaba un mal escalamiento para las colas sobrecargadas. Por el contrario, la inserción y la eliminación del min-heap se escalan de forma logarítmica, lo que ofrece un rendimiento promedio competitivo, pero destaca en las latencias finales.

En la implementación heredada de la cola, los productores y el consumidor usaban un bloqueo para coordinar el acceso exclusivo a la lista vinculada de forma individual subyacente. En DeliQueue, la pila de Treiber controla el acceso simultáneo, y el único consumidor controla el orden de su cola de trabajo.

Eliminación: Coherencia a través de lápidas

DeliQueue es una estructura de datos híbrida que une una pila de Treiber sin bloqueo con un min-heap de un solo subproceso. Mantener sincronizadas estas dos estructuras sin un bloqueo global presenta un desafío único: un mensaje podría estar presente físicamente en la pila, pero se quitaría lógicamente de la cola.

Para resolver este problema, DeliQueue usa una técnica llamada “tombstoning”. Cada Message hace un seguimiento de su posición en la pila a través de los punteros hacia atrás y hacia adelante, su índice en el array del montón y una marca booleana que indica si se quitó. Cuando un Message está listo para ejecutarse, el subproceso Looper CAS su marca de quitado y, luego, lo quita del montón y la pila.

Cuando otro subproceso necesita quitar un Message, no lo extrae de inmediato de la estructura de datos. En cambio, realiza los siguientes pasos:

1. Eliminación lógica: El subproceso usa un CAS para establecer de forma atómica la marca de eliminación de Message de falso a verdadero. El Message permanece en la estructura de datos como evidencia de su eliminación pendiente, lo que se conoce como “lápida”. Una vez que se marca un Message para su eliminación, DeliQueue lo trata como si ya no existiera en la fila cada vez que lo encuentra.
2. Limpieza diferida: La eliminación real de la estructura de datos es responsabilidad del subproceso Looper y se difiere hasta más adelante. En lugar de modificar la pila o el montón, el subproceso de eliminación agrega el Message a otra pila de lista libre sin bloqueo.
3. Eliminación estructural: Solo el Looper puede interactuar con el montón o quitar elementos de la pila. Cuando se activa, borra la lista de elementos libres y procesa los Messages que contenía. Luego, cada Message se desvincula de la pila y se quita del montón.  

Este enfoque mantiene toda la administración del montón en un solo subproceso. Minimiza la cantidad de operaciones simultáneas y barreras de memoria necesarias, lo que hace que la ruta crítica sea más rápida y simple.

Recorrido: Condiciones de carrera benignas del modelo de memoria de Java

La mayoría de las APIs de simultaneidad, como Future en la biblioteca estándar de Java, o Job y Deferred de Kotlin, incluyen un mecanismo para cancelar el trabajo antes de que se complete. Una instancia de una de estas clases coincide 1:1 con una unidad de trabajo subyacente, y llamar a cancel en un objeto cancela las operaciones específicas asociadas con él.

Los dispositivos Android actuales tienen CPU de varios núcleos y recolección de elementos no utilizados simultánea y generacional. Sin embargo, cuando se desarrolló Android por primera vez, era demasiado costoso asignar un objeto para cada unidad de trabajo. Por lo tanto, el Handler de Android admite la cancelación a través de numerosas sobrecargas de removeMessages. En lugar de quitar un Message específico, quita todos los Messages que coincidan con los criterios especificados. En la práctica, esto requiere iterar todos los Messages insertados antes de que se llamara a removeMessages y quitar los que coincidan.

Cuando se itera hacia adelante, un subproceso solo requiere una operación atómica ordenada para leer el encabezado actual de la pila. Después de eso, se usan lecturas de campos normales para encontrar el siguiente Message. Si el subproceso Looper modifica los campos next mientras quita Messages, la escritura de Looper y la lectura de otro subproceso no se sincronizan, lo que genera una condición de carrera de datos. Normalmente, una condición de carrera de datos es un error grave que puede causar grandes problemas en tu app, como fugas, bucles infinitos, fallas, bloqueos y mucho más. Sin embargo, en ciertas condiciones específicas, las condiciones de carrera pueden ser benignas dentro del modelo de memoria de Java. Supongamos que comenzamos con una pila de lo siguiente:

Realizamos una lectura atómica del encabezado y vemos A. El puntero siguiente de A apunta a B. Al mismo tiempo que procesamos B, el bucle podría quitar B y C actualizando A para que apunte a C y, luego, a D.

Aunque B y C se quitan de forma lógica, B conserva su puntero siguiente a C, y C a D. El subproceso de lectura sigue recorriendo los nodos quitados y separados, y, finalmente, se une a la pila activa en D. 

Al diseñar DeliQueue para controlar las condiciones de carrera entre el recorrido y la eliminación, permitimos una iteración segura y sin bloqueos.

Cierre: Recuento de referencias nativo

Looper se basa en una asignación nativa que se debe liberar de forma manual una vez que Looper se cierra. Si algún otro subproceso agrega Messages mientras se cierra Looper, podría usar la asignación nativa después de que se libere, lo que constituye un incumplimiento de la seguridad de la memoria. Para evitar esto, usamos un recuento de referencias etiquetado, en el que se usa un bit del atómico para indicar si el Looper se está cerrando.

Antes de usar la asignación nativa, un subproceso lee el recuento de referencias atómico. Si se establece el bit de cierre, se muestra que el Looper se está cerrando y no se debe usar la asignación nativa. De lo contrario, intenta una operación CAS para incrementar la cantidad de subprocesos activos con la asignación nativa. Después de hacer lo que necesita, disminuye el recuento. Si el bit de salida se estableció después de su incremento, pero antes de la disminución, y el recuento ahora es cero, se activa el subproceso Looper.

Cuando el subproceso Looper está listo para finalizar, usa CAS para establecer el bit de finalización en el elemento atómico. Si el recuento de referencias era 0, puede liberar su asignación nativa. De lo contrario, se detiene, sabiendo que se activará cuando el último usuario de la asignación nativa disminuya el recuento de referencias. Este enfoque implica que el subproceso Looper espera el progreso de otros subprocesos, pero solo cuando se cierra. Esto solo sucede una vez y no es sensible al rendimiento, y mantiene el otro código para usar la asignación nativa completamente sin bloqueos.

Hay muchos otros trucos y complejidades en la implementación. Puedes obtener más información sobre DeliQueue revisando el código fuente.

Optimización: Programación sin bifurcaciones

Mientras desarrollaba y probaba DeliQueue, el equipo ejecutó muchas comparativas y analizó cuidadosamente el nuevo código. Un problema que se identificó con la herramienta simpleperf fueron los vaciados de la canalización causados por el código del comparador Message.

Un comparador estándar usa saltos condicionales, con la condición para decidir qué Message viene primero simplificada a continuación:

static int compareMessages(@NonNull Message m1, @NonNull Message m2) {
    if (m1 == m2) {
        return 0;
    }

    // Primary queue order is by when.
    // Messages with an earlier when should come first in the queue.
    final long whenDiff = m1.when - m2.when;
    if (whenDiff > 0) return 1;
    if (whenDiff < 0) return -1;

    // Secondary queue order is by insert sequence.
    // If two messages were inserted with the same `when`, the one inserted
    // first should come first in the queue.
    final long insertSeqDiff = m1.insertSeq - m2.insertSeq;
    if (insertSeqDiff > 0) return 1;
    if (insertSeqDiff < 0) return -1;

    return 0;
}

Este código se compila en saltos condicionales (instrucciones b.le y cbnz). Cuando la CPU encuentra una bifurcación condicional, no puede saber si se toma la bifurcación hasta que se calcula la condición, por lo que no sabe qué instrucción leer a continuación y debe adivinar, utilizando una técnica llamada predicción de bifurcaciones. En un caso como la búsqueda binaria, la dirección de la rama será impredeciblemente diferente en cada paso, por lo que es probable que la mitad de las predicciones sean incorrectas. La predicción de ramas suele ser ineficaz en los algoritmos de búsqueda y clasificación (como el que se usa en un min-heap), ya que el costo de adivinar de forma incorrecta es mayor que la mejora que se obtiene al adivinar de forma correcta. Cuando el predictor de ramas adivina mal, debe descartar el trabajo que hizo después de suponer el valor predicho y comenzar de nuevo desde la ruta que realmente se tomó. Esto se denomina vaciado de canalización.

Para encontrar este problema, generamos perfiles de nuestras comparativas con el contador de rendimiento branch-misses, que registra los seguimientos de pila en los que el predictor de ramas adivina de forma incorrecta. Luego, visualizamos los resultados con Google pprof, como se muestra a continuación:

Recuerda que el código MessageQueue original usaba una lista vinculada única para la cola ordenada. La inserción recorrería la lista en orden de clasificación como una búsqueda lineal, deteniéndose en el primer elemento que se encuentra después del punto de inserción y vinculando el nuevo Message antes de él. Para quitar la cabeza, solo era necesario desvincularla. Mientras que DeliQueue usa un min-heap, en el que las mutaciones requieren reordenar algunos elementos (filtrado hacia arriba o hacia abajo) con una complejidad logarítmica en una estructura de datos equilibrada, en la que cualquier comparación tiene la misma probabilidad de dirigir el recorrido a un hijo izquierdo o a un hijo derecho. El nuevo algoritmo es asintóticamente más rápido, pero expone un nuevo cuello de botella, ya que el código de búsqueda se detiene en las fallas de la rama la mitad del tiempo.

Como nos dimos cuenta de que las omisiones de bifurcación ralentizaban nuestro código de montón, lo optimizamos con la programación sin bifurcaciones:

// Branchless Logic
static int compareMessages(@NonNull Message m1, @NonNull Message m2) {
    final long when1 = m1.when;
    final long when2 = m2.when;
    final long insertSeq1 = m1.insertSeq;
    final long insertSeq2 = m2.insertSeq;

    // signum returns the sign (-1, 0, 1) of the argument,
    // and is implemented as pure arithmetic:
    // ((num >> 63) | (-num >>> 63))
    final int whenSign = Long.signum(when1 - when2);
    final int insertSeqSign = Long.signum(insertSeq1 - insertSeq2);

    // whenSign takes precedence over insertSeqSign,
    // so the formula below is such that insertSeqSign only matters
    // as a tie-breaker if whenSign is 0.
    return whenSign * 2 + insertSeqSign;
}

Para comprender la optimización, desensambla los dos ejemplos en Compiler Explorer y usa LLVM-MCA, un simulador de CPU que puede generar una cronología estimada de los ciclos de CPU.

The original code:
Index     01234567890123
[0,0]     DeER .    .  .   sub  x0, x2, x3
[0,1]     D=eER.    .  .   cmp  x0, #0
[0,2]     D==eER    .  .   cset w0, ne
[0,3]     .D==eER   .  .   cneg w0, w0, lt
[0,4]     .D===eER  .  .   cmp  w0, #0
[0,5]     .D====eER .  .   b.le #12
[0,6]     . DeE---R .  .   mov  w1, #1
[0,7]     . DeE---R .  .   b    #48
[0,8]     . D==eE-R .  .   tbz  w0, #31, #12
[0,9]     .  DeE--R .  .   mov  w1, #-1
[0,10]    .  DeE--R .  .   b    #36
[0,11]    .  D=eE-R .  .   sub  x0, x4, x5
[0,12]    .   D=eER .  .   cmp  x0, #0
[0,13]    .   D==eER.  .   cset w0, ne
[0,14]    .   D===eER  .   cneg w0, w0, lt
[0,15]    .    D===eER .   cmp  w0, #0
[0,16]    .    D====eER.   csetm        w1, lt
[0,17]    .    D===eE-R.   cmp  w0, #0
[0,18]    .    .D===eER.   csinc        w1, w1, wzr, le
[0,19]    .    .D====eER   mov  x0, x1
[0,20]    .    .DeE----R   ret

Observa la rama condicional, b.le, que evita comparar los campos insertSeq si el resultado ya se conoce por la comparación de los campos when.

The branchless code:
Index     012345678
[0,0]     DeER .  .   sub       x0, x2, x3
[0,1]     DeER .  .   sub       x1, x4, x5
[0,2]     D=eER.  .   cmp       x0, #0
[0,3]     .D=eER  .   cset      w0, ne
[0,4]     .D==eER .   cneg      w0, w0, lt
[0,5]     .DeE--R .   cmp       x1, #0
[0,6]     . DeE-R .   cset      w1, ne
[0,7]     . D=eER .   cneg      w1, w1, lt
[0,8]     . D==eeER   add       w0, w1, w0, lsl #1
[0,9]     .  DeE--R   ret

Aquí, la implementación sin ramas requiere menos ciclos e instrucciones que incluso la ruta más corta a través del código con ramas, por lo que es mejor en todos los casos. La implementación más rápida y la eliminación de las bifurcaciones mal predichas generaron una mejora de 5 veces en algunos de nuestros comparativos.

Sin embargo, esta técnica no siempre es aplicable. Los enfoques sin ramas generalmente requieren realizar un trabajo que se descartará y, si la rama es predecible la mayor parte del tiempo, ese trabajo desperdiciado puede ralentizar tu código. Además, quitar una rama a menudo introduce una dependencia de datos. Las CPU modernas ejecutan varias operaciones por ciclo, pero no pueden ejecutar una instrucción hasta que sus entradas de una instrucción anterior estén listas. En cambio, una CPU puede especular sobre los datos en las bifurcaciones y trabajar con anticipación si se predice una bifurcación correctamente.

Pruebas y validación

Validar la corrección de los algoritmos sin bloqueo es notoriamente difícil.

Además de las pruebas de unidades estándar para la validación continua durante el desarrollo, también escribimos rigurosas pruebas de estrés para verificar las invariantes de la cola y tratar de inducir condiciones de carrera de datos si existieran. En nuestros laboratorios de pruebas, pudimos ejecutar millones de instancias de pruebas en dispositivos emulados y en hardware real.

Con la instrumentación de Java ThreadSanitizer (JTSan), pudimos usar las mismas pruebas para detectar también algunas condiciones de carrera de datos en nuestro código. JTSan no encontró ninguna condición de carrera problemática en DeliQueue, pero, sorprendentemente, detectó dos errores de simultaneidad en el framework de Robolectric, que corregimos de inmediato.

Para mejorar nuestras capacidades de depuración, creamos nuevas herramientas de análisis. A continuación, se muestra un ejemplo de un problema en el código de la plataforma de Android en el que un subproceso sobrecarga a otro con Messages, lo que provoca una gran acumulación de trabajo pendiente, que se puede ver en Perfetto gracias a la función de instrumentación MessageQueue que agregamos.

Para habilitar el registro de MessageQueue en el proceso de system_server, incluye lo siguiente en tu configuración de Perfetto:

data_sources {
  config {
    name: "track_event"
    target_buffer: 0  # Change this per your buffers configuration
    track_event_config {
      enabled_categories: "mq"
    }
  }
}

Impacto

DeliQueue mejora el rendimiento del sistema y de las apps, ya que elimina los bloqueos de MessageQueue.

• Comparativas sintéticas: Las inserciones de subprocesos múltiples en colas ocupadas son hasta 5,000 veces más rápidas que el MessageQueue heredado, gracias a la mejora de la simultaneidad (la pila de Treiber) y las inserciones más rápidas (el min-heap).
• En los registros de Perfetto adquiridos de verificadores beta internos, observamos una reducción del 15% en el tiempo del subproceso principal de la app dedicado a la contención de bloqueos.
• En los mismos dispositivos de prueba, la reducción de la contención de bloqueo genera mejoras significativas en la experiencia del usuario, como las siguientes:
  • Se perdieron un 4% menos de fotogramas en las apps.
  • Se redujo en un 7.7% la cantidad de fotogramas perdidos en las interacciones de la IU del sistema y el Selector.
  • El tiempo desde el inicio de la app hasta el primer fotograma dibujado se redujo en un 9.1% en el percentil 95.

Próximos pasos

DeliQueue se lanzará en las apps de Android 17. Los desarrolladores de apps deben revisar el artículo sobre cómo preparar tu app para el nuevo MessageQueue sin bloqueo en el blog para desarrolladores de Android y aprender a probar sus apps.

Referencias

[1] Treiber, R.K., 1986 Programación de sistemas: Cómo hacer frente al paralelismo International Business Machines Incorporated, Thomas J. Watson Research Center.

[2] Goetz, B., Peierls, T., Bloch, J., Bowbeer, J., Holmes, D., y Lea, D. (2006). Java Concurrency in Practice Addison-Wesley Professional.