Optimierung vom Conditional operator mit Typ 'int'

Konrad Rudolph

Hallo,

ich habe einen Bitvektor, in welchen ich links eine 1 reinschiebe. Wenn der Bitvektor in ein Prozessorwort passt, sieht das ganze so aus:

word_t bitvec = 0xdeadbeef;
bitvec <<= 1;
bitvec |= 1;

Leider ist es in meinem Fall *nicht* ein einziges Wort. Da die Länge erst zur Laufzeit bekannt ist, fällt auch 'std::bitset' flach. Also verwende ich einen Vektor, der aus mehreren Prozessorwörtern besteht.

Folgender Code funktioniert:

vector<word_t> bitvec; // ... wird initialisiert.

word_t const carry_position = 1 << (BitsPerValue<word_t>::Value - 1); // most significant bit

word_t carry = 1;

for (int i = 0; i < bitvec.size(); ++i) {
    word_t new_carry = (bitvec[i] & carry_position) != 0 ? 1 : 0;
    bitvec[i] <<= 1;
    bitvec[i] |= carry;
    carry = new_carry;
}

Das funktioniert auch, allerdings befindet sich der Code in einem geschwindigkeitskritischen Abschnitt, d.h. da muss wirklich das letzte Quentchen an Potential rausgepresst werden. Unter der Annahme, dass 'true' intern als 1 repräsentiert wird, könnte man die Berechnung von 'new_carry' auch abkürzen:

word_t new_carry = (bitvec[i] & carry_position) != 0;

Allerdings wird hier eine implizite Konversion vorgenommen und das passt mir gar nicht. Ich würde viel lieber den ternären Operator benutzen. Bekommt ein Compiler es gebacken, das zu optimieren? Also, dass bei der Verwendung des ternären Operators in diesem Fall derselbe Maschinencode herauskommt wie bei der impliziten Konvertierung (wohl kaum), bzw. dass ein gleichschneller Code erzeugt wird? Oder ist die implizite Konvertierung grundsätzlich schneller und man kann da nichts ändern? Dann müsste ich in den sauren Apfel beißen.

hustbaer

Versuch mal die Version:

vector<word_t> bitvec; // ... wird initialisiert.

word_t const msb_pos = BitsPerValue<word_t>::Value - 1;
word_t carry = 1;

for (int i = 0; i < bitvec.size(); ++i) {
    word_t new_carry = (bitvec[i] >> msb_pos) & 1;
    bitvec[i] <<= 1;
    bitvec[i] |= carry;
    carry = new_carry;
}

Die müsste eigentlich schneller sein... es sei denn der Compiler kann wirklich sehr sehr gut optimieren.
Den "?" Operator sollte ein guter Compiler wegoptimieren können, allerdings könnte es eben was bringen das "(a & b) != 0" durch ein einfaches "shift" zu ersetzen wie ich das oben gemacht habe.

Die nächste Änderung die evtl. was bringen könnte wäre dann:

//...
wort_t* p = &(bitvec[0]);
wort_t* end = p + bitvec.size();
for (; p != end; ++p) {
    word_t new_carry = ((*p) >> msb_pos) & 1;
    (*p) <<= 1;
    (*p) |= carry;
    carry = new_carry;
}

Kommt aber auf die Implementierung von std::vector drauf an und wieder darauf wie gut der Compiler optimiert.

Konrad Rudolph

hustbaer schrieb:

word_t new_carry = (bitvec[i] >> msb_pos) & 1;

Mensch, wieso bin ich darauf nicht gekommen? Danke.

wort_t* p = &(bitvec[0]);
wort_t* end = p + bitvec.size();

Pff. Also wenn, dann bitte mit Iteratoren, nicht mit Zeigern. Was sind Zeiger?

Aber das kommt bei mir sowieso nicht infrage, der Code verwendet in Wahrheit keinen Vektor sondern einen Container einer anderen Bibliothek, und dort verwende ich selbstverständlich Iteratoren.

Gast++

Konrad Rudolph schrieb:

hustbaer schrieb:
word_t new_carry = (bitvec[i] >> msb_pos) & 1;
Mensch, wieso bin ich darauf nicht gekommen? Danke.

Wieso ist es effizienter jedesmal in der Schelife zu shiften statt einmal davor ?

btw : Willst Du nicht Assembler einsetzen?

Grüsse

*this

ronny

viele stdlibs können vector<bool> mit der speicherspaaroption

Konrad Rudolph

Gast++ schrieb:

Wieso ist es effizienter jedesmal in der Schelife zu shiften statt einmal davor ?

