3. Was ist schneller?

Was ist schneller?

  • T

    achso.. Stimmt wohl.. danke

    0
  • M

    Travor schrieb:

    size_t vkSize = vector.size();
for ( size_t i = vkSize - 1; i < vkSize ; --i )

    Es wurden schon Leute für weniger verprügelt.

    0
  • E

    Vor allem ist <=, >=, >, < im Regelfall langsamer als ==/!=.
    Dh. wenn es nicht logisch relevant ist, am Besten != nehmen.

    0

  • dot schrieb:

    Travor schrieb:

    Wieso ist es keine gute Idee in einem Vector rückwärts zu laufen?

    Cache und so...

    Cache und so... was?
    Dem Cache ist es egal, und die Prefetch-Logik der CPU schnallt es auch.

    Also ich sehe da jetzt kein echtes Problem.

    0
  • D

    hustbaer schrieb:

    dot schrieb:

    Travor schrieb:

    Wieso ist es keine gute Idee in einem Vector rückwärts zu laufen?

    Cache und so...

    Cache und so... was?
    Dem Cache ist es egal, und die Prefetch-Logik der CPU schnallt es auch.

    Sie laden je nachdem in welche Richtung man den Speicher benutzt in eine andere Richtung Blöcke vor?
    Wäre mir jetzt neu, aber bestimmt im Bereich des möglichen.

    0
  • ?

    Michael E. schrieb:

    Travor schrieb:

    size_t vkSize = vector.size();
for ( size_t i = vkSize - 1; i < vkSize ; --i )

    Es wurden schon Leute für weniger verprügelt.

    😃

    0

  • drakon schrieb:

    hustbaer schrieb:

    dot schrieb:

    Travor schrieb:

    Wieso ist es keine gute Idee in einem Vector rückwärts zu laufen?

    Cache und so...

    Cache und so... was?
    Dem Cache ist es egal, und die Prefetch-Logik der CPU schnallt es auch.

    Sie laden je nachdem in welche Richtung man den Speicher benutzt in eine andere Richtung Blöcke vor?
    Wäre mir jetzt neu, aber bestimmt im Bereich des möglichen.

    Zumindest die "dicken" CPUs sollten das können.
    http://www.intel.com/Assets/en_US/PDF/manual/248966.pdf

    7.1 GENERAL PREFETCH CODING GUIDELINES schrieb:

    * Take advantage of the hardware prefetcher’s ability to prefetch data that are accessed in linear patterns, in either a forward or backward direction.

    Ich hatte auch mal ein Dokument gefunden wo noch etwas genauer beschrieben war was die CPU um die es ging alles kann - kann den Link aber nimmer finden.

    Andrerseits können es vielleicht weniger "dicke" CPUs wie ARM etc. nicht.

    Von daher ändere ich mal meine Meinung :): wenn's leicht geht bitte immer vorwärts. Bei Programmen für Desktop Plattformen würde aber auch keinen besonderen Aufwand betreiben "rückwärts" zu vermeiden - wenn's rückwärts einfacher geht, dann eben rückwärts.

    0
  • Mod

    So, Zeit für einen Benchmark. ⚠ Und ich muss sagen, ich bin sehr erstaunt über das Ergebnis. erst einmal der Code:

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

using namespace std;

typedef vector<unsigned> container;

void iterator_forward_dynamic_end(const container &numbers, unsigned &anti_opt)
{
  for (container::const_iterator it = numbers.begin(); it != numbers.end(); ++it)
    anti_opt += *it;
}

void iterator_forward_static_end(const container &numbers, unsigned &anti_opt)
{
  container::const_iterator end = numbers.end();
  for (container::const_iterator it = numbers.begin(); it != end; ++it)
    anti_opt += *it;
}

void iterator_backward_dynamic_end(const container &numbers, unsigned &anti_opt)
{
  for (container::const_reverse_iterator it = numbers.rbegin(); it != numbers.rend(); ++it)
    anti_opt += *it;
}

void iterator_backward_static_end(const container &numbers, unsigned &anti_opt)
{
  container::const_reverse_iterator end = numbers.rend();
  for (container::const_reverse_iterator it = numbers.rbegin(); it != end; ++it)
    anti_opt += *it;
}

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

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

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

