3. Was ist schneller?

Was ist schneller?

  • D

    Das ist relativ einfach per code motion umsetzbar und wenn das ein einigermassen aktueller Compiler nicht umsetzt würde mich das sehr wundern. ^^

    0
  • ?

    Travor schrieb:

    oder noch besser

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

    Vermutlich werden alle diese Minitricks eh schon richtig vom Compiler optimiert.

    ist das nicht total cacheunfreundlich?

    0
  • Mod

    PerfFrag schrieb:

    @Travor: Was soll das? Genau das hab ich doch gemacht im 1. Beispiel -.-

    Ein Vergleich gegen 0 kann einen winzigen Taktbruchteil schneller sein als ein Vergleich gegen eine andere Zahl. Aber das kommt dann wirklich ganz stark drauf an was in der Schleife steht, denn rückwärts durch einen vector gehen ist keine so tolle Idee.

    0

  • lolx schrieb:

    ist das nicht total cacheunfreundlich?

    SeppJ schrieb:

    [...] denn rückwärts durch einen vector gehen ist keine so tolle Idee.

    Jap 😉

    0
  • ?

    Also kann man ja premature optimization is the root of all evil wieder schreiben.

    0
  • ?

    Travor schrieb:

    oder noch besser

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

    Das ist eine Endlosschleife.

    0
  • T

    Es gab da noch einen Bug in meinem Beispiel.

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

    Wieso ist es keine gute Idee in einem Vector rückwärts zu laufen?
    Und ja es gibt keinen allzu großen Unterschied:)

    0

  • Travor schrieb:

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

    Cache und so...

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