Sudeći po ovome:
http://msdn.microsoft.com/en-us/library/chh3fb0k.aspx
...pominje se jedino "Specifies optimizations to be performed on a function-by-function basis.", korišćenjem "pragma" direktive.

A kako si to uopste resio? Thread scheduler moze da ti razbaca niti kako njemu odgovara, sta kostisis za sinhronizaciju?

Algoritam je takav da je imun. Svejedno je da li će jedna nit da prekine drugu u bilo kojoj tački u funkciji. Ništa dodatno nije potrebno za sinhronizaciju. E, sad, rešenje je proprietary i specifično je za problem. Naravno da se kritične sekcije i ostali rekviziti za sinhronizaciju ne mogu izbaciti jer se u 99,9% problema mogu eliminisati, ali ima slučajeva kada mogu.

No, moje je pitanje kako da isključim optimizaciju u toj jednoj funkciji (ako function by function znači to, to mi odgovara). Da li mi



obavlja posao?

1. Koristi volatile keyword ispred tvojih promenljivih

2. Iskljucivanje optimizacija ti nece resiti problem ako operacije nisu atomske i nisu zasticene nekim sinhronizacionim objektom - oslanjanje na aranziranje koda je naivno zato sto scheduler, kao sto mmix rece, moze da odluci da ti pokvari racun u bilo kom momentu. Najiskreniji savet koji mogu da ti dam tu je da se ne oslanjas na to.

Ako zelis da izbegnes koriscenje sinhronizacionih primitiva zato sto se nesto izvrsava jako puno puta i traje jako kratko onda vidi da li ti rade posao atomske operacije (Intel x86 instrukcije sa lock prefiksom, imas dodavanja, poredjenja, logicke operacije...) - kako koristis VC++/Windows, za to mozes koristiti InterlockedXXX() API-je koji ce se kompajlirati u native asemblerske instrukcije u vecini slucajeva.

http://msdn.microsoft.com/en-u...desktop/ms684122(v=vs.85).aspx

Ja imam slicne situacije u kodu koji piskaram, ali to resavam obicno na drugi nacin posto je algoritam pogodan - recimo procesiram 256 operacija sa lokalnim varijablama koje su inherentno thread-safe - a onda na kraju sa InterlockedXYZ apdejtujem "globalne" varijable (kao sto rekoh, algoritam je podesan) koje drze kompletne vrednosti za ceo proces tj. "frejm" vremena. Time izbegavam contention situacije da niti cekaju predugo vremena na atomskim operacijama.

Sve u svemu - recept je uvek isti: boris se protiv prevelikog zagusenja ali moras obezbediti bezbednost niti... Ti najbolje znas kako mozes urediti svoj algoritam da zadovolji oba uslova.

@edit - ovo ti radi posao za gasenje optimizacija:



"" ce jednostavno ugasiti sve optimizacije, a posle f-je ce vratiti prethodno stanje koje je vezano za nivo optimizacija koji je nalozen sa -Ox flegom.

Bingo! volatile je 100% portabilno rešenje!



Može on da odluči šta hoće, ali ne može da mi pokvari račun. Znam ja šta ti hoćeš da kažeš. Kod se izvršio donekle, onda je uletela neka druga nit, izvršila taj isti deo koda, namesila deljene promenljive "po svojem", a onda prva nit nastavila da radi sa tim vrednostima deljenih promenljivih. E, ja sam moj algoritam rešio tako da mu to ne smeta.

E pa ako si ga resio tako da garantovano nema potencijalnih problema sa vise niti, onda volatile i to bi trebalo da ti resi problem pristupanja promenljivoj od strane kompajlera (time mu zabranjujes da pokusa da optimizuje kod time sto ce podrazumevati da se promenljiva ne menja sama od sebe)

Obrati paznju da volatile varijabla ne znaci da su operacije nad tom varijablom atomske. Ali, ako je kako kazes - da je algoritam thread-safe, to onda ne predstavlja problem.

Meni su bitne dve stvari za moj algoritam:

1. Da je dodela jedne 64-bitne promenljive drugoj atomična.
2. Da se jedna promenljiva ne eliminiše iz računa, već koristi tačno onako kako sam napisao.

Što se 1 tiče, kod se kompajlira u 64-bitni bild za intelovu arhitekturu (i radiće na 64-bitnoj mašini jer mu treba veći adresni prostor od 4GB). Što se 2 tiče, to mi rešava volatile.

Hvala svima, a posebno Ivanu.

BTW, da li je i na 32-bitnoj intelovoj arhitekturi (i eplovoj) int64 dodela atomična? Ja milsim da jeste, alin nisam siguran. Čuo sam da kod Jave nije, tako da moj algoritam tamo nije primenljiv.

