On 02.07.2013 23:06, Edek wrote:
> Dnia pamiętnego Tue, 02 Jul 2013 21:18:51 +0200, Michoo wyjmując peta
> oznajmił:
>
>> On 02.07.2013 19:56, Edek wrote:
>>> Dnia pamiętnego Tue, 02 Jul 2013 18:16:18 +0200, Michoo wyjmując peta
>>> oznajmił:
>>
>>>> - w przypadku odczytu INIT_DONE pomijamy cały blok - inicjalizacja
>>>> została już wykonana
>>>
>>> Tak, ale nie miała miejsce synchronizacja.
>>
>> Jaka synchronizacja?
>
> No żeby udowodnić widzialność danych musisz udowodnić odpowiedni
> 'ordering' pomiędzy wątkami.

No i memory barrier jest definiowane jako:
- wszystkie zapisy wykonane do tej pory zostają commitowane do pamięci
- wszystkie odczyty od tej pory czytają ostatnio zapisany stan

>
>>>> Pisane na szybko więc co przeoczyłem?
>>>
>>> Model pamięci C++11?
>>
>> pthreads z nie_pojebaną_architekturą (tm)
>
> ARM i Itanium się kwalifikują jako poyebane? IMHO tak.

Imo nie. Nadal jak robisz barrierę to wszystkie zapisy są widoczne.

>
>>> Model Pamięci ma taką cechę że zapis w wątku A jest widoczny w wątku B
>>> gdy nastąpi uszeregowanie poprzez release w A i acquire w B. Lock() to
>>> aquire, unlock() to release, albo można w ogóle każdą operację na
>>> mutexie traktować 'stricter' jako sequence point - czyli jeżeli oba
>>> wątki przejdą op na mutex to zapis w A może być odczytany w B.
>>
>> Gwarancja jest oidp silniejsza - jeżeli wątek kończy release to zmiany
>> są "commited" w pamięci.
>
> Nie bardzo. Gwarancje dotyczą widoczności pomiędzy wątkami, nie
> ma Jednego Prawdziwego Stanu Pamięci. Nie znam finalnego standartu, ale
> takie były proposale.

Nawet w sytuacji gdy zapis jest "rozgłaszany" do odpowiedniego procesu
dopiero w momencie wywołania którejś z funkcji synchronizacyjnych masz
sytuację w której:
- nie możesz czytać obiektów przed func() bo nie zostały zainicjalizowane
- pierwszy odczyt powinien dostarczyć to co zostało commitnięte w
ostatniej synchronizacji
więc albo nie masz zsynchronizowanej wartości *once i wchodzisz do
muteksu, albo masz zsynchronizowaną wartość *once ale wtedy masz
zsynchronizowane też efekty func(). Wiem o write-reordering, ale barrier
to barrier.

Potraktuj to po prostu jako założenie(co napisałem) - tak jak autor
oryginalnego algorytmu założył, że zapisy są "ordered" tak ja zakładam,
że barrier znaczy barrier a nie niewiadomo-co.

>
>>> Jeżeli
>>> nie ma przejścia przez mutex obu wątków mamy race, czyli wątek B
>>> czyta potencjalnie śmieci.
>>
>> Czyta albo stary stan, albo nowy stan[*] a nie śmieci - dlatego m.i. się
>> używa sig_atomic_t - pierwotne rozwiązanie też to zakłada.
>
> A dlaczego wszystkie pola ustawiane przez func miałyby używać
> sig_atomic_t? Nie doczytałeś, nie chodzi o zmienne
> użyte w tym algorytmie, ale dowolne inicjalizowane przez func
> a używane po przejściu tego algorytmu. Czyli w tym algorytmie ich
> nie ma, są powodem istnienia once().

Jest barriera przed zapisem *once, które jest atomowe. barriera jest
ordered z operacją atomową, więc kolejność jest jasno zdefiniowana.

>
> Naprawdę wszystkie Twoje obiekty w polach statycznych w C++ używają
> wszędzie sig_atomic_t? Ja tam wolę float czy int i parę innych.
>
>> [*] W praktyce nawet na NUMA jest utrzymywana spójność cache więc od
>> momentu zapisu z cache do pamięci wszystkie odczyty będą miały nowy stan.
>
> Na Intelach tak, sam mówiłem, że na Intelach i tak będzie ok.

