Was ist schneller?

hustbaer

Hier mal eine leicht angepasste Version:

#define _SECURE_SCL 0

#include <iostream> 
#include <string>
#include <iterator> 
#include <vector> 
#include <cstdlib> 
#include <algorithm> 
#include <iomanip> 

#define NOMINMAX
#include <windows.h>

#pragma comment(lib, "winmm")

using namespace std; 

typedef vector<unsigned> container; 

unsigned iterator_forward_dynamic_end(const container &numbers) 
{
	unsigned result = 0;
	for (container::const_iterator it = numbers.begin(); it != numbers.end(); ++it) 
		result += *it; 
	return result;
} 

unsigned iterator_forward_static_end(const container &numbers) 
{ 
	unsigned result = 0;
	container::const_iterator end = numbers.end(); 
	for (container::const_iterator it = numbers.begin(); it != end; ++it) 
		result += *it; 
	return result;
} 

unsigned iterator_backward_dynamic_end(const container &numbers) 
{ 
	unsigned result = 0;
	for (container::const_reverse_iterator it = numbers.rbegin(); it != numbers.rend(); ++it) 
		result += *it; 
	return result;
} 

unsigned iterator_backward_static_end(const container &numbers) 
{ 
	unsigned result = 0;
	container::const_reverse_iterator end = numbers.rend(); 
	for (container::const_reverse_iterator it = numbers.rbegin(); it != end; ++it) 
		result += *it; 
	return result;
} 

unsigned index_forward_dynamic_end(const container &numbers) 
{ 
	unsigned result = 0;
	for (size_t i = 0; i < numbers.size(); ++i) 
		result += numbers[i]; 
	return result;
} 

unsigned index_forward_static_end(const container &numbers) 
{ 
	unsigned result = 0;
	size_t end = numbers.size(); 
	for (size_t i = 0; i < end; ++i) 
		result += numbers[i]; 
	return result;
} 

unsigned index_backward_static_end(const container &numbers) 
{ 
	unsigned result = 0;
	size_t end = numbers.size(); 
	for (size_t i = end - 1; i < end; --i) 
		result += numbers[i]; 
	return result;
} 

unsigned index_backward_universal_end_1(const container &numbers) 
{ 
	unsigned result = 0;
	for (size_t i = numbers.size() - 1; i != std::numeric_limits<size_t>::max(); --i) 
		result += numbers[i]; 
	return result;
} 

unsigned index_backward_universal_end_2(const container &numbers) 
{ 
	unsigned result = 0;
	for (size_t i = numbers.size() - 1; ~i; --i) 
		result += numbers[i]; 
	return result;
} 

unsigned index_backward_universal_end_3(const container &numbers) 
{ 
	unsigned result = 0;
	for (size_t i = numbers.size(); i; --i) 
		result += numbers[i - 1]; 
	return result;
} 

unsigned index_backward_universal_end_4(const container &numbers) 
{ 
	unsigned result = 0;
	for (size_t i = numbers.size(); i--;) 
		result += numbers[i]; 
	return result;
} 

void measure(unsigned (&function)(const container &), string name) 
{ 
	const size_t num_iterations = 1000000000; 
	cout << "\n-------------------------------------------------\n" << name << "\n";
	for (size_t sample_size = 10; sample_size < num_iterations; sample_size *= 100) 
	{ 
		cout << "Size ";
		cout.width(10);
		cout << sample_size << ": "; 
		container numbers; 
		back_insert_iterator<container> back_it(numbers); 
		srand(0); 
		generate_n(back_it, sample_size, rand); 
		unsigned anti_opt = 0; 

//		clock_t start = clock();
		DWORD t0 = ::timeGetTime();
		for (size_t i = 0; i < num_iterations / sample_size; ++i) 
		{ 
			anti_opt += function(numbers); 
		} 
//		clock_t end = clock(); 
		DWORD t1 = ::timeGetTime();

//		cout << fixed << static_cast<double>(end - start) / CLOCKS_PER_SEC << "  (anti_opt = " << anti_opt << ")\n";
		cout << fixed << (t1 - t0) / 1000.0 << "  (anti_opt = " << anti_opt << ")\n";
	}   
} 

