Bücher zu C++ und OOA/D/P von Stroustrup, Booch, Gamma et al. und anderen

[Gast++]

Konrad Rudolph schrieb:

Natürlich ist es möglich, aber dafür braucht man einfach C++ nicht. Da kann man auch andere Sprachen, wie z.B. Java verwenden. C++ hat hier einfach keinen Vorteil.

Ob C++ oder eine andere Sprache besser besser für Polymophie geeignet sind war hier nicht das Thema; darauf bezog sich weder mein Statement über C++ noch Denie Antwort.

Konrad Rudolph schrieb:

In C++ kann man andere Paradigmen wählen, z.B. die generische Programmierung.

Man kann damit auch prozedural programmieren.
Nur ist meine These dass man das nicht tun sollte - wenn man prozedural programmieren will kann man C nehmen.

"Ein bisschen OO", also Klassen in prozeduralem Code verwenden, geht meistens schief.
Z.B. ist das Konzept "Ressourcebelegung ist Initialisierung" prozedural nicht abzubilden wenn man sich nicht der besodern Bedeutung von Konstruktoren/Destruktoren gewärtig ist.

Konrad Rudolph schrieb:

Dass kann auf C++ als eigenstädiges Paradigma keine Anwendung finden. Das hiesse ja sich auf Funtionstemplates zu beschränken, also keine Klassen zu modellieren.
Damit würde aber die Syntax nicht ausgenutzt.

Quark. Generische Programmierung schließt die Verwendung von Klassen nicht aus.

Eben. Genau das war eine notwendige Implikation meiner These ("nicht eigenständig").
Also wieso ist das Quark wenn's nicht von Dir kommt?

Konrad Rudolph schrieb:

Das Verwenden von Klassen ist ja nicht nur mit OOP möglich.

s.o.

Konrad Rudolph schrieb:

Wenn man sich die STL anschaut, oder auch andere Bibliotheken, die für C++ entwickelt werden (Boost, Loki ...) dann sieht man, dass der Aspekt der generischen Programmierung oft einen größeren Teil einnimmt als OOP.

Boost nutzt Kapselung, somit auch das OO-Paradigma.

Konrad Rudolph schrieb:

Wenn man sich anschaut, was der Erfinder der STL, Stepanov dazu zu sagen hat, wird deutlich, dass der zentrale Punkt bei der Entwicklung der STL die generische Programmierung war.

Das mag sein, nur stehen sich die beiden Konzepte nicht diametral gegenüber.

Grüsse

Gast++

P.S.: Du polemisierst hier ein wenig.

[Gast++]

Konrad Rudolph schrieb:

Ich arbeite gerade an einer C++-Bibliothek für Bioinformatiker mit. OOP ist hier aus Performance-Gründen tabu

Jetzt ist zumindest klar warum Du auf die Eigenständigkeit "Generischer Programmierung" mit C++ Wert legst.

Konrad Rudolph schrieb:

Methoden-Dispatching zur Compilezeit

Damit wollt späte Bindung mittels VMT umgehen?

Idealerweise könnte ein Compiler das zu lediglich einem weiteren

Assembler

mov <wohinauchimmer>,<ein ptr>

(o.ä.) optimieren.

(Ich behaupte nicht dass Compiler das auch schaffen!)

Mich würde mal Deine Messung des aktuellen Perfomance-Unterschieds
(Compiler?, Optionen?)

und das Kompliat, also der Assembler-Zwischencode, interessieren.

Grüsse

Gast++

[Konrad Rudolph]

Gast++ schrieb:

P.S.: Du polemisierst hier ein wenig.

Ja. Weil es mich ärgert, dass alle immer denken, Klassen gäbe es nur in OOP. Das ist einfach falsch und da entstehen ärgerliche Missverständnisse. Zum Beispiel hast Du in Deinem letzten Posting geschrieben:

Boost nutzt Kapselung, somit auch das OO-Paradigma.

