Czy niezainicjowana zmienna lokalna jest najszybszym generatorem liczb losowych?


329

Wiem, że niezainicjowana zmienna lokalna jest nieokreślonym zachowaniem ( UB ), a także wartość może mieć reprezentacje pułapek, które mogą wpływać na dalsze działanie, ale czasami chcę użyć liczby losowej tylko do reprezentacji wizualnej i nie będę jej dalej używać w innej części program, na przykład, ustaw coś z losowym kolorem w efekcie wizualnym, na przykład:

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

czy to tak szybciej niż

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

a także szybszy niż inny generator liczb losowych?


88
+1 To jest całkowicie uzasadnione pytanie. Prawdą jest, że w praktyce niezainicjowane wartości mogą być losowe. Fakt, że nie są szczególnie i że jest to UB, nie sprawia, że prośba jest tak zła.
imallett,

35
@imallett: Oczywiście. To dobre pytanie, a przynajmniej jedna stara gra Z80 (Amstrad / ZX Spectrum) w przeszłości używała swojego programu jako danych do konfiguracji terenu. Są więc nawet precedensy. Nie mogę tego dziś zrobić. Nowoczesne systemy operacyjne zabierają całą zabawę.
Bathsheba

81
Z pewnością głównym problemem jest to, że nie jest losowy.
Jan

30
W rzeczywistości istnieje przykład niezainicjowanej zmiennej używanej jako wartość losowa, zobacz katastrofę Debian RNG (Przykład 4 w tym artykule ).
PaperBirdMaster

31
W praktyce - i wierz mi, robię wiele debugowania na różnych architekturach - twoje rozwiązanie może zrobić dwie rzeczy: albo odczyt niezainicjowanych rejestrów, albo niezainicjowaną pamięć. O ile „niezainicjowany” oznacza w pewien sposób losowy, w praktyce najprawdopodobniej będzie zawierał a) zera , b) powtarzające się lub spójne wartości (w przypadku odczytu pamięci zajmowanej wcześniej przez media cyfrowe) lub c) spójne śmieci o ograniczonej wartości zestaw (w przypadku odczytu pamięci zajmowanej wcześniej przez zakodowane dane cyfrowe). Żadne z nich nie jest prawdziwymi źródłami entropii.
mg30rg

Odpowiedzi:


299

Jak zauważyli inni, jest to niezdefiniowane zachowanie (UB).

W praktyce będzie (prawdopodobnie) faktycznie działał. Odczyt z niezainicjowanego rejestru na architekturach x86 [-64] rzeczywiście spowoduje śmieciowe wyniki i prawdopodobnie nie zrobi nic złego (w przeciwieństwie do np. Itanium, gdzie rejestry mogą być oznaczone jako nieprawidłowe , dzięki czemu odczyty propagują błędy takie jak NaN).

Istnieją jednak dwa główne problemy:

  1. To nie będzie szczególnie losowe. W tym przypadku czytasz ze stosu, więc dostaniesz wszystko, co było wcześniej. Które mogą być efektywnie losowe, całkowicie ustrukturyzowane, hasło, które wprowadziłeś dziesięć minut temu lub przepis na ciasteczka twojej babci.

  2. Zła (duża „B”) praktyka pozwala wpuszczać takie rzeczy do twojego kodu. Technicznie kompilator może wstawiać za reformat_hdd();każdym razem, gdy czyta się niezdefiniowaną zmienną. Nie będzie , ale i tak nie powinieneś tego robić. Nie rób niebezpiecznych rzeczy. Im mniej robisz wyjątków, tym bardziej jesteś bezpieczny od przypadkowych błędów przez cały czas.

Bardziej palącym problemem związanym z UB jest to, że powoduje, że zachowanie całego programu jest niezdefiniowane. Nowoczesne kompilatory mogą to wykorzystać, aby ominąć ogromne obszary kodu, a nawet cofnąć się w czasie . Zabawa z UB przypomina wiktoriańskiego inżyniera demontującego żywy reaktor jądrowy. Zillion ma wiele rzeczy do zrobienia i prawdopodobnie nie poznasz połowy podstawowych zasad lub wdrożonej technologii. To może być w porządku, ale nadal nie powinieneś na to pozwolić. Spójrz na inne fajne odpowiedzi, aby uzyskać szczegółowe informacje.

Również cię zwolnię.


39
@Potatoswatter: Rejestry Itanium mogą zawierać NaT (Not a Thing), co w efekcie jest „niezainicjowanym rejestrem”. Na Itanium czytanie z rejestru, gdy do niego nie napisałeś, może przerwać program (czytaj więcej na ten temat tutaj: blogs.msdn.com/b/oldnewthing/archive/2004/01/19/60162.aspx ). Jest więc dobry powód, dla którego odczytywanie niezainicjowanych wartości jest niezdefiniowanym zachowaniem. Jest to prawdopodobnie jeden z powodów, dla których Itanium nie jest zbyt popularny :)
tbleher