Nie pisałem o intelach - one zazwyczaj jednak są SMP.


> C++
> ma działać na innych architekturach też. W tym takich, które powstaną
> za 10 lat, najlepiej bez losowych fackapów. Jak tak słuchałem
> Ludzi Który Wiedzą Co Mówią, ARM, Itanium, Alphy są inne niż x86 ;)
> Bardzo Inne (tm).

Zaprezentowany algorytm jeżeli ma serializację odczytu to zgłosi wyjątek
w momencie zapisu - coś jak javowe ConcurrentModificationException -
pamięć została odczytana w sposób konfliktujący z zapisem.

>
>>> Zapis dotyczy zmiennych użytych tutaj i wszystkich
>>> zapisów w func(), które po przejściu algorytmu muszą być widoczne.
>>
>> Masz barrierę na lock() w linii 07 zaraz po wywołaniu func() a dopiero
>> potem modyfikację stanu zmiennej w 08.
>>
>>>
>>> Uff, definicje z głowy ;). Wątek A i wątek B i numery linii,
>>> możliwa sekwencja:
>>>
>>> A linie 1 do 5 (w 2 i 5 jest mutex)
>>> A 6: konstruktor (po to jest ten algorytm) może zapisać pola
>>> A 7: mutex (acquire)
>>> A 8: once = INIT_DONE
>>>
>>> B 1: (once == INIT_DONE) == true (co nie musi być prawdą, ale może)
>>
>> lock() synchronizuje pamięć
>
> Nie no proszę cię. Jak się synchronizuje dostęp do danych w dwóch
> wątkach to trzeba w obu użyć synchronizacji.

Z tego wynika, że mutex_lock robi synchronizację pamięci:
http://pubs.opengroup.org/onlinepubs/9699919799/base
defs/V1_chap04.html#tag_04_11

Drugi wątek ma prawo zrobić odczyt inicjalizowanych obiektów dopiero PO
zakończeniu once().

>
> Czy ty mnie nie prowokujesz?

Ależ oczywiście - wiem czego "unika" ta implementacja i uważam, że żadna
istniejąca teraz architektura ani żadna która zaistnieje w przyszłości
jeżeli daje gwarancję "serializowalności" to tym bardziej daje gwarancję
uszeregowania barrier. Po prostu uważam, że w sprytny sposób unikany
jest problem, który nie istnieje.

>
>>> B 17: wątek używa wartości z A 6, które nie muszą być poprawne,
>>> bo wątek B nie przeszedł przez żaden mutex. Może odczytać
>>> śmieci, czyli mamy race
>>
>> No właśnie nie może, bo to oznacza, że masz architekturę na której
>> zmiany wykonane po barrierze są widoczne przed zmianami wykonanymi przed
>> barrierą.
>
> Inny punkt widzenia jest taki, że drugi wątek może czytać w innej
> kolejności, skoro nie ma pomiędzy tymi punktami synchronizacji.

Nie wolno mu czytać danych, które są dopiero inicjalizowane w once() do
jego zakończenia - to by było UB. Skoro czyta nową wartość *once, które
było modyfikowane PO barrierze to w dowolnej sensownej implementacji (to
było założenie poprawności mojego algorytmu) dane zostaną commitnięte.

>
> I nie, Intel tego nie zabrania, bo kompilator może inaczej
> szeregować operacje, jeżeli tak mu wygodnie podczas optymalizacji.

Kompilator też zna coś takiego jak barriera - przenośna biblioteka
zgodna z pthreads powinna to używać w funkcjach synchronizujących.

>
>>> Powyższa sekwencja może jest mało prawdopodobna, ale mamy
>>> data race.
>>
>> Jeżeli chcesz się trzymać litery standardu C++11 to sam odczyt w linii
>> 01 oryginalnego rozwiązania to jest data race, więc całe dalsze
>> wykonanie to UB.
>
> Co najwyżej może podlegać word-tearing, ale używają typu,
> który ustawiany jest cały (czyli atomicznie, ale z najsłabszym
> ordering czyli żadnym).