Weil es wahrscheinlich schneller ist, einmal pro Schleife zu shiften statt einmal pro Schleife einen Vergleich und einen Sprung auszuführen. Aber das ist ja unabhängig vom Compiler und das werde ich dementsprechend einfach auf Assembler-Ebene testen.

btw : Willst Du nicht Assembler einsetzen?

Ich kann mich gerade noch halten, Danke.

Mal im Ernst, ich sähe keinen Vorteil von Assembler. Ich verlasse mich lieber auf die Fähigkeit des Compilers.

[quote="Konrad Rudolph"]

Gast++ schrieb:

btw : Willst Du nicht Assembler einsetzen?

Ich kann mich gerade noch halten, Danke.

Mal im Ernst, ich sähe keinen Vorteil von Assembler. Ich verlasse mich lieber auf die Fähigkeit des Compilers.

So reden Leute die Assembler nicht können.

Bellmondo schrieb:

Gast++ schrieb:

Konrad Rudolph schrieb:

btw : Willst Du nicht Assembler einsetzen?

Ich kann mich gerade noch halten, Danke.

Mal im Ernst, ich sähe keinen Vorteil von Assembler. Ich verlasse mich lieber auf die Fähigkeit des Compilers.

So reden Leute die Assembler nicht können.

So reden Leute, die glauben Assembler zu können, alles das sie in die Finger bekommen wegoptimieren und dabei lahmeren code produzieren als jeder Steinzeitcompiler.

kenner_der_dummköpfe schrieb:

Bellmondo schrieb:

Gast++ schrieb:

Konrad Rudolph schrieb:

btw : Willst Du nicht Assembler einsetzen?

Ich kann mich gerade noch halten, Danke.

Mal im Ernst, ich sähe keinen Vorteil von Assembler. Ich verlasse mich lieber auf die Fähigkeit des Compilers.

So reden Leute die Assembler nicht können.

So reden Leute, die glauben Assembler zu können, alles das sie in die Finger bekommen wegoptimieren und dabei lahmeren code produzieren als jeder Steinzeitcompiler.

So reden Leute, welche Dummköpfe sind.

Gast++

Na ja, also pauschale Statements über Assembler produzieren wohl zunächst mal gar keinen Code...

Hier könnte man sich mal halt überlegen die word_t jeweils durch das CF zu rcl'en
und solange mit bitset.size in ecx zu loopen solange CF gesetzt ist. bitvec.operator[]() kann man dann aus der Schleife anspringen nachdem man size-ecx pushed hat.

Das Assembilat zu den C++-Bitops sieht zumindest seltsam aus.

Grüsse

Gast++

Konrad Rudolph

Hallo,

um mal von der ganzen Polemik wegzukommen: Ich habe von x86-Assembler keine Ahnung, ich habe mich nie damit beschäftigt. Ich kenne MIX (Knuths Pseudoassembler) und ich kann selbstverständlich auch einfache Kompilate entziffern.

Dessen ungeachtet würde ich nie eine Bibliothek in Assembler schreiben (mal davn abgesehen, dass die Entscheidung hier nicht bei mir liegt) und die Bibliothek wird nunmal in C++ geschrieben. Das schließt Inline-Assembler einfach aus. Das ganze soll schließlich auch portabel sein (und *nicht* nur auf Intel-kompatiblen Prozessoren laufen).

Davon abgesehen sehe ich *wirklich* keinen Vorteil darin, hier Assembler zu verwenden, denn ich vertraue dem Compiler eigentlich, ebenso guten Code zu produzieren, wie ich dies kann. Ich lasse mich aber prinzipiell gerne eines besseren belehren.

Gast++ schrieb:

Das Assembilat zu den C++-Bitops sieht zumindest seltsam aus.

Inwiefern?

Simon2

Bellmondo schrieb:

...So reden Leute die Assembler nicht können.

So reden Leute, die sich lieber mit Pauschalisierungen als konstruktiven Beiträgen profilieren wollen.
Seltsam, ich habe es noch nie im Internet erlebt, dass das Argument "Du überhaupt keine Ahnung" irgendeine Diskussion weitergebracht hat - aber scheinbar machen Andere da andere Erfahrungen.

Gruß,

Simon2.

Gast++

Konrad Rudolph schrieb:

Gast++ schrieb:

Das Assembilat zu den C++-Bitops sieht zumindest seltsam aus.

Inwiefern?

Hab auf Deinen OP Code mal VC Express 2005 losgelassen

