[C++/Intel compiler] Optimalisatieprobleem

[Specy]

Hoi,

Ik was bezig om een applicatie te optimaliseren, en bij het bekijken van de door de Intel C++ Compiler (versie 9.0) gegenereerde assembly-code ontdekte ik iets vreemds: Als ik een member-variabele van mijn class gebruik, wordt deze iedere keer opnieuw uit het geheugen gelezen, zelfs als 'ie nog in een register zit.

Dit kost natuurlijk nogal wat performance. Als ik zelf aan het begin van mijn functies de member-variabelen naar locale variabelen kopieer is de code ook duidelijk sneller. Maar da's natuurlijk niet echt een fijne oplossing...

Mijn vermoeden is dat de compiler "denkt" dat meerdere threads tegelijk bij mijn objecten kunnen komen, en daarom steeds opnieuw de member-variabelen uit het geheugen haalt voor het geval dat een andere thread intussen de waarde gewijzigd heeft. Als dat inderdaad het geval is, dan moet ik op de een of andere manier de compiler duidelijk zien te maken dat dat niet kan gebeuren... Maar hoe???

Iemand een idee?

[MLM]

als de variabele niet kan wijzigen, maak em dan const. en anders moet je em idd in lokale scope opnemen (kopietje maken), de compiler optimized dat dan mogelijk naar een register.

vziw heeft de intel compiler geen switch om "single threaded" te compilen.

[.oisyn]

Heeft niets met threads te maken, je hebt het hier over het aliasing probleem. Roep je tussendoor een andere functie aan? Als de inhoud van die functie niet bekend is (als hij niet in dezelfde translation unit is geïmplementeerd), dan weet de compiler ook niet of die functie mogelijkerwijs bij dezelfde variabele kan komen en kan aanpassen, en moet hij dus code genereren om 'm elke keer uit het geheugen te halen. Kopiëren naar een lokale variabele is hierbij de enige oplossing - die variabele is lokaal voor de functie, en zolang je geen pointer/reference naar die variabele aan een andere functie geeft kan hij dus zeker weten dat niemand anders erbij kan.

[MLM]

je kan een __declspec(noalias) gebruiken met MSVC compiler, maar dat geldt voor je hele functie (afaik is dat een compilerhint dat je geen globals gebruikt (this + local scope)), maar het probleem is al met iets van this zoals ik het begrijp.

en @oisyn, ik denk dat threads zeker relevant KUNNEN zijn in dit geval, als je namelijk multithread moet je compiler members als volatile behandelen om correct functioneren te garanderen.

[farlane]

MLM schreef op woensdag 02 januari 2008 @ 23:08:
en @oisyn, ik denk dat threads zeker relevant KUNNEN zijn in dit geval, als je namelijk multithread moet je compiler members als volatile behandelen om correct functioneren te garanderen.

Maar dat werkt dus andersom: Je geeft aan de compiler aan dat ie em juist niet mag optimaliseren.

[Specy]

Ik roep in ieder geval geen andere functies aan tussendoor. Er staat in de assembly echt zoiets als dit:

movss xmm1, DWORD PTR [esi]
mulss xmm0, xmm1
movss xmm1, DWORD PTR [esi]
addss xmm2, xmm1

Overigens heb ik ook de indruk dat veel andere code ook beter zou kunnen (pas op het laatste moment registers vullen voordat je die gebruikt om een geheugenadres te lezen enzo). Ik zie in VTune op sommige plekken ook erg lange delays, die ik vaak door de C-code wat te husselen of locale variabelen aan te maken veel korter kan krijgen. Lijkt me iets wat de compiler eigenlijk zelf zou moeten doen...

Ik heb noalias opgezocht, maar zo te zien is dat toch voor andere zaken (wel nuttig trouwens!)

[ Voor 53% gewijzigd door Specy op 03-01-2008 06:28 ]

[.oisyn]

MLM schreef op woensdag 02 januari 2008 @ 23:08:
en @oisyn, ik denk dat threads zeker relevant KUNNEN zijn in dit geval, als je namelijk multithread moet je compiler members als volatile behandelen om correct functioneren te garanderen.

Een compiler zal nooit de assumptie maken dat een variabele door een andere thread gewijzigd kan worden. Bovendien ben je er dan niet door alleen het geheugen opnieuw uit te lezen - de compiler moet dan ook fences genereren voor elke read omdat een write vanuit een andere thread nog niet naar main mem committed hoeft te zijn (hij staat dan bijvoorbeeld nog in de write cache van een andere core, of de read cache van de huidige core is outdated). Dat moet je zelf aangeven door zoals farlane al aangaf de variabele als volatile te declareren.