Nie. Użyty jest dostęp przez wskaźnik a nie jeden z konstruktów c++11.
Standard wyraźnie mówi, że:
- równoczesny dostęp i zapis są "confilicting"
- "confliccting" bez synchronizacji z obu stron to UB

>
> Sam fakt że może widzieć starą wartość algorytm uwzględnia i to nie
> jest UB.

Ale UB jest sam odczyt.

> Z wątkami tak jest, albo jeden może coś zrobić wcześniej a
> drugi później albo odwrotnie i czy atomik już jest ustawiony
> czy jeszcze nie nie jest żadnym UB.

No i w moim też tak jest - najpierw jest niejawna barriera a dopiero
potem atomic - jeżeli atomic jest widoczny to stan z przed barriery też.

>
> Swoją szosą UB stosuje się do reguły "as-if program działa w jednym
> wątku".

???

>
>>> Dlatego ten algorytm jest genialny, kolejne
>>> przejścia są bez synchronizacji.
>>
>> Powiedziałbym, że jest "normalny" - działa w obrębie pewnych założeń.
>> Tyle, że rozwiązuje problem, którego imo nie ma przez nałożenie
>> ograniczenia na liczbę once a przy tym nie eliminując problemu z UB.
>
> Ok, algorytm nie jest może wiekopomny, ale jak widać dowodzenie
> jego poprawności nie jest takie trywialne.

Jak czytałeś algorytmy stosowane w bazach danych to jest.
Poza tym algorytm opiera się na założeniu, że odczyt konfliktujący z
zapisem jest ok. A ty twierdzisz, że odczyt po barrierze nie gwarantuje
spójności danych przed barrierą jeżeli barriera nie była wołana w obu
wątkach. Czemu jedno założenie ma być lepsze od innego?

--
Pozdrawiam
Michoo

do góry

Dnia pamiętnego Wed, 03 Jul 2013 02:29:38 +0200, Michoo wyjmując peta
oznajmił:

> On 02.07.2013 23:06, Edek wrote:
>> Dnia pamiętnego Tue, 02 Jul 2013 21:18:51 +0200, Michoo wyjmując peta
>> oznajmił:
>>
>>> On 02.07.2013 19:56, Edek wrote:
>>>> Dnia pamiętnego Tue, 02 Jul 2013 18:16:18 +0200, Michoo wyjmując peta
>>>> oznajmił:
>>>
>>>>> - w przypadku odczytu INIT_DONE pomijamy cały blok - inicjalizacja
>>>>> została już wykonana
>>>>
>>>> Tak, ale nie miała miejsce synchronizacja.
>>>
>>> Jaka synchronizacja?
>>
>> No żeby udowodnić widzialność danych musisz udowodnić odpowiedni
>> 'ordering' pomiędzy wątkami.
>
> No i memory barrier jest definiowane jako:
> - wszystkie zapisy wykonane do tej pory zostają commitowane do pamięci
> - wszystkie odczyty od tej pory czytają ostatnio zapisany stan

Ale wątku B w tej sekwencji NIE MA BARRIERY. Jest:

if (false) {
}
continue happily.

Każdy kompilator może zamienić kod taki:
----------------
if (sth){
jakaś_funkcja()
}
zrobB
-----------------

na taki:

------------
wczytaj_dane_doB
if (sth){
jakas_funkcja();
wczytaj_dane_doB
}
uzyj_danych_dokonczB
-------------

Efekt jednego i drugiego kodu według as-if jest identyczny.

Niezależnie od architektury sprzętu jest to legalna i nawet dość
sensowna optymalizacja, przy spekulatywnym wykonaniu chowa się
latency danych B a nawet lepiej. W oryginalnym algorytmie n2660
będzie ok, w zmodyfikowanym dane_doB są czytane za wcześnie.

Ja w ogóle nie bardzo rozumiem w Twoim wywodzie jednej rzeczy:
skoro wątek B nie ma żadnej barriery i procesor ma pipeline,
to w którym stadium pipeline procesora z wątkiem B musi
nastąpić barriera wątku A i dlaczego?

