Ist eine nicht initialisierte lokale Variable der schnellste Zufallszahlengenerator?

328

Ich weiß, dass die nicht initialisierte lokale Variable undefiniertes Verhalten ( UB ) ist, und der Wert kann auch Trap-Darstellungen aufweisen, die den weiteren Betrieb beeinflussen können, aber manchmal möchte ich die Zufallszahl nur für die visuelle Darstellung verwenden und werde sie in anderen Teilen von nicht weiter verwenden Programm zum Beispiel etwas mit zufälliger Farbe in einem visuellen Effekt einstellen, zum Beispiel:

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);
    }
}

ist es das schneller als

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);
    }
}

und auch schneller als andere Zufallszahlengeneratoren?

ggrr
quelle
88
+1 Dies ist eine absolut legitime Frage. Es stimmt , dass in der Praxis nicht initialisierte Werte könnten kindof zufällig sein. Die Tatsache, dass sie nicht besonders sind und dass es UB ist, macht das Fragen nicht so schlimm.
Imallett
35
@imallett: Auf jeden Fall. Dies ist eine gute Frage, und mindestens ein altes Z80-Spiel (Amstrad / ZX Spectrum) hat in der Vergangenheit sein Programm als Daten verwendet, um sein Terrain einzurichten. Es gibt also sogar Präzedenzfälle. Das kann ich heutzutage nicht mehr. Moderne Betriebssysteme nehmen den ganzen Spaß weg.
Bathsheba
81
Das Hauptproblem ist sicherlich, dass es nicht zufällig ist.
John
30
Tatsächlich gibt es ein Beispiel für eine nicht initialisierte Variable, die als Zufallswert verwendet wird (siehe Debian RNG-Katastrophe (Beispiel 4 in diesem Artikel )).
PaperBirdMaster
31
In der Praxis - und glauben Sie mir, ich debugge viel auf verschiedenen Architekturen - kann Ihre Lösung zwei Dinge tun: entweder nicht initialisierte Register lesen oder nicht initialisierten Speicher. Während "nicht initialisiert" in gewisser Weise zufällig bedeutet, enthält es in der Praxis höchstwahrscheinlich a) Nullen , b) sich wiederholende oder konsistente Werte (im Fall eines Lesespeichers , der früher von digitalen Medien belegt war) oder c) konsistenten Müll mit einem begrenzten Wert gesetzt (im Falle des Lesenspeichers, der früher von codierten digitalen Daten belegt war). Keine davon ist eine echte Entropiequelle.
mg30rg

Antworten:

299

Wie andere angemerkt haben, ist dies Undefined Behavior (UB).

In der Praxis wird es (wahrscheinlich) tatsächlich (irgendwie) funktionieren. Das Lesen aus einem nicht initialisierten Register auf x86 [-64] -Architekturen führt in der Tat zu Müllergebnissen und wird wahrscheinlich nichts Schlechtes bewirken (im Gegensatz zu z. B. Itanium, wo Register als ungültig gekennzeichnet werden können , sodass Lesevorgänge Fehler wie NaN verbreiten).

Es gibt jedoch zwei Hauptprobleme:

  1. Es wird nicht besonders zufällig sein. In diesem Fall lesen Sie vom Stapel, sodass Sie alles erhalten, was zuvor vorhanden war. Das kann zufällig sein, vollständig strukturiert, das Passwort, das Sie vor zehn Minuten eingegeben haben, oder das Cookie-Rezept Ihrer Großmutter.

  2. Es ist eine schlechte Praxis (Großbuchstabe 'B') , solche Dinge in Ihren Code einschleichen zu lassen. Technisch gesehen könnte der Compiler reformat_hdd();jedes Mal einfügen, wenn Sie eine undefinierte Variable lesen. Es wird nicht , aber Sie sollten es trotzdem nicht tun. Mach keine unsicheren Dinge. Je weniger Ausnahmen Sie machen, sind die sicherere Sie vor unbeabsichtigtem Fehler all die Zeit.

Das dringlichere Problem bei UB ist, dass das Verhalten Ihres gesamten Programms dadurch nicht definiert wird. Moderne Compiler können diese verwenden , um große Schwaden von Code elide oder sogar in der Zeit zurückgehen . Mit UB zu spielen ist wie ein viktorianischer Ingenieur, der einen lebenden Kernreaktor zerlegt. Es gibt zig Dinge, die schief gehen können, und Sie werden wahrscheinlich nicht die Hälfte der zugrunde liegenden Prinzipien oder der implementierten Technologie kennen. Es mag in Ordnung sein, aber Sie sollten es trotzdem nicht zulassen. Schauen Sie sich die anderen netten Antworten für Details an.

Außerdem würde ich dich feuern.