@Specy: overigens is die gegenereerde code helemaal niet zo duur. [esi] staat bij de tweede fetch gewoon in de L1 cache. Sterker nog, hij kan op deze manier zelfs sneller zijn door betere pipelining, maar eerlijk gezegd denk ik niet dat dat het geval is. Zorgen dat die variabele in een register blijft is iig een micro-optimalisatie, wat voor performanceverschil zie je?

[ Voor 16% gewijzigd door .oisyn op 03-01-2008 11:50 ]

[Xiphalon]

Specy schreef op donderdag 03 januari 2008 @ 04:24:
movss xmm1, DWORD PTR [esi]
mulss xmm0, xmm1
movss xmm1, DWORD PTR [esi]
addss xmm2, xmm1

Dit is voor zover ik kan zien gewoon nette code hoor. Een beetje vreemd kan het wel klinken, maar omdat xmm1 wordt hergevuld, kunnen er via register renaming 2 'exemplaren' van xmm1 actief zijn, waardoor de addss en de mulss tegelijkertijd kunnen worden uitgevoerd.

[MLM]

Nou ben ik geen ster in ASM, maar kan die code niet beter zijn:

GAS:

movss xmm1, DWORD PTR [esi]
movss xmm3, xmm1
mulss xmm0, xmm1
addss xmm2, xmm3

maar 1 load uit geheugen/cache, en de mul en add kunnen tegelijk worden uitgevoerd omdat ze niet dezelfde (xmm1 in het origineel) registers gebruiken. Of ben ik nou gek?

Slightly offtopic:
ik zie zelden compiler generated code die meer dan een paar van de XMM registers gebruikt (je hebt er 8 op x86 en zelfs 16 op x64). Is daar een reden voor?
Ik heb wel ASM code gezien in de intel math libraries die meer registers gebruikt, maar dat is hardcoded (__asm).

[Xiphalon]

MLM schreef op donderdag 03 januari 2008 @ 13:34:
Nou ben ik geen ster in ASM, maar kan die code niet beter zijn:

GAS:

movss xmm1, DWORD PTR [esi]
movss xmm3, xmm1
mulss xmm0, xmm1
addss xmm2, xmm3

maar 1 load uit geheugen/cache, en de mul en add kunnen tegelijk worden uitgevoerd omdat ze niet dezelfde (xmm1 in het origineel) registers gebruiken. Of ben ik nou gek?

Slightly offtopic:
ik zie zelden compiler generated code die meer dan een paar van de XMM registers gebruikt (je hebt er 8 op x86 en zelfs 16 op x64). Is daar een reden voor?
Ik heb wel ASM code gezien in de intel math libraries die meer registers gebruikt, maar dat is hardcoded (__asm).

In jouw code is de compiler een extra register kwijt. Compilers proberen zo weinig mogelijk registers actief te houden en/of te gebruiken, om te voorkomen dat er teveel naar en van de cache c.q. het geheugen wordt gestuurd door een (relatief enorm krappe) bus.

Jouw code is (even xmm3 hernoemen naar een interne xmm register) trouwens precies wat de processor intern doet volgens mij. In de processor zitten meer registers voor uops dan de registers die je kan aanspreken met assembly. Hierdoor kunnen in het geval van de originele code de mulss en de addss tegelijkertijd worden uitgevoerd omdat xmm1 naar 2 verschillende interne uop-registers worden gemapt.

[ Voor 16% gewijzigd door Xiphalon op 03-01-2008 14:01 ]

[Specy]

Ik heb de code aangepast door een locale variabele aan te maken en die te gebruiken. Als ik dat doe krijg ik de code met 1 register meer, en de "mov xmm3, xmm1" erbij. En die is beduidend sneller (zit in een loop die een paar honderdduizend keer per seconde wordt aangeroepen, en dan heeft het toch een duidelijk effect).

Op zich zou het kunnen kloppen dat de compiler een extra register vrij wil houden, maar ik heb ook ergens code gezien waarin de 2e memory-read inderdaad naar een ander register ging, terwijl het eerste register nog de juiste waarde bevatte.

