[es] - Isključivanje optimizacije

mmix
Miljan Mitrović
Software Architect
Pančevo, Srbija

SuperModerator
Član broj: 17944
Poruke: 4898

Sajt: blog.mitrovic.rs

Profil

Re: Isključivanje optimizacije

^{21.10.2011. u 15:39 - pre 575 dana i 7h}

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.

▪ The problem with Socialism is that eventually you run out of other people's money - Lady Thatcher
▪ Success is: 1% inspiration, 98% perspiration and 2% attention to detail
▪ When the only tool you know how to use is a hammer every problem begins to look like a nail

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 7375
89.216.32.*

Profil

Re: Isključivanje optimizacije

^{21.10.2011. u 17:09 - pre 575 dana i 5h}

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?

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 7375
*.3gnet.mts.telekom.rs.

Profil

Re: Isključivanje optimizacije

^{21.10.2011. u 22:49 - pre 575 dana}

Citat:

mmix: 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.

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?

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Ivan Dimkovic
Ivan Dimkovic
Vice President - Product and Business
Development, Cinemo GmbH
EU

Administrator
Član broj: 13
Poruke: 14375
*.dip.t-dialin.net.

Sajt: www.linkedin.com/in/ivand..

Profil

Re: Isključivanje optimizacije

^{21.10.2011. u 22:58 - pre 575 dana}

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

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.dimkovic.com/node/1
Demo Videos: http://www.dimkovic.com/node/17
Gallery: http://www.dimkovic.com/node/25

Odgovor na temu

the_tosic

Član broj: 37314
Poruke: 347
82.208.217.*

Profil

Re: Isključivanje optimizacije

^{21.10.2011. u 23:02 - pre 574 dana i 23h}

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]}

Odgovor na temu

Re: Isključivanje optimizacije

^{21.10.2011. u 23:06 - pre 574 dana i 23h}

^

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.

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.dimkovic.com/node/1
Demo Videos: http://www.dimkovic.com/node/17
Gallery: http://www.dimkovic.com/node/25

Odgovor na temu

the_tosic

Član broj: 37314
Poruke: 347
82.208.217.*

Profil

Re: Isključivanje optimizacije

^{21.10.2011. u 23:10 - pre 574 dana i 23h}

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.

Odgovor na temu

Re: Isključivanje optimizacije

^{21.10.2011. u 23:19 - pre 574 dana i 23h}

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.

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.dimkovic.com/node/1
Demo Videos: http://www.dimkovic.com/node/17
Gallery: http://www.dimkovic.com/node/25

Odgovor na temu

mmix
Miljan Mitrović
Software Architect
Pančevo, Srbija

SuperModerator
Član broj: 17944
Poruke: 4898

Sajt: blog.mitrovic.rs

Profil

Re: Isključivanje optimizacije

^{22.10.2011. u 07:56 - pre 574 dana i 15h}

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.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 7375
*.3gnet.mts.telekom.rs.

Profil

Re: Isključivanje optimizacije

^{22.10.2011. u 11:43 - pre 574 dana i 11h}

Hvala veliko momci, mnogo sam naučio.

Citat:

Ivan Dimkovic: 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.

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:

Code:
a = b;
...
b = a;

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?

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 7375
89.216.32.*

Profil

Re: Isključivanje optimizacije

^{25.10.2011. u 10:50 - pre 571 dana i 12h}

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?

Code:
static LONGLONG atomic = 0;
LONGLONG local = InterlockedExchangeAdd64(&atomic, 0);
// ...
InterlockedExchange64(&atomic, local);

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]}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 7375
89.216.32.*

Profil

Re: Isključivanje optimizacije

^{25.10.2011. u 11:27 - pre 571 dana i 11h}

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

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

mmix
Miljan Mitrović
Software Architect
Pančevo, Srbija

SuperModerator
Član broj: 17944
Poruke: 4898

Sajt: blog.mitrovic.rs

Profil

Re: Isključivanje optimizacije

^{25.10.2011. u 11:43 - pre 571 dana i 11h}

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

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

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 7375
*.3gnet.mts.telekom.rs.

Profil

Re: Isključivanje optimizacije

^{01.12.2011. u 22:05 - pre 533 dana i 23h}

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

Citat:

Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 3A:

8.1.1 Guaranteed Atomic Operations

The Intel486 processor (and newer processors since) guarantees that the following
basic memory operations will always be carried out atomically:
• Reading or writing a byte
• Reading or writing a word aligned on a 16-bit boundary
• Reading or writing a doubleword aligned on a 32-bit boundary
The Pentium processor (and newer processors since) guarantees that the following
additional memory operations will always be carried out atomically:
• Reading or writing a quadword aligned on a 64-bit boundary
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus
The P6 family processors (and newer processors since) guarantee that the following
additional memory operation will always be carried out atomically:
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache
line

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

Citat:

Wikipedia - Data structure alignment:

Typical alignment of C structs on x86

Data structure members are stored sequentially in a memory so that in the structure below the member Data1 will always precede Data2 and Data2 will always precede Data3:

Code:
struct MyData
{
    short Data1;
    short Data2;
    short Data3;
};

If the type "short" is stored in two bytes of memory then each member of the data structure depicted above would be 2-byte aligned. Data1 would be at offset 0, Data2 at offset 2 and Data3 at offset 4. The size of this structure would be 6 bytes.

The type of each member of the structure usually has a default alignment, meaning that it will, unless otherwise requested by the programmer, be aligned on a pre-determined boundary. The following typical alignments are valid for compilers from Microsoft (Visual C++), Borland/CodeGear (C++Builder), Digital Mars (DMC) and GNU (GCC) when compiling for 32-bit x86:

A char (one byte) will be 1-byte aligned.
A short (two bytes) will be 2-byte aligned.
An int (four bytes) will be 4-byte aligned.
A long (four bytes) will be 4-byte aligned.
A float (four bytes) will be 4-byte aligned.
A double (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux (8-byte with -malign-double compile time option).
A long double (ten bytes with C++Builder and DMC, eight bytes with Visual C++, twelve bytes with GCC) will be 8-byte aligned with C++Builder, 2-byte aligned with DMC, 8-byte aligned with Visual C++ and 4-byte aligned with GCC.
Any pointer (four bytes) will be 4-byte aligned. (e.g.: char*, int*)

The only notable difference in alignment for a 64-bit system when compared to a 32-bit system is:

A long (eight bytes) will be 8-byte aligned.
A double (eight bytes) will be 8-byte aligned.
A long double (eight bytes with Visual C++, sixteen bytes with GCC) will be 8-byte aligned with Visual C++ and 16-byte aligned with GCC.
Any pointer (eight bytes) will be 8-byte aligned.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu