[x86-64 assembly] Betere performance met meer instructies

[Soultaker]

In een hobbyprojectje genereer ik dynamisch bytecode, waarbij optioneel ook code voor bounds checking gegenereerd kan worden. Natuurlijk verwachtte ik dat die extra checks overhead zouden opleveren waardoor de code trager loopt. In de praktijk blijkt soms (niet altijd) het tegenovergestelde het geval! Dat is erg vreemd omdat mét bounds checking alleen maar meer code uitgevoerd moet worden, dus nu wil ik (vooral uit nieuwsgierigheid) weten hoe dit precies komt.

Om uit te zoeken waar dat aan ligt, heb ik geprobeerd de code te profilen met oprofile, waarbij ik wel kan zien hoe vaak elke instructie uitgevoerd wordt, maar helaas niet hoe elke instructie precies uitgevoerd wordt in de processor pipeline (daar is helaas mijn CPU te oud voor).

Voor een relatief simpel maar wel representatief voorbeeld is de gegenereerde code als volgt:

GAS:

   358  4.4778 :  400697:   subb   $0x1,(%rax)


   449  5.6160 :  40069a:   movzbq (%rax),%rcx
   525  6.5666 :  40069e:   add    %cl,0x1(%rax)


   731  9.1432 :  4006a1:   movb   $0x0,(%rax)
   858 10.7317 :  4006a4:   add    $0xffffffffffffffff,%rax
   858 10.7317 :  4006a8:   movzbq (%rax),%rcx
   299  3.7398 :  4006ac:   add    %cl,0x1(%rax)


   486  6.0788 :  4006af:   movb   $0x0,(%rax)
   602  7.5297 :  4006b2:   add    $0xffffffffffffffff,%rax
   401  5.0156 :  4006b6:   movzbq (%rax),%rcx
   451  5.6410 :  4006ba:   add    %cl,0x1(%rax)


   382  4.7780 :  4006bd:   movb   $0x0,(%rax)
   394  4.9281 :  4006c0:   addb   $0x1,(%rax)


   386  4.8280 :  4006c3:   add    $0x3,%rax
   313  3.9149 :  4006c7:   cmpb   $0x0,(%rax)
   358  4.4778 :  4006ca:   jne    400697
  ---- -------
  7851 98.1987

Met bounds checking wordt dit echter:

GAS:

     2  0.0300 :  40072e:   subb   $0x1,(%rax)
   503  7.5526 :  400731:   jae    400740
               :  400733:   ..
   384  5.7658 :  400740:   movzbq (%rax),%rcx
    25  0.3754 :  400744:   add    %cl,0x1(%rax)
               :  400747:   jae    400753
               :  400749:   ..
  1366 20.5105 :  400753:   movb   $0x0,(%rax)
     7  0.1051 :  400756:   add    $0xffffffffffffffff,%rax
               :  40075a:   movzbq (%rax),%rcx
   488  7.3273 :  40075e:   add    %cl,0x1(%rax)
    17  0.2553 :  400761:   jae    40076d
               :  400763:   ..
   664  9.9700 :  40076d:   movb   $0x0,(%rax)
     4  0.0601 :  400770:   add    $0xffffffffffffffff,%rax
   634  9.5195 :  400774:   movzbq (%rax),%rcx
               :  400778:   add    %cl,0x1(%rax)
               :  40077b:   jae    400787
               :  40077d:   ..
   719 10.7958 :  400787:   movb   $0x0,(%rax)
     3  0.0450 :  40078a:   addb   $0x1,(%rax)
               :  40078d:   jae    40079c
               :  40078f:   ..
   870 13.0631 :  40079c:   add    $0x3,%rax
    10  0.1502 :  4007a0:   cmpb   $0x0,(%rax)
   879 13.1982 :  4007a3:   jne    40072e
  ---- -------
  6575 98.7239