Ključna reč volatile nije izmišljena za potrebe sinhronizacije, nego ti samo garantuje da kompajler neće interno keširati vrednost promenljive. Volatile nije rešenje.

Za šta god da je izmišljena, obavlja ono što meni treba, a to je tačka 2.

@Nedeljko, e pa u ovom slucaju ti kod nije siguran - obicna dodela (=) >nije< atomicna, i volatile ti nece resiti problem. Da ne ulazimo sad u razloge zasto je to tako.

Treba ti InterlockedExchange64():

http://msdn.microsoft.com/en-u...desktop/ms683593(v=vs.85).aspx

Kompajler ce to prevesti u asembler (lock xchg itd...) - naravno, ako nisi iskljucio optimizacije :-)

Obrati paznju da sa tim otvaras novu pandorinu kutiju - atomske operacije nisu besplatne, i to ce te kostati nesto CPU ciklusa. Ako ti je kod takav da ce se to atomsko dodeljivanje izvrsavati mnogo puta u kratkom vremenu, razmisli o rearanziranju koda da se to izbegne.

Ako te zanima vise:

http://www.niallryan.com/node/137

nedeljko,
64bit read/write operacije su atomicne na 64bit platformi. interlocked postoji kad treba da se spoje u jednu kroz neki exchange algoritam. Iz istog razloga volatile nema efekta na atomicnost x64 koda, samo orderuje instrukcije pristupa ali cak i tada thread moze biti prekinut izmedju read i write operacije UNUTAR jedne C++ instrukcije i da dobije novu vrednost u drugom threadu, ne postoji nacin da to sprecis bez sinhornizacije. jedini nacin da tva threadu budu threadsafe izvrsavajuci isti kod je da svaki ima svoj local storage potpuno izolovan.

Ako usput želiš portabilno rešenje, koristi std::atomic templejt. To će biti dovoljno za bilo koji integralni tip ili prostu strukturu.

http://www.stdthread.co.uk/doc/headers/atomic/atomic.html

Evo šta meni konkretno treba:

Može 64-bitna dodela da bude i neatomična pod uslovom da se ne desi sledeće:

u dodeli a=b se najpre dodeli npr. viših 32 bita od b, a onda se prekine, uleti neka druga nit, promeni b i nakon toga se u prvoj niti dodeli viših 32 bita od nove vrednosti b.

To ne sme da mi se desi. Suština je da dodeljena vrednost promenljivoj a bude ili cela vrednost od b od pre prekida od strane druge niti ili da bude cela vrednost od b koju je druga nit podesila. Ne sme da se desi da pola vrednosti od a odgovara jednoj, a pola drugoj vrednosti od b.

Na kraju, imam i drugo rešenje koje ne zahteva nikakve posebne pretpostavke - ako za b kažem da je deo konteksta niti (__declspec(thread)), onda mi sve radi, jer u tom slučaju niti neće deliti ništa. No, to rešenje ima neku sasvim prihvatljivu pretpostavku o korišćenju te funkcije (da neće nijedna niti biti živa duže od mesec dana a da između dva uzastopna poziva od strane iste niti prođe više od mesec dana, što je debelo ispunjeno, ali pretpostavka je majka svih zabluda jbg), pa bih je izbegao ako nije obavezna.

A kako radi "ispod haube" atomic<int>? Ima li dodela neko zaključavanje?

Sto se tica a i b, zlatno pravilo je da ako nesto ne mora da bude deljeno izmedju threadova onda i ne treba da bude deljeno izmedju threadova. Ako tebi b moze da bude na nivou thread-a onda treba da bude local storage. Ne mora obavezno da bude u thread storage-u samo da je izolovano od drugih threadova, u osnovi lokalna varijabla u thread funkciji moze da odradi posao uz malo paznje.

A koliko znam std::atomic koristi ralicite mehanizme u zavisnosti od zeljene semantike. Ima i relaxed i full-on pristup sa acquire/release. Sad od toga proberes sta najvise odgovara tvojim potrebama, sto veca izolacija to skuplja operacija.

@Nedeljko
Ispod haube će na Windowsu biti korišćen InterlockedExchange64... a desiće se fallback na standardni locking ako si na sistemu ispod Viste ili ako nemaš hardversku podršku.

@mmix,

Koliko mi je poznato, 64-bitna dodela je na AMD64 arhitekturi atomicna ako i samo ako je memorijska adresa uravnata na 64-bita - sto nije uvek slucaj (npr... u slucaju struktura itd...). IMHO, ja se licno ne bih oslanjao na to nego bih koristio lokalne varijable ako je ikako moguce - ili 100% garantovane atomske operacije kao sto su sve ove do sada navedene u postovima.

