Dnia Thu, 9 Apr 2015 07:35:43 -0700 (PDT), Wojciech Muła naskrobał:

> Sekcje krytyczne, w sensie mutexy, czy semafory, jako obiekty systemowe
> są wolne, a nawet bardzo wolne. Dlatego tam gdzie liczy się wydajność
> pojawiają się algorytmy lockfree, czyli nie ma jako takiej blokady na
> sekwencję instrukcji, ale np. próbuje się do skutku wykonać jakąś
> operację, powiedzmy dopisania do kolejki. I tu już można to robić
> wydajnie właśnie operacjami atomowymi (głównie compare & exchange)
> no i trzeba pamiętać o barierach pamięci (memory fence).

Jak rozumieć "trzeba pamietać o barierach pamięci"? Co można/trzeba zrobić? Jak
uniknąć
lub ominąć ten problem?
Sorry za banalne pytania, ale nie mam doświadczeń w tej kwestii.

--
howgh
szemrany

do góry

On Thursday, April 9, 2015 at 6:12:42 PM UTC+2, szemrany wrote:
> Dnia Thu, 9 Apr 2015 07:35:43 -0700 (PDT), Wojciech Muła naskrobał:
>
> > Sekcje krytyczne, w sensie mutexy, czy semafory, jako obiekty systemowe
> > są wolne, a nawet bardzo wolne. Dlatego tam gdzie liczy się wydajność
> > pojawiają się algorytmy lockfree, czyli nie ma jako takiej blokady na
> > sekwencję instrukcji, ale np. próbuje się do skutku wykonać jakąś
> > operację, powiedzmy dopisania do kolejki. I tu już można to robić
> > wydajnie właśnie operacjami atomowymi (głównie compare & exchange)
> > no i trzeba pamiętać o barierach pamięci (memory fence).
>
> Jak rozumieć "trzeba pamietać o barierach pamięci"? Co można/trzeba zrobić? Jak
uniknąć
> lub ominąć ten problem?
> Sorry za banalne pytania, ale nie mam doświadczeń w tej kwestii.

Może informacje zawarte w wikipedii wystarczą:

http://pl.wikipedia.org/wiki/Bariera_pami%C4%99ci

Pozdrawiam

do góry

On Thursday, April 9, 2015 at 4:35:44 PM UTC+2, Wojciech Muła wrote:
> On Thursday, April 9, 2015 at 1:20:44 PM UTC+2, M.M. wrote:
> > Jakie korzyści płyną z tego w praktyce?
>
> No takie, że jeden procesor zawsze odczyta/zapisze całe 64 bity
> w całości, nie musi dbać o zapis i odczyt. Chodzi o to, że jak
> zapisujesz 64-bitową liczbę to masz *gwarancję*, że zapisane zostały
> wszystkie dane, a nie, że np. 1 procesor zapisał pierwsze 3 bajty,
> a 2 procesor dopisał 5 pozostałych.
Czyli mamy na myśli to samo :)

>
> > Jak mam przypisanie:
> > zmienna_lokalna = zmienna_globalna;
> > Zmienna globalna mogła zostać zmodyfikowana przez inny wątek/proces.
>
> > Jeśli dostępu do zmienna_globalna nie obejmę sekcją krytyczną, to
> > wiem że dane w zmiennej globalnej i tak będą spójne. Ale co w sytuacji, gdy
> > wątek modyfikujący robi:
> > zmienna_globalna += cos;
> > albo
> > zmienna_globalna *= cos;
> > zmienna_globalna %= cos;
> >
> > Czy dane nadal będą spójne?
>
> Ale to jest już inny przypadek.
Ściśle inny, generalnie ten sam - wątek jakoś zmodyfikował zawartość
zmiennej, a programista nie jest pewny:
1) czy zmodyfikowana zmienna jest widoczna dla innych wątków,
2) czy inny wątek może zobaczyć zmienną zmodyfikowana 'w połowie'.


> Dodawanie, odejmowanie i operacje
> bitowe też mogą być atomowe na x86, ale dla pozostałych rzeczywiście
> trzeba mieć jakąś formę sekcji krytycznej.
Ok, ale w praktyce używamy języków wysokiego poziomu. Piszę np.
a = b;
a kompilator wywnioskował że b będzie równe zero i zrobi:
a ^= a;
Na jakimś procesorze xor może nie być już atomowe.


