3. Optimierung, Templates

Optimierung, Templates

  • N

    cooky451 schrieb:

    Du weißt doch gar nicht, was foo() mit den Iteratoren macht.

    Das kann mir auch egal sein. Darin besteht ja gerade der Sinn, Iteratoren als Abstraktion zu verwenden. Wenn du intern was std::string -spezifisches machst, ist deine Schnittstelle nicht generisch genug, obwohl sie es behauptet zu sein.

    cooky451 schrieb:

    Hm.. ok, aber mich stört vor allem das ständige Neukompilieren. Vermutlich lässt sich das gar nicht vermeiden.

    Nein. Aber du kannst natürlich Code, der nicht von Template-Parametern abhängt, in separate Übersetzungseinheiten auslagern.

    0
  • C

    Hmja, ich bin gerade etwas am experimentieren - die Ergebnisse sind aber irgendwie gar nicht zu gebrauchen. 🙄

    #include <ctime>
#include <iostream>
#include <utility>

int foo(const std::string& s)
{
  return s.end() - s.begin();
}
int foo(const std::pair<std::string::const_iterator, std::string::const_iterator> p)
{
  return p.second - p.first;
}
int foo(std::string::const_iterator begin,
  std::string::const_iterator end)
{
  return end - begin;
}
int foo2(const std::pair<std::string::const_iterator, std::string::const_iterator>& p) // &
{
  return p.second - p.first;
}
int foo(const std::string::const_iterator* its)
{
  return its[1] - its[0];
}

int bar(std::string::const_iterator begin,
  std::string::const_iterator end)
{
  int b = 0;
  for (int i = 0; i < 25000000; ++i)
    b += foo(std::string(begin, end));
  return b;
}
int bar2(std::string::const_iterator begin,
  std::string::const_iterator end)
{
  int b = 0;
  for (int i = 0; i < 25000000; ++i)
    b += foo(std::pair<std::string::const_iterator, std::string::const_iterator>(begin, end));
  return b;
}
int bar3(std::string::const_iterator begin,
  std::string::const_iterator end)
{
  int b = 0;
  for (int i = 0; i < 25000000; ++i)
    b += foo(begin, end);
  return b;
}
int bar4(std::string::const_iterator begin,
  std::string::const_iterator end)
{
  int b = 0;
  for (int i = 0; i < 25000000; ++i)
    b += foo2(std::pair<std::string::const_iterator, std::string::const_iterator>(begin, end));
  return b;
}
int bar5(std::string::const_iterator begin,
  std::string::const_iterator end)
{
  int b = 0;
  std::string::const_iterator its[] = {begin, end};
  for (int i = 0; i < 25000000; ++i)
    b += foo(its);
  return b;
}

