Performancemythen?

[CStoll]

OOP als solches ist afaik nicht unbedingt langsamer, es ist eine völlig andere Herangehensweise an ein Problem. Was die Geschwindigkeit beeinflussen könnte, wäre der Unterschied zwischen "normalem" Methodenaufruf und dem Aufruf einer virtuellen Methode.

@Inkrement: Offiziell ist nicht festgelegt, daß Post-Inkrement langsamer sein MUSS, aber typischerweise ist es das, weil es eine temporäre Kopie der Operanden anlegen muß:

class test
{
  ...
public:
  test& operator++()
  {
    //erhöhe den "Wert" von *this
    return *this
  }
  test operator++(int)
  {
    test tmp=*this;
    ++*this;
    return temp;
  }
};

Der Prä-Inkrement-Operator kann direkt mit dem Operanden hantieren und gibt das Ergebnis der Berechnungen zurück. Der Post-Inkrement-Operator muß erst den alten Status des Operanden retten, dann darf er ihn verändern, bevor er den geretteten Status übergibt (das macht zwei Kopien, die der Compiler zumindest zur Kenntnis nehmen muß - je nach Intelligenz kann er eventuell eine oder beide wegoptimieren).

[lolz]

Was bei ++iter vs iter++ schneller ist muss man nicht beweisen. Dass ersteres maximal so langsam sein kann wie letzteres aber im Schnitt schneller sein kann sollte als Grund reichen.
Ansonsten löst man jedes mal, wenn man ++iter braucht aber iter++ nimmt, das Problem mit dem falschen Werkzeug.

[rapso]

zum einen haengt es vom compiler ab, viele compiler versuchen die typischen fehler weg zu optimieren, dass bei dingen wie ++it oder it++, wenn der rueckgabewert nicht genutzt wird, er auch nicht zurueckgegeben wird. virtuelle methoden werden von vielen zu oft benutzt, das stimmt schon, aber da haben die meisten cpu-bauer auch optimierungen, sodass es nur sehr wenig kostet. auf den cell kostet es hingegen sehr viel.

die meisten leute die mit solchen tollen optimierungen anfangen, machen haufenweise fehler die 100mal mehr zeit kosten und der kompiler nicht wegoptimieren kann, groesstes problem ist z.b. aliasing und das passiert bei c++ tatsaechlich oefter, einfaches beispiel

c

getListSize(list,&Size);
for(int a=0;a<Size;a++)

c++

for(int a=0;a<list.size();a++)

oder auch

for(...iterator it=list.begin();it!=list.end();++it);

in den meisten faellen werden die funktionen, selbst wenn geinlined, jedesmal ausgefuehrt weil der compiler aliasing nicht ausschliessen kann und dann jukt ++it oder it++ auch absolut wenig.

gut waere

for(size_t a=0,Size=list.size();a<Size;a++)

wenn man weiss dass es kein aliasing gibt

[Gast]

Bin weder OOP Anhänger noch Verächter, in meinen Programmen haben mir solche Detailoptimierungen aber eigentlich nie wirklich was gebracht.

Als profitabler erweist es sich hingegen, das Problem schön überschaubar zu machen, wobei OOP wirklich helfen kann. "Vom Weiten" sieht man dann viel eher inge, die man Optimieren kann, z.B. indem man sie weglässt, anders vorsortiert etc.

Ergo -> myth busted, für mich zumindest

[tntnet]

rapso schrieb:

for(size_t a=0,Size=list.size();a<Size;a++)

Das kann extrem schlecht für die Performance sein. Es gibt Implementierungen, bei dennen std::list::size die Liste iteriert. Das bei jedem Schleifendurchlauf zu machen, ist ungünstig.

Und zum eigentlichen Thema: ich habe vorhin mal einen virtuellen mit einem nicht-virtuellen Funktionsaufruf verglichen. Der virtuelle ist auf der Maschine und mit dem Compiler ca. um den Faktor 3 langsamer. Aber hier zeigt sich schon, daß Performancemessungen sehr schwierig ist. Ein virtueller Funktionsaufruf erfüllt ja auch eine Aufgabe, die ein nicht virtueller nicht erfüllt. Ich muß also den virtuellen Aufruf mit einem Funktionszeiger oder einer if-Kaskade oder einem switch-case-Konstrukt vergleichen.

Auch führt micht die OOP als Denkweise vielleicht zu völlig anderen Lösungen, die wesentlich schneller oder langsamer sein können.

Meiner Ansicht nach ist es ein einziges Performancemythos, daß C++ langsamer ist als C oder daß OOP langsamer ist, als andere Techniken. Insbesondere wenn man bedenkt, daß OOP eine Denkweise oder Modellierungstechnik ist, kann man sich sogar fragen, was das mit Performance zu tun hat.

[TomasRiker]

tntnet schrieb:

rapso schrieb:

for(size_t a=0,Size=list.size();a<Size;a++)

Das kann extrem schlecht für die Performance sein. Es gibt Implementierungen, bei dennen std::list::size die Liste iteriert. Das bei jedem Schleifendurchlauf zu machen, ist ungünstig.