58
Naprawdę sprzeciwiam się pojęciu „to działa”. Nawet jeśli było to prawdą dzisiaj, a nie jest, może się zmienić w dowolnym momencie z powodu bardziej agresywnych kompilatorów. Kompilator może zastąpić dowolny odczyt unreachable()i usunąć połowę programu. Zdarza się to również w praktyce. Takie zachowanie całkowicie zneutralizowało RNG w niektórych dystrybucjach Linuksa; Większość odpowiedzi w tym pytaniu wydaje się zakładać, że niezainicjowana wartość w ogóle zachowuje się jak wartość. To nieprawda.
usr

25
Poza tym zwolniłbym cię, wydaje się głupią rzeczą do powiedzenia, zakładając, że dobre praktyki powinny zostać wychwycone podczas przeglądu kodu, omówione i nigdy nie powinny się powtórzyć. To zdecydowanie należy złapać, ponieważ używamy poprawnych flag ostrzegawczych, prawda?
Shafik Yaghmour,

17
@Michael Właściwie to jest. Jeśli program ma niezdefiniowane zachowanie w dowolnym momencie, kompilator może zoptymalizować Twój program w sposób, który wpływa na kod poprzedzający wywołanie niezdefiniowanego zachowania. Istnieją różne artykuły i demonstracje tego, jak oszałamiające może to osiągnąć Oto całkiem niezły: blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx (który zawiera bit w standardzie, który mówi wszystkie zakłady są wyłączone, jeśli jakakolwiek ścieżka w twoim programie wywołuje UB)
Tom Tanner

19
Ta odpowiedź brzmi, jakby „powoływanie się na niezdefiniowane zachowanie jest złe w teorii, ale tak naprawdę nie zaszkodzi ci w praktyce” . To jest źle. Zbieranie entropii z wyrażenia, które spowodowałoby UB, może (i prawdopodobnie spowoduje ) utratę całej poprzednio zebranej entropii . To poważne zagrożenie.
Theodoros Chatzigiannakis

213

Powiem to jasno: w naszych programach nie odwołujemy się do nieokreślonego zachowania . To nigdy nie jest dobry pomysł, kropka. Istnieją rzadkie wyjątki od tej zasady; na przykład, jeśli jesteś implementatorem biblioteki implementującym offsetof . Jeśli Twoja sprawa objęta jest takim wyjątkiem, prawdopodobnie już o tym wiesz. W tym przypadku wiemy, że użycie niezainicjowanych zmiennych automatycznych jest zachowaniem niezdefiniowanym .

Kompilatory stały się bardzo agresywne dzięki optymalizacjom dotyczącym nieokreślonego zachowania i możemy znaleźć wiele przypadków, w których nieokreślone zachowanie doprowadziło do wad bezpieczeństwa. Najbardziej niesławnym przypadkiem jest prawdopodobnie usunięcie sprawdzania pustego wskaźnika jądra systemu Linux, o którym wspomniałem w mojej odpowiedzi na błąd kompilacji C ++? gdzie optymalizacja kompilatora wokół niezdefiniowanego zachowania zamieniła skończoną pętlę w nieskończoną.

Możemy przeczytać Niebezpieczne optymalizacje CERT i utratę przyczynowości ( wideo ), które mówią między innymi:

W coraz większym stopniu twórcy kompilatorów wykorzystują niezdefiniowane zachowania w językach programowania C i C ++ w celu poprawy optymalizacji.

Często te optymalizacje zakłócają zdolność programistów do przeprowadzania analizy przyczynowo-skutkowej na ich kodzie źródłowym, to znaczy analizy zależności wyników końcowych od wcześniejszych wyników.

W związku z tym te optymalizacje eliminują przyczynowość w oprogramowaniu i zwiększają prawdopodobieństwo błędów oprogramowania, usterek i luk w zabezpieczeniach.

W szczególności w odniesieniu do nieokreślonych wartości, raport defektu standardowego C 451: Niestabilność niezainicjowanych zmiennych automatycznych stanowi ciekawy odczyt. Nie został jeszcze rozwiązany, ale wprowadza pojęcie niestabilnych wartości, co oznacza, że ​​nieokreśloność wartości może rozprzestrzeniać się w programie i może mieć różne nieokreślone wartości w różnych punktach programu.

Nie znam żadnych przykładów, w których tak się dzieje, ale w tym momencie nie możemy tego wykluczyć.

Prawdziwe przykłady, a nie oczekiwany wynik

Jest mało prawdopodobne, aby uzyskać losowe wartości. Kompilator może całkowicie zoptymalizować pętlę odejścia. Na przykład w tym uproszczonym przypadku:

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

clang optymalizuje go ( zobacz na żywo ):

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

lub może wszystkie zera, jak w tym zmodyfikowanym przypadku:

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

zobacz na żywo :

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

Oba te przypadki są całkowicie akceptowalnymi formami niezdefiniowanego zachowania.

Uwaga: jeśli jesteśmy na Itanium, możemy otrzymać wartość pułapki :

[...] jeśli rejestr zawiera specjalną nieistotną wartość, odczytuje pułapki rejestrów, z wyjątkiem kilku instrukcji [...]

Inne ważne uwagi

Interesujące jest odnotowanie różnicy między gcc i clang, odnotowanej w projekcie Kanarek UB, nad tym, jak chętnie wykorzystują niezdefiniowane zachowanie w odniesieniu do niezainicjowanej pamięci. Artykuł zauważa ( moje podkreślenie ):