imallett
quelle
39
@Potatoswatter: Itanium-Register können NaT (Not a Thing) enthalten, das praktisch ein "nicht initialisiertes Register" ist. Unter Itanium kann das Lesen aus einem Register, wenn Sie nicht darauf geschrieben haben, Ihr Programm abbrechen (mehr dazu hier: blogs.msdn.com/b/oldnewthing/archive/2004/01/19/60162.aspx ). Es gibt also einen guten Grund, warum das Lesen nicht initialisierter Werte ein undefiniertes Verhalten ist. Es ist wahrscheinlich auch ein Grund, warum Itanium nicht sehr beliebt ist :)
Tbleher
58
Ich lehne den Begriff "es funktioniert" wirklich ab. Selbst wenn es heute wahr wäre, was es nicht ist, könnte es sich aufgrund aggressiverer Compiler jederzeit ändern. Der Compiler kann jeden unreachable()Lesevorgang durch die Hälfte Ihres Programms ersetzen und diese löschen. Dies geschieht auch in der Praxis. Dieses Verhalten hat das RNG in einigen Linux-Distributionen, glaube ich, vollständig neutralisiert.; Die meisten Antworten in dieser Frage scheinen davon auszugehen, dass sich ein nicht initialisierter Wert überhaupt wie ein Wert verhält. Das ist falsch
usr
25
Außerdem würde ich Sie entlassen, scheint eine ziemlich dumme Sache zu sein, vorausgesetzt, gute Praktiken sollten bei der Codeüberprüfung abgefangen, diskutiert und nie wieder vorkommen. Dies sollte auf jeden Fall abgefangen werden, da wir die richtigen Warnflags verwenden, oder?
Shafik Yaghmour
17
@ Michael Eigentlich ist es. Wenn ein Programm zu irgendeinem Zeitpunkt ein undefiniertes Verhalten aufweist, kann der Compiler Ihr Programm so optimieren, dass der Code beeinflusst wird , der dem Aufrufen des undefinierten Verhaltens vorausgeht . Es gibt verschiedene Artikel und Demonstrationen, wie umwerfend das man hier ein sehr gut bekommen kann: blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx (die den Bit im Standard enthält , die besagt , Alle Wetten sind
Tom Tanner
19
Diese Antwort klingt so, als ob "das Aufrufen von undefiniertem Verhalten theoretisch schlecht ist, aber in der Praxis nicht wirklich weh tut" . Das ist falsch. Sammeln Entropie aus einem Ausdruck, der UB würde dazu führen , kann (und wahrscheinlich wird ) Ursache all die zuvor gesammelte Entropie verloren werden . Dies ist eine ernsthafte Gefahr.
Theodoros Chatzigiannakis
212

Lassen Sie mich das klar sagen: Wir rufen in unseren Programmen kein undefiniertes Verhalten auf . Es ist niemals eine gute Idee, Punkt. Es gibt seltene Ausnahmen von dieser Regel; Zum Beispiel, wenn Sie ein Bibliotheksimplementierer sind, der offsetof implementiert . Wenn Ihr Fall unter eine solche Ausnahme fällt, wissen Sie dies wahrscheinlich bereits. In diesem Fall wissen wir, dass die Verwendung nicht initialisierter automatischer Variablen ein undefiniertes Verhalten ist .

Compiler sind mit Optimierungen in Bezug auf undefiniertes Verhalten sehr aggressiv geworden, und wir können viele Fälle finden, in denen undefiniertes Verhalten zu Sicherheitslücken geführt hat. Der berüchtigtste Fall ist wahrscheinlich das Entfernen der Nullzeigerprüfung des Linux-Kernels, das ich in meiner Antwort auf den C ++ - Kompilierungsfehler erwähne . wo eine Compileroptimierung um undefiniertes Verhalten eine endliche Schleife in eine unendliche verwandelte.

Wir können die gefährlichen Optimierungen von CERT und den Verlust der Kausalität ( Video ) lesen , in denen unter anderem Folgendes steht:

Compiler-Autoren nutzen zunehmend undefinierte Verhaltensweisen in den Programmiersprachen C und C ++, um die Optimierungen zu verbessern.

Häufig beeinträchtigen diese Optimierungen die Fähigkeit von Entwicklern, eine Ursache-Wirkungs-Analyse ihres Quellcodes durchzuführen, dh die Abhängigkeit der nachgelagerten Ergebnisse von früheren Ergebnissen zu analysieren.

Folglich beseitigen diese Optimierungen die Kausalität in der Software und erhöhen die Wahrscheinlichkeit von Softwarefehlern, -fehlern und -schwachstellen.

Insbesondere in Bezug auf unbestimmte Werte bietet der C-Standardfehlerbericht 451: Instabilität nicht initialisierter automatischer Variablen einige interessante Informationen . Es wurde noch nicht gelöst, führt jedoch das Konzept der wackeligen Werte ein, was bedeutet, dass sich die Unbestimmtheit eines Wertes durch das Programm ausbreiten kann und an verschiedenen Punkten im Programm unterschiedliche unbestimmte Werte haben kann.

Ich kenne keine Beispiele, wo dies passiert, aber an diesem Punkt können wir es nicht ausschließen.

Echte Beispiele, nicht das erwartete Ergebnis

Es ist unwahrscheinlich, dass Sie zufällige Werte erhalten. Ein Compiler könnte die Abwesenheitsschleife insgesamt optimieren. Zum Beispiel mit diesem vereinfachten Fall:

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

clang optimiert es weg ( live sehen ):

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

oder vielleicht alle Nullen bekommen, wie in diesem modifizierten Fall:

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

live sehen :

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

Beide Fälle sind durchaus akzeptable Formen undefinierten Verhaltens.

Beachten Sie, wenn wir uns auf einem Itanium befinden, könnten wir einen Trap-Wert erhalten :

[...] wenn das Register zufällig einen speziellen Nicht-Nichts-Wert enthält, lesen Sie die Registerfallen mit Ausnahme einiger Anweisungen [...]

Andere wichtige Hinweise

Es ist interessant festzustellen, dass im UB Canaries-Projekt eine Varianz zwischen gcc und clang festgestellt wurde, wie bereit sie sind, undefiniertes Verhalten in Bezug auf nicht initialisiertes Gedächtnis auszunutzen. Der Artikel stellt fest ( Hervorhebung von mir ):

Natürlich müssen wir uns völlig klar darüber sein, dass eine solche Erwartung nichts mit dem Sprachstandard zu tun hat und alles damit, was ein bestimmter Compiler tut, entweder weil die Anbieter dieses Compilers diese UB nicht ausnutzen wollen oder nur weil sie noch nicht dazu gekommen sind, es auszunutzen . Wenn es keine wirkliche Garantie des Compiler-Anbieters gibt, möchten wir sagen, dass noch nicht genutzte UBs Zeitbomben sind : Sie warten darauf, nächsten Monat oder nächstes Jahr loszulegen, wenn der Compiler etwas aggressiver wird.

Wie Matthieu M. betont, ist auch das , was jeder C-Programmierer über undefiniertes Verhalten # 2/3 wissen sollte, für diese Frage relevant. Es heißt unter anderem ( Hervorhebung von mir ):

Es ist wichtig und beängstigend zu erkennen, dass nahezu jede Optimierung, die auf undefiniertem Verhalten basiert, jederzeit in Zukunft für fehlerhaften Code ausgelöst werden kann . Inlining, Loop-Unrolling, Speicherförderung und andere Optimierungen werden immer besser, und ein wesentlicher Teil ihres Bestehens besteht darin, sekundäre Optimierungen wie die oben genannten bereitzustellen.

Für mich ist dies zutiefst unbefriedigend, zum Teil, weil der Compiler unweigerlich beschuldigt wird, aber auch, weil riesige C-Code-Körper Landminen sind, die nur darauf warten, explodiert zu werden.

Der Vollständigkeit halber sollte ich wahrscheinlich erwähnen, dass Implementierungen undefiniertes Verhalten gut definieren können, zum Beispiel erlaubt gcc das Durchstoßen von Typen durch Gewerkschaften, während dies in C ++ wie undefiniertes Verhalten erscheint . Wenn dies der Fall ist, sollte die Implementierung dies dokumentieren und dies ist normalerweise nicht portierbar.

Shafik Yaghmour
quelle
1
+ (int) (PI / 3) für die Compiler-Ausgabebeispiele; ein Beispiel aus der Praxis , dass UB ist, na ja, UB .
2
Die effektive Nutzung von UB war früher das Markenzeichen eines hervorragenden Hackers. Diese Tradition besteht wahrscheinlich seit 50 Jahren oder länger. Leider müssen Computer jetzt die Auswirkungen von UB aufgrund von Bad People minimieren. Ich habe es wirklich genossen herauszufinden, wie man coole Dinge mit UB-Maschinencode oder Port-Lese- / Schreibvorgängen usw. macht. In den 90er Jahren, als das Betriebssystem den Benutzer nicht so gut vor sich selbst schützen konnte.
sfdcfox
1
@sfdcfox Wenn Sie es in Maschinencode / Assembler gemacht haben, war es kein undefiniertes Verhalten (es war möglicherweise ein unkonventionelles Verhalten).
Caleth
2
Wenn Sie eine bestimmte Assembly im Sinn haben, verwenden Sie diese und schreiben Sie kein nicht konformes C. Dann wird jeder wissen, dass Sie einen bestimmten nicht portablen Trick verwenden. Und es sind keine schlechten Leute, die bedeuten, dass Sie UB nicht verwenden können, sondern Intel usw., die ihre Tricks auf dem Chip ausführen.
Caleth
2
@ 500-InternalServerError, da sie im allgemeinen Fall möglicherweise nicht leicht oder überhaupt nicht erkennbar sind und daher keine Möglichkeit besteht, sie zu verbieten. Was anders ist als Verstöße gegen die Grammatik, die erkannt werden können. Wir haben auch schlecht geformte und schlecht geformte Diagnosen, die im Allgemeinen schlecht geformte Programme, die theoretisch erkannt werden konnten, von solchen trennen, die theoretisch nicht zuverlässig erkannt werden konnten.
Shafik Yaghmour
164

Nein, es ist schrecklich.

Das Verhalten bei der Verwendung einer nicht initialisierten Variablen ist sowohl in C als auch in C ++ undefiniert, und es ist sehr unwahrscheinlich, dass ein solches Schema wünschenswerte statistische Eigenschaften aufweist.

Wenn Sie einen "schnellen und schmutzigen" Zufallszahlengenerator wollen, dann rand()ist dies die beste Wahl. In seiner Implementierung ist alles, was es tut, eine Multiplikation, eine Addition und ein Modul.

Für den schnellsten mir bekannten Generator müssen Sie a uint32_tals Typ der Pseudozufallsvariablen verwenden Iund verwenden

I = 1664525 * I + 1013904223

aufeinanderfolgende Werte zu generieren. Sie können einen beliebigen Anfangswert von I(als Samen bezeichnet ) auswählen , der Ihnen gefällt. Natürlich können Sie diese Inline codieren. Der standardgarantierte Wraparound eines vorzeichenlosen Typs fungiert als Modul. (Die numerischen Konstanten werden von dem bemerkenswerten wissenschaftlichen Programmierer Donald Knuth von Hand ausgewählt.)

Bathseba
quelle
9
Der von Ihnen vorgestellte Generator für "lineare Kongruenz" eignet sich für einfache Anwendungen, jedoch nur für nicht kryptografische Anwendungen. Es ist möglich, sein Verhalten vorherzusagen. Siehe zum Beispiel " Entschlüsseln einer linearen kongruenten Verschlüsselung " von Don Knuth selbst (IEEE Transactions on Information Theory, Band 31)
Jay,
24
@ Jay im Vergleich zu einer unitialisierten Variablen für schnell und schmutzig? Dies ist eine viel bessere Lösung.
Mike McMahon
2
rand()ist nicht zweckmäßig und sollte meiner Meinung nach völlig veraltet sein. In diesen Tagen können Sie sich frei lizenzierten Download und weit überlegen Zufallszahlengeneratoren (zB Mersenne Twister) , die sehr sind fast so schnell mit der größten Leichtigkeit , so gibt es wirklich keine Notwendigkeit, weiterhin mit der stark defektenrand()
Jack Aidley
1
rand () hat ein weiteres schreckliches Problem: Es verwendet eine Art Sperre, die als Inside-Threads bezeichnet wird und Ihren Code dramatisch verlangsamt. Zumindest gibt es eine wiedereintrittsfähige Version. Und wenn Sie C ++ 11 verwenden, bietet die Zufalls-API alles, was Sie brauchen.
Marwan Burelle
4
Um fair zu sein, fragte er nicht, ob es ein guter Zufallsgenerator sei. Er fragte, ob es schnell sei. Nun ja, es ist wahrscheinlich das Fasten. Aber die Ergebnisse werden überhaupt nicht sehr zufällig sein.
Jcoder
42

Gute Frage!

Undefiniert bedeutet nicht, dass es zufällig ist. Denken Sie darüber nach, die Werte, die Sie in globalen nicht initialisierten Variablen erhalten würden, wurden vom System oder Ihren / anderen laufenden Anwendungen dort belassen. Abhängig davon, was Ihr System mit nicht mehr verwendetem Speicher macht und / oder welche Werte das System und die Anwendungen generieren, erhalten Sie möglicherweise:

  1. Immer gleich.
  2. Seien Sie einer von wenigen Werten.
  3. Erhalten Sie Werte in einem oder mehreren kleinen Bereichen.
  4. Sehen Sie viele Werte, die durch 2/4/8 durch Zeiger auf einem 16/32/64-Bit-System teilbar sind
  5. ...

Die Werte, die Sie erhalten, hängen vollständig davon ab, welche nicht zufälligen Werte vom System und / oder den Anwendungen übrig bleiben. Es wird also tatsächlich etwas Rauschen geben (es sei denn, Ihr System löscht nicht mehr verwendeten Speicher), aber der Wertepool, aus dem Sie ziehen, ist keineswegs zufällig.

Bei lokalen Variablen wird es viel schlimmer, da diese direkt aus dem Stapel Ihres eigenen Programms stammen. Es besteht eine sehr gute Chance, dass Ihr Programm diese Stapelpositionen während der Ausführung von anderem Code tatsächlich schreibt. Ich schätze die Glückschancen in dieser Situation als sehr gering ein, und eine 'zufällige' Codeänderung, die Sie vornehmen, versucht dieses Glück.

Lesen Sie über Zufälligkeit . Wie Sie sehen werden, ist Zufälligkeit eine sehr spezifische und schwer zu beschaffende Eigenschaft. Es ist ein häufiger Fehler zu glauben, dass Sie einen zufälligen Wert erhalten, wenn Sie nur etwas nehmen, das schwer zu verfolgen ist (wie Ihr Vorschlag).

Sinn-Angelegenheiten
quelle
7
... und das lässt alle Compiler-Optimierungen aus, die diesen Code komplett entkernen würden.
Deduplikator
6 ... Sie erhalten unterschiedliche "Zufälligkeiten" in Debug und Release. Undefiniert bedeutet, dass Sie es falsch machen.
SQL Surfer
Recht. Ich würde mit "undefiniert" abkürzen oder zusammenfassen! = "Beliebig"! = "Zufällig". Alle diese Arten von "Unbekanntheit" haben unterschiedliche Eigenschaften.
fche
Globale Variablen haben garantiert einen definierten Wert, unabhängig davon, ob sie explizit initialisiert wurden oder nicht. Dies ist definitiv wahr in C ++ und in C als auch .
Brian Vandenberg
32

Viele gute Antworten, aber erlauben Sie mir, eine weitere hinzuzufügen und den Punkt zu betonen, dass in einem deterministischen Computer nichts zufällig ist. Dies gilt sowohl für die von einem Pseudo-RNG erzeugten Zahlen als auch für die scheinbar "zufälligen" Zahlen, die in Speicherbereichen gefunden werden, die für lokale C / C ++ - Variablen auf dem Stapel reserviert sind.

ABER ... es gibt einen entscheidenden Unterschied.

Die von einem guten Pseudozufallsgenerator erzeugten Zahlen haben die Eigenschaften, die sie statistisch wirklich zufälligen Ziehungen ähnlich machen. Zum Beispiel ist die Verteilung gleichmäßig. Die Zykluslänge ist lang: Sie können Millionen von Zufallszahlen erhalten, bevor sich der Zyklus wiederholt. Die Sequenz ist nicht automatisch korreliert: Wenn Sie beispielsweise jede 2., 3. oder 27. Zahl verwenden oder bestimmte Ziffern in den generierten Zahlen betrachten, werden keine merkwürdigen Muster auftreten.

Im Gegensatz dazu haben die auf dem Stapel zurückgelassenen "Zufallszahlen" keine dieser Eigenschaften. Ihre Werte und ihre offensichtliche Zufälligkeit hängen ganz davon ab, wie das Programm aufgebaut ist, wie es kompiliert wird und wie es vom Compiler optimiert wird. Als Beispiel sehen Sie hier eine Variation Ihrer Idee als eigenständiges Programm:

#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;
}