Diese Aussage ist einfach falsch. Kapselung hat a priori rein gar nichts mit OOP zu tun. "Zufälligerweise" verwendet OOP *auch* Kapselung. Aber Deine Aussage ist eine falsche Implikation, genauso wie der berühmt-berüchtigte Syllogismus "Aristoteles ist sterblich. Katzen sind sterblich. Also ist Aristoteles eine Katze." -- natürlich ist Aristoteles keine Katze, nur weil er eine Eigenschaft mit ihnen teilt (die Sterblichkeit) und genausowenig ist alles, was Kapselung verwendet, gleich OOP, nur weil dieser Code mit OOP eine Eigenschaft (die Kapselung) teilt. Kapselung gab es schon lange vor OOP.

Genauso ist der Rest Deiner Aussagen:

"Ein bisschen OO", also Klassen in prozeduralem Code verwenden, geht meistens schief.

-- Klassen in prozeduralem Code sind *nicht* zwangsläufig "ein bisschen OO". Nur weil OOP zufälligerweise Klassen verwendet, ist nicht jede Verwendung von Klassen OOP.

Z.B. ist das Konzept "Ressourcebelegung ist Initialisierung" prozedural nicht abzubilden wenn man sich nicht der besodern Bedeutung von Konstruktoren/Destruktoren gewärtig ist.

-- Weder RAII noch das Konzept von Konstruktor/Destruktor hat zwangsläufig etwas mit OOP zu tun.

wenn man prozedural programmieren will kann man C nehmen.

-- In C kann man aber eben (längst nicht so gut) generisch programmieren. C unterstützt keine ausreichend gute Kapselung. C unterstützt keine partiellen Spezialisierungen und Funktionsobjekte. C hat einen viel zu geringen Abstraktionsgrad. => C ist für die generische Programmierung ungeeignet.

Zugegeben, ich war auch mal so weit, dass ich dachte, OOP sei das absolute Nonplusultra und wenn man schon Klassen verwendet, dann sollte bitte auch *alles* OOP sein. Aber inzwischen habe ich einfach begriffen, dass das nicht zutrifft. Die Ansicht, OOP sei das Nonplusultra ist genauso eine Modeerscheinung wie Hip-Hop oder der Minirock.

[Konrad Rudolph]

Gast++ schrieb:

Damit wollt späte Bindung mittels VMT umgehen?

Idealerweise könnte ein Compiler das zu lediglich einem weiteren

Assembler

mov <wohinauchimmer>,<ein ptr>

(o.ä.) optimieren.

Nein, es muss zumindest eine Zeigeraddition (Basisadresse + Offset in der VTable) stattfinden. Außerdem verhindert dies das Inlinen von Methoden.

Das dadurch entstehende Overhead ist ein absolutes Totschlagargument gegen die Verwendung in dermaßen rechenintensiven Algorithmen.

Mich würde mal Deine Messung des aktuellen Perfomance-Unterschieds […] interessieren.

Sorry, ich selbst habe keine Messungen mit dieser Bibliothek durchgeführt. Dazu werden aber im Moment (mindestens) zwei Promotionen geschrieben. Ich glaube, diejenigen würden mir den Kopf abreißen, wenn ich einfach so deren Ergebnisse veröffentlichen würde.

[Gast++]

[quote="Konrad Rudolph"]

Gast++ schrieb:

Damit wollt späte Bindung mittels VMT umgehen?

Idealerweise könnte ein Compiler das zu lediglich einem weiteren

Assembler

mov <wohinauchimmer>,<ein ptr>

(o.ä.) optimieren.
Nein, es muss zumindest eine
Zeigeraddition (Basisadresse + Offset in der VTable)

Das wäre ja i.d.R. noch besser...

(Du polemisirst wirklich)

Konrad Rudolph schrieb:

stattfinden. Außerdem
verhindert dies

Welches "dies"?

Konrad Rudolph schrieb:

das Inlinen von Methoden.
Das dadurch entstehende Overhead ist ein absolutes Totschlagargument gegen die Verwendung in dermaßen rechenintensiven Algorithmen.

