3. Optimierung vom Conditional operator mit Typ 'int'

Optimierung vom Conditional operator mit Typ 'int'

  • 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
  • G

    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

    0
  • K

    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.

    0
  • K

    Hi camper,

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

    0
  • C
    Mod

    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.

    0

  • 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 :)
	}
}
    0
  • G

    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

    0
Anmelden zum Antworten