Pa i na intelu isto, mislio sam da se to podrazumeva :). Ja u svakom slucaju isto nikad to ne koristim umesto synca, cak ne koristim ni interlocked jer uglavnom ni ne radim sa integer tipovima. I pored toga nisam ima jos nijedan multithreaded scenario gde je locking bio toliko predominantan (tj da postoji toliki stepen uvezanosti da ne moze da se optimizuje ni particionise). Sa obzirom na to da se multi-threading obicno poteze za puno jacih workload-a 9sto bi se jebavao za nesto sto jedan core moze da ti zavrsi za zanemarljivo vreme) cena i najskupljeg acquire/release mehanizma je maginalna ako se pametno koristi, u svakom slucaju acquire/wait na svim multithreaded sistemima baca thread u sleep tako da u situacijama kad je broj taskova veci od stepena paralelizacije prakticno i nema gubljenja vremena, sledeci task ce preuzeti slobodne CPU cikluse dok ovaj ceka. Poenta paralelizacije nije nesmetani run jednog taska (iako je to lepo imati), poenta je maksimalno iskoriscenje procesora i samim tim skracenje ukupnog vremena obrade.

A kako radi std::atomic? Navodno možeš da opališ koliko god hoćeš veliku strukturetinu čiji su na primer svi atributi tipa int. Da li se ta atomičnost plaća nekim zaključavanjem?

Lepo sročeno, ali ako toga ima mnogo troši se vreme na veći broj context switch-eva nego što je neophodno.

No, na jedno mi pitanje nije odgovoreno. U čemu se sastoji ta neatomičnost dodele? Da li je moguć sledeći scenario:

Izvršava se nit t1. Promenljiva b ima vrednost v1. Naredba a=b počinje da se izršava i u sred te naredbe nit t2 prekine nit t1. Nit t2 promeni vrednost promenljive b na v2. Nit t1 nastavlja sa radom dovršavajući dodelu a=b. Da li nakon toga promenljiva može imati malo bitova od v1, a malo od v2?

Takođe, u ovom Ivanovom linku se pominje nekakvo lock u mašinskom kodu. Šta je to?

Neatomicnost 64-bitne dodele ces imati ako dodeljujes vrednost na neuravnatoj memoriji koja je van kes-linije. To ne bi trebalo da se desi sa globalno deklarisanim varijablama, ali moze da se desi sa strukturama i zato nije sigurno.

Vise detalja: http://software.intel.com/en-us/forums/showthread.php?t=48395

A sto se masinskog koda tice, lock prefiks je x86 koncept za atomske operacije - imas nekoliko atomskih operacija, i to su mahom one iste koje ti Windows daje sa InterlockedXXX() API-jima - zapravo, ako je ukljucena optimizacija, kompajler ce InterlockedXXX() pozive pretvoriti direktno u masinske instrukcije.

Recimo InterlockedCompareExchange() --> LOCK CMPXCHG

int_64 var; // globalna
// obe niti podatak iz eax:edx cuvaju u promenjivoj var

t1:
mov var, eax

t2:
mov var, eax
mov var+4, edx

t1:
mov var+4, edx

// nizih 4 bajta promenjive ce postaviti nit t2, a visih nit t1

_{[Ovu poruku je menjao the_tosic dana 22.10.2011. u 13:12 GMT+1]}

^

Da, ali ako je kod 64-bitni - dakle, mov qword ptr bla bla, r(nesto)x... to ce biti atomski upis ako je adresa uravnata na 64-bita.

32-bitni kod ima atomske 32-bitne upise na 32-bitno uravnate adrese (i na neuravnate ako je unutar kes linije)
64-bitni kod ima atomske 64-bitne upise na 64-bitno uravnate adrese (i na neuravnate ako je unutar kes linije)

Za bilo koji drugi slucaj, nije garantovano da ce operacija biti atomska.

IMHO, @Nedeljko, ja bih ipak zaobisao oslanjanje na ovo - CAK i da je 100% tacno da si uspeo da garantujes da ce sve biti procesirano kako treba, pre ili kasnije ces menjati kod koji ce dodati jos neke operacije i tad ces imati problem. Bolje to odmah resi kako treba.

Hm to znam ali posto koristi globalnu promenjivu (koja bi trebalo da bude uravnata), jedina stvar kao problem mi je izgledala ta da koristi 64b promenjivu sa 32b registrima.

