c++ - sirve - randomize en c

¿Es la variable local no inicializada el generador de números aleatorios más rápido? (22)

Sé que la variable local no inicializada es un comportamiento indefinido ( UB ), y también el valor puede tener representaciones de trampa que pueden afectar la operación adicional, pero a veces quiero usar el número aleatorio solo para representación visual y no lo usaré más en otra parte de programa, por ejemplo, establece algo con color aleatorio en un efecto visual, por ejemplo:

void updateEffect(){ for(int i=0;i<1000;i++){ int r; int g; int b; star[i].setColor(r%255,g%255,b%255); bool isVisible; star[i].setVisible(isVisible); } }

¿Es eso más rápido que

void updateEffect(){ for(int i=0;i<1000;i++){ star[i].setColor(rand()%255,rand()%255,rand()%255); star[i].setVisible(rand()%2==0?true:false); } }

y también más rápido que otro generador de números aleatorios?

Como han dicho otros, será rápido, pero no al azar.

Lo que la mayoría de los compiladores harán para las variables locales es obtener algo de espacio en la pila, pero no molestarse en configurarlo (el estándar dice que no es necesario, entonces, ¿por qué ralentizar el código que está generando?).

En este caso, el valor que obtendrá dependerá de lo que estaba previamente en la pila: si llama a una función anterior a esta que tiene un centenar de variables de caracteres locales configuradas en ''Q'' y luego llama a su función después que regresa, entonces probablemente encontrará que sus valores "aleatorios" se comportan como si los tuviera memset() todos a ''Q''.

Es importante para su función de ejemplo que intenta usar esto, estos valores no cambiarán cada vez que los lea, serán los mismos cada vez. Por lo tanto, obtendrá un total de 100 estrellas con el mismo color y visibilidad.

Además, nada dice que el compilador no debe inicializar estos valores, por lo que un compilador futuro podría hacerlo.

En general: mala idea, no lo hagas. (como muchas optimizaciones de nivel de código "inteligentes" realmente ...)

Como otros ya han mencionado, este es un comportamiento indefinido ( UB ), pero puede "funcionar".

Excepto por problemas ya mencionados por otros, veo otro problema (desventaja): no funcionará en ningún lenguaje que no sea C y C ++. Sé que esta pregunta es sobre C ++, pero si puede escribir código que será un buen código C ++ y Java y no es un problema, ¿por qué no? Tal vez algún día alguien tenga que portarlo a otro idioma y buscar errores causados por ~~"trucos de magia"~~ UB como este definitivamente será una pesadilla (especialmente para un desarrollador inexperto de C / C ++).

Here hay una pregunta sobre otra UB similar. Imagínese tratando de encontrar un error como este sin saber acerca de este UB. Si desea leer más sobre cosas tan extrañas en C / C ++, lea las respuestas a las preguntas desde el enlace y vea this GRAN presentación de diapositivas. Le ayudará a comprender qué hay debajo del capó y cómo está funcionando; no es solo otra presentación de diapositivas llena de "magia". Estoy bastante seguro de que incluso la mayoría de los programadores experimentados de C / c ++ pueden aprender mucho de esto.

El uso de datos no inicializados para aleatoriedad no es necesariamente algo malo si se hace correctamente. De hecho, OpenSSL hace exactamente esto para sembrar su PRNG.

Aparentemente, este uso no estaba bien documentado, porque alguien notó que Valgrind se quejaba de usar datos no inicializados y los "reparó", causando un error en el PRNG .

Para que pueda hacerlo, pero necesita saber lo que está haciendo y asegurarse de que cualquiera que lea su código entienda esto.

Hay una posibilidad más para considerar.

Los compiladores modernos (ejem g ++) son tan inteligentes que revisan su código para ver qué instrucciones afectan el estado y qué no, y si se garantiza que una instrucción NO afectará el estado, g ++ simplemente eliminará esa instrucción.

