Operazioni atomiche, std :: atomic e ordinamento delle scritture

GCC compila questo:

#include  std::atomic a; int b(0); void func() { b = 2; a = 1; } 

a questa:

 func(): mov DWORD PTR b[rip], 2 mov DWORD PTR a[rip], 1 mfence ret 

Quindi, per chiarire le cose per me:

  • Qualsiasi altro thread sta leggendo ‘a’ come 1 garantito per leggere ‘b’ come 2.
  • Perché la MFENCE si verifica dopo la scrittura su “a” non prima.
  • La scrittura su ‘a’ è garantita come operazione atomica (nel senso stretto, non C ++) comunque, e si applica a tutti i processori Intel? Presumo così da questo codice di uscita.

Inoltre, clang (v3.5.1 -O3) fa questo:

 mov dword ptr [rip + b], 2 mov eax, 1 xchg dword ptr [rip + a], eax ret 

Che appare più semplice per la mia piccola mente, ma perché il diverso approccio, qual è il vantaggio di ciascuno?

Ho messo il tuo esempio sul explorer del compilatore Godbolt e ho aggiunto alcune funzioni per leggere, incrementare o combinare ( a+=b ) due variabili atomiche. Ho anche usato a.store(1, memory_order_release); invece di a = 1; per evitare di ottenere più ordini del necessario, quindi è solo un semplice negozio su x86.

Vedi sotto per le spiegazioni (si spera corrette). aggiornamento : ho avuto la semantica di “rilascio” confusa con solo una barriera StoreStore. Penso di aver corretto tutti gli errori, ma potrebbe averne lasciato alcuni.


La prima domanda facile:

La scrittura su ‘a’ è garantita come atomica?

Sì, qualsiasi thread che legge a otterrà il vecchio o il nuovo valore, non un valore parzialmente scritto. Questo accade gratuitamente su x86 e sulla maggior parte delle altre architetture con qualsiasi tipo allineato che si adatti a un registro. (ad esempio non int64_t su 32 bit.) Quindi, su molti sistemi, questo è vero anche per b , come molti compilatori genererebbero codice.

Ci sono alcuni tipi di negozi che potrebbero non essere atomici su un x86, inclusi i negozi non allineati che attraversano un limite di linea della cache. Ma std::atomic naturalmente garantisce qualunque sia l’allineamento necessario.

Le operazioni di lettura-modifica-scrittura sono dove questo diventa interessante. 1000 valutazioni di a+=3 eseguite in più thread contemporaneamente produrranno sempre a += 3000 . Potresti ottenere di meno se non fosse atomico.

Un fatto divertente: i tipi atomici firmati garantiscono il complemento del complemento a due, a differenza dei normali tipi firmati. C e C ++ si aggrappano ancora all’idea di lasciare un overflow intero con segno indefinito in altri casi. Alcune CPU non hanno il giusto spostamento aritmetico, quindi lasciare il giusto spostamento dei numeri negativi indefiniti ha senso, ma per il resto sembra solo un ridicolo cerchio da attraversare ora che tutte le CPU usano il complemento a 2 e i byte a 8 bit.


Qualsiasi altro thread sta leggendo ‘a’ come 1 garantito per leggere ‘b’ come 2.

Sì, a causa delle garanzie fornite da std::atomic .

Ora stiamo entrando nel modello di memoria del linguaggio e dell’hardware su cui gira.

C11 e C ++ 11 hanno un modello di ordinazione della memoria molto debole, il che significa che il compilatore può riordinare le operazioni di memoria a meno che tu non glielo dica. (fonte: modelli deboli di Jeff Preshing contro la memoria forte ). Anche se x86 è il tuo computer di destinazione, devi fermare il compilatore dai negozi di riordino in fase di compilazione . (ad es. normalmente si vorrebbe che il compilatore salvi a = 1 di un ciclo che scrive anche in b ).

L’utilizzo di tipi atomici di C ++ 11 offre per te l’ordinamento di operazioni di coerenza sequenziale completo su di essi rispetto al resto del programma. Questo significa che sono molto più che atomici. Vedi sotto per rilassare l’ordine di ciò che è necessario, il che evita costose operazioni di recinzione.


Perché la MFENCE si verifica dopo la scrittura su “a” non prima.

I recinti di StoreStore sono un no-op con il modello di memoria forte di x86, quindi il compilatore deve semplicemente mettere l’archivio su b prima dello store su a per implementare l’ordinamento del codice sorgente.

La coerenza sequenziale completa richiede inoltre che lo store sia ordinato globalmente / globalmente visibile prima di qualsiasi carico successivo in ordine di programma.

x86 può riordinare i negozi dopo i carichi. In pratica, ciò che accade è che l’esecuzione out-of-order vede un carico indipendente nel stream di istruzioni, e lo esegue prima di un negozio che stava ancora aspettando che i dati fossero pronti. Ad ogni modo, la coerenza sequenziale vieta questo, quindi gcc usa MFENCE , che è una barriera completa, incluso StoreLoad ( l’unico tipo x86 non ha gratis . ( LFENCE/SFENCE sono utili solo per operazioni debolmente ordinate come movnt .))