Tut er doch gar nicht. Guck mal genau hin.

[CStoll]

tntnet schrieb:

rapso schrieb:

for(size_t a=0,Size=list.size();a<Size;a++)

Das kann extrem schlecht für die Performance sein. Es gibt Implementierungen, bei dennen std::list::size die Liste iteriert. Das bei jedem Schleifendurchlauf zu machen, ist ungünstig.

Erstens ruft diese Schleife size() nur ein einziges Mal auf. Und zweitens ist eine Implementierung, bei der list::size() jedes Mal neu nachzählen muß, bestimmt nicht standardkonform (der ANSI-Standard definiert nicht nur Schnittstellen, sondern auch Komplexitätsbeschränkungen - und list::size() hat konstante Laufzeit).

[loks]

OOP und Performance stehen nicht im Widerspruch zueinander. Sicher kostet ein virtueller Methodenaufruf etwas, aber es steht ja nirgendwo geschrieben das man zwingend und ausschließlich virtuelle Methoden verwenden muß. Wenn ich tatsächlich eine zeitkritische Stelle in meinem Code habe, bleibt mir ja die Wahl wie ich das umsetze und sollte ich der Meinung sein das eine "klassische" case-implementierung schneller ist als ein Aufruf über eine virtuelle Methode, dann wird halt eine case-Lösung implementiert.

Abgesehen davon ist die (mit Abstand) beste Vorgehensweise des Optimierens die, erstmal das Programm soweit zu schreiben, dann einen Profiler einzusetzen um die ENgpässe zu finden und dann gezielt diese optimieren. Nicht immer ist das, was man für den optimalsten Weg hält in auch tatsächlich ein guter Weg (Stichwort aliasing ist ja schon gefallen). Ohne die Überprüfung durch einen Profiler kann Optimierung daher auch schwer nach hinten losgehen...

Grundsätzlich denke ich, das maximale Performance nicht das Wichtigste an einem Programm ist. Viel wichtiger ist optimale Bedienbarkeit, minimale Anzahl an Fehlern usw. In den Bereichen bietet richtiger EInsatz von OOP viele Vorteile die imho unterm Strich eventuelle Performanceeinbußen mehr als wettmachen.

Die Frage ist einfach: Was benutzt man lieber, ein superschnelles Programm das alle 30 min abstürzt, oder ein etwas langsameres Programm das dafür auch mal einen ganzen Tag durchläuft. (Ja, ich behaupte damit das man mit OOP sauberere Programme schreiben kann, vor allem wenn es sich um große Projekte handelt, let the flamewar begin...)

[rapso]

CStoll schrieb:

tntnet schrieb:

rapso schrieb:

for(size_t a=0,Size=list.size();a<Size;a++)

Das kann extrem schlecht für die Performance sein. Es gibt Implementierungen, bei dennen std::list::size die Liste iteriert. Das bei jedem Schleifendurchlauf zu machen, ist ungünstig.

Erstens ruft diese Schleife size() nur ein einziges Mal auf. Und zweitens ist eine Implementierung, bei der list::size() jedes Mal neu nachzählen muß, bestimmt nicht standardkonform (der ANSI-Standard definiert nicht nur Schnittstellen, sondern auch Komplexitätsbeschränkungen - und list::size() hat konstante Laufzeit).

bist du dir da sicher? es gibt so einige quellen die meinen dass man, sofern es geht, while(!list.empty()) statt while(list.size()) nutzen sollte, weil size immer nachzaehlt... ich hab die quelle jetzt nicht zur hand.

[Jester]

Erstens ruft diese Schleife size() nur ein einziges Mal auf. Und zweitens ist eine Implementierung, bei der list::size() jedes Mal neu nachzählen muß, bestimmt nicht standardkonform (der ANSI-Standard definiert nicht nur Schnittstellen, sondern auch Komplexitätsbeschränkungen - und list::size() hat konstante Laufzeit).

Woher soll der Compiler wissen, dass sich size nicht zwischendrin ändert? Und sei es durch Multithreading? Nene, dem bleibt garnichts anderes übrig als size jedesmal auszuwerten.

Auch die konstante Laufzeit von list::size halte ich für ein Gerücht. Oder magst Du kurz erklären, wie man das zusammen mit konstantem interlist-splice hinkriegt?

[ghorst]

also die gnu-menschen haben definitiv keine konstante laufzeit für size() in einer list:

size() const
      { return std::distance(begin(), end()); }

[Phoemuex]

Jester schrieb:

Auch die konstante Laufzeit von list::size halte ich für ein Gerücht. Oder magst Du kurz erklären, wie man das zusammen mit konstantem interlist-splice hinkriegt?

http://www.cplusplus.com/reference/stl/list/size.html

Unter Complexity

Wieso sollte er denn jedesmal nachzaehlen? Man kann die Groesse doch eifnach speichern und immer, wenn sie sich veraendert die Groesse updaten...

Felix

EDIT: Das P.S. war im falschen Film

[CStoll]

Jester schrieb:

Erstens ruft diese Schleife size() nur ein einziges Mal auf. Und zweitens ist eine Implementierung, bei der list::size() jedes Mal neu nachzählen muß, bestimmt nicht standardkonform (der ANSI-Standard definiert nicht nur Schnittstellen, sondern auch Komplexitätsbeschränkungen - und list::size() hat konstante Laufzeit).

Woher soll der Compiler wissen, dass sich size nicht zwischendrin ändert? Und sei es durch Multithreading? Nene, dem bleibt garnichts anderes übrig als size jedesmal auszuwerten.

Schau dir die Schleife nochmal ganz genau an, dann siehst du den Unterschied:

for(
  size_t a=0,Size=list.size();  // Schleifeninitialisierung
  a<Size;                       // Abbruchbedingung
  ++a                           // Iteration
)
  ...

list.size() wird genau EINMAL aufgerufen - während der Schleifeninitialisierung. Für die Abbruchbedingung wird der aktuelle Index mit dem zwischengespeicherten Wert verglichen.

Auch die konstante Laufzeit von list::size halte ich für ein Gerücht. Oder magst Du kurz erklären, wie man das zusammen mit konstantem interlist-splice hinkriegt?

Sorry, wenn ich das jetzt nicht aus dem Kopf zitieren kann, ich habe den Standard nicht vorliegen. Aber ich werde mich bemühen, das nachzuholen.

[Jester]

Phoemuex schrieb:

http://www.cplusplus.com/reference/stl/list/size.html

Unter Complexity

Oha, danke. Interlist-Splice hat also garkeine konstante Laufzeit. std::list ist also noch unbrauchbarer als ich eh schon dachte.

[Mr. N]

Jester schrieb:

Phoemuex schrieb:

http://www.cplusplus.com/reference/stl/list/size.html

Unter Complexity

Oha, danke. Interlist-Splice hat also garkeine konstante Laufzeit. std::list ist also noch unbrauchbarer als ich eh schon dachte.

Du glaubst wirklich cplusplus.com? Tatsächlich ist es so, dass list<>::size() auch O(N) haben darf.

Und so implementiert es die libstdc++:

/**  Returns the number of elements in the %list.  */
      size_type
      size() const
      { return std::distance(begin(), end()); }

Also O(N).

Es ist ja nicht so, als ob du der einzige wärst, der splice kennt.

[Jester]

Womit dann wieder meine ursprüngliche Aussage richtig wäre...
Wie ist das denn nun festgelegt? Oder darf gar beides O(n) Laufzeit haben? -- Wäre ja doof. Beides zusammen konstant dürfte sich jedenfalls nicht machen lassen.

[Mr. N]

Jester schrieb:

Womit dann wieder meine ursprüngliche Aussage richtig wäre...
Wie ist das denn nun festgelegt? Oder darf gar beides O(n) Laufzeit haben? -- Wäre ja doof. Beides zusammen konstant dürfte sich jedenfalls nicht machen lassen.

Es ist nicht festgelegt. libstdc++ hat denke ich konstantes Splice und nicht-konstantes size(), und so sollte das auch sein. Ne andere Möglichkeit, wäre einen size-Cache zu haben, der bei splice invalidiert, sonst aber geupdatet wird. So oder so, ich hab ja nicht behauptet, dass std::list total praktisch wäre.

[Jester]

Mr. N schrieb:

Es ist nicht festgelegt.

Oh, das ist aber häßlich. Das heißt ich kann keine vernünftigen Laufzeitgarantien geben.

libstdc++ hat denke ich konstantes Splice und nicht-konstantes size(), und so sollte das auch sein.

Ja, sehe ich auch so.

Ne andere Möglichkeit, wäre einen size-Cache zu haben, der bei splice invalidiert, sonst aber geupdatet wird.

Das würde denke ich nicht funktionieren. Wie willst Du das implementieren? Du müßtest ja dem list-Objekt bescheid sagen, wenn was rein/rausgesplicet wird (das läuft doch nur über die Iteratoren). Damit das geht müßte jedes listen-element wissen in welcher list es gerade drin ist. Um das aber aktuell zu halten müßte man die Daten beim splicen updaten... was wiederum nicht in konstanter Zeit geht.

Ich denke auf einer Seite muß man in den sauren Apfel beißen und O(N) bezahlen.

[CStoll]

Jester schrieb:

Das würde denke ich nicht funktionieren. Wie willst Du das implementieren? Du müßtest ja dem list-Objekt bescheid sagen, wenn was rein/rausgesplicet wird (das läuft doch nur über die Iteratoren). Damit das geht müßte jedes listen-element wissen in welcher list es gerade drin ist. Um das aber aktuell zu halten müßte man die Daten beim splicen updaten... was wiederum nicht in konstanter Zeit geht.

Was meinst du, warum man bei splice() auch die Quell-Liste mit angeben muß?

[Jester]

CStoll schrieb:

Was meinst du, warum man bei splice() auch die Quell-Liste mit angeben muß?

Das weiß ich nicht. (Abgesehen davon, dass das imho eine weitere Einschränkung der Nutzbarkeit von list ist). Aber inwiefern hilft das die Zielliste upzudaten?