> > Na pewno z powodu pamięci cache i tak zostaną te same problemy.
>
> Cache akurat nie ma tutaj znaczenia.
>
> > Wątek odczytujący może otrzymać zmienna_globalna z opóźnieniem. Czyli
> > wątek zapisujący i tak musi zrobić powolną operację zrzutu
> > zmodyfikowanych danych. Nie lepiej od razu użyć sekcji krytycznej
> > i mieć prostszy kod w analizie, nie wspominając o możliwości
> > kompilacji na inne procesory, albo o uruchamianiu na klastrze.
>
> Sekcje krytyczne, w sensie mutexy, czy semafory, jako obiekty systemowe
> są wolne, a nawet bardzo wolne. Dlatego tam gdzie liczy się wydajność
> pojawiają się algorytmy lockfree, czyli nie ma jako takiej blokady na
> sekwencję instrukcji, ale np. próbuje się do skutku wykonać jakąś
> operację, powiedzmy dopisania do kolejki. I tu już można to robić
> wydajnie właśnie operacjami atomowymi (głównie compare & exchange)
> no i trzeba pamiętać o barierach pamięci (memory fence).

Myślałem że memory fence też jest wolne, ale jeszcze nigdy na oczy
nie widziałem pomiarów czasu. Może faktycznie to się opłaca...

Pozdrawiam

do góry

On 09/04/2015 17:12, szemrany wrote:
> Dnia Thu, 9 Apr 2015 07:35:43 -0700 (PDT), Wojciech Muła naskrobał:
>
>> Sekcje krytyczne, w sensie mutexy, czy semafory, jako obiekty systemowe
>> są wolne, a nawet bardzo wolne. Dlatego tam gdzie liczy się wydajność
>> pojawiają się algorytmy lockfree, czyli nie ma jako takiej blokady na
>> sekwencję instrukcji, ale np. próbuje się do skutku wykonać jakąś
>> operację, powiedzmy dopisania do kolejki. I tu już można to robić
>> wydajnie właśnie operacjami atomowymi (głównie compare & exchange)
>> no i trzeba pamiętać o barierach pamięci (memory fence).
>
> Jak rozumieć "trzeba pamietać o barierach pamięci"? Co można/trzeba zrobić? Jak
uniknąć
> lub ominąć ten problem?

Polecam te ksiazke
http://www.amazon.co.uk/C-Concurrency-Action-Practic
al-Multithreading/dp/1933988770




B.

do góry

> Zgadza się, dlatego (też) taki jestem ciekawy do czego jest to w
> praktyce potrzebne.

Np. do przerwań. Istnieje cała masa procków, które nie są przeznaczone do wykonywania
programów wielowątkowych (a te "wielowątkowe" też można wykorzystać z jednym
wątkiem), gdzie nadal można chcieć mieć pewne operacje wykonane atomowo, właśnie np.
z uwagi na przerwania.

> > Tak więc sekcja krytyczna albo mutex jest niezbędna.

Zależy do czego. Sekcja krytyczna czy inne bariery pamięci rozwiązują inny problem,
niż atomowy zapis/odczyt pojedynczego słowa.

--
Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

do góry

On Friday, April 10, 2015 at 4:16:58 PM UTC+2, Maciej Sobczak wrote:
> > Zgadza się, dlatego (też) taki jestem ciekawy do czego jest to w
> > praktyce potrzebne.
>
> Np. do przerwań. Istnieje cała masa procków, które nie są przeznaczone do
wykonywania programów wielowątkowych (a te "wielowątkowe" też można wykorzystać z
jednym wątkiem), gdzie nadal można chcieć mieć pewne operacje wykonane atomowo,
właśnie np. z uwagi na przerwania.
>
> > > Tak więc sekcja krytyczna albo mutex jest niezbędna.
>
> Zależy do czego. Sekcja krytyczna czy inne bariery pamięci rozwiązują inny problem,
niż atomowy zapis/odczyt pojedynczego słowa.

Moim zdaniem rozwiązują ten sam problem. Jednak jeśli:
1) robi to procesor, to nie trzeba sekcji krytycznej
2) jeśli nie wiemy na jakim procesorze skompilujemy/uruchomimy, to trzeba
3) jeśli nie mamy pewności jaki kod kompilator wygeneruje, to też trzeba

