[C++11] vraag over Sequential Consistent execution.

[Verwijderd]

Ik heb een stukje C++11 code gemaakt wat item insert in een lock-free circulair buffer. Thread 1 insert in het buffer, thread 2 leest en delete uit het buffer. Thread 2 voert in deze case geen writes uit, alleen plain-ol' reads.

Bij het inserten wordt gebruik gemaakt van de volgende variabelen:

C++:

// shared variabelen:
  volatile unsigned end;  // 4-byte aligned
  Foo* array[ 256 ];   // 8-byte aligned

Het inserten gebeurt als volgt:

C++:

void insert( Foo* ptr )
{
  array[ end % 256 ] = ptr;
  InterlockedIncrement( &end ); // neem aan dat hiervan een non-x86 equivalent bestaat.
};

De volatile is van belang omdat ik een bepaalde optimalisatie in een andere thread wil voorkomen.

Over deze code heb ik 2 vragen:
• Is het gegarandeerd dat, op een x86 architectuur, 'de andere thread' de wijziging aan array[] te zien krijgt vóór of gelijktijdig aan de wijziging aan end? Dat wil zeggen, de compiler/CPU/cache system mag de writes aan de geheugenlocaties van end en array[] niet omdraaien.
• houdt deze assumptie ook stand wanneer wij het hebben over een non-x86 architectuur, zoals POWER?

• bonusvraag: Houdt deze assumptie nog steeds stand wanneer de InterlockedIncrement() word verwisseld met een plain ++?

Volgens mij is het antwoord op vraag 1 'ja, want x86 reordert geen memory writes, en het memory model van C++11 staat geen write reordering toe tenzij op een std::atomic<> met std::memory_order_relaxed.'.
Het antwoord op vraag is 2 is volgens mij nee. Omdat ARM/POWER wel reads reordert en er geen impliciete acquire op standaard loads zit. Om dit op te lossen is een release op beide memory writes en een acquire op beide memory reads nodig.

Het antwoord op de bonusvraag is volgens mij 'ja onder x86, nee onder andere architecturen.'. Vanwege precies dezelfde redenen als eerst.

offtopic:
Overigens is het absoluut zuigend dat de support voor std::atomic en std::memory order super slecht is in veel compilers. Daarom kan je met c++11 atomics op dit moment nog geen code schrijven die daadwerkelijk op elke architectuur optimaal werkt met de meest populaire compilers. In theorie is het allemaal wel mogelijk.

[Zoijar]

Volgens mij gaat dat goed. InterlockedIncrement bevat namelijk een fence: "This function generates a full memory barrier (or fence) to ensure that memory operations are completed in order." en niet alleen maar een atomic variabele.

Een plain ++ is wel atomic voorzover ik weet, maar heeft geen memory fence dus kan wel re-ordered worden.

Maar helemaal zeker weet ik het niet.

[Verwijderd]

Een plain c++ is niet atomic op x86 volgens mij, want de compiler genereert een lock inc dword ptr [r14+14h] instructie op de InterlockedExchange. Als de ++ atomic zou zijn ik een normale inc verwachten.

Volgens mij volstaat een InterlockedReleaseIncrement ook in plaats van die InterlockedIncrement, maar die functie bestaat alleen op itanium.

[ Voor 26% gewijzigd door Verwijderd op 20-10-2013 10:26 ]

[Zoijar]

Ik bedoel atomic in de zin dat er niets tussen kan komen, maar dus zonder memory/order-garanties

[Verwijderd]

Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2 (2A, 2B & 2C):Instruction Set Reference, A-Z:

This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically.

Maar het is niet erg belangrijk dat de instructie atomair wordt uitgevoerd, omdat thread 1 alleen leestschrijft en thread 2 alleen schrijft leest. Wat wel belangrijk is is de volgorde van de operaties.

[ Voor 3% gewijzigd door Verwijderd op 20-10-2013 10:59 ]

[Zoijar]

