NIedeterministyczne zachowanie funkcji rand()

Mam aplikację, w której zaimplementowany jest algorytm RANSAC. Dla tych co nie wiedzą, jest to algorytm, który działa iteracyjnie i losowo - losowo oszacowuje szukane parametry i sprawdza dopasowanie zbioru danych do tych parametrów, i powtarza ten proces wielokrotnie, wybierając najlepsze oszacowanie. W tym konkretnym problemie algorytm losuje 3 indeksy punktów, na podstawie których oszacuje płaszczyznę. Do losowania korzystam z metody rand(), która jednak nie jest zainicjalizowana poprzez srand() (co jest równoważne z zainicjalizowaniem jej jako srand(1)), bo zależy mi na deterministyczności tego algorytmu, czyli żeby za każdym uruchomieniem na danej maszynie, dostawać te same ciągi pseudo-losowych liczb, tak by wyniki zawsze były te same.

Problemem jest to, że gdzieś ten determinizm został złamany i za każdym razem wyniki nieco się różnią. Domyślam się, że jest to związane właśnie z wynikiem działania rand() i być może kompilator dokonuje sobie jakichś optymalizacji, które powodują że losowanie może się różnić za każdym razem. Jednak, gdy próbuję wyświetlić te losowe wartości, by potwierdzić tę hipotezę, albo puścić program w trybie debug, to wtedy zachowuje się deterministycznie. a losowe wartości za każdym razem są takie same, tak jakbym tego oczekiwał. Przypomina to trochę pomiar kwantowy - dopóki nie dokonam obserwacji, to dana cząstka jest w superpozycji różnych stanów i dopiero odczyt spowoduje ustalenie wartości. Tutaj, dopóki nie wyświetlam wartości zmiennej, to zmienne mogą mieć różne wartości a przez to dawać różne wyniki. Nie chcę jednak wyświetlać tych wartości, bo są ich miliony. Próbowałem użyć modyfikatora volatile:

        volatile unsigned int r1 = rand();
        volatile unsigned int r2 = rand();
        volatile unsigned int r3 = rand();

nie wiem czy sensownie, ale to i tak nie pomaga. Czy ktoś może wyjaśnić co tu się dzieje, i jak przywrócić determinizm tego kodu?

Wiem oczywiście, że są nowsze generatory liczb typu mt19937, ale niekoniecznie zależy mi na lepszej "losowości", tylko na tym determinizmie.

Inne generatory są równie, a nawet bardziej deterministyczne (bo oferują konkretne algorytmy z konkretnymi parametrami).

Po co tam ten volatile?

Ogółem strzelam, że korzystasz wielowątkowo z rand() i w tym problem.

@kq:
volatile dałem trochę na ślepo - pamiętam, że jeśli gdy się użyło tego modyfikatora, to kompilator nie dokonywał sobie optymalizacji na danej zmiennej.

To właśnie nie jest aplikacja wielowątkowa, a przynajmniej nie w tej części.

Problem z rand jest taki, że nie kontrolujesz kto go używa.
Może inny fragment kodu też go używa i determinizm zostaje rozmyty.
Albo jak pisze kq używasz wielu wątków a rand nie jest nawet "reentrant" z punktu widzenia wielowątkowości.

Możesz skorzystać z POSIX-owego rand_r albo lepiej zainteresuj się nowszą maszynerią z C++11 https://dsp.krzaq.cc/post/180/nie-uzywaj-rand-cxx-ma-random/

mt19937 jest też deterministyczny, Tylko std::random_device jest naprawdę losowy (i to nie zawsze).

Pełną kontrolę nad tym co się dzieje masz dopiero gdy zaimplementujesz funkcję pseudolosową sam.

GutekSan napisał(a):

. Do losowania korzystam z metody rand(), która jednak nie jest zainicjalizowana poprzez srand() (co jest równoważne z zainicjalizowaniem jej jako srand(1)), bo zależy mi na deterministyczności tego algorytmu, czyli żeby za każdym uruchomieniem na danej maszynie, dostawać te same ciągi pseudo-losowych liczb, tak by wyniki zawsze były te same.

