To jest absolutnie to, co C ++ definiuje jako wyścig danych, który powoduje niezdefiniowane zachowanie, nawet jeśli zdarzyło się, że jeden kompilator wyprodukował kod, który zrobił to, czego oczekiwałeś na jakiejś maszynie docelowej. Musisz użyć, aby std::atomic
uzyskać wiarygodne wyniki, ale możesz go użyć, memory_order_relaxed
jeśli nie zależy Ci na zmianie kolejności. Poniżej znajduje się przykładowy kod i dane wyjściowe ASM przy użyciu fetch_add
.
Ale najpierw część pytania w języku asemblerowym:
Ponieważ num ++ jest jedną instrukcją ( add dword [num], 1
), czy możemy stwierdzić, że num ++ jest w tym przypadku niepodzielna?
Instrukcje miejsca docelowego pamięci (inne niż czyste magazyny) to operacje odczytu, modyfikacji i zapisu, które występują w wielu krokach wewnętrznych . Żaden rejestr architektoniczny nie jest modyfikowany, ale procesor musi przechowywać dane wewnętrznie, gdy wysyła je przez swoją jednostkę ALU . Rzeczywisty plik rejestru to tylko niewielka część pamięci danych wewnątrz nawet najprostszego procesora, z zatrzaskami utrzymującymi wyjścia jednego stopnia jako wejścia dla innego stopnia itp., Itd.
Operacje pamięci z innych procesorów mogą stać się globalnie widoczne między ładowaniem a przechowywaniem. Oznacza to, że dwa wątki działające add dword [num], 1
w pętli nadepnęłyby na wzajemne sklepy. (Zobacz odpowiedź @ Margaret na ładny diagram). Po 40 tys. Przyrostów z każdego z dwóch wątków licznik mógł wzrosnąć tylko o ~ 60 tys. (Nie 80 tys.) Na prawdziwym wielordzeniowym sprzęcie x86.
„Atomowy”, od greckiego słowa oznaczającego niepodzielność, oznacza, że żaden obserwator nie może postrzegać operacji jako oddzielnych kroków. Fizyczne / elektryczne natychmiastowe działanie dla wszystkich bitów jednocześnie jest tylko jednym ze sposobów osiągnięcia tego dla obciążenia lub magazynu, ale nie jest to nawet możliwe w przypadku operacji ALU. O wiele bardziej szczegółowo omówiłem czyste obciążenia i czyste sklepy w mojej odpowiedzi na temat Atomicity na x86 , podczas gdy ta odpowiedź skupia się na odczycie, modyfikacji i zapisie.
lock
Prefix może być stosowany do wielu read-modify-write (docelowym pamięci) instrukcje, aby cała operacja atomowa w odniesieniu do wszystkich możliwych obserwatorów w systemie (innych rdzeni i urządzeń DMA, nie oscyloskop podłączone do pinów procesora). Dlatego istnieje. (Zobacz także te pytania i odpowiedzi ).
Tak lock add dword [num], 1
jest atomowa . Rdzeń procesora uruchamiający tę instrukcję utrzymywałby linię pamięci podręcznej przypiętą w stanie zmodyfikowanym w swojej prywatnej pamięci podręcznej L1 od momentu, gdy ładowanie odczytuje dane z pamięci podręcznej do momentu, gdy sklep zatwierdzi wynik z powrotem do pamięci podręcznej. Zapobiega to posiadaniu przez jakąkolwiek inną pamięć podręczną w systemie kopii linii pamięci podręcznej w dowolnym momencie od załadowania do przechowywania, zgodnie z zasadami protokołu spójności pamięci podręcznej MESI (lub jego wersjami MOESI / MESIF używanymi przez wielordzeniowe AMD / Odpowiednio procesory Intel). W ten sposób wydaje się, że operacje wykonywane przez inne rdzenie mają miejsce przed lub po, a nie w trakcie.
Bez lock
prefiksu inny rdzeń mógłby przejąć na własność linię pamięci podręcznej i zmodyfikować ją po naszym załadowaniu, ale przed naszym sklepem, tak aby inny sklep stał się globalnie widoczny między naszym ładowaniem a sklepem. Kilka innych odpowiedzi jest błędnych i twierdzi, że bez lock
otrzymywania sprzecznych kopii tej samej linii pamięci podręcznej. To nigdy nie może się zdarzyć w systemie ze spójnymi pamięciami podręcznymi.
(Jeśli lock
instrukcja ed działa w pamięci, która obejmuje dwie linie pamięci podręcznej, dużo więcej pracy wymaga upewnienie się, że zmiany w obu częściach obiektu pozostaną atomowe w miarę ich propagowania do wszystkich obserwatorów, aby żaden obserwator nie mógł zobaczyć zerwania. Procesor może trzeba zablokować całą magistralę pamięci, aż dane trafią do pamięci. Nie wyrównaj zmiennych atomowych!)
Zauważ, że lock
prefiks również zamienia instrukcję w pełną barierę pamięci (jak MFENCE ), zatrzymując wszelkie zmiany kolejności w czasie wykonywania, a tym samym zapewniając sekwencyjną spójność. (Zobacz doskonały post na blogu Jeffa Preshinga . Jego pozostałe posty też są doskonałe i jasno wyjaśniają wiele dobrych rzeczy na temat programowania bez blokad , od x86 i innych szczegółów dotyczących sprzętu po reguły C ++.)
Na maszynie jednoprocesorowej lub w procesie jednowątkowym pojedyncza instrukcja RMW jest w rzeczywistości niepodzielna bez lock
przedrostka. Jedynym sposobem na uzyskanie dostępu do wspólnej zmiennej przez inny kod jest wykonanie przez procesor przełączania kontekstu, co nie może się zdarzyć w środku instrukcji. Tak więc zwykły dec dword [num]
może synchronizować się między programem jednowątkowym a jego programami obsługi sygnału lub w programie wielowątkowym działającym na maszynie jednordzeniowej. Zobacz drugą połowę mojej odpowiedzi na inne pytanie i komentarze pod nim, gdzie wyjaśniam to bardziej szczegółowo.
Powrót do C ++:
Jest to całkowicie fałszywe w użyciu num++
bez mówienia kompilatorowi, że potrzebujesz go do kompilacji do pojedynczej implementacji odczytu, modyfikacji i zapisu:
;; Valid compiler output for num++
mov eax, [num]
inc eax
mov [num], eax
Jest to bardzo prawdopodobne, jeśli użyjesz wartości num
później: kompilator zachowa ją w rejestrze po zwiększeniu. Więc nawet jeśli sprawdzisz, jak num++
kompiluje się samodzielnie, zmiana otaczającego kodu może na to wpłynąć.
(Jeśli wartość nie jest potrzebna później, inc dword [num]
jest preferowana; nowoczesne procesory x86 będą uruchamiać instrukcję RMW przeznaczoną dla pamięci co najmniej tak wydajnie, jak przy użyciu trzech oddzielnych instrukcji. Ciekawostka: gcc -O3 -m32 -mtune=i586
faktycznie wyemituje to , ponieważ superskalarny potok (Pentium) P5 nie zadziałał „t dekodowania skomplikowane instrukcje do wielu prostych mikro działań, których sposób P6 i później microarchitectures zrobić. Patrz instrukcja tabele / przewodnik mikroarchitektury Agner mgła za uzyskać więcej informacji, ax86 tag wiki dla wielu przydatnych linków (w tym podręczniki Intel x86 ISA, które są dostępne bezpłatnie w formacie PDF).
Nie należy mylić docelowego modelu pamięci (x86) z modelem pamięci C ++
Dozwolona jest zmiana kolejności w czasie kompilacji . Inną częścią tego, co otrzymujesz dzięki std :: atomic, jest kontrola nad zmianą kolejności w czasie kompilacji, aby upewnić się, że stanienum++
się globalnie widoczne dopiero po wykonaniu innej operacji.
Klasyczny przykład: przechowywanie niektórych danych w buforze, aby inny wątek mógł je obejrzeć, a następnie ustawienie flagi. Mimo że x86 pobiera magazyny ładunków / wydań za darmo, nadal musisz powiedzieć kompilatorowi, aby nie zmieniał kolejności za pomocą flag.store(1, std::memory_order_release);
.
Można się spodziewać, że ten kod zostanie zsynchronizowany z innymi wątkami:
// flag is just a plain int global, not std::atomic<int>.
flag--; // This isn't a real lock, but pretend it's somehow meaningful.
modify_a_data_structure(&foo); // doesn't look at flag, and the compilers knows this. (Assume it can see the function def). Otherwise the usual don't-break-single-threaded-code rules come into play!
flag++;
Ale tak się nie stanie. Kompilator może swobodnie przesuwać flag++
wywołanie funkcji (jeśli wstawia funkcję lub wie, że nie patrzy flag
). Wtedy może całkowicie zoptymalizować modyfikację, ponieważ flag
nie jest równa volatile
. (I nie, C ++ volatile
nie jest użytecznym substytutem std :: atomowej. Std :: atomowy robi kompilator założyć, że wartości w pamięci mogą być modyfikowane w sposób asynchroniczny podobny do volatile
, ale jest o wiele więcej niż tylko to. Ponadto, volatile std::atomic<int> foo
jest nie to samo co std::atomic<int> foo
omówiono z @Richardem Hodgesem.)
Zdefiniowanie wyścigów danych na zmiennych nieatomowych jako niezdefiniowane zachowanie pozwala kompilatorowi nadal podnosić ładunki i składować ujścia poza pętle, a także wiele innych optymalizacji pamięci, do których może mieć odniesienie wiele wątków. (Zobacz ten blog LLVM, aby uzyskać więcej informacji o tym, jak UB umożliwia optymalizacje kompilatora).
Jak wspomniałem, prefiks x86lock
jest pełną barierą pamięci, więc użycie num.fetch_add(1, std::memory_order_relaxed);
generuje ten sam kod na x86 co num++
(domyślnie jest to spójność sekwencyjna), ale może być znacznie bardziej wydajne na innych architekturach (takich jak ARM). Nawet na x86, relaxed pozwala na dłuższą zmianę kolejności w czasie kompilacji.
To właśnie robi GCC na x86, dla kilku funkcji, które działają na std::atomic
zmiennej globalnej.
Zobacz kod źródłowy + język asemblera ładnie sformatowany w eksploratorze kompilatora Godbolt . Możesz wybrać inne architektury docelowe, w tym ARM, MIPS i PowerPC, aby zobaczyć, jaki rodzaj kodu języka asemblerowego otrzymasz od atomics dla tych celów.
#include <atomic>
std::atomic<int> num;
void inc_relaxed() {
num.fetch_add(1, std::memory_order_relaxed);
}
int load_num() { return num; } // Even seq_cst loads are free on x86
void store_num(int val){ num = val; }
void store_num_release(int val){
num.store(val, std::memory_order_release);
}
// Can the compiler collapse multiple atomic operations into one? No, it can't.
# g++ 6.2 -O3, targeting x86-64 System V calling convention. (First argument in edi/rdi)
inc_relaxed():
lock add DWORD PTR num[rip], 1 #### Even relaxed RMWs need a lock. There's no way to request just a single-instruction RMW with no lock, for synchronizing between a program and signal handler for example. :/ There is atomic_signal_fence for ordering, but nothing for RMW.
ret
inc_seq_cst():
lock add DWORD PTR num[rip], 1
ret
load_num():
mov eax, DWORD PTR num[rip]
ret
store_num(int):
mov DWORD PTR num[rip], edi
mfence ##### seq_cst stores need an mfence
ret
store_num_release(int):
mov DWORD PTR num[rip], edi
ret ##### Release and weaker doesn't.
store_num_relaxed(int):
mov DWORD PTR num[rip], edi
ret
Zwróć uwagę, jak MFENCE (pełna bariera) jest potrzebna po magazynach o sekwencyjnej spójności. x86 jest ogólnie mocno uporządkowany, ale zmiana kolejności StoreLoad jest dozwolona. Posiadanie bufora magazynu jest niezbędne dla dobrej wydajności na niedziałającym potokowo procesorze. Jeff Preshing's Memory Reordering Caught in the Act pokazuje konsekwencje nieużywania MFENCE, z prawdziwym kodem pokazującym zmianę kolejności zachodzącą na prawdziwym sprzęcie.
Re: dyskusja w komentarzach do odpowiedzi @Richarda Hodgesa na temat kompilatorów łączących num++; num-=2;
operacje std :: atomic w jedną num--;
instrukcję :
Oddzielne pytania i odpowiedzi na ten sam temat: Dlaczego kompilatory nie łączą redundantnych zapisów std :: atomic? , gdzie moja odpowiedź przedstawia wiele z tego, co napisałem poniżej.
Obecne kompilatory tak naprawdę tego nie robią (jeszcze), ale nie dlatego, że nie mają na to pozwolenia. C ++ WG21 / P0062R1: Kiedy kompilatory powinny optymalizować atomiki? omawia oczekiwanie, które wielu programistów ma, że kompilatory nie będą dokonywać „zaskakujących” optymalizacji, oraz co może zrobić standard, aby dać programistom kontrolę. N4455 omawia wiele przykładów rzeczy, które można zoptymalizować, w tym ten. Wskazuje, że inlining i stała propagacja może wprowadzić rzeczy, fetch_or(0)
które mogą być w stanie przekształcić się w zwykłe load()
(ale nadal ma semantykę pozyskiwania i uwalniania), nawet jeśli oryginalne źródło nie miało żadnych oczywiście zbędnych atomowych operacji.
Prawdziwe powody, dla których kompilatory tego nie robią (jeszcze) to: (1) nikt nie napisał skomplikowanego kodu, który pozwoliłby kompilatorowi zrobić to bezpiecznie (bez pomyłki) oraz (2) potencjalnie narusza zasadę najmniejszego niespodzianka . Przede wszystkim kod bez blokady jest wystarczająco trudny do prawidłowego napisania. Dlatego nie bądź swobodny w używaniu broni atomowej: nie są one tanie i nie optymalizują zbyt wiele. std::shared_ptr<T>
Jednak nie zawsze łatwo jest uniknąć zbędnych operacji atomowych , ponieważ nie ma ich nieatomowej wersji (chociaż jedna z odpowiedzi tutaj daje łatwy sposób zdefiniowania a shared_ptr_unsynchronized<T>
dla gcc).
Wracając do num++; num-=2;
kompilacji tak, jakby to było num--
: kompilatorom wolno to robić, chyba że num
jest volatile std::atomic<int>
. Jeśli zmiana kolejności jest możliwa, reguła as-if pozwala kompilatorowi zdecydować w czasie kompilacji, że zawsze dzieje się to w ten sposób. Nic nie gwarantuje, że obserwator będzie mógł zobaczyć wartości pośrednie ( num++
wynik).
To znaczy, jeśli kolejność, w której nic nie staje się globalnie widoczne między tymi operacjami, jest zgodna z wymaganiami porządkowania źródła (zgodnie z regułami C ++ dla maszyny abstrakcyjnej, a nie architektury docelowej), kompilator może emitować pojedynczy lock dec dword [num]
zamiast lock inc dword [num]
/ lock sub dword [num], 2
.
num++; num--
nie może zniknąć, ponieważ nadal ma relację Synchronizuje z innymi wątkami, na które patrzą num
, i jest to zarówno pobieranie, jak i magazyn wersji, co uniemożliwia zmianę kolejności innych operacji w tym wątku. W przypadku x86 może to być możliwe do skompilowania do MFENCE zamiast lock add dword [num], 0
(tj num += 0
.).
Jak omówiono w PR0062 , bardziej agresywne łączenie niesąsiadujących atomowych operacji w czasie kompilacji może być złe (np. Licznik postępu jest aktualizowany tylko raz na końcu zamiast każdej iteracji), ale może również pomóc w wydajności bez wad (np. Pomijanie atomic inc / dec of ref liczy się, gdy kopia a shared_ptr
jest tworzona i niszczona, jeśli kompilator może udowodnić, że inny shared_ptr
obiekt istnieje przez cały czas życia tymczasowego.)
Nawet num++; num--
scalanie może zaszkodzić uczciwości implementacji blokady, gdy jeden wątek zostanie natychmiast odblokowany i ponownie zablokowany. Jeśli w rzeczywistości nigdy nie zostanie wydany w asm, nawet mechanizmy arbitrażu sprzętowego nie dadzą innemu wątkowi szansy na złapanie blokady w tym momencie.
Z obecnymi gcc6.2 i clang3.9, nadal otrzymujesz oddzielne lock
operacje ed nawet memory_order_relaxed
w przypadku najbardziej oczywistej optymalizacji. ( Eksplorator kompilatora Godbolt, dzięki czemu możesz sprawdzić, czy najnowsze wersje są różne).
void multiple_ops_relaxed(std::atomic<unsigned int>& num) {
num.fetch_add( 1, std::memory_order_relaxed);
num.fetch_add(-1, std::memory_order_relaxed);
num.fetch_add( 6, std::memory_order_relaxed);
num.fetch_add(-5, std::memory_order_relaxed);
//num.fetch_add(-1, std::memory_order_relaxed);
}
multiple_ops_relaxed(std::atomic<unsigned int>&):
lock add DWORD PTR [rdi], 1
lock sub DWORD PTR [rdi], 1
lock add DWORD PTR [rdi], 6
lock sub DWORD PTR [rdi], 5
ret
add
jest atomowa?