Entonces, esto es lo que sucederá. g ++ definitivamente verá que está leyendo, realizando operaciones aritméticas, guardando, lo que es esencialmente un valor basura, que produce más basura. Como no hay garantía de que la nueva basura sea más útil que la anterior, simplemente eliminará su ciclo. BLOOP!

Este método es útil, pero esto es lo que haría. Combine UB (Comportamiento indefinido) con velocidad rand ().

Por supuesto, reduce los rand() s ejecutados, pero mézclalos para que el compilador no haga nada que no quieras.

Y no te despediré.

Me gusta tu forma de pensar. Realmente fuera de la caja. Sin embargo, la compensación realmente no vale la pena. La compensación del tiempo de ejecución de la memoria es una cosa, incluido el comportamiento indefinido para el tiempo de ejecución no lo es .

Debe darle una sensación muy inquietante saber que está utilizando un método "aleatorio" como su lógica comercial. No lo haré.

Use 7757 todos los lugares donde tenga la tentación de usar variables no inicializadas. Lo elegí al azar de una lista de números primos:

es comportamiento definido
se garantiza que no siempre será 0
es primo
es probable que sea estadísticamente aleatorio como variables no inicializadas
es probable que sea más rápido que las variables no inicializadas ya que su valor se conoce en tiempo de compilación

¡Buena pregunta!

Indefinido no significa que sea aleatorio. Piénselo, los valores que obtendría en variables globales no inicializadas fueron dejados allí por el sistema o su / otras aplicaciones en ejecución. Dependiendo de lo que haga su sistema con la memoria ya no utilizada y / o qué tipo de valores generan el sistema y las aplicaciones, puede obtener:

Siempre lo mismo.
Sé uno de un pequeño conjunto de valores.
Obtenga valores en uno o más rangos pequeños.
Vea muchos valores divisibles por 2/4/8 de punteros en el sistema de 16/32/64 bits
...

Los valores que obtendrá dependen completamente de los valores no aleatorios que deja el sistema y / o las aplicaciones. Entonces, de hecho, habrá algo de ruido (a menos que el sistema elimine la memoria), pero el grupo de valores del que extraerá no será aleatorio.

Las cosas empeoran mucho para las variables locales porque provienen directamente de la pila de su propio programa. Existe una muy buena posibilidad de que su programa realmente escriba estas ubicaciones de pila durante la ejecución de otro código. Calculo que las posibilidades de suerte en esta situación son muy bajas, y un cambio de código ''aleatorio'' que realice prueba esta suerte.

Leer sobre randomness . Como verá, la aleatoriedad es una propiedad muy específica y difícil de obtener. Es un error común pensar que si solo toma algo que es difícil de rastrear (como su sugerencia) obtendrá un valor aleatorio.

¡Muy mal! Mal hábito, mal resultado. Considerar:

A_Function_that_use_a_lot_the_Stack(); updateEffect();

Si la función A_Function_that_use_a_lot_the_Stack() realiza siempre la misma inicialización, deja la pila con los mismos datos. Esos datos son lo que recibimos llamando a updateEffect() : ¡ siempre el mismo valor! .

Como la mayoría de las personas aquí mencionan un comportamiento indefinido Indefinido también significa que puede obtener un valor entero válido (por suerte) y en este caso será más rápido (ya que no se realiza la llamada a la función rand). Pero prácticamente no lo uses. Estoy seguro de que esto tendrá resultados terribles ya que la suerte no está contigo todo el tiempo.

Como otros han señalado, este es un comportamiento indefinido (UB).

En la práctica, (probablemente) realmente (tipo de) funcionará. Leer desde un registro no inicializado en arquitecturas x86 [-64] producirá resultados basura, y probablemente no hará nada malo (a diferencia de, por ejemplo, Itanium, donde los registros se pueden marcar como no válidos , de modo que se lee errores de propagación como NaN).

Sin embargo, hay dos problemas principales:

