La instrucción CAS, los "ctries" y los trileros

La intrucción CAS

La instrucción Compare and Swap (CAS para los amigos) ya estaba disponible en los IBM 370 desde los años 70 del siglo pasado, y ahora viene de fábrica en los microprocesadores más populares. Incluso los microprocesadores ARM de los móviles (ARMv6 y superiores) la soportan.

La instrucción CAS, "comparar y cambiar" recibe dos valores "A" y "B", y sirve para preguntarle al sistema cuál es el valor "X" de una posición de memoria determinada, y si el valor es el mismo que nosotros pensamos que es (esto es, si "X = A") entonces cambiarlo por el nuevo valor "B" (esto es, hacer que "X = B").

Si el valor "X" en la posición de memoria en cuestión no es el mismo que nosotros pensamos que era ("A") entonces es que alguien más nos lo ha cambiado, y la operación no actualiza la posición al nuevo valor "B". En este caso tendremos que volver a nuestro cubil con el nuevo valor (tristes y engañados como estábamos, pensando que el valor era "A" cuando era otro) y volver a hacer nuestras cuentas e intentarlo de nuevo más tarde, posiblemente con otro nuevo valor "B" diferente.

La ventaja de la instrucción CAS es, sin duda, que es atómica: da igual cuantos procesadores o núcleos o hilos de ejecución la usen al mismo tiempo: sólo uno de los muchos posibles participantes puede cambiar el valor de "A" a "B". Y, además, no hace falta detener a todos los núcleos para hacerlo: no hay un "bloqueo" generalizado para realizar el cambio del valor "X" por el nuevo valor "B".

La Wikipedia lo explica (en inglés, todavía, en español no hay) con gran detalle, incluyendo los problemas que puede haber en el proceso.

Soporte en C, C++, Objective-C y Java

Los lenguajes de programación no van al ritmo de los microprocesadores, que avanzan que es una barbaridad, por lo que la instrucción CAS (el equivalente Intel es CMPXCHG, PDF no estaba soportada en la mayoría de los lenguajes, y uno tenía que usar ensamblador para usarla.

La mayoría de compiladores modernos de C, C++, Objective-C, Java, Scala, Ruby soportan ya las operaciones atómicas que ofrecen los procesadores modernos.

Bueno, que me enrollo. El caso es que vino la Internet con todos sus usuarios, que había que atender al mismo tiempo; y vinieron también los microprocesadores con varios núcleos, que permiten hacer también cosas al mismo tiempo, y entonces hubo que actualizar los lenguajes de programación para poder hacer cosas al mismo tiempo. Y es ahora cuando la instrucción CAS y el resto de operaciones atómicas empiezan a tener especial importancia.

El caso es que en el estándar ANSI C de diciembre 2011 (C11 para los amigos) se incluyeron al fin, estas maravillas de la sincronización sin bloqueos, por lo que ya no hay que usar ensamblador para usarlas.

En español no he encontrado nada, pero en una página web de Suecia he encontrado este PDF que explica cómo funciona esto de las operaciones atómicas en C11. Mis compiladores de C en FreeBSD y Mac OS/X:

FreeBSD clang version 3.3 (tags/RELEASE_33/final 183502) 20130610
Target: i386-unknown-freebsd9.2
Thread model: posix

Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
Target: x86_64-apple-darwin12.5.0
Thread model: posix

Soportan ya muchas de estas operaciones atómicas. Este programilla en C:

#include <stdio.h>

int main(int argc, char ** argv)
{
    _Atomic(int) x;

    for(int x=0; x<10; x++) {
        printf("%d", x);
    }

    return 0;
}

Compila perfectamente en ambas plataformas (nótese el '_Atomic(int)' que indica que es un entero que se actualiza atómicamente).

Las operaciones atómicas de C++11 se soportan también con las versiones más recientes del compilador clang++ y g++.

Java dispone desde la versión 1.5 de operaciones atómicas agrupadas en java.util.concurrent.atomic y la versión de Java 8 (¿marzo 2014?) traerá incluso más avances en las operaciones atómicas.

También el Objective-C se ha modernizado, y ahora las propiedades pueden o no ser atómicas, asegurándonos que varios hilos cambian la propiedad "de golpe", de modo que el valor de la propiedad es correcto en todo momento.

En resumen: los lenguajes de programación más modernos ya disponen de estas maravillas de sincronización sin bloqueos a través de operaciones atómicas.

Colecciones sin bloqueos: ctries

Todo este soporte de operaciones atómicas en los lenguajes de programación permiten programar colecciones "sin bloqueos" en entornos con varios hilos de ejecución de forma más fácil.

La estructura de datos ctrie promete unos rendimientos espectaculares en entornos multihilo. Disponible en Scala, Common Lisp y otros. Habrá que estar atento a nuevas versiones.

Hay muchísimas colecciones sin bloqueos, desde luego: listas, pilas, colas, etcétera.

En el año 2000 se publicó un artículo "revolucionario" sobre los llamados "árboles hash ideales", o "Ideal Hash Trees", que vienen a ser una combinación de árboles (como los B-Tree) y tablas hash (como las hashtables) y que permiten obtener un valor dada una clave con velocidades muy rápidas (coste algorítmico constante O(1)).

La estructura de datos en cuestión favoreció la aparición de las llamadas Hash Array Mapped Tries, con unos rendimientos algorítmicos sorprendentes. Los lenguajes de programacion Clojure y Scala usan una variante de éstas estructuras para sus tablas hash. La estructura también está disponible para Ruby y para C++, y posiblemente para muchas otros lenguajes de programación.

Lo curioso del tema, y lo que ha originado que suelte todo este rollo, es que hay una versión sin bloqueo que utiliza operaciones atómicas: la "Concurrent Hash Trie". Como dicen en la Wikipedia es la primera estructura de datos conocida que permite sacar snapshots con concurencia con coste constante O(1)

Existen implementaciones en Scala y la estructura está disponible en la librería estándar de Scala desde el año 2012. Poco a poco están apareciendo en GitHub estas estructuras ctrie en diferentes lenguajes de programación. Esta en Common Lisp tiene una pinta estupenda. Esta en Java también.

Habrá que estar atentos a nuevas versiones de esta estructura de datos "ctrie" en otros lenguajes, ya que en principio promete poder mejorar enormemente el rendimiento de nuestro software en entornos multihilo. Iré contando novedades en el blog conforme me vaya enterando.

¿Y los trileros?

Pero, ¿qué tienen que ver los trileros con todo esto?

Pues resulta que la instrucción CAS me recuerda a los trileros, el famoso juego de estafadores en los que hay que adivinar en qué cubilete está una bolita.

Si uno tuviese una instrucción CAS en la vida real no podría fallar nunca al trile. Uno usaría la instrucción CAS para decir que la bolita ("A") está en un cubilete determinado ("X") y, si es así, proponer una apuesta ("B"). Como la operación es atómica no fallaríamos nunca, aunque el trilero nos cambie de cubilete. Genial, ¿no?

Hablando de trileros, os dejo un gran vídeo de "El Hormiguero" sobre trileros (que, afortunadamente, no dice nada de colecciones sin bloqueos ni de ctries):