Optimizar un spin-lock: de seq_cst al test-and-test-and-set con pausa
Un repaso medido al spin-lock más naíf y a las tres versiones que lo mejoran: menos misses de caché, menos ramas mal predichas y menos vatios.
Un spin-lock no duerme. El hilo se queda en la CPU girando en lugar de ceder el turno al planificador: ni syscalls ni cambios de contexto, a cambio de quemar ciclos. David Álvarez Rosa ha publicado el recorrido completo desde la implementación más naíf hasta una optimizada, con medidas de tiempo, misses y energía en cada paso. La promesa final de la serie es 5,7 veces menos tiempo y 5,4 veces menos consumo.
El banco de pruebas es sencillo: varios hilos incrementan un contador compartido dentro del lock. El lock y el contador viven cada uno en su propia línea de caché (hardware_destructive_interference_size), los hilos están fijados a núcleos y todo se compila con clang y las optimizaciones activadas.
De 3 ns a 246 ns sin salir del mismo núcleo
La primera versión es un atomic_bool con bucle de exchange. La operación escribe true y devuelve el valor anterior: si era false, el lock estaba libre y ya es nuestro. Sin contención tarda 3,14 ns. Con dos hilos se va a 61,5 ns y con cuatro a 246 ns, veinte veces más.
La explicación está en el protocolo de coherencia: para escribir una línea, un núcleo necesita posesión exclusiva, así que los que esperan se la roban entre sí en cada intento. Los fallos de L1-d pasan del 1,27% con un hilo al 61,73% con cuatro, y el 12,52% de las ramas se predicen mal. El predictor no puede aprender nada ahí: quien decide si el exchange tuvo éxito es otro núcleo.
Un ordering más débil y una carga de solo lectura
El segundo paso ataca el ordenamiento de memoria. seq_cst es más fuerte de lo que un lock necesita, que solo tiene que adquirir al entrar y liberar al salir. En x86 el lock no cambia, pero el unlock sí: por defecto añade un segundo read-modify-write bloqueado, y con memory_order_release queda en un store simple. Un atómico en vez de dos. Los números bajan a 1,57 ns, 32,5 ns y 131 ns, y el consumo de 64,92 J a 34,45 J en la máquina de pruebas.
El tercer paso se fija en que el exchange escribe la línea aunque falle. Los que esperan no deberían escribir nada. La versión test-and-test-and-set hace un único exchange y luego gira sobre una carga relajada de solo lectura, con _mm_pause marcando el bucle como espera para que el núcleo se relaje. Con dos hilos baja de 32,5 a 21,3 ns, y con cuatro de 131 a 120 ns. Los fallos de L1-d caen al 17,31%, las ramas mal predichas al 3,72% y la energía a 30,97 J.
Queda un problema conocido: todos los que esperan pausan lo mismo, así que se despiertan a la vez. La solución que cierra el artículo es el backoff exponencial que documenta Intel en su manual de optimización: duplicar la espera en cada ronda hasta un tope.
El interés de esto no es académico. Cualquiera que escriba un lock propio para un kernel, un motor de trading o una estructura lock-free se enfrenta a las mismas decisiones: qué ordering usar, cuándo dejar de escribir y cómo evitar que todos los hilos converjan en el mismo instante. El código de las cuatro versiones está en el repositorio del autor.