Wenn ich diesen Code mit GCC auf einem Linux-Computer kompiliere und ausführe, stellt sich heraus, dass er ziemlich unangenehm deterministisch ist:

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

Wenn Sie sich den kompilierten Code mit einem Disassembler ansehen, können Sie die Vorgänge detailliert rekonstruieren. Beim ersten Aufruf von notrandom () wurde ein Bereich des Stapels verwendet, der zuvor von diesem Programm nicht verwendet wurde. Wer weiß, was da drin war. Aber nach diesem Aufruf von notrandom () gibt es einen Aufruf von printf () (den der GCC-Compiler tatsächlich für einen Aufruf von putchar () optimiert, aber egal), der den Stack überschreibt. Wenn also notrandom () das nächste und nachfolgende Mal aufgerufen wird, enthält der Stapel veraltete Daten aus der Ausführung von putchar (), und da putchar () immer mit denselben Argumenten aufgerufen wird, sind diese veralteten Daten immer dieselben. zu.

Es gibt also absolut nichts Zufälliges an diesem Verhalten, und die auf diese Weise erhaltenen Zahlen haben auch keine der wünschenswerten Eigenschaften eines gut geschriebenen Pseudozufallszahlengenerators. Tatsächlich wiederholen sich ihre Werte in den meisten realen Szenarien und sind stark korreliert.