Ik heb overigens even een klein testprojectje gemaakt, en daarin wordt de code wel gecompileerd zoals ik verwacht. Dus ik ga nu even proberen om een nieuw project aan te maken en daar mijn huidige code in te stoppen. Wellicht is er ergens iets fout gegaan (mijn huidige project is al een paar jaar geleden aangemaakt, met een andere compilerversie e.d.). Ik zie niks vreemds in de settings, maar ik ga het toch even proberen.

[Xiphalon]

Oude profile gegevens?

[MLM]

darkmage schreef op donderdag 03 januari 2008 @ 13:58:
[...]


In jouw code is de compiler een extra register kwijt. Compilers proberen zo weinig mogelijk registers actief te houden en/of te gebruiken, om te voorkomen dat er teveel naar en van de cache c.q. het geheugen wordt gestuurd door een (relatief enorm krappe) bus.

Is het neit juist andersom? Hoe meer data je in je registers hebt zitten, hoe minder je uit je cache (of nog erger, je mem) moet halen. In de code die ik gaf heb je een register meer in gebruik, maar een cache read minder. Dat is volgens mijn logica, en de praktijk (post van Specy) sneller.

Jouw code is (even xmm3 hernoemen naar een interne xmm register) trouwens precies wat de processor intern doet volgens mij. In de processor zitten meer registers voor uops dan de registers die je kan aanspreken met assembly. Hierdoor kunnen in het geval van de originele code de mulss en de addss tegelijkertijd worden uitgevoerd omdat xmm1 naar 2 verschillende interne uop-registers worden gemapt.

Misschien waar, zou ik niet weten (interne registers?). Maar hoe dan ook, het lijkt me erg sterk dat een extra cache read goedkoper is dan een extra register gebruiken.

[Specy]

Ok, nieuwe info...

public int Overlap;
private float buffer[4096];

De volgende code:

for (int c=0; c<Overlap; c++)
{
buffer[c] = 0;
buffer[c] = 0;
}

compileert naar:

test ecx, ecx
jle $B56$11
$B56$8:
xor edi, edi ;
xor eax, eax
$B56$9:
mov ecx, DWORD PTR [ebp+16440]
mov DWORD PTR [ecx+edi*4], eax
mov ecx, DWORD PTR [ebp+16440]
mov DWORD PTR [ecx+edi*4], eax
mov ecx, DWORD PTR [ebp+28]
add edi, 1
cmp edi, ecx
jl $B56$9

Als ik nu vlak voor de loop een locale int _Overlap = Overlap en float *_buffer = buffer plaats, en die in plaats van de class-members gebruik, dan wordt dat:

test ecx, ecx
jle $B56$11
$B56$8:
lea edi, DWORD PTR [eax+ecx*4]
xor ecx, ecx
$B56$9:
mov DWORD PTR [eax], ecx
add eax, 4
cmp eax, edi
jb $B56$9

Wijzigingen:

• Het adres van buffer wordt niet iedere keer uit het geheugen gehaald
• De buffer wordt 1 keer geschreven in plaats van (totaal onnodig) 2 keer
• Overlap wordt niet iedere keer uit het geheugen gehaald

Dit is met een net nieuw aangemaakt project... Het verschil in performance is duidelijk erg groot. Verder is mij opgevallen dat in het 1e geval de compiler ook nooit zal vectorizen.

Ik heb geprobeerd of noalias of restrict nog effect heeft, maar dat was niet het geval.

for (c=0; c<Overlap; c++)
{
b += c;
}

gaat overigens wel goed. Wellicht vertrouwt de compiler mijn buffer[]-array niet en leest 'ie alle variabelen opnieuw voor het geval dat ze overschreven zijn? (Maar waarom?)

[ Voor 8% gewijzigd door Specy op 03-01-2008 16:03 ]

[Xiphalon]

MLM schreef op donderdag 03 januari 2008 @ 15:12:
[...]

Is het neit juist andersom? Hoe meer data je in je registers hebt zitten, hoe minder je uit je cache (of nog erger, je mem) moet halen. In de code die ik gaf heb je een register meer in gebruik, maar een cache read minder. Dat is volgens mijn logica, en de praktijk (post van Specy) sneller.

[...]
Misschien waar, zou ik niet weten (interne registers?). Maar hoe dan ook, het lijkt me erg sterk dat een extra cache read goedkoper is dan een extra register gebruiken.

Hoeft niet, bij te weinig registers kan je teveel pus'h's en pop's krijgen. Gebruik je er te weinig dan moet je idd naar het geheugen. Het blijft een NP-compleet probleem, registers alloceren.