to może użyj to srand(1);

Przetestowałem wszystkie Wasze rady, czyli:

@Miang: przetestowałem dodanie srand(1)

@MarekR22: przetestowałem rand_roraz generowanie przy użyciu

std::default_random_engine generator;
std::uniform_int_distribution<int> dist(0, points.size()-1);

niestety, żadna nie pomogła, wyniki są nadal różne.

Jak pisałem, wszystkie losowania mają miejsce w jednym wątku, i dopiero gdy losowane wartości są wyświetlane, choćby tylko w ograniczonym zakresie dla jednej iteracji, wszystko jest ładnie powtarzalne. Gdyby problemem była wielowątkowość to wyświetlenie wartości chyba by nic nie zmieniło.

U mnie działa:
https://godbolt.org/z/3E9EWEYsn
https://ideone.com/ij1tHJ
Ale jest mała pułapka: https://stackoverflow.com/a/48730423/1387438 (na mojej maszynie przez to sekwencja jest inna, kompilator AppleClang).

@MarekR22:
No ale Ty wyświetlasz te wartości
Jeśli ja wyświetlę, to u mnie też będzie działało. Problem w tym, żeby działało bez wyświetlania.

Ja mam bardzo brzydkie przeczucie, że gdzieś w Twoim kodzie czai się UB albo data race, które po wyłączeniu optymalizacji/włączeniu debugowania po prostu przestaje się objawiać.
To co zasugeruję to jest może bardzo głupie rozwiązanie (czy bardziej workaround) ale "jak nie kijem go to pałką": czy jeżeli dostarczysz te 3 liczby z zewnątrz, nie wiem, napiszesz prosty program w C losujący je z zafixowanym seedem i przekażesz je po pipie czy innym sockecie, to efekt nadal występuje?

EDIT: i zobacz proszę co pokazuje ltrace dla Twojej binarki.
Ponadto napisałeś:

Jak pisałem, wszystkie losowania mają miejsce w jednym wątku,

OK. Ale czy w tym czasie lecą inne wątki? Może coś pod spodem też losuje (do innych celów, albo nawet nawet niejawnie, ale call do rand to call do rand), a wyświetlenie powoduje globalną synchronizację na IO i akurat masz fart że dobry wątek trafia w stream mutex?

Update.
Problem rozwiązany. Faktycznie nie dotyczył funkcji rand(), był jednak na tyle perfidny, że ukrył się w sąsiedztwie miejsca, gdzie to rand() było wywoływane, i moje podejrzenie nań padło, zwłaszcza, że gdy próbowałem wyświetlić te losowe wartości, to magicznie się naprawiał.

Gdyby kogoś interesowało, co było nie tak, poniżej wyjaśnienie.

Oto pseudo-kod RANSACa

// dane
std::vector<Point3d> vp;

for(int i=0; i<maxRansacIterations; i++) {
// losuj 3 punkty z vp

// przeprowadź przez nie płaszczyznę (jeśli się da)

// sprawdź czy płaszczyzna spełnia dodatkowe warunki (to nie jest część klasycznego RANSACa, ale została dopisana)

// jeśli płaszczyzna jest lepsza niż najlepsza, zapamiętaj (lepszość określamy np. liczbą inlierów czyli punktów w pewnej określonej bliskości).
}

// wybierz najlepszą płaszczyznę

// wyznacz zbiór inlierów dla najlepszej płaszczyzny

Otóż w pewnym przypadku dla zbioru 19 punktów, w ciągu 1000 iteracji nie udało się wyznaczyć płaszczyzny, która spełniałaby dodatkowe warunki i w efekcie po tej głównej pętli pewne parametry płaszczyzny pozostawały nie zainicjalizowane. W efekcie, dostawaliśmy losowo różne zbiory inlierów na wyjściu, bo były wyznaczane w oparciu o śmieci.. Autor tego kodu (nie ja, żeby była jasność) najwyraźniej nie przewidział takiej możliwości, a ja też nie podejrzewałem, że to akurat te dodatkowe warunki będą tu tak istotne.