W QT są klasy (nigdy nie używałem, nazwy podaję z pamięci): QAtomicInc,
QAtomicPointer. Nie wiem, ale zgaduję, że są odpowiedniki w boost czy std.


Pozdrawiam
>
> --
> Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

do góry

> > Zależy do czego. Sekcja krytyczna czy inne bariery pamięci rozwiązują inny
problem, niż atomowy zapis/odczyt pojedynczego słowa.
>
> Moim zdaniem rozwiązują ten sam problem.

Nie. Sekcje krytyczne i bariery rozwiązują (również) problem widoczności i następstwa
zdarzeń. Ten problem nie ma żadnego związku z atomowością czegokolwiek.

Inny przykład: przetwornik analogowo-cyfrowy (albo jakiekolwiek inne peryferium)
produkuje wartość o długości jednego słowa. Program użytkownika czyta tą wartość -
atomowość odczytu gwarantuje, że program zawsze widzi prawidłową wartość z jakiegoś
zapisu z przeszłości. Natomiast sekcja krytyczna nie dość, że nie jest tu potrzebna,
to w ogóle nie da się jej użyć.

To są różne problemy i dlatego istnieją dla nich różne rozwiązania.

--
Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

do góry

On Saturday, April 11, 2015 at 10:47:17 AM UTC+2, Maciej Sobczak wrote:
> > > Zależy do czego. Sekcja krytyczna czy inne bariery pamięci rozwiązują inny
problem, niż atomowy zapis/odczyt pojedynczego słowa.
> >
> > Moim zdaniem rozwiązują ten sam problem.
>
> Nie. Sekcje krytyczne i bariery rozwiązują (również) problem widoczności i
następstwa zdarzeń. Ten problem nie ma żadnego związku z atomowością czegokolwiek.
>
> Inny przykład: przetwornik analogowo-cyfrowy (albo jakiekolwiek inne peryferium)
produkuje wartość o długości jednego słowa. Program użytkownika czyta tą wartość -
atomowość odczytu gwarantuje, że program zawsze widzi prawidłową wartość z jakiegoś
zapisu z przeszłości. Natomiast sekcja krytyczna nie dość, że nie jest tu potrzebna,
to w ogóle nie da się jej użyć.
>
> To są różne problemy i dlatego istnieją dla nich różne rozwiązania.
>
Albo mam zupełnie inne zdanie na ten temat, albo zupełnie inaczej
używamy pojęć... nie wiem co się dzieje. Głupio się nie zgadzać co
do podstaw, ale tak wygląda nasza rozmowa.

do góry

On Thursday, April 9, 2015 at 6:45:16 PM UTC+2, M.M. wrote:
> > Ale to jest już inny przypadek.
> Ściśle inny, generalnie ten sam - wątek jakoś zmodyfikował zawartość
> zmiennej, a programista nie jest pewny:
> 1) czy zmodyfikowana zmienna jest widoczna dla innych wątków,

No to do tego jest bariera pamięci.

> 2) czy inny wątek może zobaczyć zmienną zmodyfikowana 'w połowie'.

A od tego mamy gwarancje spójności od producenta. :)

> > Dodawanie, odejmowanie i operacje
> > bitowe też mogą być atomowe na x86, ale dla pozostałych rzeczywiście
> > trzeba mieć jakąś formę sekcji krytycznej.
> Ok, ale w praktyce używamy języków wysokiego poziomu. Piszę np.
> a = b;
> a kompilator wywnioskował że b będzie równe zero i zrobi:
> a ^= a;
> Na jakimś procesorze xor może nie być już atomowe.

