3. Optimierung vom Conditional operator mit Typ 'int'

Optimierung vom Conditional operator mit Typ 'int'

  • G

    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

    0
  • R

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

    0
  • K

    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.

    0
  • ?

    [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. 👎

    0
  • ?

    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.

    0
  • ?

    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.

    0
  • G

    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++

    0
  • K

    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?

    0
  • S

    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.

    0
  • G

    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++

    0
  • K

    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?

    0
  • C
    Mod

    /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

    0
  • K

    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?

    0
  • C
    Mod

    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 😉

    0
  • K

    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.

    0
  • G

    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++

    0
  • C
    Mod

    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?

    0
  • G

    EDIT
    War bödsinn
    /EDIT

    0
  • K

    Gast++ schrieb:

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

    Na ja ... Camper hat ja schon ganz richtig darauf hingewiesen, dass das nicht sinnvoll ist. Aber bei mir kam dann folgendes raus:

    ;; 32   :     for (word_t* i = &bitvec[0]; i < &bitvec[0] + bitvec.size(); ++i) {

	mov	eax, DWORD PTR _bitvec$[esp+72]
	cmp	eax, ebx
	mov	edi, 1
	je	SHORT $LN168@main
	mov	edx, ecx
	sub	edx, eax
	sar	edx, 2
	jne	SHORT $LN134@main
$LN168@main:
	call	ebp
	mov	ecx, DWORD PTR _bitvec$[esp+76]
	mov	eax, DWORD PTR _bitvec$[esp+72]
$LN134@main:
	mov	esi, eax
$LL3@main:
	cmp	eax, ebx
	je	SHORT $LN169@main
	mov	edx, ecx
	sub	edx, eax
	sar	edx, 2
	jne	SHORT $LN141@main
$LN169@main:
	call	ebp
	mov	ecx, DWORD PTR _bitvec$[esp+76]
	mov	eax, DWORD PTR _bitvec$[esp+72]
$LN141@main:
	cmp	eax, ebx
	jne	SHORT $LN150@main
	xor	ecx, ecx
	jmp	SHORT $LN151@main
$LN150@main:
	sub	ecx, eax
	sar	ecx, 2
$LN151@main:
	lea	ecx, DWORD PTR [eax+ecx*4]
	cmp	esi, ecx
	jae	SHORT $LN1@main

; 33   :         word_t new_carry = (*i & carry_position);

	mov	ecx, DWORD PTR [esi]
	mov	eax, ecx

; 34   :         *i <<= 1;

	lea	edx, DWORD PTR [ecx+ecx]
	and	eax, -2147483648			; 80000000H

; 35   :         *i |= carry;

	or	edx, edi
	mov	DWORD PTR [esi], edx
	mov	ecx, DWORD PTR _bitvec$[esp+76]

; 36   :         carry = new_carry;

	mov	edi, eax
	mov	eax, DWORD PTR _bitvec$[esp+72]
	add	esi, 4
	jmp	SHORT $LL3@main
$LN1@main:

    Btw :

    register

    ?

    Hm. Der Compiler sollte eigentlich selbst merken, welche Variablen er in Register packt. Das klappt doch auch eigentlich ganz gut.

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

    Warum so "aufwendig"? Es reicht doch, dem Compiler zu sagen, dass er ein Assembler-Listing ausspucken soll.

    camper schrieb:

    Mit was für Größenordnungen hinsichtlich der Größe des vectors ist denn zu rechnen?

    Hmm. Die meisten Suchen werden in ein einziges Wort passen (und in diesem Fall wird eh eine andere Methode angesprungen). Für den Fall, das die Suche über mehrere Wörter verteilt ist, werden es meistens zwei, maximal drei sein.

    0
  • C
    Mod

    Für den Fall, das die Suche über mehrere Wörter verteilt ist, werden es meistens zwei, maximal drei sein.

    axxooooo. Langweilig. Dann ist das ja gar kein Komplexitätsproblem. Der produzierte Code sieht eigentlich ganz gut aus, soweit es deine Bitoperationen betrifft. Etwas ungünstig ist der Schleifenkopf - andererseits ist das nur gerechte Strafe dafür, dass du Invarianten nicht aus der Bedingung herausgenommen hast. Wie verhält sich denn eigentlich:

    struct shift_with_carry : std::unary_function<word_t,word_t>
{
    shift_with_carry(bool carry) : carry_(carry) {}
    word_t operator()(word_t v) const
    {
        bool old_carry_ = carry_;
        carry_ = v & carry_position != 0;
        return v << 1 + old_carry;
    }
    bool carry_;
}
// und dann statt der Schleife
shift_with_carry foo(true);
std::for_each(bitvec.begin(),bitvec.end(),foo);
    0
Anmelden zum Antworten