Laufzeit OOP
-
Hallo ihr lieben,
ich bin grad dabei mich in die objektorientierte Programmierung in C++ einzuarbeiten. Eigentlich komme ich von C.
Ich habe ein etwas größeres Projekt von einem rekursiven Algorithmus, bei dem ich viele Sonderfälle abfangen und separat behandeln muss. Sowas in C zu schreiben erzeugt sehr viele Zeilen Code und wird fehleranfällig.
Dafür möchte ich gerne das Konstrukt von Klassen und Vererbung nutzen. Die Funktionen sind eben sehr ähnlich, es wäre viel übersichtlicher.Allerdings bin ich gerade erschrocken, als ich mal nach Laufzeit geguckt habe:
http://de.wikipedia.org/wiki/Objektorientierte_Programmierung#Laufzeitverhalten_und_Energieeffizienz (Anm.: Artikel ist von 2003. Da hat sich doch noch was getan
)Meine Output Dateien werden mehrere hundert MB groß. Da alles rekursiv laufen muss - es sei denn ich bin so klug und könnte P=NP beweisen
- brauche ich sehr viel Rechenleistung und Arbeitsspeicher, um eine hinreichende Approximation zu bekommen.Was ich von euch erfahrenen Nutzern und Theoretikern wissen möchte:
"verglich die Laufzeiteffektivität und die Energieeffizienz von typischen Algorithmen von prozeduralen Ansätzen und OOP-Techniken, implementiert als C- und C++-Software"
Vollständige OOP Technik? Wie vollständig? Ab wann wird es kritisch?? Hängt das von der Tiefe der Vererbung ab? Oder ist jeder Klassenaufbau viel aufwendiger als eine Struct? Was frisst am meisten Leistung, was kann man einsparen? Wenige Stdbibliotheken nutzen?Und:
Um wieviel schneller oder langsamer ist ein C++ Compiler im Vergleich zu C Compiler?
Ich glaube nämlich, ich muss sparsam mit OOP umgehen, im C++ Code sehr viel noch in C Form gebaut lassen, dann in den C++-Compiler reinschmeissen ...
argh 
Fragen über Fragen. Merci!
-
Wenn ich dich so hoere, dann kann ich nur den Kopf schuetteln:
einem rekursiven Algorithmus ... das Konstrukt von Klassen und Vererbung nutzen
Was hat ein rekursiver Algorithmus mit Vererbung und Klassen zu tun? In erster Linie nix.
Da alles rekursiv laufen muss - es sei denn ich bin so klug und könnte P=NP beweisen
Was hat rekursiv mit NP=P zu tun? In erster Linie nix.
Ob OOP angebracht ist, haengt vom Problem ab. Leider hast du nix darueber verloren.
-
knivil schrieb:
Wenn ich dich so hoere, dann kann ich nur den Kopf schuetteln:
einem rekursiven Algorithmus ... das Konstrukt von Klassen und Vererbung nutzen
Was hat ein rekursiver Algorithmus mit Vererbung und Klassen zu tun? In erster Linie nix.
Hab ich gar nicht geschrieben. Steht doch da, es geht um die Sonderfälle!
"bei dem ich viele Sonderfälle abfangen und separat behandeln muss. Sowas in C zu schreiben erzeugt sehr viele Zeilen Code und wird fehleranfällig.
Dafür möchte ich gerne das Konstrukt von Klassen und Vererbung nutzen. Die Funktionen sind eben sehr ähnlich, es wäre viel übersichtlicher."Was hat rekursiv mit NP=P zu tun
Gar nix. Ist ein NP Problem. Wenn ichs polynomiell machen könnte, würde ich hier diese Fragen nicht stellen.
Es ist schon spät ... da hab ich zuviel Info in einen Satz gepackt ...
-
@Lymogry
Kannst du mal skizzieren wie die C-Variante aussieht, und wie du es in C++ schreiben wollen würdest um den Code übersichtlicher zu machen?
So allgemein kann man dazu nämlich nicht wirklich was sagen.Das auf Wikipedia verlinkte Paper ist leider nicht gratis einsehbar, und ich hab keine Lust $20 dafür zu zahlen. Daher kann ich auch nicht beurteilen wie sinnvoll der Vergleich ist. Wäre nicht das erste Paper zu so einem Thema das total sinnfreie Vergleiche enthält.
Grundsätzlich ist OOP vs. nicht-OOP performance-mässig neutral. Was was kostet sind die "dynamischen" Dinge wie virtuelle Funktionsaufrufe,
dynamic_castundtypeid(). Doof ist z.B. wenn du virtuelle Funktionen hast die selbst kaum rechenzeit brauchen, aber verdammt oft aufgerufen werden.Und du zahlst üblicherweise auch ein wenig für das Betreten und Verlassen jedes "inlining Blocks", der Objekte enthält die keinen trivialen Destruktor haben. Und zwar für die Pflege der für Unwinding nötigen Informationen. Und mit "inlining Block" meine ich einen Code-Block der keine Funktionsaufrufe enthält die nicht inline erweitert werden.
Hier wiederrum ganz doof virtuelle Funktionen die sehr wenig tun und sehr oft aufgerufen werden.
-
Wie soll denn quicksort "Objektorientiert" aussehen? Mit nem virtuellen Compare? Hört sich alles total schwachsinnig an. Frag was Konkretes, class und struct sind in C++ quasi das gleiche, nur dass Member beim struct default-public sind.
-
Man kann in etwa sagen, dass ein in C geschriebener und von einem erfahrenen Programmierer optimierter Algorithmus schneller ist.
Dafür ist normaler (guter Code, aber nicht speziell optimiert) C++-Code gegenüber normalem C-Code einfach zu schreiben und verhältnismäßig schnell.Beispiel: In C kann man ein sortiertes Array mit bsearch durchsuchen. In C++ hat std::lower_bound ungefähr die gleiche Funktionalität.
Dennoch weiß der Compiler in C nur, dass der Callback ein Funktionspointer ist und kann damit wenig anfangen. Verwendet man in C++ hingegen ein Objekt dafür, wird dieses durch templates richtig in die Funktion eingesetzt und statt einem einfachen Zeiger hat der Compiler die Typinformationen, kann genau bestimmen, welche Funktion aufgerufen wird und setzt diese in den Algorithmus ein (inlining) und ist dadurch deutlich schneller.
Würde man jetzt die binäre Suche komplett in C schreiben und die Funktion per Hand einsetzen und weiter optimieren, wäre C vielleicht schneller.
-
Marthog schrieb:
Man kann in etwa sagen, dass ein in C geschriebener und von einem erfahrenen Programmierer optimierter Algorithmus schneller ist.
Dafür ist normaler (guter Code, aber nicht speziell optimiert) C++-Code gegenüber normalem C-Code einfach zu schreiben und verhältnismäßig schnell.Was hindert dich denn in C++ da dran, das gleiche zu tun? Die Sprache erlaubt das gleiche, aber dafür bleibt viel mehr Entwicklungszeit übrig. Von welcher Art von Optimierung redest du hier überhaupt?
-
Marthog schrieb:
Man kann in etwa sagen, dass ein in C geschriebener per Hand optimierter Algorithmus schneller ist.
Nö.
Ein in C geschriebener per Hand optimierter Algorithmus kann schneller sein als ein in idiomatischem C++ geschriebener.
Ich sehe aber nicht wie er schneller sein soll als ein in (nicht notwendigerweise idiomatischem) C++ geschriebener per Hand optimierter Algorithmus.Und dass selbst idiomatisches C++ schneller sein kann als so mancher idiomatischer C-Code, oft gleich schnell oder zumindest so-gut-wie gleich schnell wie "handoptimiertes C", schreibst du ja später selbst.
Also wieso dann erstmal anfangen mit der (IMO unsinnigen) Aussage dass handoptimiertes C "in etwa" schneller sei? Schneller als was? Als Python?
-
Die Quelle ist leider nicht umsonst abrufbar, und ich werde keine 20 Dollar ausgeben, um hier besser antworten zu können, also musst du dich mit etwas Spekulation begnügen.
Ich vermute, dass in dem Artikel Folgendes bemerkt wurde: Indirektion frisst richtig Zeit. Generell sind verlinkte Datenstrukturen schrecklich ineffizient im Vergleich zu solchen, die ihre Daten lokal halten, und in einem naiv objektorientierten Ansatz baut man sich riesige Bäume verlinkter Datenstrukturen, da man praktisch alles als Referenz vorhalten muss (Laufzeitpolymorphie ist anders nicht (bzw. nur schwer und mit Einschränkungen) machbar).
Der Grund dafür liegt in der Art und Weise, wie moderne Prozessoren mit Speicher umgehen. Ganz grob vereinfacht gesagt sind sie darauf optimiert, linear auf Speicher zuzugreifen -- ein Byte nach dem nächsten. Du kannst das prima benchmarken, wenn du ein großes 2D-Array nimmst (bspw. 20000 x 20000), es einmal zeilen- und einmal spaltenweise durchläufst (und dabei beispielsweise die Summe der Elemente berechnest) und misst, wie lange es dauert. Bei mir macht das geschmeidig einen Unterschied von Faktor 30, wobei das genaue Ergebnis von Dingen abhängt. Und das geht so: Wenn du eine Position im Arbeitsspeicher ausliest, holt die CPU die Daten erstmal in ihren lokalen Cache, auf den sie wesentlich schneller zugreifen kann. Dabei holt sie die nächsten paar Byte gleich mit (eine Cacheline, heute meistens 64 Byte), so dass diese bei einem linearen Weiterlesen gleich verfügbar sind und die CPU nicht wieder zum RAM rauslaufen muss. Das ist jetzt alles vereinfacht, aber wenn dich das im Detail interessiert, bin ich sicher, dass deine Uni da Vorlesungen anbietet.
In einem rein objektorientierten Modell ohne besondere Speicherverwaltungstricks und mit viel Vererbung (!) läuft man an diesem Optimierungsmechanismus stumpf komplett vorbei. Wenn jeder Zugriff auf die Datenmember eines Objektes erfordert, an anderer Stelle im Speicher zu suchen (weil man die konkrete Klasse eines Datenmembers zur Compilezeit halt nicht kannte und ihn deshalb nur als Verweis vorhalten kann), bringt der Cache dich halt nur sehr eingeschränkt weiter, und das werden die da gemessen haben.
Ein solches Ergebnis will aber in Kontext gesehen werden -- ein Programm hat üblicherweise viele Stellen, bei denen es auf Performance nicht so richtig ankommt. Wenn du eine Anwendung hast, in der am laufenden Meter große Datenmengen durchgecruncht werden sollen, wird es herzlich egal sein, ob die GUI ein paar Millisekunden schneller auf Eingaben reagieren könnte, während der Berechnungscode mit einiger Wahrscheinlichkeit ein geeignetes Ziel für Optimierungen darstellt. Abhängig davon, was du da berechnest, kann es gut sein, dass die Berechnung sowieso nicht besonders gut in ein objektorientiertes Modell passt, in welchem Fall du da halt stumpf keine objektorientierten Mittel verwenden solltest. Mischen ist ausdrücklich erlaubt und oft sehr sinnvoll, und gerade mit C++ hast du eine Sprache zur Hand, die dir dabei nicht im Weg steht. Trotzdem wäre es albern, den GUI-Code prozedural umzuschreiben, wenn dieser sich objektorientiert sauberer formulieren lässt.¹
Zudem lassen sich viele objektorientierte Techniken auch anwenden, ohne Verweise zu spammen. Klassen und Structs in C++ unterscheiden sich nur durch die Default-Sichtbarkeit ihrer Elemente (bei Klassen private, bei Structs public) und unterscheiden sich (mit Ausnahme der vtable, wenn vorhanden) für die Maschine nicht wesentlich von Structs in C. Es ist ohne weiteres möglich, in C++ wie in C Objekte direkt in Objekten zu versenken, ohne sich den oben beschriebenen Verweisbaum zuzuziehen. Nicht für alles braucht man Laufzeitpolymorphie, und nicht überall, wo Laufzeitpolymorphie im Spiel ist, sind konkrete Objekttypen zur Compilezeit völlig unbekannt -- wenn etwa in einem Stück Code Objekte vorgehalten werden, deren Details anderem Code nicht bekannt sein müssen. Statische Polymorphie auf Templatebasis ist auch immer einen Blick wert, wenn man Dinge lokal halten will, und für ganz harte Fälle gibt es placement-new. Man kann sich da in C++ schon helfen.
---
¹ zumal bei Dingen, die außerordentlich gut in objektorientierte Modelle passen (wie GUIs), ohnehin zweifelhaft ist, ob ein objektorientiertes Modell wirklich zu einem Performancemalus führt.
-
Marthog schrieb:
Man kann in etwa sagen, dass ein in C geschriebener und von einem erfahrenen Programmierer optimierter Algorithmus schneller ist.
Dafür ist normaler (guter Code, aber nicht speziell optimiert) C++-Code gegenüber normalem C-Code einfach zu schreiben und verhältnismäßig schnell.Beispiel: In C kann man mit bsearch ein sortiertes Array mit bsearch durchsuchen. In C++ hat std::lower_bound ungefähr die gleiche Funktionalität.
Dennoch weiß der Compiler in C nur, dass der Callback ein Funktionspointer ist und kann damit wenig anfangen. Verwendet man in C++ hingegen ein Objekt dafür, wird dieses durch templates richtig in die Funktion eingesetzt und statt einem einfachen Zeiger hat der Compiler die Typinformationen, kann genau bestimmen, welche Funktion aufgerufen wird und setzt diese in den Algorithmus ein (inlining) und ist dadurch deutlich schneller.
Würde man jetzt die binäre Suche komplett in C schreiben und die Funktion per Hand einsetzen und weiter optimieren, wäre C vielleicht schneller.Und zwar durch Magie. Und nur, wenn der Programmierer das siebente Kind eines siebenten Kindes ist und im Wald ein Drachenei findet.
-
hustbaer schrieb:
Also wieso dann erstmal anfangen mit der (IMO unsinnigen) Aussage dass handoptimiertes C "in etwa" schneller sei? Schneller als was? Als Python?
Schneller als in einer "echt objektorientierten" Sprache, und davon gibt es ja nur eine, also schneller als in Java.
-
Also diese pauschalen Aussagen von wegen "A ist schneller als B" sind aus meiner Sicht Blödsinn.
C kann schneller C++ sein und C++ kann schneller als C sein.
Das muss man schon an speziellen Beispielen belegen und vor allem nachweisen.Ich hatte das mal für STL-Strings gemacht und festgestellt, dass die ANSI-C-Variante in dem Fall deutlich schneller als die std::string-Variante war, was sich auch niemand erklären konnte, außer Volkard, der irgendwas unverständliches in seinen Bart brabbelte, was irgendwie niemand kommentieren wollte. Jedenfalls wurde nicht widersprochen
Aber pauschale Aussagen sind: buuuuh!
-
Ich glaube, der Grund dafür, dass C oft schneller ist, ist dass es darin schwieriger ist schwierige Dinge zu tun.
In C++ schreibt man gern mal string A + string B. Es ist so schön einfach. In C müsste man 2 mal strlen aufrufen, neuen Speicher+1 besorgen, 2 mal memcpy benutzen.... Das tut einfach keiner wenn er nicht unbedingt muss. Man würde sein Programm ändern, sodass die Zielfunktion auch mit 2 Strings klar kommt.
Wenn man in C dasselbe tut wie in C++, dann kommt auch das gleiche Ergebnis raus.
Ich meine aber, dass die Ersparnis bei der Programmierzeit die Laufzeit wert ist, denn man kann danach immernoch die kritischen Stellen optimieren und nicht seine Zeit an unkritischen Stellen verschwenden.Ich würde auch gern volkards Titel von "Moderator" in "Moderater Troll" ändern.
-
volkard schrieb:
hustbaer schrieb:
Also wieso dann erstmal anfangen mit der (IMO unsinnigen) Aussage dass handoptimiertes C "in etwa" schneller sei? Schneller als was? Als Python?
Schneller als in einer "echt objektorientierten" Sprache, und davon gibt es ja nur eine, also schneller als in Java.
Achwatt.
Smalltalk ist doch viel objektiger als Java.
:p
-
Vielen Dank für die vielen Antworten!
@seldon: Danke, diese Ausführung war genau das, was ich brauchte!
Für alle Interessierten, ich hab das Paper übrigens gefunden:
http://users.uom.gr/~achat/papers/IST2003.pdfLG
-
Hallo Lymogry,
die (leidige) Diskussion ob jetzt OOP langsamer ist als 'herkömmlicher C-Code' ist mindestens so alt wie OOP. Wie hier schon erwähnt wurde, kann man das gar nicht pauschal beantwortet.
Aus meiner Praxis kann ich folgendes dazu sagen. Es gibt Programme (mit OOP), wo eine bestimmte Funktion vielleicht 1sec benötigt. Dann kommt so jemand (so wie Du), der sich gut in C auskennt, der frisiert jetzt das letzte aus dem Code heraus und am Ende braucht die Funktion 0,95sec. Die 5% Beschleunigung werden dann als Sieg von C über C++ gefeiert. Das der normale Benutzer davon nichts merkt, spielt keine Rolle.
Dann gibt es Programme, die - wären sie mit 'Brut Force 'geschrieben - die Minuten, Stunden oder noch länger laufen würden, bis ein Ergebnis herauskommt. Lässt man hier den C-Progger ran, kann er dann aus 10h vielleicht 9,5h machen - dem User ist das in jedem Fall zu viel. Das Ergebnis ist u.U. Code, der schlecht zu warten ist, und evt. mehr Fehler enthält.
Wenn man es nun schafft, mit komplexen Algorithmen einen ganz anderen Weg zu beschreiben, dann kann man Laufzeiten drastisch verkürzen. Und hier hilft (nicht immer, aber oft) OOP. Denn damit wird man als Mensch zum Teil erst in die Lage versetzt, so ein komplexes Programm überhaupt zu stemmen.
Und plötzlich bleiben von den Stunden nur noch Sekunden - und wenn Du meinst ich übertreibe, dann lass Dir gesagt sein, dass ich das schon mehr als einmal erlebt habe.
Das Programm, welches dann entsteht, könnte man vielleicht noch durch Fine-Tuning um 5% drücken - nur das braucht keiner, das bezahlt Dir keiner und Du hast oft den Nachteil des erhöhten Wartungsaufwands.Lymogry schrieb:
Vollständige OOP Technik? Wie vollständig? Ab wann wird es kritisch??
Es gibt keine 'vollständige OOP Technik' - es gibt nur Probleme (nicht alle!), die man mit OOP sehr viel besser lösen kann als anders.
Lymogry schrieb:
Hängt das von der Tiefe der Vererbung ab?
Hat damit nichts zu tun, das sind statische Informationen.
Lymogry schrieb:
Oder ist jeder Klassenaufbau viel aufwendiger als eine Struct? Was frisst am meisten Leistung, was kann man einsparen?
class und struct ist das gleiche (s. Beitrag von seldon). Virtuelle Methodenaufrufe sind teuer als nicht virtuelle. Die zu vermeiden entspricht dem Beseitigen des Fliegendrecks an der Windschutzscheibe, dann wird das Auto auch schneller. In der Praxis wirst Du (vielleicht) im %-Bereich schneller (s.o.).
Lymogry schrieb:
Wenige Stdbibliotheken nutzen?
gehe einfach davon aus, dass der Code in Deiner Standard-Bibliothek von guten Programmieren geschrieben und schon ziemlich ausgereizt ist.
Ich will damit nicht sagen, dass OOP per se gut ist. Nutze OOP genau dann, wenn das Problem sich damit gut lösen lässt. Gute - und schnelle - Programme werden von guten und erfahrenen(!) Programmierern geschrieben. Wenn Du als OOP-Anfänger OOP anwendest, dann kannst Du vielleicht Fehler machen, die die Laufzeit Deines Programms nur ansteigen lässt - was Dich dann in Deiner Meinung 'OOP macht langsam' weiter bestärken wird.
Das sollte Dich aber nicht davon abhalten, Dich mit OOP zu beschäftigen. Das ist ein mächtiges Werkzeug.Gruß
Werner
-
Danke Werner. Du hast recht, ich bin OOP Anfänger, aber ich will wirklich keinen Streit entfachen, ob das eine oder andere besser ist.
Mich interessiert das, weil eben der original Algo, den ich implementiere, ab einer bestimmten Approximation mehrere Stunden braucht. Ich habe schon bessere Methoden gefunden, um ihn noch leistungsfähiger zu machen, da ist aber noch genug Luft nach oben. Ich war halt erschrocken über die 95% ... das kann ich ja gar nicht gebrauchen, würde meine Bemühungen nur zunichte machen!
Virtuelle Funktionen vermeiden *check*
-
Lymogry schrieb:
Virtuelle Funktionen vermeiden *check*
Bullshit.
-
Kellerautomat schrieb:
Lymogry schrieb:
Virtuelle Funktionen vermeiden *check*
Bullshit.
Die % sind gut ...
(ok ... wenns sein muss bleiben sie natürlich)
-
Lymogry schrieb:
Virtuelle Funktionen vermeiden *check*
Äh - nein (Du hast mich missverstanden).
wenn Du eine Virtuelle Methode brauchst, so schreibe sie.
Wenn Du sie 'vermeiden' möchtest und dazu große Kopfstände in Deinem Design machen musst, so lass es bleiben und behalte die virtuellen Methoden bei.Außerdem gilt immer - erst Laufzeiten messen und erst dann optimieren. Nach meiner Erfahrung geht die Zeit nie(!) dort verloren wo Du vorher geglaubt hast, dass es länger dauert!
Gruß
Werner
