3. Optimierung, Templates

Optimierung, Templates

  • C

    Nexus schrieb:

    Aber wieso rufst du foo() nicht direkt auf dem char -Array auf, wenn die Funktion schon eine generische Iterator-Schnittstelle anbietet?

    😮 Ich glaube, ich habe Templates und std::string unterschätzt, das löst natürlich alles. Danke!

    Äh.. da kommt gleich die nächste Frage auf:
    Kann man es irgendwie vermeiden, Templates im Funktionsrumpf zu definieren?

    0
  • Mod

    cooky451 schrieb:

    Kann man es irgendwie vermeiden, Templates im Funktionsrumpf zu definieren?

    Du kannst Templates forward-deklarieren, wenn du das meinst. Verstehe ich dich da richtig?

    Natürlich muss wie üblich die Definition zum Zeitpunkt der Instanzierung verfügbar sein.

    0
  • C

    SeppJ schrieb:

    Verstehe ich dich da richtig?

    Ne, wollte sagen: "vermeiden sie im Header zu definieren".
    Denn ich habe hier eine Klasse, die quasi nur aus Templates besteht. Das Ganze ist natürlich irgendwie nervig, da ich so die Klasse komplett im Header definieren muss. (Und sie ist doch recht umfangreich.)

    0
  • E

    Ich sehe das Problem nicht:

    //Template.hpp
template<class T>
class Foo
{
  template<class U>
  void Bar(const U&) const;
};
//Template.cpp
template<class T>
template<class U>
void Foo<T>::Bar(const U&) const
{
}
    0
  • M

    cooky451: Du kannst die Deklarationen in den Header schreiben und am Ende des Headers eine .impl inkludieren. Dann hast du ein wenig Übersicht in der .h-Datei.

    EOutOfResources: Die Definition muss zum Zeitpunkt des Aufrufs bekannt sein. Du kannst deine Funktion also nicht in einer anderen Übersetzungseinheit benutzen.

    0
  • N

    cooky451 schrieb:

    Ich glaube, ich habe Templates und std::string unterschätzt, das löst natürlich alles. Danke!

    Mit std::string hat dieser Ansatz übrigens gar nichts zu tun. Übergib lediglich zwei char -Zeiger auf Beginn und Ende (bzw. danach) der Zeichenkette, Zeiger sind in diesem Fall deine Iteratoren.

    0
  • C

    Nexus schrieb:

    Mit std::string hat dieser Ansatz übrigens gar nichts zu tun. Übergib lediglich zwei char -Zeiger auf Beginn und Ende (bzw. danach) der Zeichenkette, Zeiger sind in diesem Fall deine Iteratoren.

    Du weißt doch gar nicht, was foo() mit den Iteratoren macht. Darauf bezog sich die Bemerkung. 😉

    Michael E. schrieb:

    Dann hast du ein wenig Übersicht in der .h-Datei.

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

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