Un altro modo per mettere questo è il modo in cui i documenti C ++ usano: la coerenza sequenziale garantisce che tutti i thread vedano tutte le modifiche nello stesso ordine. Il MFENCE dopo ogni negozio atomico garantisce che questo thread veda i negozi da altri thread. Altrimenti, i nostri carichi vedrebbero i nostri negozi prima che i carichi di altri thread vedessero i nostri negozi . Una barriera StoreLoad (MFENCE) ritarda i nostri carichi fino a dopo i negozi che devono verificarsi prima.

L’ARM32 asm per b=2; a=1; b=2; a=1; è:

 # get pointers and constants into registers str r1, [r3] # store b=2 dmb sy # Data Memory Barrier: full memory barrier to order the stores. # I think just a StoreStore barrier here (dmb st) would be sufficient, but gcc doesn't do that. Maybe later versions have that optimization, or maybe I'm wrong. str r2, [r3, #4] # store a=1 (a is 4 bytes after b) dmb sy # full memory barrier to order this store wrt. all following loads and stores. 

Non conosco ARM asm, ma quello che ho capito finora è che normalmente è op dest, src1 [,src2] , ma i carichi e i negozi hanno sempre l’operando di registro per primo e l’operando di memoria 2 °. Questo è davvero strano se sei abituato a x86, in cui un operando di memoria può essere l’origine o la destinazione della maggior parte delle istruzioni non vettoriali. Il caricamento delle costanti immediate richiede anche molte istruzioni, poiché la lunghezza dell’istruzione fissa lascia spazio solo per 16b di payload per movw (move word) / movt (sposta in alto).


Rilascio / Acquisto

Il release e l’ acquire denominazione per le barriere della memoria unidirezionale provengono dai blocchi:

  • Un thread modifica una struttura di dati condivisa, quindi rilascia un blocco. Lo sblocco deve essere globalmente visibile dopo tutti i carichi / depositi ai dati che sta proteggendo. (StoreStore + LoadStore)
  • Un altro thread acquisisce il lock (read, o RMW con un release-store) e deve fare tutti i carichi / negozi nella struttura dati condivisa dopo che l’acquisizione diventa globalmente visibile. (LoadLoad + LoadStore)

Nota che std: atomic usa questi nomi anche per le recinzioni standalone che sono leggermente diverse dalle operazioni di acquisizione del carico o di rilascio del negozio. (Vedi atomic_thread_fence, sotto).

L’uscita / acquisizione della semantica è più forte di quanto richieda il produttore-consumatore. Ciò richiede solo StoreStore a senso unico (produttore) e LoadLoad (consumer) unidirezionale, senza ordine di LoadStore.

Una tabella hash condivisa protetta da un blocco lettori / scrittori (ad esempio) richiede un’operazione di lettura-modifica-scrittura atomica di acquisizione-caricamento / rilascio-archivio per acquisire il blocco. x86 lock xadd è una barriera completa (incluso StoreLoad), ma ARM64 ha una versione load-acquire / store-release di load-linked / store-condizionale per fare atomic read-modify-writes. A quanto ho capito, questo evita la necessità di una barriera StoreLoad anche per il blocco.


Usando ordini più deboli ma ancora sufficienti

Scrive su std::atomic tipi std::atomic sono ordinati rispetto ad ogni altro accesso di memoria nel codice sorgente (sia carichi che archivi), per impostazione predefinita. È ansible controllare quale ordine viene imposto con std::memory_order .

Nel tuo caso, hai solo bisogno del tuo produttore per assicurarti che i negozi diventino globalmente visibili nell’ordine corretto, vale a dire una barriera StoreStore prima del negozio in a negozio. store(memory_order_release) include questo e altro. std::atomic_thread_fence(memory_order_release) è solo una barriera StoreStore a 1 via per tutti i negozi. x86 fa StoreStore gratuitamente, quindi tutto ciò che il compilatore deve fare è mettere i negozi nell’ordine sorgente.

Release invece di seq_cst sarà una grande vittoria per le prestazioni, esp. su architetture come x86 dove la versione è economica / gratuita. Questo è ancora più vero se il caso di non contesa è comune.

La lettura delle variabili atomiche impone anche una piena coerenza sequenziale del carico rispetto a tutti gli altri carichi e negozi. Su x86, questo è gratuito. Le barriere LoadLoad e LoadStore sono no-op e implicite in ogni operazione di memoria. Puoi rendere il tuo codice più efficiente sugli ISA debolmente ordinati utilizzando a.load(std::memory_order_acquire) .