No será particularmente al azar. En este caso, está leyendo desde la pila, por lo que obtendrá lo que estaba allí anteriormente. Lo que podría ser efectivamente aleatorio, completamente estructurado, la contraseña que ingresó hace diez minutos o la receta de galletas de su abuela.
Es una mala práctica (mayúscula ''B'') dejar que cosas como estas se cuelen en tu código. Técnicamente, el compilador podría insertar reformat_hdd(); cada vez que lees una variable indefinida. No lo hará , pero no debes hacerlo de todos modos. No hagas cosas inseguras. Cuantas menos excepciones haga, más seguro estará de los errores accidentales todo el tiempo.

El problema más apremiante con UB es que hace que el comportamiento de todo su programa sea indefinido. Los compiladores modernos pueden usar esto para evitar grandes extensiones de su código o incluso retroceder en el tiempo . Jugar con UB es como un ingeniero victoriano que desmantela un reactor nuclear en vivo. Hay un montón de cosas que salen mal, y probablemente no conozca la mitad de los principios subyacentes o la tecnología implementada. Puede estar bien, pero aún así no debes dejar que suceda. Mira las otras buenas respuestas para más detalles.

Además, te despediría.

Debe tener una definición de lo que quiere decir con "aleatorio". Una definición sensata implica que los valores que obtienes deben tener poca correlación. Eso es algo que puedes medir. Tampoco es trivial lograrlo de manera controlada y reproducible. Por lo tanto, el comportamiento indefinido ciertamente no es lo que está buscando.

El comportamiento indefinido es indefinido. No significa que obtenga un valor indefinido, significa que el programa puede hacer cualquier cosa y aún así cumplir con las especificaciones del lenguaje.

Un buen compilador de optimización debería tomar

void updateEffect(){ for(int i=0;i<1000;i++){ int r; int g; int b; star[i].setColor(r%255,g%255,b%255); bool isVisible; star[i].setVisible(isVisible); } }

y compilarlo en un noop. Esto es ciertamente más rápido que cualquier otra alternativa. Tiene el inconveniente de que no hará nada, pero ese es el inconveniente del comportamiento indefinido.

El comportamiento indefinido significa que los autores de los compiladores son libres de ignorar el problema porque los programadores nunca tendrán derecho a quejarse de lo que suceda.

Si bien, en teoría, al ingresar a la tierra de UB, cualquier cosa puede suceder (incluido un demonio volando por la nariz ), lo que normalmente significa es que a los autores del compilador simplemente no les importará y, para las variables locales, el valor será lo que esté en la memoria de la pila en ese punto .

Esto también significa que a menudo el contenido será "extraño" pero fijo o ligeramente aleatorio o variable, pero con un patrón evidente claro (por ejemplo, valores crecientes en cada iteración).

Seguro que no puedes esperar que sea un generador aleatorio decente.

Hay ciertas situaciones en las que la memoria no inicializada se puede leer de forma segura utilizando el tipo "unsigned char *" [por ejemplo, un búfer devuelto por malloc ]. El código puede leer dicha memoria sin tener que preocuparse de que el compilador arroje la causalidad por la ventana, y hay momentos en que puede ser más eficiente tener el código preparado para cualquier cosa que pueda contener la memoria que para garantizar que no se leerán los datos no inicializados ( un ejemplo común de esto sería usar memcpy en un búfer parcialmente inicializado en lugar de copiar discretamente todos los elementos que contienen datos significativos).

Sin embargo, incluso en tales casos, siempre se debe suponer que si alguna combinación de bytes será particularmente irritante, leerla siempre generará ese patrón de bytes (y si un cierto patrón sería irritante en la producción, pero no en el desarrollo, tal patrón no aparecerá hasta que el código esté en producción).

La lectura de memoria no inicializada podría ser útil como parte de una estrategia de generación aleatoria en un sistema embebido donde uno puede estar seguro de que la memoria nunca se ha escrito con contenido sustancialmente no aleatorio desde la última vez que se encendió el sistema, y si la fabricación El proceso utilizado para la memoria hace que su estado de encendido varíe de forma semialeatoria. El código debería funcionar incluso si todos los dispositivos siempre producen los mismos datos, pero en casos donde, por ejemplo, un grupo de nodos necesita seleccionar ID únicos arbitrarios lo más rápido posible, tener un generador "no muy aleatorio" que le da a la mitad de los nodos la misma inicial La identificación podría ser mejor que no tener ninguna fuente inicial de aleatoriedad en absoluto.

