Optimierung, Templates

cooky451

Hi,

Ist hier davon auszugehen, dass der std::string nicht wirklich erstellt werden muss? (Soll heißen der Text der hinter p steht muss nicht kopiert werden.)

template<class T = std::string::const_iterator>
void foo(T begin, T end)
{
  // ..
}
void foo(const char* p)
{
  const std::string s(p);
  foo(s.begin(), s.end());
}

Macht so ein Template überhaupt Sinn, wenn klar ist, dass {T i; typeid(*i) == typeid(char)} gelten muss? Oder macht ihr da gleich etwas mit const char* und erwartet einfach, dass der Nutzer einen C-String übergibt und nicht darauf kommt, z.B. einen std::vector<char> ohne Nullterminierung zu nehmen und einfach &v[0] zu übergeben?

Nexus

Der Text hinter p wird garantiert in den std::string kopiert. Zumindest kann ich mir keine COW-Implementierung vorstellen, die automatisch feststellt, falls sich ein Buchstabe des ursprünglichen char -Arrays ändert.

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

Zudem dürfen Funktionstemplates keine Default-Templateparameter haben.

Skym0sh0

Nexus schrieb:

Zudem dürfen Funktionstemplates keine Default-Templateparameter haben.

aber klassen templates?
oder muss da auch mindestens ein template parameter nicht default sein?!

Nexus

Skym0sh0 schrieb:

aber klassen templates?

Ja, hier ganz normal. Es können auch alle Templateparameter mit Defaultwerten belegt sein, das führt dann zu Instanziierungen wie

boost::pool<> p(...);

SeppJ

Skym0sh0 schrieb:

Nexus schrieb:

Zudem dürfen Funktionstemplates keine Default-Templateparameter haben.

aber klassen templates?
oder muss da auch mindestens ein template parameter nicht default sein?!

Klassentemplates dürfen vollständig oder auch teilweise Defaultparameter haben.

edit: Zu langsam

EOutOfResources

Wenn du Optimieren willst, dann umgekehrt:
C-String zu std::string = teuer
std::string zu C-String = billig

cooky451

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?

SeppJ

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.

cooky451

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

EOutOfResources

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
{
}

Michael E.

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.

Nexus

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.

cooky451

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.

Nexus

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.

cooky451

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?

CStoll

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?

cooky451

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.

CStoll

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?

hustbaer

@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

hustbaer

@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/