Maar volgens mij als je in twee threads doet ++x, dan is daarna x[new] altijd x[old]+2. Wat dus niet gebeurt is: fetch[x] y=x+1 store[y] wat dan met een race wordt fetch[x1] fetch[x2] y1=x1+1 y2=x2+1 store[y1] store[y2], en x[new]=x[old]+1. Dat kan volgens mij niet ook zonder lock. aleen is dat iets dat ik ooit een keer meen gelezen te hebben, zoals zo vaak bij mij, en weet ik het niet zeker...

[Verwijderd]

Het kan zo zijn dat de inc assember opcode atomic is, maar dan is er nog steeds geen enkele garantie dat de compiler geen add instructie genereert als hij dat beter vindt.

[Zoijar]

Ik kwam trouwens op deze site http://preshing.com/20120...ordering-at-compile-time/ tijdens wat zoeken. Erg veel interessante info in zijn posts. Ik ga het nog eens allemaal doorlezen

[Verwijderd]

Je kan ook http://channel9.msdn.com/...ter-atomic-Weapons-1-of-2 en http://channel9.msdn.com/...ter-atomic-Weapons-2-of-2 doorkijken als je het interessant vind.

[Zoijar]

Ik vind het wel interessant ja Heb vroeger de artikelen van Herb wel gelezen over lockless queue en double checked locking etc, maar het is een beetje weggezakt. En ik wil inderdaad even de details van C++11 weten.

Het leukste aan dit alles is nog wel dat GPUs ook atomics hebben tegenwoordig en dus lockless algoritmes kunnen uitvoeren.

[ Voor 22% gewijzigd door Zoijar op 20-10-2013 11:35 ]

[MLM]

Sidenote: in C++11 is er ook een header <atomic>, en dan kun je

C++:

std::atomic<unsigned int> end;

gebruiken om iets meer portable code te schrijven.

(Maar std::atomic heeft volgens mij op integral types slechts add, geen inc, dus kans is dat de gecompileerde code iets anders word (lock add, 1 ipv lock inc))

[Verwijderd]

Dat heb ik eens geprobeerd ja. Dan compileert MSVC 2012:

C++:

  std::atomic<int> foo;
  foo.fetch();

Naar:

GAS:

  prefetchw [rbx+14h]
  mov     eax,dword ptr [rbx+14h]
label:
  mov     ecx,eax
  lock cmpxchg dword ptr [rbx+14h],ecx
  jne     label

Terwijl een plain mov op x86 precies de garanties geeft die std::atomic::fetch() vereist. Verder negeert mijn compiler de memory order compleet.

In MSVC 2013 schijnt dat een stuk beter te zijn, maar daar moet ik nog een maandje op wachten.

[ Voor 16% gewijzigd door Verwijderd op 20-10-2013 16:03 ]

[PrisonerOfPain]

Verwijderd schreef op zondag 20 oktober 2013 @ 02:02:

• Is het gegarandeerd dat, op een x86 architectuur, 'de andere thread' de wijziging aan array[] te zien krijgt vóór of gelijktijdig aan de wijziging aan end? Dat wil zeggen, de compiler/CPU/cache system mag de writes aan de geheugenlocaties van end en array[] niet omdraaien.

Je vraagt hier twee verschillende dingen, de ene gaat over de memory memory barriers. De andere over cache-coherence. De memory barrier zorgt er voor dat de wijzigingen in de juiste volgorde ge-propagate worden. De cache-coherence zorgt er voor dat de andere thread uberhaupt je geheugen te zien krijgt (door het MESI protocol op x86/x64).

• houdt deze assumptie ook stand wanneer wij het hebben over een non-x86 architectuur, zoals POWER?

Niet ieder platform generate een memory barrier na een atomic, en niet ieder platform propogate de cache automatisch voor je (soms alleen over dezelfde core, soms zijn alleen bepaalde bussen cache-coherent etc).

• bonusvraag: Houdt deze assumptie nog steeds stand wanneer de InterlockedIncrement() word verwisseld met een plain ++?

Nee, de compiler of de cpu kunnen dan je ++ reorderen, afhankelijk van je memory model. Wikipedia: Memory ordering heeft een mooi overzicht.

