Intrinsic Funktion _bittest langsamer?

[Christian (Gast)]

Hallo.
Wollte mal testen inwieweit intrinsische Funktionen für 
Geschwindigkeit-optimierte Programme einsetzbar sind.

Zum Vergleich habe ich die intr. Funktion _bittest() eingesetzt und
anschließend im normalen C-Code umgesetzt.

Das Ergebnis war überraschend, da _bittest() um mehrere msec langsamer
ist als die normale Bitprüfung in C.

Wie kann das sein?
Der Compiler sollte doch _bittest entsprechend optimieren können.


Hier der Programmausschnitt:

int nbit,i;
long num = 2147483648;


Code Intrinsic:
---------------------------------------
...
for(i = 0; i < 80000; i++)
  for(nbit = 0; nbit < 32; nbit++)
 {
   test[nbit] = _bittest(&num,nbit);
 }
...
---------------------------------------

normales c:
---------------------------------------
...
for(a = 0; a < 80000; a++)
  for(nbit = 0; nbit < 32; nbit++)
  {
    if( num & (1<<nbit))
      test[nbit]=1;
    else
      test[nbit]=0;
  }
...
---------------------------------------
Umgebung:
Win Vista,Dual Core,Visual Studio 2010

Danke.

Gruß
Christian

[Robert L. (lrlr)]

asm code schon angeschaut?

[Christian (Gast)]

Habe den Assemblercode noch nicht angesehen.
Wollte erstmal sehen ob mein Compiler _bittest() entsprechend optimieren 
kann und ob das effizienter ist als normales Bit prüfen.

Christian

[Peter II (Gast)]

ist überhaupt die optimierung eingeschaltet? Dann müsste er doch sogar 
die äußere schleife komplett entfernen, weil sie keinen sinn macht.

[Christian (Gast)]

Die Optimierung ist eingeschaltet(Geschwindigkeit maximieren /O2).

Die äußere Schleife dient nur dazu das Bit- testen x-mal zu wiederholen.
Ist die äußere Schleife durchlaufen, kann ich dann in milli- Sekunden
messen(GetLocalTime() kann nicht besser auflösen als 1ms).


Christian

[Kan a. (Firma: Basta) (kanasta)]

Es heisst "-O2".

[Christian (Gast)]

Nein. Richtig ist /O2.