Het tweede fragment bevat precies dezelfde instructies als het eerste, plus een aantal conditionele jumps (jnc, hier weergegeven als jae). De code die daarop volgt heb ik weggelaten omdat alle jumps altijd genomen worden (wat natuurlijk erg fijn is voor branch prediction). Ik heb in het eerste fragment witregels toegevoegd zodat de regelnummering overeenkomt met het tweede; verder betekent dat niets.

De eerste kolom is het aantal samples per instructie, de tweede ook maar dan als percentage van het totaal. De derde en vierde kolom zijn de geheugenadressen en de bijbehorende instructies. Onderaan heb ik het totaal neergezet, waaraan je ook kunt zien dat het tweede fragment ongeveer 16% sneller is dan de eerste, hoewel in beide gevallen de lus ongeveer 98% van de totale executietijd in beslag neemt.

Wat opvalt is dat in het eerste fragment de samples redelijk netjes verdeeld zijn over all instructies. In het tweede fragment zijn er echter instructies die slechts een handjevol samples hebben, waarbij het dus lijkt alsof instructies per twee of per drie gepaird worden (zie bijvoorbeeld regel 16-18 of 20-22). Dit kan te maken hebben met out-of-order-execution, want overlappende instructies kunnen uitgevoerd worden, maar moeten in volgorde met maximaal drie tegelijk geretired worden.

In eerste instantie vermoedde ik dat het iets met branch target alignment te maken had, maar zelfs als ik een nop instructie toevoeg ergens bovenaan (waardoor het eerste fragment 8-byte aligned wordt en het tweede fragment op een oneven adres terecht komt) blijft het verschil bestaan.

De vraag bij dit hele verhaal is dus: hoe is het te verklaren dat het sneller is om meer (niet eens andere!) instructies uit te voeren, en hoe kan ik in het eerste geval code genereren die minstens zo efficiënt is als in het tweede geval?

[MLM]

Lijkt alsof je eerste profile veel uniformere verdeling heeft van samples (wat me logisch lijkt). Ik zie voornamelijk moves van/naar memory, en verder weinig instructies, dus lijkt mij dan (zonder meer te weten over de code) dat de code gelimiteerd gaat zijn door memory/cache (en dus de daadwerkelijke code op instructie nivo geen hol uitmaakt). Ook het feit dat je 2e sample veel meer samples op je jump-targets heeft doet mij denken dat hij soms wel mis-predict (en dus stallt op je jump-target)

Hoe "lang" duurt je totale code (ie, een paar ms, of stress je in een loop van een paar miljoen keer)?

Zit al je data in cache?

Doen je bounds-checks niet stiekum een read waardoor je een cacheline eerder binnen trekt en daarna sneller kan werken?