[Specy]

En wederom levert Google het antwoord :-)

MEMORY OPTIMIZATION - Christer Ericson, Sony Computer Entertainment, Santa Monica
Powerpoint link: http://www.gamasutra.com/...2003/Ericson_Christer.ppt
Tekstversie (prima te lezen): http://66.102.9.104/searc...&hl=nl&ct=clnk&cd=1&gl=nl

Blijkbaar is dit een bekend issue: Als je class-members gebruikt MOET de compiler ervan uitgaan dat er aliasing kan plaatvinden, en dan zal 'ie steeds alles uit het geheugen halen.

De Intel-compiler lijkt een optie te hebben om dit uit te schakelen, die heb ik even getest maar had geen effect. Bovendien is dat een beetje gevaarlijk (je zou dan ALLE aliasing onmogelijk maken).

De tip die in de bovenstaande presentatie wordt gegeven is: Maak van member variabelen locale kopieen...

Nog een leuke tip: Als je een functie hebt, gebruik dan het "restrict" keyword om de compiler te kunnen laten optimaliseren (m.n. vectorizen, SSE2 e.d.).

Voorbeeld:

void VecAdd(int * restrict a, int *b, int *c)
{
for (int i = 0; i < 4; i++)
a[i] = b[i] + c[i];
}

Zonder die restrict zou a b of c kunnen zijn, met die restrict niet meer.

[MSalters]

Oud verhaal. VC8 heeft bijvoorbeeld Whole Program Optimization, en dan weet de VC8 vaak wel dat a != b. Je samenvatting ("Als je class-members gebruikt MOET de compiler ervan uitgaan dat er aliasing kan plaatvinden") onjuist. this-> is een pointer die minder aliasing problemen oplevert. De strict-aliasing rules werkt erg goed. this-> wijst namelijk altijd naar een object van jouw type. Andere pointers die niet naar een member van jouw class kunnen wijzen, danwel naar een encapsulating class zijn dus vrij van aliasing. Dat is logisch: als A geen B bevat, en B geen A, dan overlappen A en B objecten elkaar niet.

[Specy]

Hm... Op zich werkt die oplossing wel, maar... Hij blijft variabelen inlezen in de volgorde waarin ik het in de code zet. En als ik voorin een functie alles naar locale variabelen kopieer, dan compileert 'ie dat ook zo.

Deze oplossing zal dus wel werken, maar het is ontzettend veel werk om alles handmatig te optimaliseren...

[MLM]

MSalters schreef op donderdag 03 januari 2008 @ 20:41:
Oud verhaal. VC8 heeft bijvoorbeeld Whole Program Optimization, en dan weet de VC8 vaak wel dat a != b. Je samenvatting ("Als je class-members gebruikt MOET de compiler ervan uitgaan dat er aliasing kan plaatvinden") onjuist. this-> is een pointer die minder aliasing problemen oplevert. De strict-aliasing rules werkt erg goed. this-> wijst namelijk altijd naar een object van jouw type. Andere pointers die niet naar een member van jouw class kunnen wijzen, danwel naar een encapsulating class zijn dus vrij van aliasing. Dat is logisch: als A geen B bevat, en B geen A, dan overlappen A en B objecten elkaar niet.

ik bedoelde dat je in een multithreaded omgeving waar foo->bar() aangeroepen wordt in meerdere threads, het mogelijk is dat foo::bar leest en schrijft naar this->something, waardoor je zou willen dat als 1 thread this->something schrijft, de andere threads this->something opnieuw ophalen ipv een gecachete local gebruiken.
Dat komt overeen met wat de compiler nu doet. De TS wil echter dat dat niet gebeurt.

Het was meer een idee van wat ik DACHT dat de compiler DACHT dat mogelijk het geval was, en het daardoor zou compilede. Erg duidelijk weer allemaal, wel een intressante discussie ;P

[Specy]

Ik heb nog wat gezocht op de Intel fora, en er blijkt uiteindelijk toch een (combinatie van) compileropties te zijn om dit voor elkaar te krijgen:

/Ow /Qansi-alias

Met deze opties werd mijn programma 18% sneller. Op het Intel-forum waren er mensen die tot een factor 30 kwamen op hele specifieke code...

Waarschuwing: Als je deze opties gebruikt, dan gaat de compiler ervan uit dat variabelen NIET aliased zijn. Zijn ze dat wel, dan kun je hele rare resultaten krijgen...