void measure(void (&function)(const container &, unsigned &), string name)
{
  const size_t num_iterations = 1000000000;
  cout << "\n\nMeasuring: " << name << '\n';
  for (size_t sample_size = 10; sample_size < num_iterations; sample_size *= 100)
    {
      cout << "Sample size " << sample_size << "\nGenerating numbers...\n";
      container numbers;
      back_insert_iterator<container> back_it(numbers);
      srand(0);
      generate_n(back_it, sample_size, rand);
      unsigned anti_opt = 0;
      cout << "Starting measure.\n"; 
      clock_t start = clock();
      for (size_t i = 0; i < num_iterations / sample_size; ++i)
        {
          function(numbers, anti_opt);
        }
      clock_t end = clock();
      cout << "Cummulative value: " << anti_opt 
           << "\nTime: " << setprecision(2) << fixed << static_cast<double>(end - start) / CLOCKS_PER_SEC << " seconds.\n";
    }  
}

int main()
{
  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.");
}

    Und das Ergebnis von GCC 4.6 (-Ofast -march="native" -flto) auf einem älteren i7, Hyperthreading deaktiviert:

    Measuring: Forward iterator, dynamic exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.02 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.72 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.71 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.77 seconds.

Measuring: Forward iterator, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.03 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.71 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.72 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.78 seconds.

Measuring: Reverse iterator, dynamic exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.03 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.72 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.72 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.78 seconds.

Measuring: Reverse iterator, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.03 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.72 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.73 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.77 seconds.

Measuring: Indexed forward loop, dynamic exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 0.96 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 1.06 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 1.06 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 1.13 seconds.

Measuring: Indexed forward loop, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 0.96 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 1.06 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 1.07 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 1.13 seconds.

Measuring: Indexed reverse loop, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.37 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 1.07 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 1.06 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 1.12 seconds.

    Analyse:

    • Vorwärts/Rückwärts ist anscheinend doch egal. edit: nach hustbaers Erklärung über mir aber auch nicht überraschend.
    • Vorspeichern des Endwertes ist, wie erwartet, auch egal.
    • Indexzugriff ist langsamer als Iteratoren! Wer hätte das gedacht? 😮

    Ein deutlich anderes Bild beim Intelcompiler 11 (-O3, -xHOST -ipo):

    Measuring: Forward iterator, dynamic exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.34 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.72 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.74 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.80 seconds.

Measuring: Forward iterator, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 0.90 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.18 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.20 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.42 seconds.

Measuring: Reverse iterator, dynamic exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.02 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.72 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.74 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.81 seconds.

Measuring: Reverse iterator, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.17 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 0.54 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 0.55 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 0.62 seconds.

Measuring: Indexed forward loop, dynamic exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.39 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 1.08 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 1.10 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 1.16 seconds.

Measuring: Indexed forward loop, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.34 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 1.07 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 1.07 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 1.13 seconds.

Measuring: Indexed reverse loop, static exit condition.
Sample size 10
Generating numbers...
Starting measure.
Cummulative value: 608822528
Time: 1.05 seconds.
Sample size 1000
Generating numbers...
Starting measure.
Cummulative value: 3832652736
Time: 1.07 seconds.
Sample size 100000
Generating numbers...
Starting measure.
Cummulative value: 2989154464
Time: 1.06 seconds.
Sample size 10000000
Generating numbers...
Starting measure.
Cummulative value: 3906159848
Time: 1.13 seconds.

    Analyse:

    • Vorwärts/Rückwärts ist egal
    • Vorspeichern der Abbruchbedingung bringt unter Umständen deutliche Steigerungen
    • Iteratoren sind hier auch schneller als Indexzugriff
    • Der etwas veraltete Intelcompiler ist hier mal ein kleines bisschen langsamer als der neueste GCC, außer bei Iteratoren mit statischer Abbruchbedingung. Hier greift wohl irgendeine Wunderoptimierung. Wenn jemand sehr interessiert ist, kann ich mal versuchen den Assemblercode davon zu extrahieren. Ohne dass das jemand lesen möchte, ist mir das im Moment zu schwer zu suchen, das das hochoptimierter Code und entsprechend unlesbar ist.

    Fazit:

    • Will man iterieren, nehme man Iteratoren :p .
    • Im Zweifelsfall den Vergleichswert für die Abbruchbedingung vorher speichern.
    0

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

    0
  • D

    @hustbaer
    Danke fürs raussuchen. Dachte mir schon, dass es, wenn, nicht so standardmässig ist wie andere Optimierungen, da ich mir das in HW schon recht kompliziert vorstelle anhand der Richtung zu optimieren.

    0

  • @drakon
    Keine Ursache 🙂

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

    0
  • T

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

    0

  • 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)
    0
  • 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
Anmelden zum Antworten