In der Tat würde ich, wie andere auch, ernsthaft in Betracht ziehen, jemanden zu entlassen, der versucht hat, diese Idee als "Hochleistungs-RNG" auszugeben.

Viktor Toth
quelle
1
"In einem deterministischen Computer ist nichts zufällig" - Dies ist eigentlich nicht wahr. Moderne Computer enthalten alle Arten von Sensoren, mit denen Sie ohne separate Hardwaregeneratoren echte , unvorhersehbare Zufälligkeiten erzeugen können. In einer modernen Architektur stammen die Werte von /dev/randomhäufig aus solchen Hardwarequellen und sind in der Tat „Quantenrauschen“, dh im besten physikalischen Sinne des Wortes wirklich unvorhersehbar.
Konrad Rudolph
2
Aber das ist doch kein deterministischer Computer, oder? Sie verlassen sich jetzt auf Umwelteinflüsse. In jedem Fall geht dies weit über die Diskussion eines herkömmlichen Pseudo-RNG gegenüber "zufälligen" Bits in einem nicht initialisierten Speicher hinaus. Schauen Sie sich auch die Beschreibung von / dev / random an, um festzustellen, wie weit die Implementierer von ihrem Weg entfernt waren, um sicherzustellen, dass die Zufallszahlen kryptografisch sicher sind ... gerade weil die Eingabequellen kein reines, unkorreliertes Quantenrauschen sind, sondern Vielmehr potenziell stark korrelierte Sensorwerte mit nur geringem Zufallsgrad. Es ist auch ziemlich langsam.
Viktor Toth
29