Muchas buenas respuestas, pero me permiten agregar otra y enfatizar el punto de que en una computadora determinista, nada es aleatorio. Esto es cierto tanto para los números producidos por un pseudo-RNG como para los números aparentemente "aleatorios" que se encuentran en áreas de memoria reservadas para variables locales C / C ++ en la pila.

PERO ... hay una diferencia crucial.

Los números generados por un buen generador pseudoaleatorio tienen las propiedades que los hacen estadísticamente similares a los sorteos verdaderamente aleatorios. Por ejemplo, la distribución es uniforme. La duración del ciclo es larga: puede obtener millones de números aleatorios antes de que el ciclo se repita. La secuencia no está autocorrelacionada: por ejemplo, no comenzará a ver emerger patrones extraños si toma cada segundo, tercero o 27º número, o si observa dígitos específicos en los números generados.

En contraste, los números "aleatorios" que quedan en la pila no tienen ninguna de estas propiedades. Sus valores y su aparente aleatoriedad dependen completamente de cómo se construye el programa, cómo se compila y cómo el compilador lo optimiza. A modo de ejemplo, aquí hay una variación de su idea como programa autónomo:

#include <stdio.h> notrandom() { int r, g, b; printf("R=%d, G=%d, B=%d", r&255, g&255, b&255); } int main(int argc, char *argv[]) { int i; for (i = 0; i < 10; i++) { notrandom(); printf("/n"); } return 0; }

Cuando compilo este código con GCC en una máquina Linux y lo ejecuto, resulta ser bastante desagradable determinista:

R=0, G=19, B=0 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255 R=130, G=16, B=255

Si miraba el código compilado con un desensamblador, podría reconstruir lo que estaba sucediendo, en detalle. La primera llamada a notrandom () usó un área de la pila que este programa no usaba anteriormente; Quién sabe lo que había allí. Pero después de esa llamada a notrandom (), hay una llamada a printf () (que el compilador GCC realmente optimiza para una llamada a putchar (), pero no importa) y que sobrescribe la pila. Por lo tanto, las próximas veces y posteriores, cuando se llama a notrandom (), la pila contendrá datos obsoletos de la ejecución de putchar (), y dado que putchar () siempre se llama con los mismos argumentos, estos datos obsoletos siempre serán los mismos, también.

Por lo tanto, no hay absolutamente nada al azar sobre este comportamiento, ni los números obtenidos de esta manera tienen ninguna de las propiedades deseables de un generador de números pseudoaleatorios bien escrito. De hecho, en la mayoría de los escenarios de la vida real, sus valores serán repetitivos y altamente correlacionados.

De hecho, como otros, también consideraría seriamente despedir a alguien que intentó pasar esta idea como un "RNG de alto rendimiento".

No, es terrible

El comportamiento de usar una variable no inicializada no está definido tanto en C como en C ++, y es muy poco probable que dicho esquema tenga propiedades estadísticas deseables.

Si desea un generador de números aleatorios "rápido y sucio", entonces rand() es su mejor opción. En su implementación, todo lo que hace es una multiplicación, una suma y un módulo.

El generador más rápido que conozco requiere que use un uint32_t como el tipo de la variable pseudoaleatoria I , y use

I = 1664525 * I + 1013904223

para generar valores sucesivos. Puede elegir cualquier valor inicial de I (llamado semilla ) que desee. Obviamente puedes codificar eso en línea. La envoltura garantizada estándar de un tipo sin signo actúa como módulo. (Las constantes numéricas son cuidadosamente seleccionadas por el notable programador científico Donald Knuth).