int main() 
{ 
	::timeBeginPeriod(2);
	::timeBeginPeriod(1);

	measure(iterator_forward_dynamic_end, "Forward iterator, dynamic exit condition."); 
	measure(iterator_forward_static_end, "Forward iterator, static exit condition."); 
	measure(iterator_backward_dynamic_end, "Reverse iterator, dynamic exit condition."); 
	measure(iterator_backward_static_end, "Reverse iterator, static exit condition."); 
	measure(index_forward_dynamic_end, "Indexed forward loop, dynamic exit condition."); 
	measure(index_forward_static_end, "Indexed forward loop, static exit condition."); 
	measure(index_backward_static_end, "Indexed reverse loop, static exit condition."); 
	measure(index_backward_universal_end_1, "Indexed reverse loop, universal exit condition 1."); 
	measure(index_backward_universal_end_2, "Indexed reverse loop, universal exit condition 2."); 
	measure(index_backward_universal_end_3, "Indexed reverse loop, universal exit condition 3."); 
	measure(index_backward_universal_end_4, "Indexed reverse loop, universal exit condition 4."); 
}

MSVC 2010, Windows 7 x64, Core 2 Q6600 (2.4 GHz):

-------------------------------------------------
Forward iterator, dynamic exit condition.
Size         10: 1.060000  (anti_opt = 776872960)
Size       1000: 0.614000  (anti_opt = 2363704064)
Size     100000: 0.608000  (anti_opt = 4073586576)
Size   10000000: 0.846000  (anti_opt = 3694308556)

-------------------------------------------------
Forward iterator, static exit condition.
Size         10: 1.045000  (anti_opt = 776872960)
Size       1000: 0.614000  (anti_opt = 2363704064)
Size     100000: 0.609000  (anti_opt = 4073586576)
Size   10000000: 0.842000  (anti_opt = 3694308556)

-------------------------------------------------
Reverse iterator, dynamic exit condition.
Size         10: 1.045000  (anti_opt = 776872960)
Size       1000: 0.614000  (anti_opt = 2363704064)
Size     100000: 0.609000  (anti_opt = 4073586576)
Size   10000000: 0.839000  (anti_opt = 3694308556)

-------------------------------------------------
Reverse iterator, static exit condition.
Size         10: 1.044000  (anti_opt = 776872960)
Size       1000: 0.613000  (anti_opt = 2363704064)
Size     100000: 0.611000  (anti_opt = 4073586576)
Size   10000000: 0.839000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed forward loop, dynamic exit condition.
Size         10: 0.851000  (anti_opt = 776872960)
Size       1000: 0.444000  (anti_opt = 2363704064)
Size     100000: 0.496000  (anti_opt = 4073586576)
Size   10000000: 0.823000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed forward loop, static exit condition.
Size         10: 0.846000  (anti_opt = 776872960)
Size       1000: 0.437000  (anti_opt = 2363704064)
Size     100000: 0.495000  (anti_opt = 4073586576)
Size   10000000: 0.822000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed reverse loop, static exit condition.
Size         10: 1.369000  (anti_opt = 776872960)
Size       1000: 0.847000  (anti_opt = 2363704064)
Size     100000: 0.838000  (anti_opt = 4073586576)
Size   10000000: 1.005000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed reverse loop, universal exit condition 1.
Size         10: 1.138000  (anti_opt = 776872960)
Size       1000: 0.659000  (anti_opt = 2363704064)
Size     100000: 0.663000  (anti_opt = 4073586576)
Size   10000000: 0.858000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed reverse loop, universal exit condition 2.
Size         10: 1.713000  (anti_opt = 776872960)
Size       1000: 1.089000  (anti_opt = 2363704064)
Size     100000: 1.076000  (anti_opt = 4073586576)
Size   10000000: 1.251000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed reverse loop, universal exit condition 3.
Size         10: 1.044000  (anti_opt = 776872960)
Size       1000: 0.653000  (anti_opt = 2363704064)
Size     100000: 0.691000  (anti_opt = 4073586576)
Size   10000000: 0.856000  (anti_opt = 3694308556)

-------------------------------------------------
Indexed reverse loop, universal exit condition 4.
Size         10: 1.045000  (anti_opt = 776872960)
Size       1000: 0.651000  (anti_opt = 2363704064)
Size     100000: 0.687000  (anti_opt = 4073586576)
Size   10000000: 0.852000  (anti_opt = 3694308556)

SeppJ

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?

camper

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.

hustbaer

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

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.

SeppJ

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?

cooky451

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

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.

SeppJ

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

cooky451

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.

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