>>>>> Pisane na szybko więc co przeoczyłem?
>>>>
>>>> Model pamięci C++11?
>>>
>>> pthreads z nie_pojebaną_architekturą (tm)
>>
>> ARM i Itanium się kwalifikują jako poyebane? IMHO tak.
>
> Imo nie. Nadal jak robisz barrierę to wszystkie zapisy są widoczne.

Może powiedz co rozumiesz przez słowo barriera. To że jeden
wątek coś robi nie ma żadnego magicznego związku z innymi wątkami. Musi
być happens-before, coś w wątku A przed czymś w wątku B wraz z memory
barrier. A tu w wątku B jest tylko odczyt *once, który nie ma semantyki
memory barrier.

>>>> Model Pamięci ma taką cechę że zapis w wątku A jest widoczny w wątku B
>>>> gdy nastąpi uszeregowanie poprzez release w A i acquire w B. Lock() to
>>>> aquire, unlock() to release, albo można w ogóle każdą operację na
>>>> mutexie traktować 'stricter' jako sequence point - czyli jeżeli oba
>>>> wątki przejdą op na mutex to zapis w A może być odczytany w B.
>>>
>>> Gwarancja jest oidp silniejsza - jeżeli wątek kończy release to zmiany
>>> są "commited" w pamięci.
>>
>> Nie bardzo. Gwarancje dotyczą widoczności pomiędzy wątkami, nie
>> ma Jednego Prawdziwego Stanu Pamięci. Nie znam finalnego standartu, ale
>> takie były proposale.
>
> Nawet w sytuacji gdy zapis jest "rozgłaszany" do odpowiedniego procesu
> dopiero w momencie wywołania którejś z funkcji synchronizacyjnych masz
> sytuację w której:
> - nie możesz czytać obiektów przed func() bo nie zostały zainicjalizowane
> - pierwszy odczyt powinien dostarczyć to co zostało commitnięte w
> ostatniej synchronizacji
> więc albo nie masz zsynchronizowanej wartości *once i wchodzisz do
> muteksu, albo masz zsynchronizowaną wartość *once ale wtedy masz
> zsynchronizowane też efekty func(). Wiem o write-reordering, ale barrier
> to barrier.

A gdzie jest ta bariera?

> Potraktuj to po prostu jako założenie(co napisałem) - tak jak autor
> oryginalnego algorytmu założył, że zapisy są "ordered" tak ja zakładam,
> że barrier znaczy barrier a nie niewiadomo-co.

Gdzie autor robił takie założenie?

Główny powód dla którego nie miesza się sprzętu do logiki poprawności
w abstrakcyjnym modelu jest to, że wiele elementów zachowuje się zgodnie
z tym modelem i w ramach tego modelu może robić co jest akurat potrzebne
- na przykład kompilator optymalizuje. Wolno mu, taki jest model,
a ty zakładasz, że kompilator nic nie robi i wszystko jest zgodne na
poziomie języka z właściwościami sprzętu. Nie jest.

>>>> Jeżeli
>>>> nie ma przejścia przez mutex obu wątków mamy race, czyli wątek B
>>>> czyta potencjalnie śmieci.
>>>
>>> Czyta albo stary stan, albo nowy stan[*] a nie śmieci - dlatego m.i. się
>>> używa sig_atomic_t - pierwotne rozwiązanie też to zakłada.
>>
>> A dlaczego wszystkie pola ustawiane przez func miałyby używać
>> sig_atomic_t? Nie doczytałeś, nie chodzi o zmienne
>> użyte w tym algorytmie, ale dowolne inicjalizowane przez func
>> a używane po przejściu tego algorytmu. Czyli w tym algorytmie ich
>> nie ma, są powodem istnienia once().
>
> Jest barriera przed zapisem *once, które jest atomowe. barriera jest
> ordered z operacją atomową, więc kolejność jest jasno zdefiniowana.