[Verwijderd]

PrisonerOfPain schreef op zondag 20 oktober 2013 @ 16:38:
Niet ieder platform generate een memory barrier na een atomic, en niet ieder platform propogate de cache automatisch voor je (soms alleen over dezelfde core, soms zijn alleen bepaalde bussen cache-coherent etc).

Dat is een heel goed punt, daar had ik nooit aan gedacht.

[...]

Nee, de compiler of de cpu kunnen dan je ++ reorderen, afhankelijk van je memory model. Wikipedia: Memory ordering heeft een mooi overzicht.

goede bron.

Ik heb nog een keer die presentatie doorgekeken. Volgens mij zijn de basisregels voor C++11 als volgt:
• De compiler mag geen memory write creëren, op een locatie waar anders geen memory write zou plaatsvinden.
• De compiler mag geen memory read of write onder een memory acquire boven een memory acquire verplaatsen. Code generation zorgt ervoor dat dit ook voor de hardware zo is bij gebruik van atomics.
• De compiler mag geen memory read of write boven een memory release onder een memory release verplaatsen. Code generation zorgt ervoor dat dit ook voor de hardware zo is bij gebruik van atomics.

Het enige wat mij nu nog onduidelijk is is of de volgende code kan falen:

code:

a = 1;  // plain var.
b = 1;  // atomic met release.

code:

if ( b == 1 )  // atomic met acquire
  assert( a == 1 );  // plain var. faalt indien 'a' zichtbaar is vóór 'b'

De compiler zal deze code nooit reorderen, en x86 ook niet, maar is dat voor alle hardware zo?

---

De code uit de topicstart is dus niet correct, want: op een architectuur welke reads reordert, of atomics reordert met writes, kan het zijn dat de wijziging aan end zichtbaar is vóór de wijziging aan array[]. Concreet betekent dit dat mijn code op z'n bek gaat op alles wat geen SPARC of x86/64 of zSeries is volgens het wikipedia overzicht...

Mijn code is dus te fixen door op alle writes naar shared variabelen een release te plaatsen, en op alle reads naar shared variabelen een acquire te plaatsen. Dat compileert op x86/64 naar een xchg (write + std::memory_order_release) en mov (read + std::memory_order_acquire). Overigens is dat niet de optimale code generatie. Een x86 mov bied meer garanties dan nodig waardoor je kunt wegkomen met std::memory_order_relaxed, welke een plain mov als write genereert... als je een fatsoenlijke compiler hebt. Dit werkt niet op ARMv7/POWER/SPARC.

..wat een lap text om zeker te weten dat een bepaalde memory operatie in de juiste volgorde gebeurt..

[MLM]

volgens mij is in c++11 GEGARANDEERD dat het werkt zoals beschreven (immers, dat is de standaard).
eerdere versies, weet je het niet zeker (ligt dus aan de compiler)

[Verwijderd]

C++03 werkt ook al 'gegarandeerd' zo als beschreven in singlethreaded omgevingen. want de C++03 standaard kent geen threads