s.o.

Wie und wo wird in dem Projekt eigentlich alloziert?
(Das ist eins meiner Schwerpunktthemen)

Mich würde mal Deine Messung des aktuellen Perfomance-Unterschieds […] interessieren.

Konrad Rudolph schrieb:

Sorry, ich selbst habe keine Messungen mit dieser Bibliothek durchgeführt. Dazu werden aber im Moment (mindestens) zwei Promotionen geschrieben. Ich glaube, diejenigen würden mir den Kopf abreißen, wenn ich einfach so deren Ergebnisse veröffentlichen würde.

Das ist schade, aber bis ich Zahlen sehe gehe ich davon aus dass die Doppelte Indirektion eben nicht wesentlich ins Gewicht fällt.

Grüsse

Gast++

[Konrad Rudolph]

Gast++ schrieb:

Konrad Rudolph schrieb:

Nein, es muss zumindest eine
Zeigeraddition (Basisadresse + Offset in der VTable)

Das wäre ja i.d.R. noch besser...

Nö ... das kommt ja noch zum Aufruf *hinzu*.

Konrad Rudolph schrieb:

stattfinden. Außerdem
verhindert dies

Welches "dies"?

Na, die virtuelle Funktion bzw. die dadurch entstehende Indirektion. Da der Compiler nicht weiß, welche Methode aufgerufen wird, kann er sie eben nicht inlinen. Das ist bei der Parametrisierung von Algorithmen ein recht großer Unterschied.

Wie und wo wird in dem Projekt eigentlich alloziert?

Was meinst Du damit? Wie Heapspeicher angefodert wird? Wie wir den Speicher verwalten? Oder generell wie Objekte konstruiert werden?

Das ist schade, aber bis ich Zahlen sehe gehe ich davon aus dass die Doppelte Indirektion eben nicht wesentlich ins Gewicht fällt.

Also, es lässt sich recht leicht illustieren, dass genau dies sehr wohl ins Gewicht fällt.

Nimm mal die 'qsort'-Funktion aus C und die 'sort'-Funktion aus C++. Angenommen, die beiden Funktionen besäßen denselben Algorithmus (Quicksort, average case O(n log n)). In C wird ein Funktionszeiger übergeben, der jedes Mal aufgerufen werden muss. In C++ hingegen kann man einen Funktor übergeben, der geinlined werden kann. Die Laufzeit ist n log n, d.h. es wird in C n log n-mal eine Funktion aufgerufen, die oft eine an sich triviale Operation (einen Vergleich) ausführt. D.h. im Vergleich zu dem, was passiert, nimmt der Aufruf einen großen Anteil der Verarbeitungszeit in Anspruch. In C++ fällt dieses Overhead komplett flach. Der Laufzeitunterschied ist hier nicht zu verachten.

Man beachte, dass der Funktionszeiger natürlich keine virtuelle Funktion ist, d.h. hier fällt sogar noch die Addition des Offsets flach. Wenn man hier mit einer virtuellen Funktion arbeiten würde, wäre der Unterschied noch größer. Ich habe gerade keine Zahlen im Kopf aber der Unterschied ist merklich. Generell fallen solche Unterschiede immer dann ins Gewicht, wenn sie sich in einem Algorithmus in der zentralen Schleife befinden. Leider kommt genau diese Situation in sehr vielen Algorithmen vor.

[Gast++]

Konrad Rudolph schrieb:

Gast++ schrieb:

Konrad Rudolph schrieb:

Nein, es muss zumindest eine
Zeigeraddition (Basisadresse + Offset in der VTable)

Das wäre ja i.d.R. noch besser...

Nö ... das kommt ja noch zum Aufruf *hinzu*.

Da ist mir, wie auch in Deinem folgenden Absatz, zuviel Mustmassung drin:

mov <wohinauchimmer>,[Offset + Displacement]

ginge nämlich auch.

Konrad Rudolph schrieb:

Das ist schade, aber bis ich Zahlen sehe gehe ich davon aus dass die Doppelte Indirektion eben nicht wesentlich ins Gewicht fällt.

Also, es lässt sich recht leicht illustieren, dass genau dies sehr wohl ins Gewicht fällt.

Nimm mal die 'qsort'-Funktion aus C und die 'sort'-Funktion aus C++. Angenommen, die beiden Funktionen besäßen denselben Algorithmus (Quicksort, average case O(n log n)). In C wird ein Funktionszeiger übergeben, der jedes Mal aufgerufen werden muss. In C++ hingegen kann man einen Funktor

Ja, und?

Konrad Rudolph schrieb:

d.h. es wird in C n log n-mal eine Funktion aufgerufen, die oft eine an sich triviale Operation (einen Vergleich) ausführt. D.h. im Vergleich zu dem, was passiert, nimmt der Aufruf einen großen Anteil der Verarbeitungszeit in Anspruch. In C++ fällt dieses Overhead komplett flach. Der Laufzeitunterschied ist hier nicht zu verachten.

Man beachte, dass der Funktionszeiger natürlich keine virtuelle Funktion ist, d.h. hier fällt sogar noch die Addition des Offsets flach.

Eben.

Konrad Rudolph schrieb:

Die Laufzeit ist n log n,

Das ist nicht die Laufzeit, sondern die Komplexität von Quicksort.
Die wird durch jeweils einen weiteren Befehl mit konstanter Laufzeit nicht verändert.

Konrad Rudolph schrieb:

Wie und wo wird in dem Projekt eigentlich alloziert?

Was meinst Du damit? Wie Heapspeicher angefodert wird? Wie wir den Speicher verwalten? Oder generell wie Objekte konstruiert werden?

Zwar bin ich mir sicher dass Du Dir das aus dem Kontext erschliessen könntest, aber sei's drum:
Allokation von Arbeitsspeicher.

Insbesondere interessiert mich übrigens der Umgang mit new().

Grüsse

Gast++

[Gast++]

Konrad Rudolph schrieb:

Gast++ schrieb:

P.S.: Du polemisierst hier ein wenig.

Ja.

Das lass ich mal so stehen.

Konrad Rudolph schrieb:

Boost nutzt Kapselung, somit auch das OO-Paradigma.

Diese Aussage ist einfach falsch.

Diese Aussage hingegen wäre nur dann zwingend richtig, wenn es keinen Kontext gäbe innerhald dessen wir hier argumentierten.

Konrad Rudolph schrieb:

Aber Deine Aussage ist eine falsche Implikation, genauso wie der berühmt-berüchtigte Syllogismus "Aristoteles ist sterblich. Katzen sind sterblich. Also ist Aristoteles eine Katze."

Das ist aber dann richtig wenn man dabei auf einen Käfig nur mit Katzen und Katzenspielzeug zeigt. Und wir diskutieren hier über hier eine Katze namens C++.

Konrad Rudolph schrieb:

ist nicht jede Verwendung von Klassen OOP.

Genau. Und unter andeerem deshalb führt das auch zu Problemen.

Konrad Rudolph schrieb:

Z.B. ist das Konzept "Ressourcebelegung ist Initialisierung" prozedural nicht abzubilden wenn man sich nicht der besodern Bedeutung von Konstruktoren/Destruktoren gewärtig ist.

-- Weder RAII noch das Konzept von Konstruktor/Destruktor hat zwangsläufig etwas mit OOP zu tun.

Aber gerade die STL schafft hier eine Verbindung und somit auch Notwendigkeiten.

Konrad Rudolph schrieb:

Zugegeben, ich war auch mal so weit, dass ich dachte, OOP sei das absolute Nonplusultra und wenn man schon Klassen verwendet, dann sollte bitte auch *alles* OOP sein. Aber inzwischen habe ich einfach begriffen, dass das nicht zutrifft. Die Ansicht, OOP sei das Nonplusultra ist genauso eine Modeerscheinung wie Hip-Hop oder der Minirock.