Undefiniertes Verhalten bedeutet, dass die Autoren von Compilern das Problem ignorieren können, da Programmierer niemals das Recht haben, sich zu beschweren, was auch immer passiert.

Während theoretisch beim Betreten von UB-Land alles passieren kann (einschließlich eines Daemons, der von Ihrer Nase fliegt ), bedeutet dies normalerweise, dass sich Compilerautoren einfach nicht darum kümmern und für lokale Variablen der Wert der Wert ist, der sich zu diesem Zeitpunkt im Stapelspeicher befindet .

Dies bedeutet auch, dass der Inhalt oft "seltsam", aber fest oder leicht zufällig oder variabel ist, aber ein klar erkennbares Muster aufweist (z. B. steigende Werte bei jeder Iteration).

Sie können sicher nicht erwarten, dass es sich um einen anständigen Zufallsgenerator handelt.

6502
quelle
28

Undefiniertes Verhalten ist undefiniert. Dies bedeutet nicht, dass Sie einen undefinierten Wert erhalten, sondern dass das Programm alles kann und dennoch die Sprachspezifikation erfüllt.

Ein guter optimierender Compiler sollte nehmen

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);
    }
}

und kompiliere es zu einem noop. Dies ist sicherlich schneller als jede Alternative. Es hat den Nachteil, dass es nichts tun wird, aber dies ist der Nachteil von undefiniertem Verhalten.

Martijn
quelle
3
Viel hängt davon ab, ob der Zweck eines Compilers darin besteht, Programmierern bei der Erstellung ausführbarer Dateien zu helfen, die den Domänenanforderungen entsprechen, oder ob der Zweck darin besteht, die "effizienteste" ausführbare Datei zu erstellen, deren Verhalten mit den Mindestanforderungen des C-Standards übereinstimmt Überlegen Sie, ob ein solches Verhalten einem nützlichen Zweck dient. In Bezug auf das erstere Ziel wäre es nützlicher, wenn der Code einige willkürliche Anfangswerte für r, g, b verwendet oder eine Debugger-Falle auslöst, wenn dies praktikabel wäre, als den Code in einen NOP umzuwandeln. In Bezug auf das letztere Ziel ...
Supercat
2
... sollte ein optimaler Compiler bestimmen, welche Eingaben die obige Methode zur Ausführung veranlassen würden, und jeglichen Code entfernen, der nur relevant wäre, wenn solche Eingaben empfangen würden.
Supercat
1
@supercat Oder sein Zweck könnte C. sein, effiziente ausführbare Dateien in Übereinstimmung mit dem Standard zu erstellen und dem Programmierer dabei zu helfen, Orte zu finden, an denen Compliance möglicherweise nicht nützlich ist. Compiler können diesen Kompromisszweck erfüllen, indem sie mehr Diagnosen ausgeben, als der Standard erfordert, wie z. B. GCCs -Wall -Wextra.
Damian Yerrick
1
Dass die Werte undefiniert sind, bedeutet nicht, dass das Verhalten des umgebenden Codes undefiniert ist. Kein Compiler sollte diese Funktion deaktivieren. Die beiden Funktionsaufrufe MÜSSEN unbedingt aufgerufen werden, unabhängig davon, welche Eingaben sie erhalten. Der erste MUSS mit drei Zahlen zwischen 0 und 255 aufgerufen werden, und der zweite MUSS entweder mit einem wahren oder einem falschen Wert aufgerufen werden. Ein "guter Optimierungs-Compiler" könnte die Funktionsparameter auf beliebige statische Werte optimieren und die Variablen vollständig entfernen, aber das ist so weit wie möglich (naja, es sei denn, die Funktionen selbst könnten bei bestimmten Eingaben auf noops reduziert werden).
Dewi Morgan
@DewiMorgan - Da die aufgerufenen Funktionen vom Typ "set this parameter" sind, reduzieren sie sich mit ziemlicher Sicherheit auf noops, wenn die Eingabe mit dem aktuellen Wert des Parameters übereinstimmt, den der Compiler annehmen kann.
Jules
18