Oczywiście musimy mieć całkowitą jasność wobec siebie, że wszelkie takie oczekiwania nie mają nic wspólnego ze standardem językowym i wszystko, co ma związek z tym, co dzieje się z konkretnym kompilatorem, albo dlatego, że dostawcy tego kompilatora nie chcą wykorzystywać tego UB, ani po prostu ponieważ jeszcze nie udało im się go wykorzystać . Kiedy nie ma żadnej prawdziwej gwarancji od dostawcy kompilatora, chcemy powiedzieć, że jeszcze niewykorzystane UB to bomby zegarowe : czekają na start w przyszłym miesiącu lub w przyszłym roku, kiedy kompilator stanie się nieco bardziej agresywny.

Jak zauważa Matthieu M. Co każdy programista C powinien wiedzieć o nieokreślonym zachowaniu # 2/3, jest również istotny dla tego pytania. Mówi między innymi ( moje podkreślenie ):

Ważną i przerażającą rzeczą jest uświadomienie sobie, że prawie jakakolwiek optymalizacja oparta na niezdefiniowanym zachowaniu może zostać uruchomiona na błędnym kodzie w dowolnym momencie w przyszłości . Inlining, rozwijanie pętli, promocja pamięci i inne optymalizacje będą się poprawiać, a znaczną część ich powodów jest ujawnianie wtórnych optymalizacji, takich jak te powyżej.

Dla mnie jest to głęboko niezadowalające, częściowo dlatego, że kompilator nieuchronnie kończy się winą, ale także dlatego, że oznacza to, że ogromne części kodu C to miny lądowe, które tylko czekają na wybuch.

Dla kompletności powinienem chyba wspomnieć, że implementacje mogą zdecydować o tym, aby niezdefiniowane zachowanie było dobrze zdefiniowane, na przykład gcc pozwala na pisanie przez związki, podczas gdy w C ++ wydaje się to niezdefiniowanym zachowaniem . W takim przypadku wdrożenie powinno to udokumentować i zwykle nie będzie to przenośne.


1
+ (int) (PI / 3) dla przykładów danych wyjściowych kompilatora; prawdziwy przykład, że UB to cóż, UB .

2
Wykorzystanie UB skutecznie było znakiem towarowym doskonałego hakera. Ta tradycja trwa już prawdopodobnie 50 lat lub więcej. Niestety, komputery są teraz wymagane, aby zminimalizować skutki UB z powodu złych ludzi. Naprawdę podobało mi się wymyślanie fajnych rzeczy za pomocą kodu maszynowego UB lub portu do odczytu / zapisu itp. W latach 90., kiedy system operacyjny nie był w stanie chronić użytkownika przed sobą.
sfdcfox

1
@ sfdcfox, jeśli robiłeś to w kodzie maszynowym / asemblerze, nie było to niezdefiniowane zachowanie (być może było to zachowanie niekonwencjonalne).
Caleth,

2
Jeśli masz na myśli konkretny zestaw, użyj go i nie pisz niezgodnej C. Wtedy wszyscy będą wiedzieć, że używasz określonej nieprzenośnej sztuczki. I to nie źli ludzie oznaczają, że nie możesz używać UB, to Intel itp. Robi swoje sztuczki na chipie.
Caleth,

2
@ 500-InternalServerError, ponieważ mogą nie być łatwo wykrywalne lub mogą nie być w ogóle wykrywalne w ogólnym przypadku, a zatem nie byłoby sposobu, aby je zabronić. Który jest inny niż naruszenia gramatyki, które można wykryć. Mamy również źle sformułowane i źle sformułowane nie wymaganie diagnostyki, co na ogół oddziela źle sformułowane programy, które można wykryć w teorii od programów, których w teorii nie można wiarygodnie wykryć.
Shafik Yaghmour,

164

Nie, to okropne.

Zachowanie używania niezainicjowanej zmiennej jest niezdefiniowane zarówno w C, jak i C ++, i jest bardzo mało prawdopodobne, aby taki schemat miał pożądane właściwości statystyczne.

Jeśli chcesz „szybkiego i brudnego” generatora liczb losowych, to rand()jest najlepszy wybór. W swojej implementacji wszystko, co robi, to mnożenie, dodawanie i moduł.

Najszybszy generator, jaki znam, wymaga użycia uint32_tjako typu pseudolosowej zmiennej Ii użycia

I = 1664525 * I + 1013904223

generować kolejne wartości. Możesz wybrać dowolną wartość początkową I(zwaną ziarnem ), która ci się spodoba. Oczywiście możesz kodować to wstawianie. Standardowo gwarantowane objęcie typu bez znaku działa jako moduł. (Stałe numeryczne są wybierane ręcznie przez tego niezwykłego programistę naukowego Donalda Knutha.)


9
Przedstawiony generator „liniowy przystający” nadaje się do prostych aplikacji, ale tylko do aplikacji innych niż kryptograficzne. Można przewidzieć jego zachowanie. Zobacz na przykład „ Odszyfrowanie liniowego szyfrowania przystającego ” autorstwa samego Don Knutha (Transakcje IEEE dotyczące teorii informacji, tom 31)
Jay

24
@Jay w porównaniu ze zmienną jednostkową dla szybkiego i brudnego? To jest znacznie lepsze rozwiązanie.
Mike McMahon,