Żeby kolejność była zdefiniowa, musi zaistnieć happens-before, czyli
mamy 'barierę' w jednym wątku przed 'barierą' w drugim wątku. A tu
jest tylko w jednym, więc właśnie nie jest zdefiniowana wcale.

Zresztą na procesorze ogólnie jest podobnie, tylko x86 ma dość ścisły
model pamięci. Tak naprawdę pod tym względem x86 jest bardzo
tolerancyjnym sprzętem, dlatego działały wszystkie akcje typu
while(a==0) {}; jako cond.wait().

> Zaprezentowany algorytm jeżeli ma serializację odczytu to zgłosi wyjątek
> w momencie zapisu - coś jak javowe ConcurrentModificationException -
> pamięć została odczytana w sposób konfliktujący z zapisem.

Jaką serializację odczytu?

Tak btw, ConcurrentModificationException oznacza zmiany strukturalne
w kontenerze i użycie 'starego' iteratora, niekoniecznie ma związek z wątkami.

> Z tego wynika, że mutex_lock robi synchronizację pamięci:
> http://pubs.opengroup.org/onlinepubs/9699919799/base
defs/V1_chap04.html#tag_04_11

Jak rozumiesz "with respect to other threads"? Najwyraźniej inaczej niż ja.

> Drugi wątek ma prawo zrobić odczyt inicjalizowanych obiektów dopiero PO
> zakończeniu once().

Tak być powinno.

>> Czy ty mnie nie prowokujesz?
>
> Ależ oczywiście - wiem czego "unika" ta implementacja i uważam, że żadna
> istniejąca teraz architektura ani żadna która zaistnieje w przyszłości
> jeżeli daje gwarancję "serializowalności" to tym bardziej daje gwarancję
> uszeregowania barrier. Po prostu uważam, że w sprytny sposób unikany
> jest problem, który nie istnieje.

Ok...

Chcesz uważać że llvm i gcc dla c++11 mają UB i to jest zapisane
w standardzie że mają mieć zgodnie z n2660 - wolna wola, uchylę się od
dalszych odpowiedzi.

>>>> B 17: wątek używa wartości z A 6, które nie muszą być poprawne,
>>>> bo wątek B nie przeszedł przez żaden mutex. Może odczytać
>>>> śmieci, czyli mamy race
>>>
>>> No właśnie nie może, bo to oznacza, że masz architekturę na której
>>> zmiany wykonane po barrierze są widoczne przed zmianami wykonanymi przed
>>> barrierą.
>>
>> Inny punkt widzenia jest taki, że drugi wątek może czytać w innej
>> kolejności, skoro nie ma pomiędzy tymi punktami synchronizacji.
>
> Nie wolno mu czytać danych, które są dopiero inicjalizowane w once() do
> jego zakończenia - to by było UB. Skoro czyta nową wartość *once, które
> było modyfikowane PO barrierze to w dowolnej sensownej implementacji (to
> było założenie poprawności mojego algorytmu) dane zostaną commitnięte.

Oryginalna implementacja jest zgodna ze standardem. Spróbuj może znaleźć
odpowiednie zapisy w standarcie c++11 na poparcie Twojej tezy.

>> I nie, Intel tego nie zabrania, bo kompilator może inaczej
>> szeregować operacje, jeżeli tak mu wygodnie podczas optymalizacji.
>
> Kompilator też zna coś takiego jak barriera - przenośna biblioteka
> zgodna z pthreads powinna to używać w funkcjach synchronizujących.

No ale jak w wątku B nie ma barriery, to kompilator ma ją wymyśleć?

Poza tym pthreads miało rację bytu przed c++11 i kompilator jednak
nie zwracał większej uwagi na pthreads. Po prostu zakładał, że
każda nieznana funkcja może zrobić cokolwiek - to już załatwia
potencjalne problemy z pthreads. Istniał instrinsic chyba __mb(),
ale on nic nie robił poza wstawianiem odpowiednich instrukcji.
Kompilator przed C++11 sprawę wątków centralnie olewał, bo mógł.

> Nie. Użyty jest dostęp przez wskaźnik a nie jeden z konstruktów c++11.
> Standard wyraźnie mówi, że:
> - równoczesny dostęp i zapis są "confilicting"
> - "confliccting" bez synchronizacji z obu stron to UB