Yep... sa globalnom promenljivom i x64 kompajlerom ce dodeljivanje biti atomsko.

Ali to je put koji vodi ka bagovitom kodu, kao sto rekoh - jer neko jednog dana tu promenljivu moze maknuti u neku strukturu i to, recimo, posle neke 32-bitne promenljive itd... Zato se ja licno ne bih oslanjao na to, ali ako Nedeljko smatra da mu to radi posao (+volatile) onda je to valjda resilo stvar.

Pa nije samo ni to, prvobitni intel x64 bit procesori nisu imali ni atomicnost na 64bit boundary ;) Plus neki releasovi procesora imaju bugove, da bi zaista mogao da racunas na tako nesto u opstem protabilnom slucaju morao bi da imas errata za sve verzije procesora da znas workarounds (npw citao sam skoro da na nekom xeonu write na neku lokaciju ima zadrsku u L1 kesu pa ne moze odmah da procitas tu lokaciju vec moras da ubacis jedan NOP izmedju write i read). Vecina koda koji racuna na atomicnost mov operacija zapravo podrzavaju samo core2 na ovamo i "novije" xeone :), doduse istini za volju to je verovatno 99.9% intel procesora u upotrebi.


Nedeljko, lock osigurava atomicnost, kao sto ti je Ivan rekao, ali ti nije rekao da lock u stvari predstavlja upravo ono sto si ti mislio da si prevazisao. Kljucni deo spin-lock mehanizma (iznad kojeg su izgradjeni ostali acquire/release mehanizmi) je upravo (lock) xchg, a da bi lock osigurao da se vrednost ne menja izmedju dve interne operacije on ZAKLJUCA magistralu (assert LOCK#) sto na kratko blokira sva jezgra u trenutku pristupa memoriji. Na novijim procesorima umesto da zakljuca magistralu zakljuca cache line ali eskalira u bus lock ako je cross-boundary. U svakom slucaju i cache lock "boli" ako je algoritam toliko dobro optimizovan da je radni set u kesu (ka cemo se obicno stremi) i ako je contention za deljenim resursom veliki. "Cena" lock operacije je oko 100-ak cpu ciklusa izvrsnog jezgra plus gubitak na svim ostalim jezgrima kad ulete u lock. To je i dalje daleko jeftinije od kernel sync objeakta ali ako racunas da sporadicne pozive sync objekata zamenis tonom interlocked operacija onda i nisi bas nesto uradio. Nije svaki algoritam dobar za paralelizaciju, ili promenis algoritam tako da minimizujes contention (i samim tim smanjis broj lockova i smanjis broj context switcheva) ili ga pustis na jednom jezgru.

Hvala veliko momci, mnogo sam naučio.



Sve je to jasno i rešiću kako treba. No, kasnije se ovaj kod neće menjati, već će biti izbačen kao nepotreban, ali dobro, razumeli smo se.

Znači, imam dve promenljie, jednu statičku b i jednu lokalnu a, obe tipa uint64 i obe van bilo kakvih struktura. Kod izgleda ovako:



Nema nikakvih petlji itd. Imam tačno jedno a = b i tačno jedno b = a. Šta biste preporučili kao konačno rešenje?

Imam dve promenljive, atomic i local. Treba mi dodela u oba smera. Funkcija InterlockedExchange64 obavlja posao punjenja, ali kako pročitati atomičnu promenljivu bez menjanja stanja?



Rešenje je prosto: funkcija InterlockedExchangeAdd64(LONGLONG *atomic, LONGLONG value) povećava vrednost atomične promenljive *atomic za value i vraća prethodnu vrednost promenljive *atomic. Ako ne želite da promenite vrednost, već samo da je pročitate, rešenje je "dodavanje" nule.

_{[Ovu poruku je menjao Nedeljko dana 25.10.2011. u 12:03 GMT+1]}

Samo što InterlockedXXX64 funkcije nisu podržane na XP-u, a VS 2010 naravno ne podržava std::atomic.

podrzane su na xp64 ;) tj br bi trebalo da su.


mislim da ovde mozes da pokupis atomic lib, http://threadingbuildingblocks.org/

Ko bre kaže da 64-bitna dodela nije atomična!



Jeste i to počev od P6. Što se potrebnog poravnavanja tiče, može da se zada direktiva, a i ne mora:

Takođe, polazni problem neeliminacije promenljive optimizacijom je umesto sa volatile bolje rešiti korišćenjem asemblera, jer volatile sprečava keširanje.



Možda ovaj asembler nisam dobro napisao, ali to je ono što sam hteo da kažem.

Samo da pitam da li je sledeći kod dobar: