Performancemythen?

[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?

[kleine Bemerkung]

Hallo

OOP frißt ebensowenig Performance im Vergleich zu C wie ein Makroassembler
Performance frißt im Vergleich zu Maschinencode.

Es sei denn, man legt es darauf an.

Wenn man jedes einzelne Zeichen als Objekt behandeln würde und einen String dann als Liste von Zeichen-Objekten, dann kostet das Performance.
Aber deshalb hat man ja in C++ auch noch alle Low-Level-Strukturen von C
(Arrays usw.), die man im Zweifelsfall einsetzen kann.

Für Performace-unkritische Anwendungen wäre die bessere Wartbarkeit dank OOP
selbst einen gewissen Performance-Verlust wert.

Gruß

[rüdiger]

kleine Bemerkung schrieb:

Wenn man jedes einzelne Zeichen als Objekt behandeln würde und einen String dann als Liste von Zeichen-Objekten, dann kostet das Performance.

Quatsch.

[CStoll]

Jester schrieb:

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?

Ganz einfach: Du brauchst in den Iteratoren nicht zu speichern, welcher Liste sie gehören. Stattdessen hast du beide betroffenen Listen vor Ort (die Quelle als Parameter, das Ziel steckt hinter this) und kannst direkt deren Größenwerte anpassen (oder wenn du willst, auch nur für ungültig erklären).