Noch nicht erwähnt, aber Codepfade, die undefiniertes Verhalten aufrufen, dürfen tun, was der Compiler will, z

void updateEffect(){}

Was sicherlich schneller als Ihre richtige Schleife ist und aufgrund von UB perfekt konform ist.

Caleth
quelle
18

Aus Sicherheitsgründen muss der einem Programm zugewiesene neue Speicher bereinigt werden, da sonst die Informationen verwendet werden können und Kennwörter von einer Anwendung in eine andere übertragen werden können. Nur wenn Sie den Speicher wiederverwenden, erhalten Sie andere Werte als 0. Und es ist sehr wahrscheinlich, dass auf einem Stapel der vorherige Wert nur fest ist, da die vorherige Verwendung dieses Speichers fest ist.

Arne
quelle
13

Ihr spezielles Codebeispiel würde wahrscheinlich nicht das tun, was Sie erwarten. Während technisch gesehen jede Iteration der Schleife die lokalen Variablen für die Werte r, g und b neu erstellt, ist es in der Praxis genau der gleiche Speicherplatz auf dem Stapel. Daher wird es nicht bei jeder Iteration neu randomisiert, und Sie werden am Ende für jede der 1000 Farben dieselben 3 Werte zuweisen, unabhängig davon, wie zufällig r, g und b einzeln und anfänglich sind.

In der Tat, wenn es funktionieren würde, wäre ich sehr neugierig, was es neu randomisiert. Das einzige, was ich mir vorstellen kann, wäre ein verschachtelter Interrupt, der auf diesem Stapel schweinisch verpackt ist, was höchst unwahrscheinlich ist. Vielleicht würde auch eine interne Optimierung, die diese als Registervariablen und nicht als echte Speicherorte beibehält, an denen die Register weiter unten in der Schleife wiederverwendet werden, den Trick tun, insbesondere wenn die eingestellte Sichtbarkeitsfunktion besonders registerhungrig ist. Trotzdem alles andere als zufällig.

Jos
quelle
12

Wie die meisten Leute hier undefiniertes Verhalten erwähnten. Undefiniert bedeutet auch, dass Sie möglicherweise einen gültigen ganzzahligen Wert erhalten (zum Glück). In diesem Fall ist dies schneller (da kein Rand-Funktionsaufruf erfolgt). Aber benutze es praktisch nicht. Ich bin mir sicher, dass dies schreckliche Folgen haben wird, da das Glück nicht immer bei Ihnen ist.

Ali Kazmi
quelle
1
Sehr guter Punkt! Es mag ein pragmatischer Trick sein, aber tatsächlich erfordert er Glück.
Bedeutungsangelegenheiten
1
Es gibt absolut kein Glück. Wenn der Compiler das undefinierte Verhalten nicht optimiert, sind die Werte, die Sie erhalten, perfekt deterministisch (= hängen vollständig von Ihrem Programm, seinen Eingaben, seinem Compiler, den von ihm verwendeten Bibliotheken und dem Timing seiner Threads ab, wenn er Threads hat). Das Problem ist, dass Sie diese Werte nicht begründen können, da sie von Implementierungsdetails abhängen.
cmaster
Wenn kein Betriebssystem mit einem vom Anwendungsstapel getrennten Interrupt-Handling-Stack vorhanden ist, kann dies ein Glücksfall sein, da Interrupts den Speicherinhalt häufig geringfügig über den aktuellen Stack-Inhalt hinaus stören.
Supercat
12

Wirklich schlecht! Schlechte Angewohnheit, schlechtes Ergebnis. Erwägen:

A_Function_that_use_a_lot_the_Stack();
updateEffect();

Wenn die Funktion A_Function_that_use_a_lot_the_Stack()immer dieselbe Initialisierung vornimmt, verlässt sie den Stapel mit denselben Daten. Diese Daten nennen wir updateEffect(): immer der gleiche Wert! .

Frankie_C
quelle
11

Ich habe einen sehr einfachen Test durchgeführt, der überhaupt nicht zufällig war.

#include <stdio.h>

int main() {

    int a;
    printf("%d\n", a);
    return 0;
}

Jedes Mal, wenn ich das Programm ausführte, druckte es dieselbe Nummer ( 32767in meinem Fall) - viel weniger zufällig kann man nicht bekommen. Dies ist vermutlich unabhängig vom Startcode in der Laufzeitbibliothek, der auf dem Stapel verbleibt. Da bei jeder Programmausführung derselbe Startcode verwendet wird und zwischen den Läufen nichts anderes im Programm variiert, sind die Ergebnisse vollkommen konsistent.

Barmar
quelle
Guter Punkt. Ein Ergebnis hängt stark davon ab, wo dieser "Zufallszahlengenerator" im Code aufgerufen wird. Es ist eher unvorhersehbar als zufällig.
NO_NAME
10

Sie müssen eine Definition dessen haben, was Sie unter "zufällig" verstehen. Eine sinnvolle Definition beinhaltet, dass die Werte, die Sie erhalten, wenig korrelieren sollten. Das kann man messen. Es ist auch nicht trivial, auf kontrollierte, reproduzierbare Weise zu erreichen. Undefiniertes Verhalten ist also sicherlich nicht das, wonach Sie suchen.