Oczywiście, o to trzeba zadbać. C++11 ma std::atomic, które daje ładne
API do atomiców, barier itp., natomiast kompilator ma wiedzę, którą
jest w stanie wykorzystać. Nie wiem, jak to wygląda w innych językach
imperatywnych (Ada, C#).

> > Sekcje krytyczne, w sensie mutexy, czy semafory, jako obiekty systemowe
> > są wolne, a nawet bardzo wolne. Dlatego tam gdzie liczy się wydajność
> > pojawiają się algorytmy lockfree, czyli nie ma jako takiej blokady na
> > sekwencję instrukcji, ale np. próbuje się do skutku wykonać jakąś
> > operację, powiedzmy dopisania do kolejki. I tu już można to robić
> > wydajnie właśnie operacjami atomowymi (głównie compare & exchange)
> > no i trzeba pamiętać o barierach pamięci (memory fence).
>
> Myślałem że memory fence też jest wolne, ale jeszcze nigdy na oczy
> nie widziałem pomiarów czasu. Może faktycznie to się opłaca...

Ostatnio kolega wykonał proste testy: prefiks lock na instrukcji
increment (tj. pełna blokada) vs increment, później store fence --
z barierą było 2-3 razy szybciej. Podejrzewam, że to trochę
zależy od całego komputera (kontroler pamięci, liczba procesorów),
ale sądzę, że czynnik 2 jest dobrym przybliżeniem.

w.

do góry

On Monday, April 13, 2015 at 8:27:29 PM UTC+2, Wojciech Muła wrote:
> On Thursday, April 9, 2015 at 6:45:16 PM UTC+2, M.M. wrote:
> > > Ale to jest już inny przypadek.
> > Ściśle inny, generalnie ten sam - wątek jakoś zmodyfikował zawartość
> > zmiennej, a programista nie jest pewny:
> > 1) czy zmodyfikowana zmienna jest widoczna dla innych wątków,
>
> No to do tego jest bariera pamięci.
>
> > 2) czy inny wątek może zobaczyć zmienną zmodyfikowana 'w połowie'.
>
> A od tego mamy gwarancje spójności od producenta. :)
>
> > > Dodawanie, odejmowanie i operacje
> > > bitowe też mogą być atomowe na x86, ale dla pozostałych rzeczywiście
> > > trzeba mieć jakąś formę sekcji krytycznej.
> > Ok, ale w praktyce używamy języków wysokiego poziomu. Piszę np.
> > a = b;
> > a kompilator wywnioskował że b będzie równe zero i zrobi:
> > a ^= a;
> > Na jakimś procesorze xor może nie być już atomowe.
>
> Oczywiście, o to trzeba zadbać. C++11 ma std::atomic, które daje ładne
> API do atomiców, barier itp., natomiast kompilator ma wiedzę, którą
> jest w stanie wykorzystać. Nie wiem, jak to wygląda w innych językach
> imperatywnych (Ada, C#).
>
> > > Sekcje krytyczne, w sensie mutexy, czy semafory, jako obiekty systemowe
> > > są wolne, a nawet bardzo wolne. Dlatego tam gdzie liczy się wydajność
> > > pojawiają się algorytmy lockfree, czyli nie ma jako takiej blokady na
> > > sekwencję instrukcji, ale np. próbuje się do skutku wykonać jakąś
> > > operację, powiedzmy dopisania do kolejki. I tu już można to robić
> > > wydajnie właśnie operacjami atomowymi (głównie compare & exchange)
> > > no i trzeba pamiętać o barierach pamięci (memory fence).
> >
> > Myślałem że memory fence też jest wolne, ale jeszcze nigdy na oczy
> > nie widziałem pomiarów czasu. Może faktycznie to się opłaca...
>
> Ostatnio kolega wykonał proste testy: prefiks lock na instrukcji
> increment (tj. pełna blokada) vs increment, później store fence --
> z barierą było 2-3 razy szybciej. Podejrzewam, że to trochę
> zależy od całego komputera (kontroler pamięci, liczba procesorów),
> ale sądzę, że czynnik 2 jest dobrym przybliżeniem.

Czyli przyspieszenie niezbyt duże. Blokady są koszmarnie wolne, dwukrotnie
przyspieszenie to za mało dla wielu praktycznych zastosowań. Z kolei
jeśli dzielimy zadania na bardzo duże porcje, to nawet 10cio krotne
przyspieszenie mechanizmu synchronizacji nie przyniesie mierzalnego
przyspieszenia całego programu.

Ciekawym rozwiązaniem, jak pisałeś, wydają się klasy obudowujące inta w
bibliotece qt czy std. Jest też klasa atomic pointer. Jeszcze nigdy nie używałem tych
klas, trudno mi się wypowiedzieć o ich przydatności i
wydajności. Najbardziej ciekawe jest jednak, jak się mają możliwości tych
klas do spotykanych problemów w praktyce. Może warto im się przyjrzeć.

Pozdrawiam

do góry