{"id":1663,"date":"2024-02-10T13:34:20","date_gmt":"2024-02-10T12:34:20","guid":{"rendered":"https:\/\/intsight.com\/?p=1663"},"modified":"2024-02-10T13:34:20","modified_gmt":"2024-02-10T12:34:20","slug":"xoshiro256","status":"publish","type":"post","link":"https:\/\/intsight.com\/index.php\/2024\/02\/10\/xoshiro256\/","title":{"rendered":"Xoshiro256**"},"content":{"rendered":"

Aunque parezca que<\/span> el t\u00edtulo de la entrada lo tecle\u00f3 mi gato, es en realidad el nombre de un algoritmo de generaci\u00f3n de n\u00fameros aleatorio, inventado por Sebastiano Vigna y David Blackman (enlaces al final).<\/p>\n

El nombre es una combinaci\u00f3n de las operaciones principales del algoritmo: xor<\/strong>, shift<\/strong>, rotate<\/strong>. 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\u00f3n 6 (implementaci\u00f3n aqu\u00ed<\/a>).<\/p>\n

Xoshiro256** es muy r\u00e1pido, es robusto (aunque no te recomiendan que lo uses en aplicaciones de criptograf\u00eda), y utiliza muy poca memoria. Como se puede ver en la implementaci\u00f3n de .NET 8, s\u00f3lo necesita cuatro variables de tipo ulong<\/code>. Es decir, 32 bytes por cada instancia del generador.<\/p>\n

Xoshiro vectorial<\/h4>\n

Austra utiliza generadores de n\u00fameros aleatorios a diestra y siniestra. \u00bfEs f\u00e1cil escribir una versi\u00f3n 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\u00f3n. Es curioso que los lenguajes modernos de programaci\u00f3n no te den directamente esta operaci\u00f3n como parte de los operadores de bit. C# tiene un >><\/code> y un <<<\/code>, por ejemplo, pero las rotaciones tienes que buscarlas en la clase BitOperations<\/code>. De todos modos, el problema es que AVX\/AVX2 no tiene una operaci\u00f3n SIMD de rotaci\u00f3n. Podr\u00edamos simularla con shifts<\/em> y m\u00e1scaras, pero perder\u00edamos parte de las ventajas de la vectorizaci\u00f3n. Hay implementaciones en GitHub de generadores aleatorios con AVX2, pero no dan una ganancia de velocidad destacable.<\/p>\n

Hay otro problema con el que hay que tener sumo cuidado. Pongamos como ejemplo el constructor de la clase DVector<\/code> que genera un vector con valores aleatorios:<\/p>\n

\n\/\/\/ \n\/\/\/ Creates a vector filled with a uniform distribution generator.\n\/\/\/ <\/summary>\n\/\/\/ Size of the vector.<\/param>\n\/\/\/ A random number generator.<\/param>\n[MethodImpl(MethodImplOptions.AggressiveInlining)]\npublic DVector(int size, Random rnd);\n<\/pre>\n
Omito la implementaci\u00f3n para simplificar. Lo que quiero subrayar es que este constructor recibe una instancia expl\u00edcita de la clase Random<\/code>. \u00bfPor qu\u00e9? Pues porque al cliente de la librer\u00eda puede necesitar resultados repetibles<\/em>. Es decir, puede que para que un vector \u00abaleatorio\u00bb tenga siempre los mismos resultados, podr\u00eda ser que la instancia de Random<\/code> se inicializase siempre con la misma semilla. Si no nos interesa usar una semilla, casi siempre utilizaremos Random.Shared<\/code>, que es una propiedad est\u00e1tica de Random<\/code>, que es \u00fanica para cada hilo y que se crea por demanda.<\/p>\n
Podr\u00edamos complicarnos la vida al escribir la versi\u00f3n vectorizada de este constructor, y averiguar c\u00f3mo recuperar la semilla del generador que nos pasa el cliente para crear un generador vectorial con esa misma semilla. Pero:<\/p>\n
    \n
  1. No tengo claro que recuperar esa semilla sea tarea f\u00e1cil<\/li>\n
  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).<\/li>\n<\/ol>\n
    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<\/code>. Eso lo interpretamos como que al cliente no le interesa la repetibilidad de los resultados. Naturalmente, hay que verificar antes si AVX512F est\u00e1 disponible en el ordenador.<\/p>\n
    Cuando usamos el generador vectorial, los tiempos de ejecuci\u00f3n se reducen a una cuarta o quinta parte. No se reducen a la octava parte mec\u00e1nicamente porque en la mayor\u00eda de estas rutinas pesa m\u00e1s la asignaci\u00f3n de memoria y el posterior llenado de la misma. Pero bajar el tiempo de ejecuci\u00f3n a la cuarta parte me parece meritorio.<\/p>\n
    Enlaces<\/h4>\n
    Estos son los enlaces a la clase de Austra.Library que genera ocho n\u00fameros de golpe por llamada, y a la p\u00e1gina de Sebastiano Vigna, el autor del algoritmo que hemos vectorizado. Mi implementaci\u00f3n, con toda seguridad, est\u00e1 abierta a mejoras. Por ejemplo, no me convence la forma en que tengo que convertir un valor ulong<\/code> en otro de tipo double<\/code>, porque no es vectorial. Debe existir algo m\u00e1s eficiente, pero de momento no lo he encontrado. De todas maneras, ah\u00ed tiene mi implementaci\u00f3n, por si le es \u00fatil en alguno de sus proyectos.<\/p>\n