Zsolt Szatmari
quelle
7

Es gibt bestimmte Situationen, in denen nicht initialisierter Speicher mit dem Typ "unsigned char *" sicher gelesen werden kann [z. B. ein Puffer, von dem zurückgegeben wird malloc]. Code kann solchen Speicher lesen, ohne sich Sorgen machen zu müssen, dass der Compiler die Kausalität aus dem Fenster wirft, und es kann vorkommen, dass es effizienter ist, Code für alles vorzubereiten, was Speicher enthält, als sicherzustellen, dass nicht initialisierte Daten nicht gelesen werden ( Ein alltägliches Beispiel hierfür wäre die Verwendung eines memcpyteilweise initialisierten Puffers, anstatt alle Elemente, die aussagekräftige Daten enthalten, diskret zu kopieren.

Selbst in solchen Fällen sollte man jedoch immer davon ausgehen, dass, wenn eine Kombination von Bytes besonders ärgerlich ist, das Lesen immer dieses Muster von Bytes ergibt (und wenn ein bestimmtes Muster in der Produktion ärgerlich wäre, aber nicht in der Entwicklung, wie z Muster wird erst angezeigt, wenn Code in Produktion ist.

Das Lesen von nicht initialisiertem Speicher kann als Teil einer Strategie zur zufälligen Generierung in einem eingebetteten System nützlich sein, bei dem sichergestellt werden kann, dass der Speicher seit dem letzten Einschalten des Systems und bei der Herstellung nie mehr mit im Wesentlichen nicht zufälligen Inhalten geschrieben wurde Der für den Speicher verwendete Prozess bewirkt, dass sein Einschaltzustand halbzufällig variiert. Code sollte funktionieren, auch wenn alle Geräte immer die gleichen Daten liefern, aber in Fällen, in denen z. B. eine Gruppe von Knoten jeweils so schnell wie möglich beliebige eindeutige IDs auswählen muss, mit einem "nicht sehr zufälligen" Generator, der der Hälfte der Knoten die gleiche Initiale gibt ID ist möglicherweise besser, als überhaupt keine anfängliche Zufallsquelle zu haben.

Superkatze
quelle
2
"Wenn eine Kombination von Bytes besonders ärgerlich ist, ergibt das Lesen immer das Muster der Bytes" - bis Sie codieren, um mit diesem Muster fertig zu werden. An diesem Punkt ist es nicht mehr ärgerlich und ein anderes Muster wird in Zukunft gelesen.
Steve Jessop
@SteveJessop: Genau. Meine Linie über Entwicklung und Produktion sollte einen ähnlichen Begriff vermitteln. Code sollte sich nicht darum kümmern, was sich in einem nicht initialisierten Gedächtnis befindet, abgesehen von einer vagen Vorstellung von "Einige Zufälligkeiten könnten nett sein". Wenn das Programmverhalten durch den Inhalt eines Teils des nicht initialisierten Speichers beeinflusst wird, kann der Inhalt von Teilen, die in Zukunft erworben werden, wiederum davon beeinflusst werden.
Supercat
5

Wie andere gesagt haben, wird es schnell sein, aber nicht zufällig.

Was die meisten Compiler für lokale Variablen tun, ist, etwas Platz für sie auf dem Stapel zu schaffen, sich aber nicht die Mühe zu machen, ihn auf irgendetwas zu setzen (der Standard sagt, dass dies nicht erforderlich ist, warum also den von Ihnen generierten Code verlangsamen?).

In diesem Fall hängt der Wert, den Sie erhalten, davon ab, was zuvor auf dem Stapel aktiviert war. Wenn Sie eine Funktion vor dieser aufrufen, bei der hundert lokale Zeichenvariablen auf 'Q' gesetzt sind, und dann Ihre Funktion aufrufen Wenn dies zurückkehrt, werden Sie wahrscheinlich feststellen, dass sich Ihre "zufälligen" Werte so verhalten, als hätten Sie memset()alle Q- Werte .

Wichtig für Ihre Beispielfunktion, die versucht, dies zu verwenden, ist, dass sich diese Werte nicht jedes Mal ändern, wenn Sie sie lesen. Sie sind jedes Mal gleich. So erhalten Sie 100 Sterne, die alle auf die gleiche Farbe und Sichtbarkeit eingestellt sind.

Außerdem sagt nichts aus, dass der Compiler diesen Wert nicht initialisieren sollte - ein zukünftiger Compiler könnte dies also tun.

Im Allgemeinen: schlechte Idee, tu es nicht. (wie viele "clevere" Optimierungen auf Codeebene wirklich ...)

Alun Thomas
quelle
2
Sie machen einige starke Vorhersagen darüber, was passieren wird , obwohl dies aufgrund von UB nicht garantiert ist. Dies ist auch in der Praxis nicht der Fall.
usr
3

Wie andere bereits erwähnt haben, ist dies undefiniertes Verhalten ( UB ), aber es kann "funktionieren".

Abgesehen von Problemen, die bereits von anderen erwähnt wurden, sehe ich ein weiteres Problem (Nachteil) - es funktioniert nicht in einer anderen Sprache als C und C ++. Ich weiß, dass es bei dieser Frage um C ++ geht, aber wenn Sie Code schreiben können, der guter C ++ - und Java-Code ist und kein Problem darstellt, warum dann nicht? Vielleicht muss es eines Tages jemand in eine andere Sprache portieren und nach Fehlern suchen, die durch "Zaubertricks" verursacht werden. UB wie dieses wird definitiv ein Albtraum sein (insbesondere für einen unerfahrenen C / C ++ - Entwickler).

Hier gibt es Fragen zu einem anderen ähnlichen UB. Stellen Sie sich vor, Sie versuchen, einen solchen Fehler zu finden, ohne etwas über diese UB zu wissen. Wenn Sie mehr über solche seltsamen Dinge in C / C ++ lesen möchten, lesen Sie die Antworten auf Fragen aus dem Link und sehen Sie sich diese großartige Diashow an. Es wird Ihnen helfen zu verstehen, was sich unter der Haube befindet und wie es funktioniert. Es ist nicht nur eine weitere Diashow voller "Magie". Ich bin mir ziemlich sicher, dass selbst die meisten erfahrenen C / C ++ - Programmierer viel daraus lernen können.

Cyriel
quelle
3

Nicht keine gute Idee, unsere Logik auf sprachundefiniertes Verhalten zu verlassen. Zusätzlich zu dem, was in diesem Beitrag erwähnt / besprochen wurde, möchte ich erwähnen, dass ein solches Programm mit einem modernen C ++ - Ansatz / Stil möglicherweise nicht kompiliert werden kann.

Dies wurde in meinem vorherigen Beitrag erwähnt, der den Vorteil der automatischen Funktion und einen nützlichen Link dafür enthält.

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

Wenn wir also den obigen Code ändern und die tatsächlichen Typen durch auto ersetzen , wird das Programm nicht einmal kompiliert.

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);
    }
}
Mantosh Kumar
quelle
3