int main()
{
  std::string s = "Hello, world!";

  std::clock_t t = std::clock();
  std::cout << "string const&: " << bar(s.begin(), s.end());
  std::cout << "\t\tTime: " << std::clock() - t << std::endl;

  t = std::clock();
  std::cout << "pair: " << bar2(s.begin(), s.end());
  std::cout << "\t\tTime: " << std::clock() - t << std::endl;

  t = std::clock();
  std::cout << "direct: " << bar3(s.begin(), s.end());
  std::cout << "\t\tTime: " << std::clock() - t << std::endl;

  t = std::clock();
  std::cout << "pair const&: " << bar4(s.begin(), s.end());
  std::cout << "\t\tTime: " << std::clock() - t << std::endl;

  t = std::clock();
  std::cout << "direct array: " << bar5(s.begin(), s.end());
  std::cout << "\t\tTime: " << std::clock() - t << std::endl;

  std::cin.get();
}

    Visual Studio 2010 (Standard Release): ~
    string const&: 534
    pair: 1
    direct: 20 (???)
    pair const&: 17 (???)
    direct array: 17

    GCC 4.5.2 (Windows, O2): ~
    string const&: 11294 (???)
    pair: 1
    direct: 1
    pair const&: 1
    direct array: 1

    WTF mache ich falsch? 😃

    0
  • C

    cooky451 schrieb:

    WTF mache ich falsch? 😃

    bar() erzeugt in jedem Schleifendurchlauf einen neuen temporären String, in den es den Inhalt von s reinkopiert (inklusive Speicheranforderung und -freigabe), die übrigen Funktionen hantieren alle mit Iteratoren auf den ursprünglich in der main() angelegten String. Die Unterschiede bei den anderen Funktionen könnten durch unterschedlich gute Optimierungen zustandekommen und durch die Anzahl der benötigten Kopien (foo(pair) und foo(iterator,iterator) müssen je zwei Iteratoren bei der Parameterübergabe kopieren, foo2(const pair&) und foo(iterator[]) nur eine Adresse).

    PS: Haben diese Funktionen einen tieferen Sinn?

    0
  • C

    CStoll schrieb:

    bar() erzeugt in jedem Schleifendurchlauf einen neuen temporären String, in den es den Inhalt von s reinkopiert (inklusive Speicheranforderung und -freigabe),

    Das war der Plan. Bzw. der Plan war zu sehen wie gut der Compiler hier optimiert. Mich wundert nur der krasse Unterschied zwischen VS und GCC. (-O3 hilft auch nicht wirklich.)

    CStoll schrieb:

    Die Unterschiede bei den anderen Funktionen könnten durch unterschedlich gute Optimierungen zustandekommen

    Soweit war ich auch. 😃

    CStoll schrieb:

    und durch die Anzahl der benötigten Kopien (foo(pair) und foo(iterator,iterator) müssen je zwei Iteratoren bei der Parameterübergabe kopieren, foo2(const pair&) und foo(iterator[]) nur eine Adresse).

    Und hier wird es spannend. Hast du dir die Ergebnisse überhaupt richtig durchgelesen? Unter VS ist std::pair<> 20 mal(!) schneller als std::pair const& oder eine direkte Parameterübergabe! (Edit: Man könnte argumentieren, dass die Dereferenzierung teuer ist. Allerdings verstehe ich nicht, warum VS das nicht einfach wegoptimiert. GCC schafft das doch auch!)

    CStoll schrieb:

    PS: Haben diese Funktionen einen tieferen Sinn?

    Na, nicht direkt. Ich wollte eigentlich nur gucken wie viel std::string kaputt macht und da hat Eins zum Anderen geführt.

    0
  • C

    cooky451 schrieb:

    CStoll schrieb:

    bar() erzeugt in jedem Schleifendurchlauf einen neuen temporären String, in den es den Inhalt von s reinkopiert (inklusive Speicheranforderung und -freigabe),

    Das war der Plan. Bzw. der Plan war zu sehen wie gut der Compiler hier optimiert. Mich wundert nur der krasse Unterschied zwischen VS und GCC. (-O3 hilft auch nicht wirklich.)

    Also entweder der VS ist an der Stelle wirklich besser beim Optimieren oder er hat eine kopierfreundlichere Version von std::string (irgendwas mit Referenzzählung könnte dort helfen, wenn der Iterator weiß, zu wem er gehört).

    CStoll schrieb:

    und durch die Anzahl der benötigten Kopien (foo(pair) und foo(iterator,iterator) müssen je zwei Iteratoren bei der Parameterübergabe kopieren, foo2(const pair&) und foo(iterator[]) nur eine Adresse).

    Und hier wird es spannend. Hast du dir die Ergebnisse überhaupt richtig durchgelesen? Unter VS ist std::pair<> 20 mal(!) schneller als std::pair const& oder eine direkte Parameterübergabe! (Edit: Man könnte argumentieren, dass die Dereferenzierung teuer ist. Allerdings verstehe ich nicht, warum VS das nicht einfach wegoptimiert. GCC schafft das doch auch!)

    Inlining könnte auch eine Rolle spielen - und die Kenntnis des Compilers über die betiligten Datentypen. Hast du denn mal in den Headern nachgesehen, was sich auf beiden Systemen hinter std::string::const_iterator verbirgt?

    0

  • @CStoll:
    MSVC's std::string hat nen eingebauten Puffer ("SSO") für IIRC 16 Character (oder 16 Bytes? - egal, in dem Fall das selbe).
    Der String von cooky ist ausreichend kurz -> booyah 🙂

    MSVC's schlimmste Bremse, der relativ langsame Heap, kommt dadurch nicht zum Zuge.

    EDIT: Alles Blödsinn. Hier wird ja sowieso nix kopiert, bloss die Länge auf furchtbar komplizierte Art und Weise ausgerechnet. Und die CLOCKS_PER_SEC Sache muss erstmal bereinigt werden, bevor man irgendwas vergleichen kann.
    Eigentlich müsste MSVC hier langsamer sein, wegen der ollen Checked-Iterators.

    EDIT2: OK, an einer Stelle wird doch kopiert, hab' ich übersehen 🙂

    0

  • @cooky:

    Du kannst std::clock() Differenzen verschiedener Compiler nicht unbedingt miteinander vergleichen. Googel mal nach CLOCKS_PER_SEC.

    Oder lies da:
    http://www.cplusplus.com/reference/clibrary/ctime/clock/

    0
  • C

    hustbaer schrieb:

    @CStoll:
    MSVC's std::string hat nen eingebauten Puffer ("SSO") für IIRC 16 Character (oder 16 Bytes? - egal, in dem Fall das selbe).
    Der String von cooky ist ausreichend kurz -> booyah 🙂

    MSVC's schlimmste Bremse, der relativ langsame Heap, kommt dadurch nicht zum Zuge.

    EDIT: Alles Blödsinn. Hier wird ja sowieso nix kopiert, bloss die Länge auf furchtbar komplizierte Art und Weise ausgerechnet. Und die CLOCKS_PER_SEC Sache muss erstmal bereinigt werden, bevor man irgendwas vergleichen kann.
    Eigentlich müsste MSVC hier langsamer sein, wegen der ollen Checked-Iterators.

    Wow! Tatsache, MSVC macht von "123456789abcdef" auf "123456789abcdefZ" einen Sprung von 543 auf 25545 ms! Den GCC interessiert das gar nicht. Schon lustig, wie unterschiedlich gut die Compiler optimieren.

    Edit:
    Dein Edit war wohl nix. :p

    hustbaer schrieb:

    Du kannst std::clock() Differenzen verschiedener Compiler nicht unbedingt miteinander vergleichen.

    Ist mir schon bewusst, ich habe nur noch nie erlebt, dass clock() unter Windows etwas anderes als ms zurückgegeben hat (wie auch hier). Ist natürlich trotzdem nicht ganz korrekt, aber ist ja auch nur dreckiger Testcode. 🙂

    0

  • OK, alles zurück, DA wird ja doch kopiert

    int bar(std::string::const_iterator begin, 
   std::string::const_iterator end) 
 { 
   int b = 0; 
   for (int i = 0; i < 25000000; ++i) 
     b += foo(std::string(begin, end));  // <------ DAAAAAAA :)
   return b; 
 }
    0

  • cooky451 schrieb:

    Wow! Tatsache, MSVC macht von "123456789abcdef" auf "123456789abcdefZ" einen Sprung von 543 auf 25545 ms! Den GCC interessiert das gar nicht. Schon lustig, wie unterschiedlich gut die Compiler optimieren.

    Was hat das mit Optimieren zu tun 😕
    Tu mal bei MSVC die Checked Iterator Dingens deaktivieren. Mach mal ein

    #define _SECURE_SCL 0

    in dein Precompiled-Header File rein (stdafx.h), oder falls du keins verwendest, eben irgendwo wo es vor allem anderen steht, und für alle .cpp Files gilt.

    Und dann vergleich nochmal.

    0
  • C

    hustbaer schrieb:

    Und dann vergleich nochmal.

    Kein Unterschied. Hätte mich jetzt auch etwas überrascht, es werden doch überall Iteratoren verwendet?

    hustbaer schrieb:

    Was hat das mit Optimieren zu tun 😕

    Na ja, dass std::pair<> viel schneller als std::pair<> const& ist, finde ich schon komisch. Ich hätte erwartet, dass dem Compiler das egal ist.

    0

  • Das sollte einen Unterschied machen, gerade WEIL Iteratoren verwendet werden.

    Und nochwas: die Aufslöung von clock() mag 1 msec sein, aber die Genauigkeit von clock() ist auf Windows Systemen üblicherweise max. 15~17 msec.
    D.h. ein Unterschied von 1 vs. 17 oder 20 sagt ... nicht sehr viel bis gar nix.

    -> QueryPerformanceCounter

    EDIT:
    Und dann ist der ganze Test eigentlich sowieso Schmarrn, denn bis auf den Aufruf von "foo", wo der String kopiert werden muss, sollte ein guter Compiler das sowieso alles zu (fast) Nichts optimieren.

    0
  • C

    hustbaer schrieb:

    Und dann ist der ganze Test eigentlich sowieso Schmarrn, denn bis auf den Aufruf von "foo", wo der String kopiert werden muss, sollte ein guter Compiler das sowieso alles zu (fast) Nichts optimieren.

    Hatte ich auch erwartet, ist aber wohl nicht der Fall. Bzw. der GCC macht das. VS aber nicht. Wenn man ihn bis 429496729 iterieren lässt, braucht pair<> immer noch 1ms, die anderen drei Version ~244ms. Nimmt man übertriebenderweise mal 4294967295U, braucht VS für alles 0 Sekunden, außer für "direct", da braucht er 3680ms. Der GCC optimiert weiterhin alles völlig weg. Ich versteh das nicht, also vor allem nicht, was VS da veranstaltet.

    (Der eigentliche Ziel war ja eh nur std::string, aber irgendwie interessiert mich das jetzt..)

    0
  • C

    cooky451 schrieb:

    Nimmt man übertriebenderweise mal 4294967295U, braucht VS für alles 0 Sekunden, außer für "direct", da braucht er 3680ms.

    Dafür hast du hoffentlich den Typ der Schleifenvariable korrigiert.

    Ich versteh das nicht, also vor allem nicht, was VS da veranstaltet.

    Wenn du ein wenig tiefer in die Materie einsteigen willst, schau dir doch mal den Maschinen/Assembler-Code an, den die Compiler hinten ausspucken.

    0
  • C

    CStoll schrieb:

    Dafür hast du hoffentlich den Typ der Schleifenvariable korrigiert.

    Latürnich! 🙂

    CStoll schrieb:

    Wenn du ein wenig tiefer in die Materie einsteigen willst, schau dir doch mal den Maschinen/Assembler-Code an, den die Compiler hinten ausspucken.

    Nun ja, wie geahnt baut der Compiler außer bei der pair<> Version noch echte Schleifen ein. Bei 4294967295U sind sie dann (außer bei direct) aber weg. Ich frage mich nur, warum er das macht. (Also warum er zwei Schleifen bei 429496729 drin lässt.)

    0

  • Hihi, OK, hast Recht, das ist einigermassen Schräg.
    Ich kann dir auch nicht beantworten was da abgeht.

    0
Anmelden zum Antworten