2
rand()nie nadaje się do celu i moim zdaniem powinien być całkowicie przestarzały. W dzisiejszych czasach możesz pobrać swobodnie licencjonowane i znacznie lepsze generatory liczb losowych (np. Mersenne Twister), które są prawie tak szybkie i bardzo łatwe, więc naprawdę nie ma potrzeby dalszego używania wysoce wadliwegorand()
Jacka Aidleya

1
rand () ma jeszcze jeden okropny problem: używa pewnego rodzaju blokady, zwanej wewnętrznymi wątkami, co znacznie spowalnia kod. Przynajmniej istnieje nowa wersja. A jeśli używasz C ++ 11, losowy interfejs API zapewnia wszystko, czego potrzebujesz.
Marwan Burelle,

4
Szczerze mówiąc, nie zapytał, czy to dobry generator liczb losowych. Zapytał, czy to szybko. Cóż, tak, to prawdopodobnie post., Ale wyniki wcale nie będą losowe.
jcoder,

42

Dobre pytanie!

Niezdefiniowany nie oznacza, że ​​jest losowy. Pomyśl o tym, wartości, które uzyskasz w globalnych niezainicjowanych zmiennych, zostały tam pozostawione przez system lub działające aplikacje. W zależności od tego, co robi Twój system z nieużywaną pamięcią i / lub jakie wartości generuje system i aplikacje, możesz uzyskać:

  1. Zawsze to samo.
  2. Bądź jednym z małego zestawu wartości.
  3. Uzyskaj wartości z jednego lub więcej małych zakresów.
  4. Zobacz wiele wartości podzielnych przez 2/4/8 ze wskaźników w systemie 16/32/64-bit
  5. ...

Wartości, które otrzymasz, całkowicie zależą od tego, które nieprzypadkowe wartości pozostawiają system i / lub aplikacje. Tak więc rzeczywiście będzie trochę szumu (chyba że twój system wyczyści pamięć, która nie jest już używana), ale pula wartości, z której będziesz czerpać, nie będzie losowa.

W przypadku zmiennych lokalnych sytuacja staje się znacznie gorsza, ponieważ pochodzą one bezpośrednio ze stosu własnego programu. Istnieje bardzo duża szansa, że ​​Twój program zapisze te lokalizacje stosu podczas wykonywania innego kodu. Szanse na szczęście w tej sytuacji oceniam na bardzo niskie, a dokonana przez ciebie „losowa” zmiana kodu próbuje tego szczęścia.

Przeczytaj o losowości . Jak zobaczysz, losowość jest bardzo specyficzną i trudną do uzyskania własnością. Powszechnym błędem jest myślenie, że jeśli weźmiesz coś trudnego do śledzenia (np. Twoją sugestię), otrzymasz losową wartość.


7
... a to pomija wszystkie optymalizacje kompilatora, które całkowicie wypchnęłyby ten kod.
Deduplicator

6 ... Dostaniesz inną „losowość” w debugowaniu i wydaniu. Niezdefiniowane oznacza, że ​​robisz to źle.
Sql Surfer,

Dobrze. Skrócę lub podsumuję za pomocą „undefined”! = „Arbitrary”! = „Random”. Wszystkie tego rodzaju „niewiadome” mają różne właściwości.
fche

Zmienne globalne mają określoną wartość, niezależnie od tego, czy zostały jawnie zainicjowane czy nie. Jest to z pewnością prawda w C ++ oraz w C jak dobrze .
Brian Vandenberg,

32

Wiele dobrych odpowiedzi, ale pozwolę sobie dodać jeszcze jedną i podkreślić, że w deterministycznym komputerze nic nie jest przypadkowe. Dotyczy to zarówno liczb generowanych przez pseudo-RNG, jak i pozornie „losowych” liczb znajdujących się w obszarach pamięci zarezerwowanych dla zmiennych lokalnych C / C ++ na stosie.

ALE ... jest zasadnicza różnica.

Liczby generowane przez dobry generator pseudolosowy mają właściwości, które czynią je statystycznie podobnymi do losowych losowań. Na przykład rozkład jest jednolity. Długość cyklu jest długa: można uzyskać miliony liczb losowych, zanim cykl się powtórzy. Sekwencja nie jest autokorelowana: na przykład nie zaczniesz pojawiać się dziwnych wzorów, jeśli weźmiesz co 2, 3 lub 27 liczbę lub spojrzysz na konkretne cyfry w generowanych liczbach.

Natomiast „losowe” liczby pozostawione na stosie nie mają żadnej z tych właściwości. Ich wartości i ich pozorna losowość zależą całkowicie od tego, jak program jest zbudowany, jak jest kompilowany i jak jest optymalizowany przez kompilator. Przykładowo, oto odmiana twojego pomysłu jako samodzielnego programu:

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

Kiedy kompiluję ten kod za pomocą GCC na komputerze z systemem Linux i okazuje się, że jest to raczej nieprzyjemnie deterministyczne:

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