Permítanme decir esto claramente: no invocamos comportamientos indefinidos en nuestros programas . Nunca es una buena idea, punto. Hay raras excepciones a esta regla; por ejemplo, si es un implementador de bibliotecas que implementa offsetof . Si su caso se encuentra bajo tal excepción, probablemente ya lo sepa. En este caso, sabemos que el uso de variables automáticas no inicializadas es un comportamiento indefinido .

Los compiladores se han vuelto muy agresivos con optimizaciones en torno al comportamiento indefinido y podemos encontrar muchos casos en los que el comportamiento indefinido ha dado lugar a fallas de seguridad. El caso más infame es probablemente la eliminación de la comprobación de puntero nulo del kernel de Linux que menciono en mi respuesta al error de compilación de C ++. donde una optimización del compilador en torno al comportamiento indefinido convirtió un bucle finito en uno infinito.

Podemos leer las optimizaciones peligrosas y la pérdida de causalidad de CERT ( video ) que dice, entre otras cosas:

Cada vez más, los escritores de compiladores se aprovechan de comportamientos indefinidos en los lenguajes de programación C y C ++ para mejorar las optimizaciones.

Con frecuencia, estas optimizaciones interfieren con la capacidad de los desarrolladores para realizar análisis de causa y efecto en su código fuente, es decir, analizar la dependencia de los resultados posteriores de los resultados anteriores.

En consecuencia, estas optimizaciones eliminan la causalidad en el software y aumentan la probabilidad de fallas, defectos y vulnerabilidades del software.

Específicamente con respecto a los valores indeterminados, el informe de defectos estándar C 451: La inestabilidad de las variables automáticas sin inicializar constituye una lectura interesante. Todavía no se ha resuelto, pero introduce el concepto de valores tambaleantes, lo que significa que la indeterminación de un valor puede propagarse a través del programa y puede tener diferentes valores indeterminados en diferentes puntos del programa.

No conozco ningún ejemplo de dónde sucede esto, pero en este momento no podemos descartarlo.

Ejemplos reales, no el resultado que esperas

Es poco probable que obtenga valores aleatorios. Un compilador podría optimizar por completo el ciclo. Por ejemplo, con este caso simplificado:

void updateEffect(int arr[20]){ for(int i=0;i<20;i++){ int r ; arr[i] = r ; } }

clang lo optimiza ( verlo en vivo ):

updateEffect(int*): # @updateEffect(int*) retq

o tal vez obtener todos los ceros, como con este caso modificado:

void updateEffect(int arr[20]){ for(int i=0;i<20;i++){ int r ; arr[i] = r%255 ; } }

verlo en vivo :

updateEffect(int*): # @updateEffect(int*) xorps %xmm0, %xmm0 movups %xmm0, 64(%rdi) movups %xmm0, 48(%rdi) movups %xmm0, 32(%rdi) movups %xmm0, 16(%rdi) movups %xmm0, (%rdi) retq

Ambos casos son formas perfectamente aceptables de comportamiento indefinido.

Tenga en cuenta que si estamos en un Itanium podríamos terminar con un valor de trampa :

[...] si el registro tiene un valor especial que no es nada, lea las trampas del registro excepto por unas pocas instrucciones [...]

Otras notas importantes

Es interesante observar la variación entre gcc y clang notada en el proyecto de UB Canarias sobre cuán dispuestos están a aprovechar el comportamiento indefinido con respecto a la memoria no inicializada. El artículo señala ( énfasis mío ):

Por supuesto, debemos ser completamente claros con nosotros mismos de que cualquier expectativa no tiene nada que ver con el estándar del lenguaje y todo lo que tiene que ver con lo que un compilador en particular hace, ya sea porque los proveedores de ese compilador no están dispuestos a explotar esa UB o simplemente porque aún no han llegado a explotarlo . Cuando no existe una garantía real del proveedor del compilador, nos gusta decir que los UB aún no explotados son bombas de tiempo : están esperando para explotar el próximo mes o el próximo año cuando el compilador se vuelva un poco más agresivo.

