Optimierung vom Conditional operator mit Typ 'int'

[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

[Konrad Rudolph]

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.

[camper]

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);

[Gast++]

Konrad Rudolph schrieb:

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:

Eigentlich hatte er eher darauf hingewisen dass es nicht sinnvoll sei dass du mittels der von Dir vermuteten Implementierung argumentierst.

Was auch meine Meinung ist, wie Du weisst.

Konrad Rudolph schrieb:

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

Was soll das?

Das ist doch nicht Dein OP.
Von der Art Iteration ist doch wohl generell abzuraten; Du nutzt eine bestimmte Art der Datenrepräsentation.

Einmal in der Schleife &(bitvec[i]) bestimmen, wie ich's vorgeschlagen hatte, ist ganz etwas anderes.
Was ist denn jetzt i?

Konrad Rudolph schrieb:

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

"Sollte wissen" braucht gar kein Listing...

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.

Ach was! Wolltest Du das mal jemandem erklären?
(Aber bitte nicht mir! :D)
Nur ist es dann halt offenbar viel schlechter zu lesen. als mein Listing, gell ?

Grüsse

*this

[Konrad Rudolph]

Gast++ schrieb:

Konrad Rudolph schrieb:

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

Was soll das?

Das ist doch nicht Dein OP.
Von der Art Iteration ist doch wohl generell abzuraten; Du nutzt eine bestimmte Art der Datenrepräsentation.

Natürlich ist das nicht der Originalcode, ich sagte doch vorher, dass man Zeiger verwenden könnte, um den Assembler-Code drastisch zu vereinfachen. Und dass man die Zeiger so normalerweise nicht verwendet, ist mir auch klar, vielen Dank. Ich hab' das jetzt halt einfach mal so schnell dahingeschrieben. Im echten Code werden, wie gesagt, ja eh Iteratoren verwendet.

Was ist denn jetzt i?

Na ein Zeiger aufs aktuelle Wort, was sonst?

Konrad Rudolph schrieb:

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

"Sollte wissen" braucht gar kein Listing...

Also, ich behaupte einfach mal, dass der Compiler durch Codefluss-Analyse viel besser als der Programmierer bestimmen kann, welche Variablen in Register gehören. Und selbst wenn man es im Code angibt, muss sich der Compiler eh nicht dran halten.

[Konrad Rudolph]

Hi camper,

ich sehe den Vorteil des Funktors nicht, vielleicht kannst Du mich darüber aufklären, was der Unterschied sein soll.

[camper]

Konrad Rudolph schrieb:

Hi camper,

ich sehe den Vorteil des Funktors nicht, vielleicht kannst Du mich darüber aufklären, was der Unterschied sein soll.

Kein besonderen, außer das es evtl. etwas klarer wird. Mir war nicht ganz bewusst, dass dein obiges Listing nicht dem richtigen Code entspricht. Wie gesagt, Berechnungen mit Invarianten (und das schließt im Zweifel den Aufruf von size() ein) gehören aus der Schleife heraus. Bei Verwendung von Standardalgorithmen passiert das ganz automatisch. Betrachte das also als im Wesentlichen gegenstandslos.

[hustbaer]

Optimieren verträgt sich oft nicht mit "gutem Design", und auch oft nicht mit "schönem Code". Von daher... versuch mal den Code:

void foo(std::vector<unsigned __int32>& vec)
{
	unsigned __int32* pend = &(vec[0]) + vec.size();
	__int32 count = - static_cast<signed __int32>(vec.size());

	__asm
	{
		mov eax, pend
		mov ecx, count
		stc // set carry flag
	}
the_loop:
	__asm
	{
		rcl dword ptr [eax + ecx*4], 1 // "rotate through carry left"
		inc ecx // inc doesn't modify the carry flag!
		jnz the_loop // doesn't modify carry flag too :)
	}
}

[Gast++]

Sind ein paart kleinere Bugs drin:

[cpp]
unsigned __int32 count = - static_cast<unsigned __int32>(vec.size());
[/cpp]

Zm Assembler einbauen

- ggf. push eax,ecx,flags,ebx

- count nach ebx, 0 nach ecx
- cls
- eax gegen 0 ( NULL ptr ) und ebx gegen 0 ( empty ) testen
- jz ende
- dec ebx
- xor ecx,ecx
- ecx hochzählen und gegen 0 testen bringt nichts, deshalb:

- inc ecx
- cmp ecx, ebx
- jae ende

- ggf. end: pop eax,ecx,flags,ebx (von hinten nach vorn)

Grüsse

*this