/Ob2 /Ot /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Yu"stdafx.h" /Fp"Release\foo.pch" /Fo"Release\" /Fd"Release\vc80.pdb" /W3 /nologo /c /Wp64 /Zi /TP /errorReport:prompt

und zwar mit einem

typdef unsigned int word_t

for (int i = 0; i < bitvec.size(); ++i) {
004011CE  xor         esi,esi 
@start:
004011D0  mov         eax,dword ptr [ebp-28h] ; &(bitset[0]) = _MyFirst
004011D3  cmp         eax,edi                 ; == edi ( = 0 )
004011D5  je          main+11Ch (40122Ch)     ; if goto @end
004011D7  mov         ecx,edx                 ; else ecx = edx = bitvec._MyLast
004011D9  sub         ecx,eax                 ; -= _MyFirst
004011DB  sar         ecx,2                   ; /= 4
004011DE  cmp         esi,ecx                 ; &(bitset[esi = i]) < _MyLast    
004011E0  jae         main+11Ch (40122Ch)     ; @end
    81: //		BREAK;
    82: 		word_t new_carry = (bitvec[i] & carry_position) != 0 ? 1 : 0;
004011E2  mov         edi,dword ptr [eax+esi*4] 
004011E5  shr         edi,1Fh 
    83: 		bitvec[i] <<= 1;
004011E8  test        eax,eax 
004011EA  je          main+0E5h (4011F5h) 
004011EC  sub         edx,eax 
004011EE  sar         edx,2 
004011F1  cmp         esi,edx 
004011F3  jb          main+0EEh (4011FEh) 
@Handler_1
004011F5  call        dword ptr [__imp___invalid_parameter_noinfo (4020B8h)] 
004011FB  mov         eax,dword ptr [ebp-28h] 
@ok_1:
004011FE  shl         dword ptr [eax+esi*4],1 ; => HERE IT IS !!! <=
    84: 		bitvec[i] |= carry;
00401201  mov         eax,dword ptr [ebp-28h] 
00401204  test        eax,eax 
00401206  je          main+104h (401214h) 
00401208  mov         ecx,dword ptr [ebp-24h] ; 
0040120B  sub         ecx,eax 
0040120D  sar         ecx,2   
00401210  cmp         esi,ecx 
00401212  jb          main+10Dh (40121Dh)     ; ok_2
@Handler_2
00401214  call        dword ptr [__imp___invalid_parameter_noinfo (4020B8h)] 
0040121A  mov         eax,dword ptr [ebp-28h] 
@ok_2:
0040121D  or          dword ptr [eax+esi*4],ebx ; => HERE IT IS !!! <=
00401220  mov         edx,dword ptr [ebp-24h] 
    85: 		carry = new_carry; 
00401223  mov         ebx,edi ; 
00401225  add         esi,1 
00401228  xor         edi,edi 
0040122A  jmp         main+0C0h (4011D0h) ; @start
@end:
0040122C

Also :

Das ist eigentlich doppelte Buchführung:

- esi hält i vor.
- Der Abbruch wird aber getestet über
( ecx = _MyLast ) - ( eax = _MyFirst ) / 4 > esi
also über den aktuellen Zeiger !
- So werden für die Tests die Register verbraucht
- Dann rechnet er das dreimal pro Schleife aus - bringt aber nichts, threadsicher wird's dadurch auch nicht.

Grüsse

Gast++

Konrad Rudolph

Gast++ schrieb:

Konrad Rudolph schrieb:

Gast++ schrieb:

Das Assembilat zu den C++-Bitops sieht zumindest seltsam aus.

Inwiefern?

[…]

Also :

Das ist eigentlich doppelte Buchführung:

- esi hält i vor.
- Der Abbruch wird aber getestet über
( ecx = _MyLast ) - ( eax = _MyFirst ) / 4 > esi
also über den aktuellen Zeiger !
- So werden für die Tests die Register verbraucht
- Dann rechnet er das dreimal pro Schleife aus - bringt aber nichts, threadsicher wird's dadurch auch nicht.

Das liegt aber nicht an den Bitoperationen sondern aus dem Zugriff auf den Vektor. Schau Dir denselben Code mal mit Zeigern statt Indexzugriff an. Ach so, ich habe natürlich mit /O2 kompiliert, und nicht mit der Express Edition. Was ist denn /Ot?

camper

/Ox und _SECURE_SCL=0
vorher ist eine Effizienzdiskussion recht sinnlos

Im Übrigen glaube ich sowieso, dass das Optimierung an der falschen Stelle ist. Stichwort lazy evaluation

Konrad Rudolph

camper schrieb:

/Ox und _SECURE_SCL=0
vorher ist eine Effizienzdiskussion recht sinnlos

Irgendwie richtig.

Im Übrigen glaube ich sowieso, dass das Optimierung an der falschen Stelle ist. Stichwort lazy evaluation

Was hat Lazy evaluation hiermit zu tun?

camper

Im Übrigen glaube ich sowieso, dass das Optimierung an der falschen Stelle ist. Stichwort lazy evaluation

Was hat Lazy evaluation hiermit zu tun?

Bei einer Operation dieser Komplexität wird es regelmäßig nur kritisch, wenn du sie oft ausführen musst. Eine Einfügeoperation in dieser Form hat ja nur dann Sinn, wenn du anschließend auch regelmäßig auf den Vektorzugreifen musst und es auf diese Organisation der Daten als Vektor ankommt. Da du nichts dazu gesagt hast, kann ich nur spekulieren. Im Allgemeinen würde ich erwarten, dass nicht nach jeder einzelnen Einfügeoperation auf den vektor anderweitig zugegriffen wird. Andererseits ist das Einfügen von x bits (nahezu) genauso schnell wie das Einfügen von einem Einzigen. Es könnte also Sinn machen, das tatsächliche Einfügen zu verzögern, bis auf den Vektor durch op[],begin,end usw. zugegriffen wird. Vielleicht ist auch weder die Organisation als Array notwendig noch müssen die Daten mit dem 0. bit beginnen. Dann bieten sich deque oder ein von hinten gefüllter vector an. Und wenn es ein array, das beim 0.bit anfängt, sein muss, könnte man auch hier speicher für geschwindigkeit tauschen (indem wir x(=anzahl der bits in word_t) vectoren haben, deren beginn jeweils um 1 bit verschoben ist, und die wir von hinten füllen). Dann benötigte das Einfügen wieder eine (amortisiert) konstante Zeit.

Ach ja: Die Fragestellung an sich legt die Assoziation mit Assembler nahe - denn letzten Endes argumentierst du ja mit einer bestimmten von dir vermuteten Art der Implementation deines Codes. Und das ist eigentlich sinnlos

Konrad Rudolph

Hi Camper,

der Code wird als Teil von Shift-And (bzw. einer Erweiterung davon) verwendet, um reguläre Muster in großen Strings zu suchen. Der Algorithmus (und insbesondere das Verwenden von Bitvektoren) ist dementsprechend schon der Richtige und da kann man nicht viel drehen.

camper schrieb:

Ach ja: Die Fragestellung an sich legt die Assoziation mit Assembler nahe - denn letzten Endes argumentierst du ja mit einer bestimmten von dir vermuteten Art der Implementation deines Codes. Und das ist eigentlich sinnlos

Na ja ... so ist es im wahren Leben jenseits der akademischen Mauern eben. Der Code wird in der Bioinformatik verwendet, theoretisch auf mehrerne Gigabytes an Daten. Da bin ich schon ein wenig darauf angewiesen, dass der Code *tatsächlich* der schnellste ist und nicht nur in der grauen Theorie.

Gast++

Konrad Rudolph schrieb:

camper schrieb:

/Ox und _SECURE_SCL=0
vorher ist eine Effizienzdiskussion recht sinnlos

Irgendwie richtig.

@Konrad:

Kompilierst Du dann das Snippet mal mit Deinen gewünschten Optionen und postest das Listing ?

Btw /Ox meint "Size und Speed".
Ich denke es ist besser nur nach einer Größe zu optimieren.

_SECURE_SCL=0 - Na Ja, EINMAL prüfen darf er meinetwegen gerne; soll er auch.
Nur dreimal macht imo wenig Sinn wenn's dadurch nicht threadsicher wird.

Wie das mit foo = &(bitset[i]) aussieht interessiert mich auch noch mal.

Btw :

register

?

@All

Solch ein Listing kann man recht einfach erzeugen wenn man einen Breakpoint in den Code setzt. Respektive

__asm { int 3 }

, aber hinterher wieder raus damit!

Dann das Programm starten; wenn der Breakpoint erreicht wird mit
"<ALT>+8" das Disassembilierungsfenter anzeigen lassen.

Grüsse

Gast++

camper

Die letzte Option, die genannt hatte, steht immer offen. Mit was für Größenordnungen hinsichtlich der Größe des vectors ist denn zu rechnen?

Gast++

EDIT
War bödsinn
/EDIT