Jeśli spojrzysz na skompilowany kod za pomocą dezasemblera, możesz szczegółowo zrekonstruować, co się dzieje. Pierwsze wywołanie notrandom () wykorzystało obszar stosu, który wcześniej nie był używany przez ten program; kto wie co tam było. Ale po tym wywołaniu notrandom () następuje wywołanie printf () (które kompilator GCC faktycznie optymalizuje do wywołania putchar (), ale nieważne), co zastępuje stos. Tak więc następnym razem i po wywołaniu notrandom () stos będzie zawierał nieaktualne dane z wykonania putchar (), a ponieważ putchar () jest zawsze wywoływany z tymi samymi argumentami, te nieaktualne dane zawsze będą takie same, też.

Tak więc nie ma absolutnie nic losowego w tym zachowaniu, ani liczby uzyskane w ten sposób nie mają żadnych pożądanych właściwości dobrze napisanego generatora liczb pseudolosowych. W rzeczywistości w większości rzeczywistych scenariuszy ich wartości będą powtarzalne i wysoce skorelowane.

Rzeczywiście, podobnie jak inni, poważnie rozważyłbym również zwolnienie kogoś, kto próbował przekazać ten pomysł jako „wysokowydajny RNG”.


1
„W deterministycznym komputerze nic nie jest przypadkowe” - tak naprawdę nie jest to prawdą. Nowoczesne komputery zawierają wszelkiego rodzaju czujniki, które pozwalają uzyskać prawdziwą , nieprzewidywalną losowość bez osobnych generatorów sprzętowych. W nowoczesnej architekturze wartości /dev/randomczęsto pochodzą z takich źródeł sprzętowych i są w rzeczywistości „szumem kwantowym”, tj. Naprawdę nieprzewidywalnym w najlepszym fizycznym tego słowa znaczeniu.
Konrad Rudolph,

2
Ale to nie jest komputer deterministyczny, prawda? Teraz polegasz na wkładzie środowiska. W każdym razie wykracza to daleko poza dyskusję o konwencjonalnym pseudo-RNG vs. „losowych” bitach w niezainicjowanej pamięci. Ponadto ... spójrz na opis / dev / random, aby docenić, jak daleko odeszli od siebie realizatorzy, aby upewnić się, że liczby losowe są bezpieczne kryptograficznie ... właśnie dlatego, że źródła wejściowe nie są czystym, nieskorelowanym szumem kwantowym, ale raczej potencjalnie wysoce skorelowane odczyty czujnika z niewielkim stopniem losowości. Jest też dość wolny.
Viktor Toth,

29

Niezdefiniowane zachowanie oznacza, że ​​autorzy kompilatorów mogą zignorować problem, ponieważ programiści nigdy nie będą mieli prawa narzekać na cokolwiek się stanie.

Podczas gdy teoretycznie przy wchodzeniu na ląd UB wszystko może się zdarzyć (w tym demon lecący z twojego nosa ), co zwykle oznacza, że ​​autorzy kompilatora po prostu nie będą się tym przejmować, a dla zmiennych lokalnych wartością będzie cokolwiek, co jest w pamięci stosu w tym momencie .

Oznacza to również, że często treść będzie „dziwna”, ale stała lub nieco losowa lub zmienna, ale z wyraźnym wyraźnym wzorem (np. Rosnąca wartość przy każdej iteracji).

Na pewno nie można oczekiwać, że będzie to przyzwoity generator losowy.


28

Niezdefiniowane zachowanie jest niezdefiniowane. Nie oznacza to, że otrzymujesz niezdefiniowaną wartość, oznacza to, że program może zrobić wszystko i nadal spełniać specyfikację języka.

Dobry kompilator optymalizacyjny powinien wziąć

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

i skompiluj to do noop. Jest to z pewnością szybsze niż jakakolwiek alternatywa. Ma tę wadę, że nic nie zrobi, ale taka jest wada niezdefiniowanego zachowania.


3
Wiele zależy od tego, czy celem kompilatora jest pomoc programistom w tworzeniu plików wykonywalnych spełniających wymagania domeny, czy też celem jest stworzenie najbardziej „wydajnego” pliku wykonywalnego, którego zachowanie będzie zgodne z minimalnymi wymaganiami standardu C, bez rozważenie, czy takie zachowanie będzie służyło jakimkolwiek przydatnym celom. Jeśli chodzi o poprzedni cel, użycie kodu w dowolnej wartości początkowej dla r, g, b lub uruchomienie pułapki debuggera, jeśli jest to praktyczne, byłoby bardziej przydatne niż przekształcenie kodu w nop. W odniesieniu do tego ostatniego celu ...
supercat

2
... optymalny kompilator powinien określić, które dane wejściowe spowodowałyby wykonanie powyższej metody, i wyeliminować wszelkie kody, które byłyby istotne tylko w przypadku otrzymania takich danych wejściowych.
supercat

1
@supercat Lub jego celem może być C. tworzenie wydajnych plików wykonywalnych zgodnie ze standardem, pomagając programistom w znalezieniu miejsc, w których zgodność może nie być przydatna. Kompilatory mogą spełnić ten cel kompromisu, wysyłając więcej diagnostyki niż wymaga Standard, na przykład GCC -Wall -Wextra.
Damian Yerrick

