La gran mayoría de mis publicaciones sobre generación de números aleatorios se ocuparon principalmente de las propiedades de varios esquemas de generación. Esto puede resultar inesperado, pero el rendimiento del algoritmo de aleatorización puede depender no del esquema de generación elegido, sino de otros factores. En esta publicación (que me inspiró un excelente
artículo de Daniel Lemyr ), examinaremos las principales razones de la disminución del rendimiento de generación de números aleatorios, que a menudo superan el rendimiento del motor PRN.
Imagina esta situación:
Como tarea, Juan y Sasha implementan el mismo algoritmo aleatorio en C ++, que se ejecutará en la misma computadora de la universidad y con un conjunto de datos. Su código es casi idéntico y solo difiere en la generación de números aleatorios. Juan tiene prisa por sus lecciones de música, así que simplemente eligió el torbellino de Mersenne. Sasha, por otro lado, pasó unas horas extra investigando. Sasha realizó puntos de referencia de varios de los PRNG más rápidos, que recientemente aprendió de las redes sociales, y eligió el más rápido. En la reunión, Sasha estaba impaciente por alardear y le preguntó a Juan: "¿Qué sistema PRNG usaste?"
"Personalmente, acabo de tomar el vórtice de Mersenne, está integrado en el lenguaje y parece funcionar bastante bien".
"¡Ja!", Respondió Sasha. “
jsf32 . ¡Es mucho más rápido que el viejo y lento torbellino de Mersenne! ¡Mi programa se ejecuta en 3 minutos y 15 segundos! "
"Hmm, no está mal, pero el mío puede hacerlo en menos de un minuto", dice Juan y se encoge de hombros. “Bueno, entonces tengo que ir al concierto. ¿Vendrás conmigo?
"No", responde Sasha. "Yo ... eh ... necesito mirar mi código de nuevo".
Esta incómoda situación ficticia
no es particularmente ficticia; Se basa en resultados reales. Si su algoritmo aleatorio no funciona tan rápido como nos gustaría, y el cuello de botella parece ser la generación de números aleatorios, entonces, curiosamente, ¡el problema puede no estar en el generador de números aleatorios!
Introducción: números aleatorios en la práctica
La mayoría de los generadores de números aleatorios modernos de alta calidad crean palabras de máquina llenas de bits aleatorios, es decir, generalmente generan números en el intervalo [0..2
32 ) o [0..2
64 ). Pero en muchos casos de uso, los usuarios necesitan números en un cierto intervalo; por ejemplo, para lanzar un dado o elegir una carta de juego aleatoria, se necesitan números en pequeños intervalos constantes. Sin embargo, muchos algoritmos, desde la
mezcla y el
muestreo de yacimientos hasta
los árboles de búsqueda binarios aleatorios, requieren números tomados de otros intervalos.
Métodos
Veremos muchos métodos diferentes. Para simplificar la discusión, en lugar de generar números en el intervalo [
i ..
j ) o [
i ..
j ], generaremos números en el intervalo [0 ..
k ). Teniendo tal esquema, podemos, por ejemplo, generar números en el intervalo [
i ..
j ) estableciendo
k =
j -
i , generando un número en el intervalo [0 ..
k ), y luego añadiéndole
i .
Herramientas integradas de C ++
Muchos idiomas tienen herramientas integradas para obtener un número aleatorio en un intervalo específico. Por ejemplo, para eliminar una carta de un mazo con 52 cartas en lenguajes de script como Perl y Python, podemos escribir
int(rand(52)) y
random.randint(0,52) . [Nota Usuario de
CryptoPirate :
Me parece un error aquí, en Python randint (a, b) genera números de a a b, incluido b. Y como hay 52 cartas en el mazo y la primera es "0", debería ser random.randint (0,51) .] En C ++, podemos usar
uniform_int_distribution misma
uniform_int_distribution .
El código C ++ para implementar este enfoque es simple:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { std::uniform_int_distribution<uint32_t> dist(0, range-1); return dist(rng); }
Por lo general, una de las técnicas descritas a continuación se usa en las herramientas integradas, pero la mayoría de los usuarios simplemente usan estas herramientas, sin pensar en lo que está sucediendo "bajo el capó", creyendo que estas herramientas están diseñadas correctamente y son bastante efectivas. En C ++, las herramientas integradas son más complejas porque deberían poder trabajar con motores de generación bastante arbitrarios: un generador que produce valores en el rango de -3 a 17 puede ser bastante válido y puede usarse con
std::uniform_int_distribution para crear números en cualquier intervalo, por ejemplo [0..1000). Es decir, las herramientas integradas de C ++ son demasiado complicadas para la mayoría de los casos en los que se usan.
El resto clásico de la división (sesgado)
Pasemos de un enfoque demasiado simplificado a uno demasiado simplista.
Cuando estudié programación, generamos números en el intervalo (por ejemplo, para seleccionar una carta en un mazo de 52 cartas) usando el operador restante. Para obtener el número en el intervalo [0..52), escribimos
rand() % 52 .
En C ++, este enfoque se puede implementar de la siguiente manera:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { return rng() % range; }
A pesar de la simplicidad de este enfoque, demuestra la razón por la que obtener números en el intervalo correcto suele ser una tarea lenta: requiere división (para calcular el resto obtenido por el operador
% ). La división suele ser al menos un orden de magnitud más lenta que otras operaciones aritméticas, por lo que una sola operación aritmética lleva más tiempo que todo el trabajo realizado por un PRNG rápido.
Pero además de la baja velocidad, también está
sesgada . Para comprender por qué
rand() % 52 devuelve números sesgados, suponga que
rand() crea números en el intervalo [0..2
32 ), y tenga en cuenta que 52 no divide 2
32 por completo, lo divide 82 595 524 veces con el resto 48. Es decir, si usamos
rand() % 52 , tendremos 82 595 525 formas de seleccionar las primeras 48 cartas del mazo y solo 82 595 524 formas de seleccionar las últimas cuatro cartas. En otras palabras, hay un sesgo de 0.00000121% contra estas últimas cuatro cartas (¡quizás sean reyes!). Cuando era estudiante y escribía la tarea de tirar dados o dibujar cartas, nadie se molestaba con distorsiones tan pequeñas, pero con un aumento en el intervalo, la distorsión crece linealmente. Para un PRNG de 32 bits, un intervalo limitado de menos de 2
24 tiene un sesgo de menos del 0,5%, pero por encima de 2
31 un sesgo del 50%: algunos números regresarán el doble de veces que otros.
En este artículo, consideraremos principalmente técnicas que usan estrategias para eliminar un error sistemático, pero probablemente valga la pena decir que para un PRNG de 64 bits, el valor de sesgo en las aplicaciones normales probablemente sea insignificante.
Otro problema puede ser que algunos generadores tienen bits bajos débiles. Por ejemplo, las familias GPRS Xoroshiro + y Xoshiro + tienen bits bajos que no pasan las pruebas estadísticas. Cuando ejecutamos
% 52 (porque 52 es par), pasamos el bit de orden inferior directamente a la salida.
Multiplicar números de coma flotante (sesgados)
Otra técnica común es el uso de un PRNG que genera números de coma flotante en el intervalo [0..1) con la conversión posterior de estos números al intervalo deseado. Este enfoque se usa en Perl, se
recomienda usar
int(rand(10)) para generar un número entero en el intervalo [0..10) generando un número de punto flotante seguido de redondeo hacia abajo.
En C ++, este enfoque se escribe así:
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { double zeroone = 0x1.0p-32 * rng(); return range * zeroone; }
(Tenga en cuenta que
0x1.0p-32 es una constante binaria de coma flotante para 2
-32 , que usamos para convertir un entero aleatorio en el intervalo [0..2
32 ) para duplicar en el intervalo de la unidad; en cambio, podemos realizar dicha conversión usando
ldexp(rng(), -32) , pero cuando comparé este enfoque, resultó ser mucho más lento).
Este enfoque es tan sesgado como el resto clásico de la división, pero el sesgo parece diferente. Por ejemplo, si tuviéramos que seleccionar números en el intervalo [0..52), los números 0, 13, 26 y 39 ocurrirían una vez con menos frecuencia que otros.
Esta versión, cuando se generaliza a 64 bits, es aún más desagradable, ya que requiere un tipo de coma flotante cuya mantisa es de al menos 64 bits. En máquinas x86 con Linux y macOS, podemos usar el
long double para aprovechar la mayor precisión de los números de coma flotante x86 que tienen una mantisa de 64 bits, pero el
long double no se transfiere universalmente a todos los sistemas; en algunos sistemas, el
long double equivalente al
double .
Hay un buen lado: este enfoque es más rápido que las soluciones residuales para PRNG con bits bajos débiles.
Multiplicación de enteros (sesgada)
El método de multiplicación se puede adaptar a la aritmética de punto fijo en lugar de flotante. De hecho, simplemente multiplicamos constantemente por 2
32 ,
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); return m >> 32; }
Puede parecer que esta versión requiere aritmética de 64 bits, en los procesadores x86 un buen compilador compilará este código en una instrucción
mult 32 bits (que nos da dos valores de salida de 32 bits, uno de los cuales es el valor de retorno). Se puede esperar que esta versión sea rápida, pero está sesgada exactamente como el método de multiplicar números de coma flotante.
División de caída (sin sesgo)
Podemos modificar el esquema de multiplicación de coma flotante en un esquema basado en división. En lugar de multiplicar
x * range / 2**32 calculamos
x / (2**32 / range) . Dado que estamos trabajando con aritmética de enteros, el redondeo en esta versión se realizará de manera diferente y, a veces, generará valores fuera del intervalo deseado. Si descartamos estos valores (por ejemplo, nos deshacemos de ellos y generamos nuevos valores), entonces como resultado obtenemos una técnica sin distorsiones.
Por ejemplo, en el caso de extraer una tarjeta usando un PRNG de 32 bits, podemos generar un número de 32 bits y dividirlo por 2 32/52 = 82 595 524 para seleccionar una tarjeta. Esta técnica funciona si el valor aleatorio del PRNG de 32 bits es menor que 52 × 82595524 = 2 32/32 - 48. Si el valor aleatorio del PRNG es uno de los últimos 48 valores de la parte superior del intervalo del generador, entonces debe descartarlo y buscar otro.
Nuestro código para esta versión usa un truco para dividir 2
32 por
range sin usar matemáticas de 64 bits. Para el cálculo directo de
2**32 / range necesitamos representar el número 2
32 , que es demasiado grande (¡por uno!) Para representar como un entero de 32 bits. En cambio, tenemos en cuenta que para los enteros sin signo, el
range operación de negación unaria calcula un valor positivo de 2
32 -
range ; dividiendo este valor por
range , obtenemos una respuesta menor a
2**32 / range .
Por lo tanto, el código C ++ para generar números usando división y soltar se ve así:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
Por supuesto, este enfoque requiere dos operaciones lentas basadas en la división, que generalmente son más lentas que otras operaciones aritméticas, por lo que no debe esperar que sea rápido.
El resto de la división (doble) sin distorsiones - técnica OpenBSD
También podemos adoptar el enfoque de caída para eliminar la distorsión en el método clásico de resto de división. En el ejemplo con naipes, nuevamente necesitamos soltar 48 valores. En esta versión, en lugar de descartar los
últimos 48 valores, (equivalentemente) descartamos los
primeros 48 valores.
Aquí está la implementación de este enfoque en C ++:
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
Esta técnica elimina el sesgo, pero requiere dos operaciones de división que requieren mucho tiempo con el resto de cada valor de salida (y es posible que necesite un generador interno para crear varios números). Por lo tanto, se debe esperar que el método sea aproximadamente dos veces más lento que el enfoque sesgado clásico.
arc4random_uniform OpenBSD (que también se usa en OS X e iOS) usa esta estrategia.
Resto de división (simple) sin sesgo - metodología Java
Java usa un enfoque diferente para generar un número en un intervalo que usa solo una operación de división restante, con la excepción de casos bastante raros de descartar el resultado. Código:
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x, r; do { x = rng(); r = x % range; } while (x - r > (-range)); return r; }
Para entender por qué funciona esta opción, debe pensar un poco. A diferencia de la versión anterior basada en residuos, que elimina el sesgo al eliminar parte de los valores más bajos del motor de generación interna, esta versión filtra los valores de la parte superior del intervalo del motor.
Multiplicación de enteros sesgados - método de Lemira
De la misma manera que eliminamos el sesgo del resto del método de división, podemos eliminar el sesgo de la técnica de multiplicación de enteros. Esta técnica fue inventada por Lemyr.
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t t = (-range) % range; do { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); } while (l < t); return m >> 32; }
Soltar máscara de bits (sin sesgo): técnica de Apple
En nuestro último enfoque, la división y las operaciones restantes se eliminan por completo. En cambio, utiliza una operación de enmascaramiento simple para obtener un número aleatorio en el intervalo [0..2
k ), donde
k es el valor más pequeño, de modo que 2
k es mayor que el intervalo. Si el valor es demasiado grande para nuestro intervalo, lo descartamos e intentamos obtener otro. El código se muestra a continuación:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t mask = ~uint32_t(0); --range; mask >>= __builtin_clz(range|1); uint32_t x; do { x = rng() & mask; } while (x > range); return x; }
Apple adoptó este enfoque cuando (en el lanzamiento de macOS Sierra) realizó
su propia revisión del código
arc4random_uniform .
Técnicas básicas de evaluación comparativa
Ahora tenemos varios enfoques que pueden evaluarse. Desafortunadamente, cuando nos preocupan los costos de una operación de división única, la evaluación comparativa se convierte en algo no trivial. Ningún punto de referencia puede tener en cuenta todos los factores que afectan el campo de aplicación, y no hay garantía de que la mejor opción para su aplicación sea la mejor para la mía.
Utilizamos tres puntos de referencia y probamos las técnicas con muchos PRNG diferentes.
Benchmark Large-Shuffle
Probablemente el punto de referencia más obvio es la mezcla. En este punto de referencia, simulamos realizar mezclas a gran escala. Para ordenar una matriz de tamaño
N, debemos generar números en los intervalos [0 ..
N ), [0 .. (
N -1)), ..., [0..1). En este punto de referencia, asumiremos que
N es el número máximo posible (para
uint32_t es 2
32 -1). Código:
for (uint32_t i = 0xffffffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; }
Tenga en cuenta que "usamos" cada número agregándolo a la
sum (para que no sea desechado por la optimización), pero no realizamos ninguna mezcla para centrarnos en la generación de números.
Para probar la generación de 64 bits, tenemos una prueba similar, pero no será práctico realizar una prueba que corresponda a mezclar una matriz de 2
64-1 en tamaño (porque tomará muchos miles de años completar este punto de referencia más grande). En cambio, cruzamos todo el intervalo de 64 bits, pero generamos el mismo número de valores de salida que en la prueba de 32 bits. Código:
for (uint32_t i = 0xffffffff; i > 0; --i) { uint64_t bound = (uint64_t(i)<<32) | i; uint64_t bval = bounded_rand(rng, bound ); assert(bval < bound); sum += bval; }
Resultados del vórtice de Mersenne
Los resultados que se muestran a continuación demuestran el rendimiento de este punto de referencia para cada uno de los métodos que examinamos cuando usamos el vórtice de Mersenne y probamos en el código de 32 bits (usando
std::mt19937 de
libstdc++ ) y un código similar de 64 bits (usando
std:mt19937_64 de
libstdc++ ) Los resultados son la media geométrica de 15 corridas con diferentes valores de semillas, que luego se normaliza para que el método clásico de resto de división tenga un solo tiempo de corrida.
Puede parecer que tenemos respuestas claras sobre el rendimiento: parece que puede construir técnicas para su perfección y preguntarse en qué estaban pensando los desarrolladores de
libstdc++ cuando escribieron una implementación tan terrible para números de 32 bits. Pero, como suele ser el caso con la evaluación comparativa, la situación es más complicada de lo que parece a partir de estos resultados. En primer lugar, existe el riesgo de que los resultados puedan ser específicos del vórtice de Mersenne, por lo que ampliaremos los numerosos PRNG probados. En segundo lugar, puede haber un problema sutil con el punto de referencia mismo. Primero tratemos con la primera pregunta.
Resultados de diferentes PRNG
Probamos
arc4_rand32 32 bits con
arc4_rand32 ,
chacha8r ,
gjrand32 ,
jsf32 ,
mt19937 ,
pcg32 ,
pcg32_fast ,
sfc32 ,
splitmix32 ,
xoroshiro64+ ,
xorshift*64/32 xoshiro128+ ,
xoshiro128+ y
xoshiro128** , y
gjrand64 64 bits
jsf64 ,
mcg128 ,
mcg128_fast ,
mt19937_64 ,
pcg64 ,
pcg64_fast ,
sfc64 ,
splitmix64 ,
xoroshiro128+ ,
xorshift*128/64 xoshiro256+ ,
xoshiro256+ y
xoshiro256* . Estos kits nos darán algunos PRN lentos y muchos muy rápidos.
Aquí están los resultados:
Podemos ver las diferencias clave de los resultados con el vórtice de Mersenne. Los PRNG más rápidos desplazan el equilibrio hacia el código delimitador y, por lo tanto, la diferencia entre los diferentes enfoques se vuelve más pronunciada, especialmente en el caso de los PRNR de 64 bits. Con un conjunto más amplio de
libstc++ implementación de
libstc++ deja de parecer tan terrible.
Conclusiones
En este punto de referencia por un margen significativo, el enfoque basado en la multiplicación con sesgo gana en velocidad. Hay muchas situaciones en las que los límites serán pequeños en relación con el tamaño del PRNG, y el rendimiento es absolutamente crítico. En tales situaciones, es poco probable que un ligero sesgo tenga un efecto notable, pero la velocidad PRNG sí lo tendrá. Un ejemplo de ello es Quicksort con un punto de referencia aleatorio. De los métodos sesgados, la técnica de máscara de bits parece prometedora.
Pero antes de llegar a conclusiones serias, debemos señalar el gran problema de este punto de referencia: la mayor parte del tiempo se gasta en límites muy altos, lo que probablemente da una importancia excesiva a los grandes intervalos. Por lo tanto, debemos pasar al segundo punto de referencia.
Benchmark Small-Shuffle
Este punto de referencia es similar al anterior, pero realiza mucho menos "mezcla de matriz" (múltiple). Código: for (uint32_t j = 0; j < 0xffff; ++j) { for (uint32_t i = 0xffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; } }
Resultados del vórtice de Mersenne
Resultados de diferentes PRNG
Conclusiones
Este punto de referencia evita demasiado énfasis en los límites grandes y refleja con mayor precisión los casos de uso del mundo real, pero ahora descarta por completo los límites grandes.Punto de referencia para todos los intervalos
Este punto de referencia tiene como objetivo evitar las desventajas de los dos anteriores; realiza pruebas en cada tamaño de la potencia de dos para que cada tamaño esté presente, pero su influencia no se sobreestima. for (uint32_t bit = 1; bit != 0; bit <<= 1) { for (uint32_t i = 0; i < 0x1000000; ++i) { uint32_t bound = bit | (i & (bit - 1)); uint32_t bval = bounded_rand(rng, bound); assert(bval < bound); sum += bval; } }
Resultados del vórtice de Mersenne
Resultados de diferentes PRNG
Conclusiones
Muchos de nuestros hallazgos permanecen sin cambios. El método de inclinación es rápido si podemos soportar el error, y el esquema de máscara de bits parece ser una buena opción promedio.Podríamos terminar esto si no quisiéramos volver atrás, echar un vistazo crítico a nuestro código y realizar cambios en él.Hacer mejoras
Hasta este punto, todos los métodos de eliminación de sesgo requerían el uso de una operación adicional de división de división, razón por la cual se realizan mucho más lentamente que los métodos de sesgo. Sería útil si pudiéramos reducir esta ventaja.Caída basada en el umbral más rápido
Algunos de nuestros algoritmos tienen código que utiliza un valor umbral, por ejemplo: uint32_t bounded_rand(rng_t& rng, uint32_t range) {
Cuando es rangepequeño en comparación con el intervalo de salida PRNG, la mayoría de las veces el número será mucho mayor que el umbral. Es decir, si podemos agregar una estimación preliminar del umbral, que puede ser un poco más, ahorraremos en la costosa operación de tomar el resto de la división.El siguiente código maneja esta tarea: uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t r = rng(); if (r < range) { uint32_t t = (-range) % range; while (r < t) r = rng(); } return r % range; }
Este cambio puede aplicarse tanto a "Mod doble sin distorsiones" (ver arriba) como a "multiplicación entera sin distorsiones". La idea fue inventada por Lemir, quien la aplicó al segundo método (pero no al primero).Resultados comparativos de gran tamaño aleatorio
Esta optimización conduce a una mejora significativa en los resultados del benchmark de 64 bits (en el que el mod es aún más lento), pero de hecho degrada ligeramente el rendimiento en el benchmark de 32 bits. A pesar de las mejoras, el método de máscara de bits aún gana.Resultados de referencia compactos pequeños
Por otro lado, este cambio acelera significativamente el punto de referencia de shuffle pequeño tanto para el método de multiplicación de enteros como para el método del doble resto de división. En ambos casos, su rendimiento se acerca más a los resultados de las opciones sin distorsiones. El rendimiento del método de doble residuo (OpenBSD) ahora es casi igual al rendimiento del método de un solo residuo (Java).Resultados de referencia para todos los intervalos
Vemos una mejora similar en el punto de referencia para todos los intervalos.Parece que podemos anunciar un nuevo ganador universal: un método optimizado para multiplicar enteros Lemire sin sesgar.División resto optimización
Típicamente, un cálculo a % brequiere división, pero en situaciones donde el a < bresultado es simple ay no se requiere división. Y cuando a/2 < b, el resultado es simple a - b. Por lo tanto, en lugar de computar a %= b;
podemos cumplir if (a >= b) { a -= b; if (a >= b) a %= b; }
El costo de dividir es tan significativo que aumentar el costo de este código más complejo puede justificarse ahorrando tiempo debido a la falta de división.Resultados comparativos de gran tamaño aleatorio
Agregar esta optimización mejora en gran medida los resultados del punto de referencia de reproducción aleatoria grande. Esto es nuevamente más notable en el código de 64 bits, donde la operación de tomar el resto es más costosa. El método de doble residuo (estilo OpenBSD) muestra versiones con optimizaciones para una sola operación restante y para ambas.En este punto de referencia, la máscara de bits sigue siendo la ganadora, pero el límite entre esta y el enfoque de Lemira se ha reducido significativamente.Resultados de referencia compactos pequeños
Agregar esta optimización no aumenta el rendimiento del punto de referencia de reproducción aleatoria pequeña, por lo que la pregunta sigue siendo solo si agrega costos significativos. En algunos casos, no; en otros, los costos aumentan ligeramente.Resultados de referencia para todos los intervalos
En el punto de referencia para todos los intervalos, los cambios también son pequeños.Bonificación: resultados de comparación de PRSP
La razón principal para utilizar una gran cantidad de PRNG para probar esquemas numéricos a intervalos fue evitar la distorsión accidental de los resultados debido a las peculiaridades de la operación de los esquemas PRNG individuales. Pero podemos usar los mismos resultados de las pruebas internas para comparar los esquemas de generación en sí.PRNG con salida de 32 bits
El siguiente gráfico muestra el rendimiento de diferentes esquemas de generación de 32 bits, promediados para todos los métodos y quince ejecuciones, normalizados para el rendimiento del vórtice Mersenne de 32 bits:Por un lado, me alegra ver que pcg32_fastes realmente rápido: fue derrotado solo por una versión pequeña de Xoroshiro (que no pasa las pruebas estadísticas). Pero esto también muestra por qué rara vez me molesto por el rendimiento de los PRSP modernos de alto rendimiento de propósito general: la diferencia entre los diferentes métodos es muy insignificante. En particular, los cuatro circuitos más rápidos difieren en rendimiento en menos del 5%, y creo que esto es simplemente causado por el "ruido".PRNG con la salida de números de 64 bits
El gráfico muestra el rendimiento de varios esquemas de generación de 64 bits promediados entre todas las técnicas y quince ejecuciones normalizadas para el rendimiento del vórtice Mersenne de 32 bits. Puede parecer extraño que la normalización se realice utilizando el vórtice Mersenne de 32 bits, pero esto nos permite ver los costos adicionales del uso de la generación de 64 bits en los casos en que la generación de 32 bits es suficiente.Estos resultados confirman que es mcg128_fastincreíblemente rápido, pero las últimas cuatro técnicas nuevamente difieren solo en un 5%, por lo que es difícil elegir entre los métodos más rápidos. pcg64y pcg64_fastdebe ser más lento mcg128_fast, porque sus generadores básicos son generadores congruentes lineales de 128 bits (LCG) y generadores congruentes multiplicativos de 128 bits (MCG, MCG). A pesar de que no son las técnicas más rápidas en este conjunto, siguen pcg64siendo un 20% más rápidas que el vórtice Mersenne de 64 bits.Pero quizás lo más importante, estos resultados también muestran que si no necesita una salida de 64 bits, un PRNG de 64 bits suele ser más lento que uno de 32 bits.Conclusiones
Desde nuestros puntos de referencia, podemos ver que la transición de los PRNG utilizados de manera estándar (por ejemplo, el vórtice Mersenne de 32 bits) a PRNP más rápidos redujo el tiempo de ejecución de los puntos de referencia en un 45%. Pero la transición del método estándar de encontrar el número en el intervalo a nuestro método más rápido nos permitió reducir el tiempo de referencia en aproximadamente un 66%; en otras palabras, hasta un tercio del tiempo original.El método más rápido (sin distorsiones) es el método Lemira (con mi optimización adicional). Aquí esta: uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); if (l < range) { uint32_t t = -range; if (t >= range) { t -= range; if (t >= range) t %= range; } while (l < t) { x = rng(); m = uint64_t(x) * uint64_t(range); l = uint32_t(m); } } return m >> 32; }
El uso del método Lemira mejorará el rendimiento de la mayoría de los algoritmos aleatorios más que pasar de un motor de generación rápida a uno más rápido.Apéndices: Notas de prueba
El código de todas las pruebas se publica en GitHub . En total, probé 23 métodos para bounded_randusar 26 PRN diferentes (13 PRN de 32 bits y 13 de 64 bits), en dos compiladores (GCC 8 y LLVM 6), que me dieron 26 * 23 * 2 = 1196 archivos ejecutables, cada uno de los cuales se realizó con las mismas 15 semillas, lo que da 1196 * 15 = 17,940 ejecuciones de prueba únicas, en cada una de las cuales se combinan tres puntos de referencia. Básicamente, realicé pruebas en una máquina de 48 núcleos con cuatro procesadores Xeon E7-4830v3 de 2.1 GHz. Realizar un conjunto completo de pruebas tomó un poco menos de un mes de tiempo de procesador.Al final, volvemos a la situación desde la introducción del artículo. Imagina que Sasha usaba jsf32.STD-libc++y Juan ...mt19937.BIASED_FP_MULT_SCALE. En el punto de referencia 3, este último lleva un 69,6% menos de tiempo. Es decir, el tiempo de esta situación ficticia se basa en datos de la realidad.