Categorías
C#

Xoshiro256**

Aunque parezca que el título de la entrada lo tecleó mi gato, es en realidad el nombre de un algoritmo de generación de números aleatorio, inventado por Sebastiano Vigna y David Blackman (enlaces al final).

El nombre es una combinación de las operaciones principales del algoritmo: xor, shift, rotate. En realidad, hay toda una familia de algoritmos similares, con nombres que se parecen mucho. El xoshiro256** es, simplemente, el que ha adoptado .NET Core desde la versión 6 (implementación aquí).

Xoshiro256** es muy rápido, es robusto (aunque no te recomiendan que lo uses en aplicaciones de criptografía), y utiliza muy poca memoria. Como se puede ver en la implementación de .NET 8, sólo necesita cuatro variables de tipo ulong. Es decir, 32 bytes por cada instancia del generador.

Xoshiro vectorial

Austra utiliza generadores de números aleatorios a diestra y siniestra. ¿Es fácil escribir una versión de este algoritmo usando instrucciones AVX? La respuesta es: no, a no ser que uses directamente AVX512F. El problema es que este algoritmo realiza una rotación. Es curioso que los lenguajes modernos de programación no te den directamente esta operación como parte de los operadores de bit. C# tiene un >> y un <<, por ejemplo, pero las rotaciones tienes que buscarlas en la clase BitOperations. De todos modos, el problema es que AVX/AVX2 no tiene una operación SIMD de rotación. Podríamos simularla con shifts y máscaras, pero perderíamos parte de las ventajas de la vectorización. Hay implementaciones en GitHub de generadores aleatorios con AVX2, pero no dan una ganancia de velocidad destacable.

Hay otro problema con el que hay que tener sumo cuidado. Pongamos como ejemplo el constructor de la clase DVector que genera un vector con valores aleatorios:

/// 
/// Creates a vector filled with a uniform distribution generator.
/// 
/// Size of the vector.
/// A random number generator.
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public DVector(int size, Random rnd);

Omito la implementación para simplificar. Lo que quiero subrayar es que este constructor recibe una instancia explícita de la clase Random. ¿Por qué? Pues porque al cliente de la librería puede necesitar resultados repetibles. Es decir, puede que para que un vector «aleatorio» tenga siempre los mismos resultados, podría ser que la instancia de Random se inicializase siempre con la misma semilla. Si no nos interesa usar una semilla, casi siempre utilizaremos Random.Shared, que es una propiedad estática de Random, que es única para cada hilo y que se crea por demanda.

Podríamos complicarnos la vida al escribir la versión vectorizada de este constructor, y averiguar cómo recuperar la semilla del generador que nos pasa el cliente para crear un generador vectorial con esa misma semilla. Pero:

  1. No tengo claro que recuperar esa semilla sea tarea fácil
  2. El generador aleatorio vectorial que he programado no tiene, de momento, la posibilidad de inicializarse con una semilla (y no me parece tampoco sencillo).

Por lo tanto, las rutinas que se han acelerado con el generador vectorial comprueban si el generador que han recibido del cliente es Random.Shared. Eso lo interpretamos como que al cliente no le interesa la repetibilidad de los resultados. Naturalmente, hay que verificar antes si AVX512F está disponible en el ordenador.

Cuando usamos el generador vectorial, los tiempos de ejecución se reducen a una cuarta o quinta parte. No se reducen a la octava parte mecánicamente porque en la mayoría de estas rutinas pesa más la asignación de memoria y el posterior llenado de la misma. Pero bajar el tiempo de ejecución a la cuarta parte me parece meritorio.

Enlaces

Estos son los enlaces a la clase de Austra.Library que genera ocho números de golpe por llamada, y a la página de Sebastiano Vigna, el autor del algoritmo que hemos vectorizado. Mi implementación, con toda seguridad, está abierta a mejoras. Por ejemplo, no me convence la forma en que tengo que convertir un valor ulong en otro de tipo double, porque no es vectorial. Debe existir algo más eficiente, pero de momento no lo he encontrado. De todas maneras, ahí tiene mi implementación, por si le es útil en alguno de sus proyectos.

Queda también pendiente la vectorización de números aleatorios provenientes de una distribución normal. Austra utiliza el método de Box-Muller, pero este método exige el cálculo de un logaritmo y de senos y cosenos. No es tarea imposible, pero tengo primero que proporcionar una rutina que genere vectorialmente senos y cosenos y, quizás antes, decidir si me interesa realmente el método de Box-Muller, o si merece la pena ir directamente a una implementación vectorial del algoritmo del zigurat. Todo, en su debido momento.

Categorías
Insights

La mentalidad predominante

Intentaré ser breve.

Hace ya más de diez años, a una persona muy inteligente y a mí nos pusieron a trabajar a destajo en dos proyectos paralelos en Java cuyo núcleo técnico era bastante parecido: había que enviar precios en una red local a toda leche. Por entonces, Java iba sólo por la versión 7, y había una estructura de datos en Java que se había puesto de moda: el «patrón Disruptor». No pongo enlaces porque no se lo merece. La idea del famoso disruptor era sustituir la típica cola bloqueante (o el Channel que ahora tiene .NET Core) por una cola circular, sin bloqueos… y con un hilo dedicado, girando como un demonio constantemente, calentando la CPU y robando recursos. Teóricamente, este desperdicio se traduciría en menos latencia entre procesos… lo cual incluso puede ser cierto.