Soweit war ich noch nie.
Aber lass uns bitte beim Thema bleiben.
Pro und Contra OOP führt hier zu weit.

Grüsse

Gast++

[Konrad Rudolph]

Gast++ schrieb:

Da ist mir, wie auch in Deinem folgenden Absatz, zuviel Mustmassung drin:

mov <wohinauchimmer>,[Offset + Displacement]

ginge nämlich auch.

Korrigier mich, wenn's falsch ist aber meinen beschränkten x86-ASM-Kenntnissen zufolgen kann das Displacement nicht eine beliebige Zahl sein sondern nur bestimmte Werte. Zumindest ist das in den meisten Assemblern so. Und damit wäre dieser Opcode ungeeignet.

Konrad Rudolph schrieb:

Die Laufzeit ist n log n,

Das ist nicht die Laufzeit, sondern die Komplexität von Quicksort.

Das ist doch für die Diskussion total egal, zumal ich bereits vorher die Landau-Notation erwähnt hatte. Die Laufzeit ist linear zur Komplexität des Algorithmus. Und damit gilt: Es wird k*n*logn-mal dieser Sprung ausgeführt -- das ist eine Menge!

Die wird durch jeweils einen weiteren Befehl mit konstanter Laufzeit nicht verändert.

Das ist mir bewusst, genau darum geht es aber doch: Der Algorithmus wird um einen konstante Faktor verlangsamt -- und zwar unnötigerweise -- und dieser Faktor ist messbar. Bei aufwendigen Berechnungen kann man sich sowas einfach nicht leisten. Bei einem einfachen Quicksort ist das nicht besonders tragisch aber bei der Sequenzierung eines Genoms entscheidet dieser konstante (!) Faktor darüber, ob das Projekt finanzierbar ist oder nicht. Die Sequenzierung des menschlichen Genoms hat grob zehn Jahre gebraucht! Wenn die Berechnung auch nur um einen Faktor zwei langsamer gewesen wäre, hätte man das Projekt nicht finanzieren können! Bei solchen Größenordnung ist man auf jedes Quentchen Geschwindigkeit angewiesen, selbst auf eine konstante Verbesserung.

Konrad Rudolph schrieb:

Wie und wo wird in dem Projekt eigentlich alloziert?

Was meinst Du damit? Wie Heapspeicher angefodert wird? Wie wir den Speicher verwalten? Oder generell wie Objekte konstruiert werden?

Zwar bin ich mir sicher dass Du Dir das aus dem Kontext erschliessen könntest, aber sei's drum:

Grmpf. Wenn ich es erschlossen hätte, hätte ich nicht nachgefragt. Kaugummidiskussionen machen (zumindest mir) *keinen* Spaß.

Wozu ist denn die Art der Allokation in diesem Kontext interessant?

Sei's drum. Dynamischer Speicher wird in der Bibliothek vorzugsweise über eigene Allokatoren bereitgestellt. Der Standardallokator verwendet intern soweit ich das gerade sehe placement new. Es gibt aber je nach Benutzung recht unterschiedliche Allokationsstrategien.

[Siegfried75]

Meine Favoriten sind die hier:
http://www.galileocomputing.de/

[Gast++]

Konrad Rudolph schrieb:

Gast++ schrieb:

Da ist mir, wie auch in Deinem folgenden Absatz, zuviel Mustmassung drin:

mov <wohinauchimmer>,[Offset + Displacement]

ginge nämlich auch.

Korrigier mich, wenn's falsch ist aber meinen beschränkten x86-ASM-Kenntnissen zufolgen kann das Displacement nicht eine beliebige Zahl sein sondern nur bestimmte Werte. Zumindest ist das in den meisten Assemblern so. Und damit wäre dieser Opcode ungeeignet.

Wieso? Das Displacemt für die "Zeile" ("42. Funktionszeiger...") in der VMT ist konstant.
Nur halt nicht was drinsteht.

Anm: [foo] in Assembler meint *foo in C.