1
To, że wartości są niezdefiniowane, nie oznacza, że ​​zachowanie otaczającego kodu jest niezdefiniowane. Żaden kompilator nie powinien odbierać tej funkcji. Dwa wywołania funkcji, niezależnie od podanych danych wejściowych, MUSZĄ być wywoływane; pierwszy MUSI zostać wywołany trzema cyframi od 0 do 255, a drugi MUSI zostać wywołany z wartością prawdziwą lub fałszywą. „Dobry kompilator optymalizujący” może zoptymalizować parametry funkcji do dowolnych wartości statycznych, całkowicie pozbywając się zmiennych, ale jest to tak daleko, jak to możliwe (cóż, chyba że same funkcje mogą zostać zredukowane do noops na niektórych wejściach).
Dewi Morgan

@DewiMorgan - ponieważ wywoływane funkcje są typu „ustaw ten parametr”, prawie na pewno zmniejszają się do noops, gdy dane wejściowe są takie same, jak bieżąca wartość parametru, którą kompilator może przyjąć.
Jules

18

Nie wspomniano jeszcze, ale ścieżki kodu, które wywołują niezdefiniowane zachowanie, mogą wykonywać wszystko, co chce kompilator, np

void updateEffect(){}

Co jest z pewnością szybsze niż twoja właściwa pętla, a dzięki UB jest całkowicie zgodne.


18

Ze względów bezpieczeństwa nowa pamięć przypisana do programu musi zostać wyczyszczona, w przeciwnym razie informacje mogłyby zostać wykorzystane, a hasła mogłyby wyciekać z jednej aplikacji do drugiej. Dopiero po ponownym użyciu pamięci otrzymujesz wartości inne niż 0. I jest bardzo prawdopodobne, że na stosie poprzednia wartość została właśnie naprawiona, ponieważ poprzednie użycie tej pamięci zostało naprawione.


13

Twój przykładowy kod prawdopodobnie nie zrobiłby tego, czego oczekujesz. Podczas gdy technicznie każda iteracja pętli odtwarza zmienne lokalne dla wartości r, gib, w praktyce jest to dokładnie ta sama przestrzeń pamięci na stosie. W związku z tym nie będzie ponownie losowo przydzielany przy każdej iteracji, a w końcu przypisujesz te same 3 wartości dla każdego z 1000 kolorów, niezależnie od tego, jak losowo r, gib są indywidualnie i początkowo.

Rzeczywiście, gdyby zadziałało, byłbym bardzo ciekawy, co go ponownie randomizuje. Jedyne, co mogę wymyślić, to przeplatane przerwanie, które warkocze na szczycie stosu, bardzo mało prawdopodobne. Być może wewnętrzna optymalizacja, która zachowywała te zmienne jako zmienne rejestru, a nie jako prawdziwe miejsce w pamięci, gdzie rejestry są ponownie wykorzystywane w dalszej części pętli, również by załatwiła sprawę, szczególnie jeśli ustawiona funkcja widoczności jest szczególnie wymagająca rejestru. Nadal dalekie od losowości.


12

Jak większość osób wspomniała tutaj o niezdefiniowanym zachowaniu. Niezdefiniowana oznacza również, że możesz uzyskać pewną prawidłową wartość całkowitą (na szczęście), w tym przypadku będzie to szybsze (ponieważ nie jest wywoływane funkcja rand). Ale nie używaj go praktycznie. Jestem pewien, że przyniesie to okropne wyniki, ponieważ szczęście nie jest przez cały czas z tobą.


1
Bardzo dobra uwaga! To może być pragmatyczna sztuczka, ale w rzeczywistości wymagająca szczęścia.
znaczenie

1
Nie ma absolutnie żadnego szczęścia. Jeśli kompilator nie zoptymalizuje niezdefiniowanego zachowania, otrzymane wartości będą całkowicie deterministyczne (= zależą całkowicie od programu, jego danych wejściowych, jego kompilatora, bibliotek, których używa, taktowania wątków, jeśli ma wątki). Problem polega na tym, że nie można uzasadnić tych wartości, ponieważ zależą one od szczegółów implementacji.
cmaster

W przypadku braku systemu operacyjnego ze stosem obsługi przerwań oddzielnym od stosu aplikacji, może być zaangażowane szczęście, ponieważ przerwania często zakłócają zawartość pamięci nieco ponad bieżącą zawartość stosu.
supercat

12

Naprawdę źle! Zły nawyk, zły wynik. Rozważać:

A_Function_that_use_a_lot_the_Stack();
updateEffect();

Jeśli funkcja A_Function_that_use_a_lot_the_Stack()zawsze wykonuje tę samą inicjalizację, pozostawia stos z tymi samymi danymi. Te dane nazywamy updateEffect(): zawsze ta sama wartość! .


11

Przeprowadziłem bardzo prosty test i wcale nie był przypadkowy.

#include <stdio.h>