Zit je profiler niet je performance te beinvloeden (met zo'n kleine hoeveelheid code best mogelijk)?

Draait het op een single-thread of meer tegelijk? Zit je op met hyperthreading?

Kan je profiler niet ipv samplen de cache-misses profilen?

code:

4006a1:   movb   $0x0,(%rax)
4006a4:   add    $0xffffffffffffffff,%rax
4006a8:   movzbq (%rax),%rcx
4006ac:   add    %cl,0x1(%rax)

Ik ben meer van intel ASM, maar staat hier

C:

char *rax;
qword rcx;

*rax = 0;
rax--;
rcx = (qword)*rax;
*(rax + 1) += (char)rcx; //*(rax + 1) == 0, zie eerste instructie

ben je dan niet beter af met

code:

add    $0xffffffffffffffff,%rax  ;of sub 1,%rax voor leesbaarheid :P
movb  (%rax), %cl
movb  %cl, 0x1(%rax)

dat scheelt een write

[ Voor 31% gewijzigd door MLM op 27-02-2011 22:49 ]

[Soultaker]

MLM schreef op zondag 27 februari 2011 @ 22:15:
Ik zie voornamelijk moves van/naar memory, en verder weinig instructies, dus lijkt mij dan (zonder meer te weten over de code) dat de code gelimiteerd gaat zijn door memory/cache (en dus de daadwerkelijke code op instructie nivo geen hol uitmaakt).

Goed mogelijk; dat verklaart inderdaad waarom die extra check weinig overhead heeft (zolang branch prediction betrouwbaar werkt) maar dat verklaart niet waarom de tweede versie sneller is, want die doet precies alle instructies als het eerste fragment, plus wat extra.

Ook het feit dat je 2e sample veel meer samples op je jump-targets heeft doet mij denken dat hij soms wel mis-predict (en dus stallt op je jump-target)

Hmm, hoe bedoel je dit precies? Ik zie wel dat er in het tweede fragment weliswaar meer samples staan op regel 14 en 20 (vergeleken met het eerste fragment) maar daar staat weer tegenover dat bij de volgende instructie juist (praktisch) geen samples staan (in tegenstelling tot het eerste fragment). Sowieso zou ik bij stalls door mispredictions juist verwachten dat het tweede fragment trager is.

Hoe "lang" duurt je totale code (ie, een paar ms, of stress je in een loop van een paar miljoen keer)?

35-45 ms; vrij weinig dus. De samples zijn over tien identieke runs genomen, dus wel enigzins betrouwbaar, lijkt me.

Zit al je data in cache?

Kan je profiler niet ipv samplen de cache-misses profilen?

Volgens mij zit de data meestal wel in de cache. oprofile kan niet cacheprofilen (met mijn CPU althans) maar met cachegrind vind ik de volgende exacte stats voor de data cache (over het hele programma):

D   refs:      36,036,603  (27,046,891 rd   + 8,989,712 wr)
D1  misses:        48,416  (    47,938 rd   +       478 wr)
LLd misses:        48,228  (    47,780 rd   +       448 wr)
D1  miss rate:        0.1% (       0.1%     +       0.0%  )
LLd miss rate:        0.1% (       0.1%     +       0.0%  )

Die is voor beide fragmenten hetzelfde (want de extra instructies in het tweede fragment referencen geen data). Dit geeft echter geen informatie over wanneer die missses plaatsvinden (zoals je zegt zou het om stalls te voorkomen helpen om misses eerder te triggeren, maar ik zie niet hoe dat zou kunnen).

Doen je bounds-checks niet stiekum een read waardoor je een cacheline eerder binnen trekt en daarna sneller kan werken?

De bound checks zijn de jae instructies; die gebruiken alleen de flags, en refereren niet aan het geheugen. Dat zijn sowieso de enige extra instructies die uitgevoerd worden, dus die helpen blijkbaar op de een of andere manier, maar hoe werkt dat dan precies?

Zit je profiler niet je performance te beinvloeden (met zo'n kleine hoeveelheid code best mogelijk)?

Ik heb de profiler pas opgestart nádat ik het fenomeen gesignaleerd had (gewoon met time op de command line) dus dat lijkt me niet. De profiler geeft wel enige overhead, maar met profiler blijft het absolute verschil in executietijd ongeveer gelijk als zonder.

Draait het op een single-thread of meer tegelijk? Zit je op met hyperthreading?

Single thread. Geen hyperthreading. CPU frequency scaling disabled.

Ben je niet beter af met

code:

add    $0xffffffffffffffff,%rax  ;of sub 1,%rax voor leesbaarheid :P
movb  (%rax), %cl
movb  %cl, 0x1(%rax)

dat scheelt een write

Dit is automatisch gegenereerde code, dus komen dit soort dingen soms voor (ondanks de aanwezigheid van een rudimentaire peephole optimizer). Regel 20 en 21 zouden op een soortgelijke manier kunnen worden samengevoegd. Maar met dit topic wil ik in de eerste plaats uitvinden waar het verschil in performance vandaan komt, los van eventuele andere optimalisaties op de code die ook gedaan kunnen worden.

[MLM]

Soultaker schreef op maandag 28 februari 2011 @ 01:54:
[...]

Goed mogelijk; dat verklaart inderdaad waarom die extra check weinig overhead heeft (zolang branch prediction betrouwbaar werkt) maar dat verklaart niet waarom de tweede versie sneller is, want die doet precies alle instructies als het eerste fragment, plus wat extra.


[...]

Hmm, hoe bedoel je dit precies? Ik zie wel dat er in het tweede fragment weliswaar meer samples staan op regel 14 en 20 (vergeleken met het eerste fragment) maar daar staat weer tegenover dat bij de volgende instructie juist (praktisch) geen samples staan (in tegenstelling tot het eerste fragment). Sowieso zou ik bij stalls door mispredictions juist verwachten dat het tweede fragment trager is.

Ik bedoel, als je jumpt, word je RIP register naar de jumptarget verplaatst. Je sampler leest gewoon periodiek RIP, dus die vind schijnbaar relatief veel "stalls" direct na een jump. Misschien dat jumps altijd overhead hebben (ook correct gepredicte), dus dat je daarom zoveel samples daar hebt. Hoe het dan sneller kan zijn, verbaast me (ik zou eerder andersom verwachten)

35-45 ms; vrij weinig dus. De samples zijn over tien identieke runs genomen, dus wel enigzins betrouwbaar, lijkt me.


[...]

Volgens mij zit de data meestal wel in de cache. oprofile kan niet cacheprofilen (met mijn CPU althans) maar met cachegrind vind ik de volgende exacte stats voor de data cache (over het hele programma):

D   refs:      36,036,603  (27,046,891 rd   + 8,989,712 wr)
D1  misses:        48,416  (    47,938 rd   +       478 wr)
LLd misses:        48,228  (    47,780 rd   +       448 wr)
D1  miss rate:        0.1% (       0.1%     +       0.0%  )
LLd miss rate:        0.1% (       0.1%     +       0.0%  )

Die is voor beide fragmenten hetzelfde (want de extra instructies in het tweede fragment referencen geen data). Dit geeft echter geen informatie over wanneer die missses plaatsvinden (zoals je zegt zou het om stalls te voorkomen helpen om misses eerder te triggeren, maar ik zie niet hoe dat zou kunnen).

okay, nu vind ik het raar. het lijkt alsof alles wel in cache zit (met zo'n lage missrate), verder heb ik geen goede ideeen. misschien eerste cache-warmen (1 iteratie) en dan significante hoeveelheid werk doen (paar seconden) om iets exactere resultaten te verkrijgen, en eventuele meetfout in de timing te reduceren.

De bound checks zijn de jae instructies; die gebruiken alleen de flags, en refereren niet aan het geheugen. Dat zijn sowieso de enige extra instructies die uitgevoerd worden, dus die helpen blijkbaar op de een of andere manier, maar hoe werkt dat dan precies?

Normaal zou ik zeggen, meer ruimte tussen conditional jumps helpt de predictor op sommige hardware (anders worden meerdere jumps in 1x gepredict), maar het eerste fragment heeft geen jumps, dus die zou geen nadeel kunnen ondervinden...

Ik heb de profiler pas opgestart nádat ik het fenomeen gesignaleerd had (gewoon met time op de command line) dus dat lijkt me niet. De profiler geeft wel enige overhead, maar met profiler blijft het absolute verschil in executietijd ongeveer gelijk als zonder.


[...]

Single thread. Geen hyperthreading. CPU frequency scaling disabled.


[...]

Dit is automatisch gegenereerde code, dus komen dit soort dingen soms voor (ondanks de aanwezigheid van een rudimentaire peephole optimizer). Regel 20 en 21 zouden op een soortgelijke manier kunnen worden samengevoegd. Maar met dit topic wil ik in de eerste plaats uitvinden waar het verschil in performance vandaan komt, los van eventuele andere optimalisaties op de code die ook gedaan kunnen worden.

geen goeie ideeen meer. je kan een duidelijke demo maken en op intel site posten, zien wat ze er van maken, daar zitten wel wat pro's

[Soultaker]

MLM schreef op maandag 28 februari 2011 @ 10:54:
Ik bedoel, als je jumpt, word je RIP register naar de jumptarget verplaatst. Je sampler leest gewoon periodiek RIP, dus die vind schijnbaar relatief veel "stalls" direct na een jump. Misschien dat jumps altijd overhead hebben (ook correct gepredicte), dus dat je daarom zoveel samples daar hebt. Hoe het dan sneller kan zijn, verbaast me (ik zou eerder andersom verwachten)

Alle instructies updaten de IP in principe, en aangezien een interrupt niet tijdens een instructie kan worden afgehandeld, zou ik denken dat álle samples die tijdens een instructie plaatsvinden op de volgende instructie terecht komen...

Dat lijkt te kloppen als ik test met deze code:

C:

int a[100], b[100], c[100], d[100], e[100];

int main() {
    int i, j;
    for (i = 0; i < 100; ++i) {
        b[i] = 12345*(i + 1337);
        c[i] = i + 1;
        d[i] =  6789*(i - 1337);
        e[i] = i + 107;
    }
    for (i = 0; i < 1000000; ++i) {
        for (j = 0; j < 100; ++j) a[j] += b[j]/c[j] + d[j]/e[j];
    }
}

Dit levert de volgende profiling data op:

GAS:

     1  0.0011 :  400538:   xor    %ecx,%ecx
     2  0.0023 :  40053a:   nopw   0x0(%rax,%rax,1)
               :  400540:   mov    0x601520(%rcx),%esi
     7  0.0080 :  400546:   mov    %esi,%edx
   332  0.3790 :  400548:   mov    %esi,%eax
               :  40054a:   sar    $0x1f,%edx
     2  0.0023 :  40054d:   idivl  0x6016c0(%rcx)
 42996 49.0833 :  400553:   mov    %eax,%esi
   449  0.5126 :  400555:   mov    0x601040(%rcx),%eax
               :  40055b:   mov    %eax,%edx
               :  40055d:   sar    $0x1f,%edx
   126  0.1438 :  400560:   idivl  0x6011e0(%rcx)
 43051 49.1461 :  400566:   add    %eax,%esi
   111  0.1267 :  400568:   add    %esi,0x601380(%rcx)
     2  0.0023 :  40056e:   add    $0x4,%rcx
               :  400572:   cmp    $0x190,%rcx
   125  0.1427 :  400579:   jne    400540 <main+0x50>
               :  40057b:   add    $0x1,%edi
    87  0.0993 :  40057e:   cmp    $0xf4240,%edi
   307  0.3505 :  400584:   jne    400538 <main+0x48>

Hier is duidelijk te zien dat de interrupts die plaatsvinden tijdens de relatief trage idiv-instructies terecht komen bij de daaropvolgende instructie.

Je hebt dus gelijk dat samples niet precies terechtkomen bij instructies waar je ze zou verwachten, maar dit geldt voor álle instructies, niet per se jumps. We kunnen ons dus beter niet blindstaren op de preciese sample counts per instructie. Het totale aantal samples binnen de lus is gelukkig wel betrouwbaar, en het lijkt me ook duidelijk dat in het tweede fragment instructies per twee of drie tegelijk geretired worden, terwijl dat in het eerste fragment niet zo is. Daar moet het verschil 'm in zitten...

je kan een duidelijke demo maken en op intel site posten, zien wat ze er van maken, daar zitten wel wat pro's

Dat is op zich een goede suggestie, ware het niet dat ik het fenomeen (met deze case in ieder geval) niet op een Intel CPU kan reproduceren...

[PrisonerOfPain]

Je hergebruikt steeds dezelfde registers waar door er eerst gewacht moet worden op de store naar L1 cache voor dat je het register weer kunt gebruiken. Waarschijnlijk kan door de jump de writeback async gedaan worden en zit je dus niet meer tegen die stalls aan te kijken.

[ Voor 6% gewijzigd door PrisonerOfPain op 02-03-2011 16:20 ]

[Soultaker]

PrisonerOfPain schreef op woensdag 02 maart 2011 @ 16:20:
Je hergebruikt steeds dezelfde registers waar door er eerst gewacht moet worden op de store naar L1 cache voor dat je het register weer kunt gebruiken.

Welke registers bedoel je dan precies? De waarden die geschreven worden zitten steeds in het C-register en het adres is relatief aan het A-register, maar die laatste wordt nooit uit het geheugen gelezen. Maar tussen een write ("add %cl, 1(%rax)") en een read ("movzbq (%rax),%rcx") zitten steeds enkele (minstens twee) instructies.

Verder zou ik denken dat register renaming hier efficiënt toegepast kan worden omdat movzbq geen dependency op het doelregister introduceert. Maar ik weet niet in hoeverre je er van uit mag gaan dat dit inderdaad gebeurt.

edit:
Als ik alternerend de C- en D-registers gebruik in plaats van C alleen, blijft de performance (en dus het verschil) hetzelfde.

Waarschijnlijk kan door de jump de writeback async gedaan worden en zit je dus niet meer tegen die stalls aan te kijken.

Hoe werkt dit precies? Waarom zou de stall in het eerste geval langer duren dan de vertraging die de extra jump instructie in het tweede geval oplevert?

[ Voor 8% gewijzigd door Soultaker op 02-03-2011 17:41 ]

[MLM]

Volgens mij doelt PoP op cache-line gedrag van de CPU.

Jouw code bewerkt telkens 2 bytes die naast elkaar liggen, dus een grote kans dat die in dezelfde cacheline vallen. Omdat de reads en writes vrij alternerend komen, moet de CPU bij elke read wachten totdat de writes op dezelfde cacheline klaar zijn (immers, misschien is de data wel veranderd).

Dat heeft volgens mij niets te maken met de namen van de registers, maar ik kan me voorstellen dat dat een korte stall geeft (alhoewel L1 cache wel vrij snel is natuurlijk, dunno of dit praktisch voorkomt)

Hoe jumps dat positief beinvloeden kan ik niet bedenken tbh. Maar misschien begrijp ik hem verkeerd

[PrisonerOfPain]

MLM schreef op woensdag 02 maart 2011 @ 21:07:
Volgens mij doelt PoP op cache-line gedrag van de CPU.

Ik probeerde het verdrag te verklaren aan de hand van load-hit-stores maar aangezien er telkens andere registers en adress gehit worden lijkt me dit sterk. Het meest waarschijnlijke is dat de jump er voor zorgen dat er een instruction latency gehide en dat er instruction gepaired kunnen worden terwijl dat in het andere geval niet kan.

[.oisyn]

De x86 heeft niet zoveel last van een load-hit-store zoals een powerpc dat wel heeft. Ook past ie registry aliasing toe, dus de registers die je specificeert zijn grotendeels virtueel.

zit je al in Zweden?

[ Voor 45% gewijzigd door .oisyn op 03-03-2011 01:58 ]

[PrisonerOfPain]

Het grootste nadeel aan de x86 tegenwoordig is dat omdat het een enorme krachtpatser is, er zo veel dingen in de pipeline gebeuren dat de bottleneck op een specifiek punt te plaatsen valt. Dat gecombineerd met slechte of ontbrekende tools om de daadwerkelijke bottleneck te vinden (GPUs doen dat een heel stuk beter), kortom ik denk dat een verklaring relatief moeilijk te geven valt tenzij je de hardware specs van je processor gaat doorspitten.

.oisyn schreef op donderdag 03 maart 2011 @ 01:55:
zit je al in Zweden?

Ben net terug van snowboard vakantie in Polen en vlieg zondagochtend lekker naar Stockholm, eens zien wat ze in die studio allemaal aan het bekokstoven zijn.

[djc]

offtopic:
Ben nu wel benieuwd naar het desbetreffende hobbyprojectje...