Siehe: [[http://msdn.microsoft.com/en-us/library/8f8h5cxt.aspx]]

Christian

[Kan a. (Firma: Basta) (kanasta)]

Ok, Standard ist gcc, deshalb habe ich es mal angenommen, weil du keinen 
Comnpiler nennst. Was ist mit dem Assembler-Code?

[Peter II (Gast)]

Christian schrieb:
> Die äußere Schleife dient nur dazu das Bit- testen x-mal zu wiederholen.

das ist schon klar, aber der optimierer kann sie entfernen weil sie für 
ihn kein sinn macht und der egebniss am ende das gleiche ist.

[Peter II (Gast)]

liese mal ob du nicht noch andere schalter setzen musst

http://msdn.microsoft.com/en-us/library/26td21ds%28v=vs.80%29.aspx

[Christian (Gast)]

Hier mal den Assemblercode für Bitset():

test[nbit] = _bittest(&num,nbit);
01201072  lea         ecx,[ebp-7Ch]
01201075  bt          dword ptr [ecx],eax
01201078  inc         eax
01201079  cmp         eax,20h
0120107C  jl          wmain+72h (1201072h)

Sieht nicht unbedingt optimiert aus.

Christian

[Christian (Gast)]

Der Schalter für /Oi (Generate Intrinsic Functions) ist auch gesetzt.

Trotzdem produziert _bittest() langsameren Programmcode!

Christian

[Fabian O. (xfr)]

Hast Du die Variable num als volatile deklariert? Wenn nicht, wird wie 
gesagt wahrscheinlich die äußere Schleife wegoptimiert.

[Robert L. (lrlr)]

>wegoptimiert

wäre auch mein erster verdacht gewesen, aber wie soll der compiler das 
erkennen?

[Christian (Gast)]

>Hast Du die Variable num als volatile deklariert?

Hab ich. Keine Veränderung.

Christian

[Kan a. (Firma: Basta) (kanasta)]

Christian schrieb:
> Hier mal den Assemblercode für Bitset():
>
> test[nbit] = _bittest(&num,nbit);
> 01201072  lea         ecx,[ebp-7Ch]
> 01201075  bt          dword ptr [ecx],eax
> 01201078  inc         eax
> 01201079  cmp         eax,20h
> 0120107C  jl          wmain+72h (1201072h)
>
> Sieht nicht unbedingt optimiert aus.
>
> Christian

Und wie sieht der Assembler-Code zur C-Bittest-Funktion aus? Es wäre 
nicht schlecht, beides zu posten, wenn es um den Vergleich geht...

[Robert L. (lrlr)]

vermutlich lassen sich bei der Version mit shl und cmp
die Sprünge besser vorhersehen und/oder einige Instruktionen parallel 
bearbeiten
also (auch wenn es mehr sind)  schneller abarbeiten..



ps

---------------------------------------
...
for(a = 0; a < 80000; a++)
  for(nbit = 0; nbit < 32; nbit++)
  {
    if( _bittest(&num,nbit))
      test[nbit]=1;
    else
      test[nbit]=0;


hast das schon mal probiert? nur so interessehalber (nicht weil es 
sinnvoll wäre)

[Christian (Gast)]

Hier mal das Assembly vom C Code:

00E91030  test        ecx,80000000h
00E91036  setne       dl
00E91039  mov         byte ptr [ebp+eax-24h],dl
00E9103D  inc         eax
00E9103E  rol         ecx,1
00E91040  cmp         eax,20h
00E91043  jl          wmain+30h (0E91030h)

Warum dieser asm Code schneller ist als der asm Code von _bittest()
erschließt sich mir leider nicht.

Christian

[Robert L. (lrlr)]

>erschließt sich mir leider nicht.

weil dort überhaupt kein "bittest" mehr drinnen ist

der ganze teil wurde wegoptimiert (weil test[] nach der schleife NIE 
verwende wird...

[Kan a. (Firma: Basta) (kanasta)]

Ich erkenne da schon noch einen Bittest, mit test ecx und rol ecx.
Die lea-Instruktion im ersten asm-Auszug benötigt viel Zeit.

[Christian (Gast)]

>der ganze teil wurde wegoptimiert

Habe mal das array test[] auf volatile und auch nach der Schleife mal 
mit Dummy Werten beschrieben.Der Compiler sollte nichts mehr 
wegoptimieren. Das Ergebnis ist dasselbe.

_bittest() benötigt im Schnitt 10ms, ein normaler Bittest(ohne 
_bittets()) benötigt im Schnitt 5ms.

Also doppelt so schnell wenn man keine Intrinsic einsetzt.

Christian

[Kan a. (Firma: Basta) (kanasta)]

Das ganze hängt stark von Prozessortyp, Cache und Speichermodell ab.
Grundsätzlich steht intrinsic function für eine in eine Funktion 
eingebettete Operation. Danach sieht der Assembler-Auszug nicht aus. 
Christian, hast du beim intrinsic-Asm-Code evtl. zu viel weggeschnitten?

Zwar enthält die Intrinsic-Version in der Schleife weniger 
Instruktionen, trotzdem benötigt lea viel Zeit, und du hast einen 
Datenkonflikt in eax, was zu einem Pipeline-Stall führt, was zusätzlich 
Zeit kostet.

Christian schrieb:
> Wollte mal testen inwieweit intrinsische Funktionen für
> Geschwindigkeit-optimierte Programme einsetzbar sind.

Fazit: Die Anwendung von intrinsischen Funktionen macht nur in 
Spezialfällen Sinn. Aus meiner Sicht ist das ganze Experiment stark 
sinnfrei.

[Christian (Gast)]

>Christian, hast du beim intrinsic-Asm-Code evtl. zu viel weggeschnitten?

Hab ich.Aber nur denn Teil mit den Schleifen.

>und du hast einen Datenkonflikt in eax

Woran erkennst du das?

> Aus meiner Sicht ist das ganze Experiment stark sinnfrei.

Wollte nur mal wissen welche Auswirkungen _bittest() auf mein Programm 
hat hinsichtlich Geschwindigkeit.Wenn der Compiler so leistungsfähige 
Optionen bietet,warum dann nicht verwenden.Daher der Test.Nur das 
Ergebnis ist ernüchternd.

Christian

[Robert L. (lrlr)]

>Ich erkenne da schon noch einen Bittest, mit test ecx

das ist die Schleife (8000 in oct ??)

[Kan a. (Firma: Basta) (kanasta)]

Per Definition hat Intrinsic nichts mit leistungsfähig zu tun, eher
im Gegenteil.

Was Datenkonflikte sind lernt man in Rechnerarchitektur, da findest du 
bestimmt auch zahlreiche Infos im Internet. Im C-Code erkenne ich zw. 
setne und mov einen RAW(Read after Write)-Konflikt mit dl. In der 
intrinsischen Variante finde ich zw. lea und bt, bzgl. ecx und zw. inc 
und cmp bzgl. eax einen Konflikt.

[Kan a. (Firma: Basta) (kanasta)]

Christian schrieb:

> 00E91030  test        ecx,80000000h
> 00E91036  setne       dl
> 00E91039  mov         byte ptr [ebp+eax-24h],dl
> 00E9103D  inc         eax
> 00E9103E  rol         ecx,1
> 00E91040  cmp         eax,20h
> 00E91043  jl          wmain+30h (0E91030h)

für Robert:

test ecx, 8... testet das höchste Bit in ecx
Das Ergebnis landet in dl, und dann im Speicher (00E91036, 00E91039)
eax ist die Schleifen-Variable und wird hochgezählt
ecx enthält das zu prüfende Wort und wird um eine Stelle nach links 
geshiftet. eax wird mit 32 verglichen, danach kommt die Schleife...
P.S. Kein Asm-Dump enthält oct...

[Robert L. (lrlr)]

(hab ich ja ziemlich Blödsinn gepostet..)

unglaublich dass das so optimiert wird..

[Christian (Gast)]

>Im C-Code erkenne ich zw. setne und mov einen RAW(Read after Write)-Konflikt mit 
dl.

Sorry, aber auch wenn ich die Vorlesung Rechner- Architektur nicht 
besucht
habe, bin ich mir sicher, das man aus den asm Ausschnitten oben, keine
Konflikte ableiten kann.

Weil 1.
Assembler Code aus rein sequenziellen Ausführungseinheiten besteht.
Der RAW-Konflikt macht sich aber erst in der massiven parallel 
ausgeführten Pipeline bemerkbar. Ohne Kenntnisse der verwendeten 
CPU/Pipeline Einheit und des eingesetzten Compilers solch eine Aussage 
zutreffen halte ich für gewagt.

2.
Es sind keine Umordnungsbefehle oder Verzögerungselemente (_NOP) im asm 
Code.

3.
Prozessoren heutzutage Datenkonflikte in Hardware lösen(Data Forwarding 
Unit).

Gruß
Christian

[Christian (Gast)]

>Per Definition hat Intrinsic nichts mit leistungsfähig zu tun

Meinte damit die Leistungsfähigkeit eines Compilers, bestimmte 
Funktionen optimierend auszuführen.

Christian

[Arc N. (arc)]

Christian schrieb:
>>Per Definition hat Intrinsic nichts mit leistungsfähig zu tun
>
> Meinte damit die Leistungsfähigkeit eines Compilers, bestimmte
> Funktionen optimierend auszuführen.
>
> Christian

Auch die optimierte Variante ist langsamer:

int bitTestStandard(const long* array, long bitNumber, size_t len) {
    int numberOfSetBits = 0;
    for (size_t i = 0; i < len; i++) {
        numberOfSetBits += (*array & (1 << bitNumber)) ? 1 : 0;
        array++;
    }
    return numberOfSetBits;
}

int bitTestIntrinsic(const long* array, long bitNumber, size_t len) { 
    int numberOfSetBits = 0;
    for (size_t i = 0; i < len; i++) {
        numberOfSetBits += _bittest(array, bitNumber) ? 1 : 0;
        array++;
    }
    return numberOfSetBits;
}

const int testArraySize = 123456789;
const long testArrayBitNumber = 13;
long *testArray;

int _tmain(int argc, _TCHAR* argv[]) {
    testArray = new long[testArraySize];

    for (size_t i = 0; i < testArraySize; i++) {
        testArray[i] = i;
    }  

    auto tickCountIntrinsic = GetTickCount64();
    auto resultIntrinsic = bitTestIntrinsic(testArray, testArrayBitNumber, testArraySize);
    tickCountIntrinsic = GetTickCount64() - tickCountIntrinsic;

    auto tickCountStandard = GetTickCount64();
    auto resultStandard = bitTestStandard(testArray, testArrayBitNumber, testArraySize);
    tickCountStandard = GetTickCount64() - tickCountStandard;

    printf("Intrinsic: %lld, %d, Standard: %lld, %d\n",  tickCountIntrinsic, resultIntrinsic, tickCountStandard, resultStandard);

    return 0;
}

VC2012
/Ox (full optimization)
/Ob2 (inline any suitable)
/Oi (enable intrinsics)
/Ot (favor fast code)
/Oy (omit frame pointers)
/GL (whole program optimization)
/arch:AVX

  testArray = new long[testArraySize];
00C8100D  push        1D6F3454h  
00C81012  call        dword ptr ds:[0C82094h]  
00C81018  movdqa      xmm1,xmmword ptr ds:[0C82130h]  
00C81020  add         esp,4  
00C81023  mov         dword ptr ds:[00C83368h],eax  

  for (size_t i = 0; i < testArraySize; i++) {
00C81028  xor         ecx,ecx  
00C8102A  mov         edx,eax  
00C8102C  lea         esp,[esp]  
00C81030  movd        xmm0,ecx  
00C81034  pshufd      xmm0,xmm0,0  
00C81039  paddd       xmm0,xmm1  
00C8103D  add         ecx,4  
    testArray[i] = i;
00C81040  movdqu      xmmword ptr [edx],xmm0  
00C81044  lea         edx,[edx+10h]  
00C81047  cmp         ecx,75BCD14h  
00C8104D  jb          wmain+30h (0C81030h)  

  for (size_t i = 0; i < testArraySize; i++) {
00C8104F  cmp         ecx,75BCD15h  
00C81055  jae         wmain+6Ch (0C8106Ch)  
00C81057  jmp         wmain+60h (0C81060h)  
00C81059  lea         esp,[esp]  
    testArray[i] = i;
00C81060  mov         dword ptr [eax+ecx*4],ecx  
00C81063  inc         ecx  
00C81064  cmp         ecx,75BCD15h  
00C8106A  jb          wmain+60h (0C81060h)  
  }  

  auto tickCountIntrinsic = GetTickCount64();
00C8106C  mov         ebx,dword ptr ds:[0C82000h]  
00C81072  call        ebx  
  auto resultIntrinsic = bitTestIntrinsic(testArray, testArrayBitNumber, testArraySize);
00C81074  mov         ecx,dword ptr ds:[0C83368h]  
  auto resultIntrinsic = bitTestIntrinsic(testArray, testArrayBitNumber, testArraySize);
00C8107A  mov         ebp,eax  
00C8107C  mov         dword ptr [esp+10h],edx  
00C81080  xor         edi,edi  
  }  

  auto tickCountIntrinsic = GetTickCount64();
00C81082  mov         esi,75BCD15h  
00C81087  jmp         wmain+90h (0C81090h)  
00C81089  lea         esp,[esp]  
  auto resultIntrinsic = bitTestIntrinsic(testArray, testArrayBitNumber, testArraySize);
00C81090  bt          dword ptr [ecx],0Dh  
00C81094  mov         eax,0  
00C81099  setb        al  
00C8109C  lea         ecx,[ecx+4]  
00C8109F  add         edi,eax  
00C810A1  dec         esi  
00C810A2  jne         wmain+90h (0C81090h)  
  tickCountIntrinsic = GetTickCount64() - tickCountIntrinsic;
00C810A4  call        ebx  
00C810A6  sub         eax,ebp  
00C810A8  mov         ecx,edx  
00C810AA  sbb         ecx,dword ptr [esp+10h]  
00C810AE  mov         dword ptr [esp+1Ch],eax  
00C810B2  mov         dword ptr [esp+18h],ecx  

  auto tickCountStandard = GetTickCount64();
00C810B6  call        ebx  
00C810B8  mov         ecx,dword ptr ds:[0C83368h]  
00C810BE  mov         dword ptr [esp+14h],edx  
00C810C2  xor         edx,edx  
00C810C4  xor         ebx,ebx  
00C810C6  mov         dword ptr [esp+10h],eax  
00C810CA  add         ecx,8  
00C810CD  mov         ebp,273EF07h  
  auto resultStandard = bitTestStandard(testArray, testArrayBitNumber, testArraySize);
00C810D2  mov         eax,dword ptr [ecx-8]  
00C810D5  shr         eax,0Dh  
  auto resultStandard = bitTestStandard(testArray, testArrayBitNumber, testArraySize);
00C810D8  and         eax,1  
00C810DB  add         esi,eax  
00C810DD  mov         eax,dword ptr [ecx-4]  
00C810E0  shr         eax,0Dh  
00C810E3  and         eax,1  
00C810E6  add         ebx,eax  
00C810E8  mov         eax,dword ptr [ecx]  
00C810EA  shr         eax,0Dh  
00C810ED  and         eax,1  
00C810F0  add         edx,eax  
00C810F2  lea         ecx,[ecx+0Ch]  
00C810F5  dec         ebp  
00C810F6  jne         wmain+0D2h (0C810D2h)  
  tickCountStandard = GetTickCount64() - tickCountStandard;
00C810F8  lea         eax,[edx+ebx]  
00C810FB  add         esi,eax  
00C810FD  call        dword ptr ds:[0C82000h]  
00C81103  sub         eax,dword ptr [esp+10h]

[(prx) A. K. (prx)]

_bittest steht nicht für die schnellstmögliche Operation, Bits in Worten 
zu testen, sondern direkt für den Befehl BT. Und der ist bei variabler 
Bitnummer auf Speicher ausgesprochen komplex, weil nicht auf 0..31 oder 
0..63 begrenzt.

Die Bitnummer wird vom Prozessor per unoptimiertem Microcode erst in 
eine Nummer innerhalb des Wortes und einen Offset auf die Adresse 
umgerechnet. Folglich ist diese Variante von BT ausgesprochen langsam, 
bei leidlich aktuellen Intels beispielsweise ~10 Takte.

In realem Code wird man nicht selten feststellen, dass ein Compiler 
solchen Code besser optimiert, als die Hardware ihn per Microcode 
ausführt. Solche Effekte führten mit zur Entwicklung von RISC 
Architekturen.

[Yalu X. (yalu) (Moderator)]

Das meinen die GCC-Entwickler dazu:

;; %%% bts, btr, btc, bt.
;; In general these instructions are *slow* when applied to memory,
;; since they enforce atomic operation.  When applied to registers,
;; it depends on the cpu implementation.  They're never faster than
;; the corresponding and/ior/xor operations, so with 32-bit there's
;; no point.  But in 64-bit, we can't hold the relevant immediates
;; within the instruction itself, so operating on bits in the high
;; 32-bits of a register becomes easier.
;;
;; These are slow on Nocona, but fast on Athlon64.  We do require the use
;; of btrq and btcq for corner cases of post-reload expansion of absdf and
;; negdf respectively, so they can never be disabled entirely.

(aus ggg-4.7.2/gcc/config/i386/i386.md)