3. Was ist schneller?

Was ist schneller?

  • Mod

    hustbaer schrieb:

    @SeppJ:
    Mach mal "return" statt anti_opt per Referenz zurückzugeben.
    Macht bei alles Faktor 3 schneller (MSVC 2010, Core 2 Q6600, x64 Code).

    Ja, bei mir auch. Das sollte vor allem die Rechnung innerhalb der Schleife beschleunigen, da man dann die mögliche Pointerindirektion verliert. Aber: Wenn ich das mache, wird der Rückwärtslauf doch ein bisschen langsamer als der Vorwärtslauf. ein bisschen was scheint es also doch auszumachen. Und zweitens komme ich mit allen Compilern ungefähr auf den "Wunderwert" den der Intelcompiler beim ersten Versuch im Falle von Forwariteratoren mit statischem Abbruch erreicht hat. Und nach der Änderung wird der Wert bei Intelcompiler hier auch nicht besser. Es scheint, als wäre die Wunderoptimierung gerade die, dass der Compiler hier beim ersten Fall tatsächlich die Referenz vollständig wegoptimieren konnte und alles direkt auf einer lokalen Variablen lief.

    edit: @hustbaer: nanu, bei dir sind die Iteratoren langsamer als die Indizes? Hast du vielleicht noch die berüchtigten Checked Iterators vom MSVC an?

    0
  • C
    Mod

    theliquidwave schrieb:

    hustbaer schrieb:

    SeppJ schrieb:

    for (size_t i = end - 1; i < end; --i)

    Boah, das hat jetzt ein paar Sekunden gedauert bis mir klar war warum das funktioniert...

    Und ich verstehe es immer noch nicht? Für mich ist das eine Endlosschleife...

    Edit: Omg. Wie obvious 😃 Sehr geil. 👍

    Man kann das auch auf natürliche Weise hinschreiben:

    for (size_t i = end; i-- != 0; )

    wobei es dem Compiler egal sein dürfte, ich habe jedenfalls weder mit gcc (4.5.3,4.6.2,4.7 alpha) noch mit clang irgendwelche signifikanten Unterschiede zwischen den Versionen feststellen können, zwischen verschiedenen Compilern allerdings schon.

    0

  • Ja, rückwärts ist langsamer, aber nicht sehr viel. Wenn der Prefetcher es nicht checken würde, müsste der Unterschied mMn. viel grösser sein.

    Und ja, indexed fwd. ist bei mir schneller. Warum auch immer (andere CPU, anderer Compiler, ...). Checked Iterators sind aber auf jeden Fall aus (mit Checked Iterators sind die Iterator-Schleifen VIEL langsamer).

    Zeiger statt Iteratoren macht auch keinen Unterschied:

    unsigned pointer_forward_static_end(const container &numbers) 
{ 
	unsigned result = 0;
	unsigned int const* ptr = &numbers[0];
	unsigned int const* const end = ptr + numbers.size();
	for (; ptr != end; ++ptr) 
		result += *ptr; 
	return result;
} 

unsigned pointer_backward_static_end(const container &numbers) 
{ 
	unsigned result = 0;
	unsigned int const* const begin = &numbers[0];
	unsigned int const* ptr = begin + numbers.size();
	while (ptr-- != begin)
		result += *ptr; 
	return result;
}

    -------------------------------------------------
Forward pointers, static exit condition.
Size         10: 1.045000  (anti_opt = 776872960)
Size       1000: 0.626000  (anti_opt = 2363704064)
Size     100000: 0.612000  (anti_opt = 4073586576)
Size   10000000: 0.870000  (anti_opt = 3694308556)