int main() {

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

Za każdym razem, gdy uruchamiałem program, drukował ten sam numer ( 32767w moim przypadku) - nie można dostać dużo mniej losowego niż ten. Jest to prawdopodobnie dowolny kod startowy z biblioteki wykonawczej pozostawionej na stosie. Ponieważ używa tego samego kodu startowego przy każdym uruchomieniu programu i nic innego nie zmienia się w programie między uruchomieniami, wyniki są idealnie spójne.


Słuszna uwaga. Wynik silnie zależy od tego, gdzie w kodzie wywoływany jest ten „losowy” generator liczb. Jest to raczej nieprzewidywalne niż losowe.
NO_NAME

10

Musisz zdefiniować, co rozumiesz przez „losowy”. Rozsądna definicja zakłada, że ​​otrzymywane wartości powinny mieć niewielką korelację. To jest coś, co możesz zmierzyć. Osiągnięcie w kontrolowany, powtarzalny sposób również nie jest łatwe. Tak więc nieokreślone zachowanie z pewnością nie jest tym, czego szukasz.


7

Istnieją pewne sytuacje, w których niezainicjowana pamięć może być bezpiecznie odczytana przy użyciu typu „unsigned char *” [np. Bufor zwrócony z malloc]. Kod może odczytywać taką pamięć, nie martwiąc się o to, że kompilator wyrzuci przyczynę przez okno. Czasami bardziej efektywne może być przygotowanie kodu na wszystko, co może zawierać pamięć, niż zapewnienie, że niezainicjowane dane nie zostaną odczytane ( powszechnym przykładem tego byłoby użycie memcpyw częściowo zainicjowanym buforze zamiast dyskretnego kopiowania wszystkich elementów zawierających znaczące dane).

Jednak nawet w takich przypadkach należy zawsze zakładać, że jeśli jakakolwiek kombinacja bajtów będzie szczególnie dokuczliwa, czytanie jej zawsze da taki wzór bajtów (a jeśli pewien wzorzec byłby dokuczliwy w produkcji, ale nie w rozwoju, taki wzorzec nie pojawi się, dopóki kod nie zostanie wyprodukowany).

Czytanie niezainicjowanej pamięci może być przydatne jako część strategii generowania losowego w systemie wbudowanym, w którym można mieć pewność, że pamięć nigdy nie została napisana z zasadniczo nieprzypadkową zawartością od czasu ostatniego włączenia systemu, a także proces zastosowany dla pamięci powoduje, że jej stan włączenia zmienia się w sposób pół-losowy. Kod powinien działać, nawet jeśli wszystkie urządzenia zawsze dają te same dane, ale w przypadkach, gdy np. Każda grupa węzłów musi jak najszybciej wybrać dowolne unikalne identyfikatory, mając generator „niezbyt losowy”, który daje połowie węzłów taki sam początkowy Identyfikator może być lepszy niż brak początkowego źródła losowości.


2
„jeśli jakakolwiek kombinacja bajtów będzie szczególnie dokuczliwa, czytanie jej zawsze da taki wzór bajtów” - dopóki nie kodujesz, aby poradzić sobie z tym wzorcem, w którym to momencie nie jest już irytujące, a inny wzorzec zostanie odczytany w przyszłości.
Steve Jessop,

@SteveJessop: Dokładnie. Moja linia rozwoju i produkcji miała na celu przekazanie podobnego pojęcia. Kod nie powinien przejmować się tym, co znajduje się w niezainicjowanej pamięci poza niejasnym pojęciem „Pewna przypadkowość może być miła”. Jeśli na zawartość programu wpływa zawartość niezainicjowanej pamięci, może to z kolei wpływać na zawartość części pozyskanych w przyszłości.
supercat

5

Jak powiedzieli inni, będzie szybki, ale nie losowy.

Większość kompilatorów zrobi dla zmiennych lokalnych, aby zdobyć dla nich miejsce na stosie, ale nie zawracać sobie głowy ustawieniem go na cokolwiek (standard mówi, że nie muszą, więc po co spowalniać generowanie kodu?).

W takim przypadku wartość, którą otrzymasz, będzie zależeć od tego, co było wcześniej na stosie - jeśli wywołasz funkcję przed tą, która ma sto lokalnych zmiennych char ustawionych na „Q”, a następnie wywołujesz funkcję po który zwraca, wtedy prawdopodobnie zauważysz, że twoje „losowe” wartości zachowują się tak, jakbyś miał memset()wszystkie na „Q”.

Co ważne, dla przykładowej funkcji próbującej tego użyć, wartości te nie zmieniają się za każdym razem, gdy je czytasz, będą za każdym razem takie same. Otrzymasz 100 gwiazdek ustawionych w tym samym kolorze i widoczności.

Ponadto nic nie mówi, że kompilator nie powinien inicjować tych wartości - może to zrobić przyszły kompilator.

Ogólnie: zły pomysł, nie rób tego. (tak jak wiele „sprytnych” optymalizacji poziomu kodu naprawdę ...)


2
Robisz pewne mocne prognozy dotyczące tego , co się stanie, chociaż żadne z nich nie jest gwarantowane z powodu UB. Nie jest to również prawdą w praktyce.
usr

3

Jak już wspomniano inni, jest to zachowanie niezdefiniowane ( UB ), ale może „działać”.

Oprócz problemów, o których wspominali już inni, widzę jeszcze jeden problem (wadę) - nie będzie działał w żadnym języku innym niż C i C ++. Wiem, że to pytanie dotyczy C ++, ale jeśli możesz napisać kod, który będzie dobrym kodem C ++ i Java i nie jest to problem, to dlaczego nie? Być może pewnego dnia ktoś będzie musiał przenieść go na inny język i poszukiwanie błędów spowodowanych przez „magiczne sztuczki” UB takie jak ten na pewno będzie koszmarem (szczególnie dla niedoświadczonego programisty C / C ++).

Tutaj jest pytanie o inny podobny UB. Wyobraź sobie, że próbujesz znaleźć taki błąd, nie wiedząc o tym UB. Jeśli chcesz przeczytać więcej o takich dziwnych rzeczach w C / C ++, przeczytaj odpowiedzi na pytanie z linku i zobacz ten WIELKI pokaz slajdów. Pomoże ci zrozumieć, co jest pod maską i jak działa; to nie tylko kolejny pokaz pełen „magii”. Jestem pewien, że nawet większość doświadczonych programistów C / c ++ może się wiele z tego nauczyć.


3

Nie jest dobrym pomysłem opieranie naszej logiki na niezdefiniowanych zachowaniach językowych. Oprócz wszystkiego, co wspomniano / omówiono w tym poście, chciałbym wspomnieć, że przy nowoczesnym podejściu / stylu C ++ taki program może nie być kompilowany.

Zostało to wspomniane w moim poprzednim poście, który zawiera zaletę funkcji auto i przydatny link do tego samego.

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

Jeśli więc zmienimy powyższy kod i zastąpimy rzeczywiste typy auto , program nawet się nie skompiluje.

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

3

Podoba mi się twój sposób myślenia. Naprawdę nieszablonowe. Jednak kompromis naprawdę nie jest tego wart. Pamięć-runtime kompromis jest rzeczą, w tym zachowanie niezdefiniowane na starcie jest nie .

To musi dać ci bardzo niepokojące uczucie, wiedząc, że używasz takiej „losowej” jak logika biznesowa. Nie zrobię tego.


3

Używaj 7757każdego miejsca, w którym masz ochotę używać niezainicjowanych zmiennych. Wybrałem go losowo z listy liczb pierwszych:

  1. jest to określone zachowanie

  2. gwarantuje się, że nie zawsze będzie to 0

  3. to jest liczba pierwsza

  4. prawdopodobnie będzie tak samo statystycznie losowy jak niezainicjowane zmienne

  5. prawdopodobnie będzie szybszy niż niezainicjowane zmienne, ponieważ jego wartość jest znana w czasie kompilacji


Dla porównania zobacz wyniki w tej odpowiedzi: stackoverflow.com/a/31836461/2963099
Glenn Teitelbaum

1

Jest jeszcze jedna możliwość do rozważenia.

Nowoczesne kompilatory (ahem g ++) są tak inteligentne, że przechodzą przez twój kod, aby zobaczyć, które instrukcje wpływają na stan, a co nie, a jeśli gwarantowana instrukcja NIE wpłynie na stan, g ++ po prostu usunie tę instrukcję.

Oto co się stanie. g ++ na pewno zobaczy, że czytasz, wykonujesz arytmetykę, oszczędzasz, co jest w zasadzie wartością śmieci, która powoduje więcej śmieci. Ponieważ nie ma gwarancji, że nowe śmieci będą bardziej przydatne niż stare, po prostu usunie pętlę. BLOOP!

Ta metoda jest przydatna, ale oto, co bym zrobił. Połącz UB (niezdefiniowane zachowanie) z prędkością rand ().

Oczywiście zmniejsz rand()s wykonywane, ale wklej je, aby kompilator nie zrobił nic, czego nie chcesz.

I nie zwolnię cię.


Bardzo trudno mi uwierzyć, że kompilator może zdecydować, że Twój kod robi coś głupiego i usunąć go. Spodziewałbym się, że tylko zoptymalizuje nieużywany kod , a nie niewskazany kod. Czy masz odtwarzalny przypadek testowy? Tak czy inaczej, zalecenie UB jest niebezpieczne. Co więcej, GCC nie jest jedynym kompetentnym kompilatorem, więc niesprawiedliwe jest wyróżnianie go jako „nowoczesnego”.
underscore_d

-1

Używanie niezainicjowanych danych dla przypadkowości niekoniecznie jest złą rzeczą, jeśli jest wykonane właściwie. W rzeczywistości OpenSSL robi to dokładnie, aby zaszczepić swój PRNG.

Najwyraźniej to użycie nie było jednak dobrze udokumentowane, ponieważ ktoś zauważył, że Valgrind narzeka na używanie niezainicjowanych danych i „naprawił” je, powodując błąd w PRNG .

Możesz to zrobić, ale musisz wiedzieć, co robisz i upewnić się, że każdy czytający Twój kod to rozumie.


1
Będzie to zależeć od twojego kompilatora, czego oczekuje się od nieokreślonego zachowania, jak widzimy z mojej odpowiedzi, klang dzisiaj nie zrobi tego, czego chcą.
Shafik Yaghmour,

6
To, że OpenSSL użył tej metody jako danych wejściowych entropii, nie oznacza, że ​​było to dobre. W końcu jedynym innym źródłem entropii, z którego korzystali, był PID . Niezupełnie dobra losowa wartość. Od kogoś, kto polega na tak złym źródle entropii, nie oczekuję dobrej oceny innego źródła entropii. Mam tylko nadzieję, że ludzie, którzy obecnie utrzymują OpenSSL, są jaśniejsi.
cmaster
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.