Optimierung vom Conditional operator mit Typ 'int'

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