Overigens blijken ook ineens optimalisaties die tot nu toe niet werkten (performance werd er slechter van) nu wel goed te werken, dus het eind is nog niet bereikt...

[ Voor 14% gewijzigd door Specy op 04-01-2008 03:30 ]

[MSalters]

MLM schreef op vrijdag 04 januari 2008 @ 00:00:
[...]
ik bedoelde dat je in een multithreaded omgeving waar foo->bar() aangeroepen wordt in meerdere threads, het mogelijk is dat foo::bar leest en schrijft naar this->something, waardoor je zou willen dat als 1 thread this->something schrijft, de andere threads this->something opnieuw ophalen ipv een gecachete local gebruiken.

Dat is nooit een compilerprobleem; je moet in deze gevallen memory barriers gebruiken. Dat staat ook los van class members; dat geldt voor alle gedeelde data.

[Soultaker]

Even een zijspoor. Kan zijn dat ik het niet goed begrijp (m'n assembly is wat roestig), maar ik vind dit extreem onlogische code:

Specy schreef op donderdag 03 januari 2008 @ 16:00:

GAS:

mov       ecx, DWORD PTR [ebp+16440]
mov       DWORD PTR [ecx+edi*4], eax
mov       ecx, DWORD PTR [ebp+16440]
mov       DWORD PTR [ecx+edi*4], eax

Als ik het goed lees, wordt hier op regel 1 en 3 het adres van buffer bepaalt. Waarom is die offset zo hoog? Aangezien 'ie positief is, zou ik verwachten dat het een argument van de functie is, wat suggereert dat je 16KB aan argumenten naar de functie passt? Pass je een struct met zo'n float array erin by-value ofzo?

Dat terzijde, is het vreemd dat dat adres herberekend wordt. Logischerwijs zou je zeggen dat alleen gebeurt als de compiler denkt dat de waarde van de this-pointer kan veranderen ondertussen. Als je er vanuit gaat dat die constant is kun je de hele ecx uit de lus halen natuurlijk (en de tweede move weghalen) dus dat lijkt me de oorzaak van het probleem.

De vraag is waarom de compiler dit niet doet, want zelfs als een this-pointer niet constant is (geen idee wat de C++ standaard daar precies over zegt eigenlijk) mag de compiler aannemen dat 'ie dat is binnen deze functie, aangezien er geen synchronisatie plaatsvindt en er geen externe function calls in de lus zitten.

Specy schreef op donderdag 03 januari 2008 @ 16:32:
En wederom levert Google het antwoord :-)
[..]
Blijkbaar is dit een bekend issue: Als je class-members gebruikt MOET de compiler ervan uitgaan dat er aliasing kan plaatvinden, en dan zal 'ie steeds alles uit het geheugen halen.

Waar haal je dat vandaan? Bedoel je dat de this pointer gealiast kan worden door de float array? Dat lijkt mij extreem onlogisch eigenlijk, want de compiler kan bewijzen dat de (geldige) inhoud van die array niet overlapt met de this pointer, en in het geval van strict aliasing kan van aliasing geen sprake zijn omdat de pointers een ander type hebben.

Het voorbeeld in de slides dat er op lijkt, gebruikt een int en een int *; die situatie is anders. Het lijkt mij dat je problemen ook verdwijnen als je de compiler instrueert om strict aliasing te gebruiken (kan de Intel compiler dat ueberhaupt?)

[ Voor 26% gewijzigd door Soultaker op 05-01-2008 13:07 ]

[Specy]

Soultaker schreef op zaterdag 05 januari 2008 @ 11:14:
Als ik het goed lees, wordt hier op regel 1 en 3 het adres van buffer bepaalt. Waarom is die offset zo hoog? Aangezien 'ie positief is, zou ik verwachten dat het een argument van de functie is, wat suggereert dat je 16KB aan argumenten naar de functie passt? Pass je een struct met zo'n float array erin by-value ofzo?

Nee, het is een member van de class. En blijkbaar kan de compiler in dat geval niet zelf bepalen dat er geen aliasing plaats vindt. (Wel vreemd eigenlijk...)

Soultaker schreef op zaterdag 05 januari 2008 @ 11:14:
Het lijkt mij dat je problemen ook verdwijnen als je de compiler instrueert om strict aliasing te gebruiken (kan de Intel compiler dat ueberhaupt?)

Yup, dat waren die "/Ow /Qansi-alias" flags.