C++11 (en java, en ongeveer C#) is SC-DRF, dat betekent dat de hardware jouw programma uitvoert op een zodanige manier dat de illusie stand houdt dat het daadwerkelijk jouw programma is. Maar dat is alleen zo als je software vrij van data races is. Een set shared variabelen niet beschermd door een std::mutex of std::atomic introduceert een data race. De code in de topicstart voldoet dus strikt gezien niet aan de standaard.

[MLM]

Verwijderd schreef op maandag 21 oktober 2013 @ 00:22:
C++03 werkt ook al 'gegarandeerd' zo als beschreven in singlethreaded omgevingen. want de C++03 standaard kent geen threads

Singlethreaded is niet het onderwerp van dit topic lijkt me
Desondanks is er natuurlijk in eerdere compilers ook al support voor atomics (door intrinsics of anders), die hardware fences genereren, en de compiler is slim genoeg om daar niet omheen te re-orderen, dus je kan ook dan wel thread-safe code schrijven.

C++11 (en java, en ongeveer C#) is SC-DRF, dat betekent dat de hardware jouw programma uitvoert op een zodanige manier dat de illusie stand houdt dat het daadwerkelijk jouw programma is. Maar dat is alleen zo als je software vrij van data races is. Een set shared variabelen niet beschermd door een std::mutex of std::atomic introduceert een data race. De code in de topicstart voldoet dus strikt gezien niet aan de standaard.

Een programma dat niet vrij is van data-races is natuurlijk bugged Maar dat is in elke taal (en elke versie van C++) zo.
Het enige wat C++11 formaliseert is HOE compilers om moeten gaan met reads/writes in atomics, zodat je daadwerkelijk thread-safe portable code kan schrijven, zonder afhankelijkheid van eerdergenoemde intrinsics/APIs.

Sidenote op de code in TS, je dient bij InterlockedIncrement de returnvalue te gebruiken.

code:

void insert( Foo* ptr ) 
{ 
  unsigned int safe_end = InterlockedIncrement(&end) - 1; //de ENIGE (en atomic) read/write op end
  array[ safe_end % 256 ] = ptr;
};

[Verwijderd]

MLM schreef op maandag 21 oktober 2013 @ 00:32:
Een programma dat niet vrij is van data-races is natuurlijk bugged Maar dat is in elke taal (en elke versie van C++) zo.

De formele definitie van een race is anders dan de definitie van race die je meestal tegenkomt. Access op een variabele vanuit meer dan 1 thread zonder mutex of std::atomic is volgens c++11 altijd undefined behavior. Echter kan je prima multithreaded code schrijven met volatile. std::memory_order_relaxed bied niet veel meer garanties dan volatile. Met name garanties die hier niet nodig zijn.

Sidenote op de code in TS, je dient bij InterlockedIncrement de returnvalue te gebruiken.

code:

void insert( Foo* ptr ) 
{ 
  unsigned int safe_end = InterlockedIncrement(&end) - 1; //de ENIGE (en atomic) read/write op end
  array[ safe_end % 256 ] = ptr;
};

Er is slechts één thread tegelijk die in insert aanwezig is. Dat is in deze use case te implementeren met een mutex met nauwelijks (waarschijnlijk: geen) contention. Sterker nog, ik heb net wat aanpassingen gemaakt aan het bewuste programma waardoor die assumptie breekt door een programmeerfout, het resultaat is een deadlock aan de 'thread 2' kant. Daar ga ik nog even een check voor bouwen...

Maar jouw code is niet correct, voor mijn use case is het noodzakelijk dat dat de write aan end pas te zien is na de write aan array[], maar dat is met jouw code zelden tot nooit het geval afhankelijk van de architectuur.

[.oisyn]

Zoijar schreef op zondag 20 oktober 2013 @ 10:56:
Maar volgens mij als je in twee threads doet ++x, dan is daarna x[new] altijd x[old]+2

Nope, niet waar.

Wat dus niet gebeurt is: fetch[x] y=x+1 store[y] wat dan met een race wordt fetch[x1] fetch[x2] y1=x1+1 y2=x2+1 store[y1] store[y2], en x[new]=x[old]+1

Dat is typisch wel wat er gebeurt, ook op x86. De ALU zit immers niet in het geheugen . Goed, op een single core machine waarbij er geen andere hardware is die iets met het geheugen doet heb je gelijk. De thread zal niet ergens midden-in de load-modify-store gepre-empt worden, x86 instructies zelf zijn wat dat betreft atomair. Maar de geheugenoperaties die ze doen zijn dat niet.

[ Voor 238% gewijzigd door .oisyn op 21-10-2013 01:44 ]

[Verwijderd]

Mijn compiler genereert een

code:

inc     dword ptr [rcx+14h]

op een volatile ++, en

code:

lock inc dword ptr [rsp+0A0h]

op een InterlockedExchange().

Het lijkt er dus op dat een plain ++ niet atomair is. Dat boeit in mijn geval overigens niet.