Und damit gilt: Es wird k*n*logn-mal dieser Sprung ausgeführt -- das ist eine Menge!

???
Was ist jetzt k?

Nein; "der" Sprung wird n*log n ausgeführt und das kostet jeweils (k ?) Takte.
Wobei wir bislang nur über ops sprachen, aber eigentlich wollen wir ja erstaml Takte minimieren.

Ausserdem ist die Laufzeit nicht linear zu O(n).

Realiter gibt's da noch
- Caching
- Pipelining / Preemtive Execution
- Threadwechsel
- ggf I/O
- ggf Parallelisierungseffizienz
- ...

Da die Faktoren sich teilweise gegenläufig die Laufzeit in Abhängigkeit von n beinflussen wird die Berechung der Laufzeit sehr komplex.

Konrad Rudolph schrieb:

Bei aufwendigen Berechnungen kann man sich sowas einfach nicht leisten. Bei einem einfachen Quicksort ist das nicht besonders tragisch

???

Bei einem Quicksort könnte das nocht am "tragischten" sein, wenn die Operationen trivial sind. Deshalb hattest Du ja wohl auch das Beispiel gewählt.
Wenn die Berechnungen aufwenig sind wird das Verhältnis eines konstanten "Delays" durch die doppelte Indirektion zu den Nutzoperationen doch nur besser...
Vergleich doch mal die Takte für mov mit FPU Instr. Takten.

Oder wie meinst Du das jetzt?

Konrad Rudolph schrieb:

Wozu ist denn die Art der Allokation in diesem Kontext interessant?

Weil im Gegensatz zu solch einem kleinen "mov" der Overhead von Systemrufen gigantisch ist.

Konrad Rudolph schrieb:

placement new.

Mit Allokatoren mit überladenem operator void * () als _Where ?

Konrad Rudolph schrieb:

Es gibt aber je nach Benutzung recht unterschiedliche Allokationsstrategien.

Das dachte ich mir jetzt schon irgendwie...
Verstösst _DAS_ schon wieder gegen irgendwelche "Geheimhaltungspflichten"?

So kann man schwerlich substantiell diskutieren.

Grüsse

*this

[Konrad Rudolph]

Gast++ schrieb:

Konrad Rudolph schrieb:

Bei aufwendigen Berechnungen kann man sich sowas einfach nicht leisten. Bei einem einfachen Quicksort ist das nicht besonders tragisch

???

Bei einem Quicksort könnte das nocht am "tragischten" sein, wenn die Operationen trivial sind.

Natürlich kommt das auf die Datenmengen an. Was ich meinte ist, dass es dann tragisch ist, wenn man Algorithmen hat, die man im Normalfall auf einige hundert Megabytes an Daten anwendet, z.B. Suchalgorithmen (daran arbeite ich gerade). Die atomaren Operationen sind hier auch oft relativ trivial.

Konrad Rudolph schrieb:

Wozu ist denn die Art der Allokation in diesem Kontext interessant?

Weil im Gegensatz zu solch einem kleinen "mov" der Overhead von Systemrufen gigantisch ist.

Das setzt voraus, dass ähnlich oft Speicher angefordert wird, wie Methoden aufgerufen werden werden. Das ist natürlich Quatsch. Dynamischer Speicher wird -- wenn überhaupt -- meistens *einmal* angefordert, zu Beginn des Algorithmus. Die wenigsten Algorithmen benötigen dynamischen Speicher, den man nicht vorher bereits angefordert hat.

Konrad Rudolph schrieb:

Es gibt aber je nach Benutzung recht unterschiedliche Allokationsstrategien.

Das dachte ich mir jetzt schon irgendwie...
Verstösst _DAS_ schon wieder gegen irgendwelche "Geheimhaltungspflichten"?

Nein, es ist nur absolut irrelevant für die Diskussion. Für die Diskussion kann man einfach davon ausgehen, dass während eines Algorithmus nur ein einziges Mal Speicher angefordert wird. Das ist natürlich eine Vereinfachung, aber keine extreme.