Ich mag deine Denkweise. Wirklich über den Tellerrand hinaus. Der Kompromiss ist es jedoch wirklich nicht wert. Ein Kompromiss zwischen Speicher und Laufzeit ist eine Sache, einschließlich eines undefinierten Verhaltens für die Laufzeit nicht .

Es muss Ihnen ein sehr beunruhigendes Gefühl geben, zu wissen, dass Sie so "zufällig" wie Ihre Geschäftslogik verwenden. Ich würde es nicht tun.

DDan
quelle
3

Verwenden Sie 7757jeden Ort, an dem Sie versucht sind, nicht initialisierte Variablen zu verwenden. Ich habe es zufällig aus einer Liste von Primzahlen ausgewählt:

  1. es ist definiertes Verhalten

  2. Es ist garantiert nicht immer 0

  3. es ist Prime

  4. Es ist wahrscheinlich statistisch so zufällig wie nicht-ritualisierte Variablen

  5. Es ist wahrscheinlich schneller als nicht initialisierte Variablen, da sein Wert zur Kompilierungszeit bekannt ist

Glenn Teitelbaum
quelle
Zum Vergleich sehen Sie die Ergebnisse in dieser Antwort: stackoverflow.com/a/31836461/2963099
Glenn Teitelbaum
1

Es gibt noch eine Möglichkeit zu prüfen.

Moderne Compiler (ahem g ++) sind so intelligent, dass sie Ihren Code durchgehen, um festzustellen, welche Anweisungen den Status beeinflussen und welche nicht. Wenn garantiert wird, dass eine Anweisung den Status NICHT beeinflusst, entfernt g ++ diese Anweisung einfach.

Also hier ist was passieren wird. g ++ wird definitiv sehen, dass Sie lesen, rechnen, speichern, was im Wesentlichen ein Müllwert ist, der mehr Müll erzeugt. Da es keine Garantie dafür gibt, dass der neue Müll nützlicher ist als der alte, wird Ihre Schleife einfach beseitigt. BLOOP!

Diese Methode ist nützlich, aber hier ist, was ich tun würde. Kombiniere UB (Undefined Behaviour) mit der Geschwindigkeit von rand ().

Reduzieren Sie natürlich die rand()ausgeführten s, aber mischen Sie sie ein, damit der Compiler nichts tut, was Sie nicht wollen.

Und ich werde dich nicht feuern.

ps95
quelle
Ich finde es sehr schwer zu glauben, dass ein Compiler entscheiden kann, dass Ihr Code etwas Dummes tut, und ihn entfernen kann. Ich würde erwarten, dass nur nicht verwendeter Code optimiert wird , nicht nicht empfohlener Code. Haben Sie einen reproduzierbaren Testfall? In jedem Fall ist die Empfehlung von UB gefährlich. Außerdem ist GCC nicht der einzige kompetente Compiler, weshalb es unfair ist, ihn als "modern" zu bezeichnen.
underscore_d
-1

Die Verwendung nicht initialisierter Daten für die Zufälligkeit ist nicht unbedingt eine schlechte Sache, wenn sie richtig durchgeführt wird. Tatsächlich tut OpenSSL genau dies, um sein PRNG zu setzen.

Anscheinend war diese Verwendung jedoch nicht gut dokumentiert, da Valgrind bemerkte, dass er sich über die Verwendung nicht initialisierter Daten beschwerte und diese "reparierte", was zu einem Fehler im PRNG führte .

Sie können es also tun, aber Sie müssen wissen, was Sie tun, und sicherstellen, dass jeder, der Ihren Code liest, dies versteht.

dbush
quelle
1
Dies hängt von Ihrem Compiler ab, der mit undefiniertem Verhalten erwartet wird, wie wir aus meiner heutigen Antwort ersehen können. Clang wird heute nicht das tun, was sie wollen.
Shafik Yaghmour
6
Dass OpenSSL diese Methode als Entropieeingabe verwendet hat, bedeutet nicht, dass sie gut war. Schließlich war die einzige andere Entropiequelle, die sie verwendeten, die PID . Nicht gerade ein guter Zufallswert. Von jemandem, der sich auf eine so schlechte Entropiequelle verlässt, erwarte ich kein gutes Urteil über seine andere Entropiequelle. Ich hoffe nur, dass die Leute, die derzeit OpenSSL pflegen, besser sind.
cmaster - wieder Monica