Como Matthieu M. señala Lo que todo programador de C debe saber sobre el comportamiento indefinido # 2/3 también es relevante para esta pregunta. Dice entre otras cosas ( énfasis mío ):

Lo importante y aterrador es darse cuenta de que casi cualquier optimización basada en un comportamiento indefinido puede comenzar a activarse en un código defectuoso en cualquier momento en el futuro . La alineación, el desenrollado de bucles, la promoción de memoria y otras optimizaciones seguirán mejorando, y una parte importante de su razón para existir es exponer optimizaciones secundarias como las anteriores.

Para mí, esto es profundamente insatisfactorio, en parte porque inevitablemente se culpa al compilador, pero también porque significa que enormes cuerpos de código C son minas terrestres que esperan explotar.

Para completar, probablemente debería mencionar que las implementaciones pueden elegir hacer que el comportamiento indefinido esté bien definido, por ejemplo, gcc permite la escritura de tipos a través de uniones, mientras que en C ++ esto parece un comportamiento indefinido . Si este es el caso, la implementación debería documentarlo y, por lo general, esto no será portátil.

Por razones de seguridad, se debe limpiar la nueva memoria asignada a un programa; de lo contrario, se podría usar la información y las contraseñas podrían filtrarse de una aplicación a otra. Solo cuando reutiliza la memoria, obtiene valores diferentes a 0. Y es muy probable que en una pila el valor anterior sea fijo, porque el uso anterior de esa memoria es fijo.

Realicé una prueba muy simple, y no fue aleatoria en absoluto.

#include <stdio.h> int main() { int a; printf("%d/n", a); return 0; }

Cada vez que ejecuté el programa, imprimió el mismo número ( 32767 en mi caso): no puede ser mucho menos aleatorio que eso. Probablemente sea el código de inicio en la biblioteca de tiempo de ejecución que quede en la pila. Dado que usa el mismo código de inicio cada vez que se ejecuta el programa, y nada más varía en el programa entre ejecuciones, los resultados son perfectamente consistentes.

Su ejemplo de código particular probablemente no haría lo que espera. Si bien técnicamente cada iteración del bucle recrea las variables locales para los valores r, g y b, en la práctica es exactamente el mismo espacio de memoria en la pila. Por lo tanto, no se volverá a aleatorizar con cada iteración, y terminará asignando los mismos 3 valores para cada uno de los 1000 colores, independientemente de cuán aleatorios sean r, g y b individualmente e inicialmente.

De hecho, si funcionara, tendría mucha curiosidad sobre lo que lo aleatoriza. Lo único que se me ocurre es una interrupción intercalada que se coloca encima de esa pila, muy poco probable. Quizás la optimización interna que los mantuvo como variables de registro en lugar de como ubicaciones de memoria real, donde los registros se reutilizan más abajo en el ciclo, también sería el truco, especialmente si la función de visibilidad establecida es particularmente hambrienta de registros. Aún así, lejos de ser al azar.

Todavía no se menciona, pero las rutas de código que invocan un comportamiento indefinido pueden hacer lo que el compilador quiera, por ejemplo

void updateEffect(){}

Lo cual es ciertamente más rápido que su bucle correcto, y debido a UB, es perfectamente conforme.

No es una buena idea confiar nuestra lógica en el comportamiento indefinido del lenguaje. Además de lo mencionado / discutido en esta publicación, me gustaría mencionar que con el enfoque / estilo moderno de C ++, dicho programa puede no compilarse.

Esto se mencionó en mi publicación anterior que contiene la ventaja de la función automática y un enlace útil para la misma.

https://.com/a/26170069/2724703

Entonces, si cambiamos el código anterior y reemplazamos los tipos reales con auto , el programa ni siquiera se compilaría.

void updateEffect(){ for(int i=0;i<1000;i++){ auto r; auto g; auto b; star[i].setColor(r%255,g%255,b%255); auto isVisible; star[i].setVisible(isVisible); } }