A esta idea del bucle en perpetuo movimiento se le añadía un poco de polvo de hadas: la cola circular estaba pensada para evitar pedir memoria dentro de lo posible (un problema que provoca el propio Java), y estaba todo calculado para evitar cosas con nombres tan feos como el false sharing (que es un problema real cuando hay concurrencia). Es decir, por estar hecho en Java, el disruptor era ya la leche… aunque terminó teniendo versiones en C# y supongo que hasta en Python. Toda la mierda que los gatos tiran al suelo termina cayendo en una librería de Python y ahí se hace eterna.

La cruda realidad

Como soy incrédulo, sobre todo de las cosas que no me gustan, lo que hicimos (la persona inteligente y yo) fue crear una demo. Probamos el disruptor contra la cola bloqueante de serie de Java, y ganaba el disruptor, aunque no por KO. El ganador absoluto, sin embargo, fue una variante de la cola bloqueante, con el añadido de recuperar e insertar los elementos en lotes. Es una idea estúpidamente simple y efectiva. Si miras la cola y ves que tienes cuatro elementos pendientes de recuperar, aprovecha y tráetelos todos. En Java tienes que ser cuidadoso con estas cosas, y no crear un array cada vez que te traigas n objetos, pero esto tiene una solución tan sencilla como adosar un array a la cola bloqueante en lotes, y reaprovecharlo todo el tiempo.

¿Cuál era el problema del disruptor? Pues que la idea de quemar un hilo empieza pareciendo atractiva, hasta que te das cuenta de que, si esta filosofía la sigues aplicando al resto de la aplicación, te quedas sin CPU en un plisplás. Creo que la única aplicación del disruptor que llegó a usarse en mi empresa de entonces fue en un proceso de logging sin bloqueos. Me dio un ataque de risa cuando me lo contaron, y todavía creo que quien me lo contó bromeaba.

¡Más Java!

Hay un meme rondando Internet y sacado de una peli barata, sobre un productor musical que todo lo resolvía añadiendo more cowbell, es decir, más cencerro, a la pista de percusión de cualquier canción. En el mundo de la programación, el equivalente es añadir más Java a Java. Me explico:

La otra gran decisión a tomar en el par de proyectos paralelos de hace más de diez años era qué íbamos a utilizar para leer y escribir en sockets. Como uno es un idiota iletrado que conoce poco Java, mi razonamiento es que, a no ser que montase una librería de muy bajo nivel en código nativo, cualquier librería basada en sockets que no implementase algún protocolo experimental no iba a ser mejor que la que ya venía en Java. Todas las librerías de sockets de terceros, y había para escoger, lo único que aportaban eran «abstracciones» como superestructura, que presuntamente podían simplificar la programación, pero jamás iban a conseguir que todo fuese más rápido. Por eso, yo me quedé con los sockets de toda la vida, y mi amigo, que es un experto en Java, se decidió por una librería de la famosa fundación Apache.

Y llegó el día del estreno. Mi aplicación llegaba a leer hasta 250.000 mensajes por cada hilo o canal que habilitase en el proceso. La otra aplicación reventó por un límite absurdo que imponía la librería de terceros. El problema se solucionó, por supuesto, tras algo de trabajo adicional. Pero yo, que soy un idiota, me quedé con una moraleja: añadir más Java a Java no suele aportar nada de valor.

Tiempos modernos

Como sospechará el lector, nadie saca una historia de hace diez años si no ha pasado algo parecido recientemente. En efecto. Una librería escrita en C# resuelve un problema de negocios muy interesante. Pero es una librería a secas, y el equipo que la mantiene no da abasto para conectarla a todas las diferentes fuentes de datos posibles. El tiempo de respuesta, además, es sumamente importante, en este caso.

Entonces apareció un Fervoroso Creyente de la Religión Verdadera, que es Java (y Martin Fowler es uno de sus profetas). La solución propuesta fue añadir Java, y polvos de unicornio. Y, como Java iba a estar obligatoriamente en otro proceso, traer un equivalente moderno del disruptor: una librería de comunicaciones que «resuelve» el problema de la «latencia» poniendo un proceso intermedio que gira como un púlsar al que se le ha ido la olla, y un par de hilos en cada extremo haciendo lo mismo. Es decir, la idea del hilo eterno del disruptor multiplicada por tres. Lo probaron en una máquina razonable, con sólo esos tres componentes: un publicador, el intermediario, y un subscriptor. El invento añadió sólo una decena de microsegundos, o eso me contaron, a la transmisión. Eso ya me habría hecho dudar, si lo hubiese sabido a tiempo. El problema es que la aplicación necesita transmitir datos de unos ocho canales. Tres por ocho, aquí y en Javalandia, siempre ha sido igual a veinticuatro. Estoy escribiendo en la máquina a la que llamo El Pepino, y que es un Core i9 con 8 núcleos físicos y 16 núcleos virtuales por hyperthreading. Es decir, menor estrictamente que veinticuatro.

Creo que todavía están apretado y soltando tuercas para intentar que la cosa funcione. Best of the luck, my friends.

Prometí ser breve, pero no lo conseguí.