-------------------------------------------------
Reverse pointers, static exit condition.
Size         10: 1.054000  (anti_opt = 776872960)
Size       1000: 0.618000  (anti_opt = 2363704064)
Size     100000: 0.611000  (anti_opt = 4073586576)
Size   10000000: 0.916000  (anti_opt = 3694308556)

    EDIT: OK, indexed ist schneller, weil MSVC es da checkt dass er unrollen kann:

    unsigned index_forward_static_end(const container &numbers) 
{ 
000000013FEF1570  mov         qword ptr [rsp+8],rbx  
	unsigned result = 0;
	size_t end = numbers.size(); 
000000013FEF1575  mov         rbx,qword ptr [rcx]  
000000013FEF1578  mov         r11,qword ptr [rcx+8]  
000000013FEF157C  xor         edx,edx  
000000013FEF157E  sub         r11,rbx  
000000013FEF1581  mov         r8d,edx  
000000013FEF1584  mov         r10d,edx  
000000013FEF1587  sar         r11,2  
	for (size_t i = 0; i < end; ++i) 
000000013FEF158B  mov         r9d,edx  
000000013FEF158E  cmp         r11,2  
000000013FEF1592  jl          index_forward_static_end+4Fh (13FEF15BFh)  
		result += numbers[i]; 
000000013FEF1594  lea         rcx,[r11-2]  
000000013FEF1598  mov         rax,rbx  
000000013FEF159B  shr         rcx,1  
000000013FEF159E  inc         rcx  
000000013FEF15A1  lea         r9,[rcx+rcx]  
000000013FEF15A5  nop         word ptr [rax+rax]  

*** UNROLLED LOOP ANFANG ***

000000013FEF15B0  add         edx,dword ptr [rax]  
000000013FEF15B2  add         r8d,dword ptr [rax+4]  
000000013FEF15B6  add         rax,8  
000000013FEF15BA  dec         rcx  
000000013FEF15BD  jne         index_forward_static_end+40h (13FEF15B0h)  

*** UNROLLED LOOP ENDE ***

	for (size_t i = 0; i < end; ++i) 
000000013FEF15BF  cmp         r9,r11  
000000013FEF15C2  jae         index_forward_static_end+58h (13FEF15C8h)  
		result += numbers[i]; 
000000013FEF15C4  mov         r10d,dword ptr [rbx+r9*4]  
	return result;
} 
000000013FEF15C8  mov         rbx,qword ptr [rsp+8]  
000000013FEF15CD  lea         eax,[rdx+r8]  
000000013FEF15D1  add         eax,r10d  
000000013FEF15D4  ret
    0
  • ?

    SeppJ schrieb:

    Vorspeichern der Abbruchbedingung bringt unter Umständen deutliche Steigerungen

    Wie kann das sein, wenn der Standard für begin und end eine Komplexität von O(1) garantiert? Ich habe hier einen 5 Jahre alten PC und dort ist das Vorspeichern der Abbruchbedingung fast doppelt so schnell.

    0
  • Mod

    Gugelmoser schrieb:

    SeppJ schrieb:

    Vorspeichern der Abbruchbedingung bringt unter Umständen deutliche Steigerungen

    Wie kann das sein, wenn der Standard für begin und end eine Komplexität von O(1) garantiert?

    Wo ist da der Widerspruch? Weißt du, was die O-Notation bedeutet?

    0
  • C

    Gugelmoser schrieb:

    Komplexität von O(1)

    Das sagt aus, dass die benötigte Zeit konstant und unabhängig von der Anzahl der Elemente in einem Container ist.

    Edit:
    Zu spät. -.-

    0
  • ?

    cooky451 schrieb:

    Gugelmoser schrieb:

    Komplexität von O(1)

    Das sagt aus, dass die benötigte Zeit konstant und unabhängig von der Anzahl der Elemente in einem Container ist.

    Heißt das nicht, dass der Wert praktisch sofort feststeht? Also ich dachte jetzt, dass es äquivalent zum Vorspeichern wäre.

    0
  • Mod

    Nein, heißt es nicht. Unabhängig von der Länge != Sofort.

    0
  • C

    Gugelmoser schrieb:

    Heißt das nicht, dass der Wert praktisch sofort feststeht? Also ich dachte jetzt, dass es äquivalent zum Vorspeichern wäre.

    Durch die asymptotische Laufzeit kannst du nur die Steigung der benötigten Operationen in Abhängigkeit der Elemente in einem Container erkennen. Du hast keine, aber auch gar keine Information darüber, wie lange eine Operation letztendlich wirklich dauern wird.

    0
  • ?

    Alles klar, danke euch :). Dann hatte ich das immer falsch verstanden.

    0
Anmelden zum Antworten