Któryś z nas jest mocno niewyspany. Jaki konstruktor?

Atomics z definicji są dostępne bez innej synchronizacji. Nawet na
Intelach niektóre orderings zaimplementowane są przez
mov value, [addr]
... bo skutek jest zgodny z modelem pamięci.

>> Sam fakt że może widzieć starą wartość algorytm uwzględnia i to nie
>> jest UB.
>
> Ale UB jest sam odczyt.

Bzdura. Dlaczego odczyt atomika miałby być UB?

>> Z wątkami tak jest, albo jeden może coś zrobić wcześniej a
>> drugi później albo odwrotnie i czy atomik już jest ustawiony
>> czy jeszcze nie nie jest żadnym UB.
>
> No i w moim też tak jest - najpierw jest niejawna barriera a dopiero
> potem atomic - jeżeli atomic jest widoczny to stan z przed barriery też.

Ano nie, standard przewiduje różne 'ordering' tych samych operacji. Dla
niektórych jest tak jak mówisz, dla innych nie. Jest, własnymi słowami,
1. sequence point (czyli Twoja bariera), 2. Acquire semantics
3. Release semantics (połowiczne barriery) i 4. Zapisz po prostu
atomicznie wartość bez żadnego szeregowania. *once ma tę ostatnią.

>> Swoją szosą UB stosuje się do reguły "as-if program działa w jednym
>> wątku".
>
> ???

Nigdy nie słyszałem, żeby określenie UB było stosowane do błędów
związanych z wielowątkowością. Przeciwnie, przed C++11 podstawowym
założeniem kompilatora było to, że kompilowany kod jest jednowątkowy
i tylko miejscami zawiera wywołanie nieznanej funkcji, która może
zrobić cokolwiek. I w ramach jednego wątku działa reguła as-if,
na której opierają się wszystkie optymalizacje, czyli wynik
[jednowątkowego] kodu musi być taki sam jak bez optymalizacji.
Kolejna reguła mówi, że kompilator może założyć że nie ma UB
(a jeżeli jest to programista ma problem tak czy inaczej).

Zwróć uwagę, że optymalizacja może zmienić kolejność dowolnych
odczytów i zapisów do pamięci jeżeli wynik jest taki sam,
o ile nie ma pomiędzy nimi wywołania nieznanej funkcji. I cała
Twoja bariera wyparowuje, gdy jej nie ma w wątku B, podobnie
uszeregowanie odczytów - kompilator nic o tym nie wie i zmieni
kolejność jak mu wygodnie.

> Jak czytałeś algorytmy stosowane w bazach danych to jest.
> Poza tym algorytm opiera się na założeniu, że odczyt konfliktujący z
> zapisem jest ok. A ty twierdzisz, że odczyt po barrierze nie gwarantuje
> spójności danych przed barrierą jeżeli barriera nie była wołana w obu
> wątkach. Czemu jedno założenie ma być lepsze od innego?

Prawdziwe założenie bywa lepsze od fałszywego. Możemy się
oprzeć co najwyżej na standarcie C++11.

--
Edek

do góry

> Owszem, ale to dziala w obie strony.

to sa dwa różne działy programowania mozna by
powiedziec (takie w ktorych zaklada sie wiedze
o tym jak dzialaja nizsze warstwy i takie
gdzie zaklada sie ? brak takiej wiedzy)

dla mnie podstawowe pytanie dotyczace (2)
jest takie czy i tak tego co w (1) jest
po prostu wiedza na temat nizszych warstw
tutaj nie trzeba zastapic czyms innym (naprzyklad
zbiorem dennych reguł albo testami, bvez tej
wiedzy programowanie w takim (2) robi sie czasem
jakby babraniem w niewiadmych (traci sie poczucie
jakosci i wogole jest masa chały - duzo zalezy
np od tego czy ta liste reguł jest długa czy
nie ;-)

do góry

> >>(choćby lubiane prze mnie producent-konsument
>

:/\ //niesmak (distaste)

do góry