Si noti che il recinto standalone std :: atomic funziona in modo confuso per riutilizzare i nomi “acquisisci” e “rilascia” per le recinzioni StoreStore e LoadLoad che ordinano tutti i negozi (o tutti i carichi) almeno nella direzione desiderata . In pratica, di solito emettono istruzioni HW che sono StoreStore a 2 vie o barriere LoadLoad. Questo documento è la proposta per quello che è diventato lo standard corrente. Puoi vedere come memory_order_release esegue il mapping su #LoadStore | #StoreStore #LoadStore | #StoreStore su SPARC RMO, che presumo sia stato incluso in parte perché ha tutti i tipi di barriera separatamente. (hmm, la pagina web cppref menziona solo gli archivi di ordinazione, non il componente LoadStore. Non è lo standard C ++, quindi forse lo standard completo dice di più.)


memory_order_consume non è abbastanza forte per questo caso d’uso. Questo post parla del tuo caso di usare un flag per indicare che altri dati sono pronti e parla di memory_order_consume .

consume sarebbe sufficiente se il tuo flag fosse un puntatore a b , o anche un puntatore a una struct o array. Tuttavia, nessun compilatore sa come eseguire il monitoraggio delle dipendenze per assicurarsi che collochi le cose nell’ordine corretto in asm, quindi le implementazioni correnti trattano sempre il consume come acquire . Questo è un peccato, perché ogni architettura tranne DEC alpha (e il modello di software C ++ 11) fornisce questo ordinamento gratuitamente. Secondo Linus Torvalds, solo alcune implementazioni hardware Alpha potevano effettivamente avere questo tipo di riordino, quindi le costose istruzioni di barriera necessarie in tutto il luogo erano puramente negativi per la maggior parte degli Alpha.

Il produttore deve ancora utilizzare la semantica di release (una barriera StoreStore), per assicurarsi che il nuovo carico utile sia visibile quando il puntatore viene aggiornato.

Non è una ctriggers idea scrivere codice usando il consume , se sei sicuro di capire le implicazioni e non dipendere da tutto ciò che consume non garantisce. In futuro, una volta che i compilatori saranno più intelligenti, il codice verrà compilato senza istruzioni di barriera anche su ARM / PPC. Il movimento effettivo dei dati deve ancora avvenire tra cache su diverse CPU, ma su macchine con modelli di memoria deboli, è ansible evitare di attendere la visualizzazione di scritture non correlate (ad es. Buffer di scratch nel produttore).

memory_order_consume a mente che non puoi testare sperimentalmente il codice memory_order_consume , perché i compilatori attuali ti danno un ordine più forte rispetto alle richieste di codice.

È davvero difficile testare tutto ciò in via sperimentale, perché è sensibile alla sincronizzazione. Inoltre, a meno che il compilatore non riordini le operazioni (perché non si è riusciti a dirlo di no), i thread produttore-consumatore non avranno mai un problema su x86. Dovresti testare su un ARM o PowerPC o qualcosa anche per cercare di cercare problemi di ordinamento che si verificano nella pratica.


Riferimenti:

  • https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67458 : ho segnalato il bug gcc che ho trovato con b=2; a.store(1, MO_release); b=3; b=2; a.store(1, MO_release); b=3; producendo a=1;b=3 su x86, piuttosto che b=3; a=1; b=3; a=1;

  • https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67461 : Ho anche riportato il fatto che ARM gcc usa due dmb sy in una riga per a=1; a=1; a=1; a=1; e x86 gcc potrebbe forse fare con meno operazioni mfence. Non sono sicuro che sia necessario un mfence tra ogni negozio per proteggere un gestore del segnale dall’assunzione di ipotesi errate o se si tratta solo di un’ottimizzazione mancante.

  • Lo scopo di memory_order_consume in C ++ 11 (già collegato sopra) copre esattamente questo caso dell’uso di un flag per passare un carico utile non atomico tra i thread.

  • Quali barriere StoreLoad (x86 mfence) sono per: un programma di esempio funzionante che dimostra la necessità: http://preshing.com/20120515/memory-reordering-caught-in-the-act/

  • Barriere della dipendenza dai dati (solo Alpha ha bisogno di barriere esplicite di questo tipo, ma il C ++ potrebbe averne bisogno per impedire al compilatore di fare carichi speculativi): http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt#360
  • Barriere di controllo-dipendenza: http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt#592

  • Doug Lea dice che x86 ha bisogno solo di LFENCE per i dati che sono stati scritti con scritture “streaming” come movntdqa o movnti . (NT = non temporale). Oltre a bypassare la cache, i carichi / negozi NT x86 hanno semantica debolmente ordinata.

  • http://preshing.com/20120913/acquire-and-release-semantics/

  • http://preshing.com/20120612/an-introduction-to-lock-free-programming/ (puntatori a libri e altre cose che raccomanda).

  • Interessante discussione su realworldtech sul fatto che le barriere ovunque o i modelli di memoria forti siano migliori, compreso il punto in cui la dipendenza dai dati è quasi gratuita in HW, quindi è stupido ignorarlo e mettere un grosso peso sul software. (La cosa Alpha (e C ++) non ha, ma tutto il resto lo fa). Tornate indietro di alcuni post per vedere i divertenti insulti di Linus Torvalds, prima di dare spiegazioni più dettagliate / tecniche sui suoi argomenti.