Polymorphie und moderne Compiler

Gibt es mittlerweile schon neue Ansätze um Anwendungen die sehr stark von Polymorphie gebrauch machen, Frameworks z. B., besser zu optimieren? Wenn ja wie sehen diese Ansätze aus? Wieso können Sprachen wie Java und C# Polymorphie besser optimieren als statische C++ Compiler? Liegt das an der späten Übersetzung in Binärcode, so dass man genau weiß von welchem Typ ein Objekt ist?

hustbaer

Können sie das denn?
Bei Java ist halt ein Punkt wichtig, nämlich dass das Ding bloss einfache Vererbung kann -- da ergeben sich viele Probleme nicht.

Und die einzigen Dinge die nach meinem Kenntnisstand in C++ wirklich weh tun sind virtuelle Basisklassen und dynamic casts. Ggf. noch typeid, bloss das braucht man eh sogut wie nie (ich zumindest).

Mathias

Was bitte ist ein statischer Compiler?
Und was verstehst du unter Optimieren?
Wenn das Klassenmodell in C++ mit dem in Java und C# übereinstimmt sehe ich keinen Grund wieso ein C++-Compiler nicht ähnliche Ergebnisse in Maschinencode liefern könnte.
Wenn du natürlich ein Klassenmodell, das alle Merkmale von C++ ausschöpft und ein Klassenmodell, das alle Merkmale von Java ausschöpft, als Basis deines Vergleichs heranziehst... sieht die Sache anders aus.
Dann ist dies aber ein Vergleich von Äpfeln mit Birnen.

Artchi

Compilerbauer schrieb:

Gibt es mittlerweile schon neue Ansätze um Anwendungen die sehr stark von Polymorphie gebrauch machen, Frameworks z. B., besser zu optimieren? Wenn ja wie sehen diese Ansätze aus? Wieso können Sprachen wie Java und C# Polymorphie besser optimieren als statische C++ Compiler? Liegt das an der späten Übersetzung in Binärcode, so dass man genau weiß von welchem Typ ein Objekt ist?

Naja, du stellst Behauptungen an, ohne Fakten und Begründungen zu liefern. Was sollen wir dir da also für eine Antwort liefern?

Konrad Rudolph

Ich finde leider gerade keinen Link, aber als Hinweis für die Suche: VM-Sprachen (Java, .NET) verwenden Heuristiken, um die Sprungziele von virtuellen Funktionsaufrufen im Voraus zu bestimmen. Auf diese Weise schaffen sie es, Aufrufe einer Methode für ein Interface in vielen Fällen enorm zu beschleunigen.

Ich weiß nicht genau wie das geht, es ist aber im Prinzip so, dass das konkrete Sprungziel in einer Variable gespeichert wird, wenn ein spezielles Objekt X fast immer verwendet wird (und kein anderes Objekt Y). Statt nun einen virtuellen Aufruf à la X->foo() zu tätigen, macht die VM folgendes (vereinfacht):

if (X == saved_obj_ptr) CALL saved_foo_location
else CALL VIRTUAL X->foo()

Und reduziert den virtuellen Funktionsaufruf so zu einer If-Abfrage und einem einfachen CALL-Statement.

tntnet

Und du meinst, daß dieser if-Aufruf und der einfache call schneller sein soll, als ein call über die vtable?

Hast Du mal virtuelle und statische Funktionsaufrufe gebenchmarkt? Du kommst wahrscheinlich auf Resultate, wo der virtuelle Funktionsaufruf gar nicht so teuer ist. Es ist ein hartnäckiges Gerücht, daß virtuelle Funktionsaufrufe teurer sind, als statische. Das mag sein, daß da ein halber Taktzyklus verschwendet wird, aber das spielt sich in einem Bereich ab, der in aller Regel vernachlässigbar ist.

Tntnet

Die Informationen habe ich aus einer Vorlesung zu dem oben genannten Thema. Ich schrieb nicht, dass VM-Sprachen bessere Perfromance erzielen, sondern nur das sie angeblich aufgrund der vielen Laufzeit Infos Code besser optimieren können. Das meinte ich mit "statisch", C++ erzeugt optimierten Binärcode zur Compilezeit, VM-Sprachen erzeugen Binärcode beim erstmaligen Aufruf und optimieren diesen ständig weiter(HotSpot).

hustbaer schrieb:

Und die einzigen Dinge die nach meinem Kenntnisstand in C++ wirklich weh tun sind virtuelle Basisklassen und dynamic casts. Ggf. noch typeid, bloss das braucht man eh sogut wie nie (ich zumindest).

Genau das ist dann starker Gebrauch von Polymorphie. Ich habe eine rein abstrakte(virtual) Basisschicht mit vielen Klassen, für welche es dann verschiedene Implementierungen gibt.

Artchi schrieb:

Compilerbauer schrieb:

Gibt es mittlerweile schon neue Ansätze um Anwendungen die sehr stark von Polymorphie gebrauch machen, Frameworks z. B., besser zu optimieren? Wenn ja wie sehen diese Ansätze aus? Wieso können Sprachen wie Java und C# Polymorphie besser optimieren als statische C++ Compiler? Liegt das an der späten Übersetzung in Binärcode, so dass man genau weiß von welchem Typ ein Objekt ist?

Naja, du stellst Behauptungen an, ohne Fakten und Begründungen zu liefern. Was sollen wir dir da also für eine Antwort liefern?

Meine Frage war ja genau, wie teuer denn virtuelle Funktionsaufrufe bei heutigen Compilern wirklich sind. Das Java und C# mit der HotSpot Technik genau dieses Problem sehr gut lösen findet man überall im Netz. Aber warum sollte man das mit C++ nicht auch tun können? Profiler erzeugen doch auch Zusatzinformationen bei den Testläufen.

tntnet schrieb:

Hast Du mal virtuelle und statische Funktionsaufrufe gebenchmarkt? Du kommst wahrscheinlich auf Resultate, wo der virtuelle Funktionsaufruf gar nicht so teuer ist. Es ist ein hartnäckiges Gerücht, daß virtuelle Funktionsaufrufe teurer sind, als statische. Das mag sein, daß da ein halber Taktzyklus verschwendet wird, aber das spielt sich in einem Bereich ab, der in aller Regel vernachlässigbar ist.

Hast Du dazu Benchmarks, Artikel oder andere Links zum Nachlesen?

Artchi

Zu der Polymorphie: es kostet immer irgendwie Rechenzeit (Taktzyklen) um herauszufinden oder zu bestimmen, welcher konkrete Typ zur Laufzeit auftaucht. Man kann das über vtables lösen oder durch switch/cases (ich bleib mal bei Pseudocode-Formulierungen). So, da kommt auch eine VM nicht drum herum. Deshalb verstehe ich die Bedenken nicht.

Was die Heuristik zur Laufzeit angeht. Das was die VM-Hersteller können, können die C++-Compiler schon lange.

Sowohl Intel als auch MS haben in ihren Compilern eine PGO (Profile Guided Optimierung). Das ganze funktioniert ähnlich einem Hotspot, der anhand von häufigkeiten von Situationen einen optimierten Code erstellt. Dazu muß einfach der Entwickler den PGO einschalten (sinnvollerweise nur für ein Release-Build) und das Programm einmal laufen lassen. Natürlich mit einem Probelaufszenario, z.B. würde in einem Egoshooter der Entwickler eine Runde rumlaufen und rumballern. Hört sich schräg an, gell? Aber anhand eines solchen realen Falls macht der PGO ein Protokoll und kann nachträglich einen optimierteren Build erstellen.

D.h. es gibt hier Lösungen. Man sollte nicht glauben, das die C++-Zeit stehen geblieben ist. Ganz im Gegenteil, die Firmen wie Portland Group, Intel, MS usw. wollen Highformance-Kunden bedienen und tun dies auch mit sehr guten Compilern. Deshalb kosten die auch genug Geld. Der MSVC 2005 Express-Compiler z.B. ist kostenlos, hat Codeoptimierung (!), aber PGO (also dieses eine nette Feature) bekommt man z.B. erst in der Pro-Version. Aber es gibt sie!

ten

Artchi schrieb:

Sowohl Intel als auch MS haben in ihren Compilern eine PGO (Profile Guided Optimierung). Das ganze funktioniert ähnlich einem Hotspot, der anhand von häufigkeiten von Situationen einen optimierten Code erstellt. Dazu muß einfach der Entwickler den PGO einschalten (sinnvollerweise nur für ein Release-Build) und das Programm einmal laufen lassen. Natürlich mit einem Probelaufszenario, z.B. würde in einem Egoshooter der Entwickler eine Runde rumlaufen und rumballern. Hört sich schräg an, gell? Aber anhand eines solchen realen Falls macht der PGO ein Protokoll und kann nachträglich einen optimierteren Build erstellen.

und was ist wenn jemand anders einen anderen kurs läuft und statt mit 'ner bazooka mit'm säbel kämpft? läuft das programm dann saulangsam oder muss eine neue .exe erstellt werden?
ich denke vm's haben den vorteil, dass sie sowas 'online' optimieren können...
:xmas2:

Artchi

Also ich bezweifel mal, das es bei PGO um Typ-Findung geht. Noch werden vtables in C++ benutzt. Aber Hotspots optimieren ja wohl genug andere Dinge. Darum ging es mir. Ohne PGO läuft ein Programm auch nicht saulangsam. Es kann durch PGO höchstens noch schneller werden. Oder sind alle C++Compiler ohne PGO unbrauchbar? Wollen wir jetzt hier einen VM vs. C++ Compiler Flamewar anzetteln?

Deine Frage ist ziemlich kätzerich und hat einen Hauch von Verfolgungswahn bzgl. C++-Code. Bleiben wir mal lieber bei den Tatsachen.

Und wenn es um VM vs. C++ Compiler gehen soll, dann bitte einen neuen Thread im "Rund um die Programmierung" anfangen. Hier im Forum gehts um C++.

Konrad Rudolph

tntnet schrieb:

Und du meinst, daß dieser if-Aufruf und der einfache call schneller sein soll, als ein call über die vtable?

Ich meine gar nichts. Aber sowohl Microsoft als auch Sun haben anscheinend einschlägige Studien, die das bestätigen. Wie gesagt finde ich die Links leider nicht mehr.

Entenwickler

Ist ja nicht so, dass ein C++ Compiler das nicht auch kann. Wenn er schon zur Laufzeit weiss welchen Typ ein Objekt hat braucht er kein Lookup in der vtable (oder wie auch immer das realisert ist), sondern kann direkt die Richtige Funktion aufrufen.

dsadsadsadasiudsaziudsaoid sdfsfdsfdsdsadsadsafdafds dsfdsf ???????

ten

Entenwickler schrieb:

Wenn er schon zur Laufzeit weiss welchen Typ ein Objekt hat braucht er kein Lookup in der vtable (oder wie auch immer das realisert ist), sondern kann direkt die Richtige Funktion aufrufen.

du meinst zur compilezeit, ne?

btw: gibt's eigentlich c++ taugliche prozessoren? welche mit einem oo-like instruction set und vtable-lookup in der hardware?
:xmas2:

Entenwickler

Ja irgendwie verdacht.

tntnet

Ich habe hier mal einen kleinen Benchmark gemacht. Folgendes Programm:
a.h:

#ifndef A_H
#define A_H

class B
{
  public:
    virtual void inc_v() = 0;
};

class A : public B
{
    unsigned a;

    A() : a(0) {}
    static A theA;

  public:

    unsigned get() const  { return a; }
    void reset()          { a = 0; }

    void inc_v();
    void inc_s();
    void inc_i()  { ++a; }

    static A& getA();
    static A* getP();
};

#endif

a.cpp:

#include "a.h"

A A::theA;

void A::inc_v()
{ ++a; }

void A::inc_s()
{ ++a; }

A& A::getA()
{
  return theA;
}

A* A::getP()
{
  return &theA;
}

main.cpp:

#include "a.h"
#include <sys/time.h>
#include <iostream>

#define T(what, expr, get) \
  a.reset();                   \
  gettimeofday(&t0, 0);                   \
  for (unsigned i = 0; i < max; ++i)                   \
    expr;                   \
  gettimeofday(&t1, 0);                   \
  std::cout << what ": " << (get) << ' ' << tv2d(t1) - tv2d(t0) << std::endl;

double tv2d(const timeval& tv)
{
  return static_cast<double>(tv.tv_sec) + static_cast<double>(tv.tv_usec) / 1e6;
}

int main()
{
  A& a = A::getA();
  A* p = A::getP();

  timeval t0, t1;
  const unsigned max = 1e8;

  T("virtual via ref", a.inc_v(), a.get());
  T("static via ref ", a.inc_s(), a.get());
  T("inline via ref ", a.inc_i(), a.get());
  T("virtual via ptr", p->inc_v(), p->get());
  T("static via ptr ", p->inc_s(), p->get());
  T("inline via ptr ", p->inc_i(), p->get());
}

Das ganze compiliert mit "$(CXX) -o a a.cpp main.cpp" und ausgeführt liefert, wie lange es dauert, um eine einfache Methode aufzurufen. $(CXX) ist natürlich mit dem zu testenden Compiler zu ersetzen. Zusätzlich sollte der Compiler angewiesen werden, zu optimieren. Mit den Optimierungsstufen könnt ihr ein wenig rum spielen. Ich habe hier gerade ein AIX-System vorliegen. Der Compiler heißt xlC und unterstützt mehrere Optimierungsstufen. Die Ergebnisse:

ohne Optimierung:
virtual via ref: 100000000 3.93702
static via ref : 100000000 1.29718
inline via ref : 100000000 1.82919
virtual via ptr: 100000000 3.88433
static via ptr : 100000000 1.83586
inline via ptr : 100000000 1.24874

mit -O2:
virtual via ref: 100000000 1.69642
static via ref : 100000000 0.531626
inline via ref : 100000000 0
virtual via ptr: 100000000 1.70686
static via ptr : 100000000 0.790132
inline via ptr : 100000000 0.534315

mit -O5:
virtual via ref: 100000000 1.63159
static via ref : 100000000 1.19209e-06
inline via ref : 100000000 9.53674e-07
virtual via ptr: 100000000 1.57123
static via ptr : 100000000 9.53674e-07
inline via ptr : 100000000 9.53674e-07

Der virtuelle Aufruf benötigt ca. 3 mal so lange, wie der statische. Selbst bei einfacher Optimierung wird der inline-Aufruf vollständig weg optimiert. Interessant ist auch der Unterschied zwischen Zeiger und Referenz. Ein Aufruf über eine Referenz kann xlC offensichtlich leichter optimieren, als über Zeiger. Virtuelle Aufrufe kann xlC nie weg optimieren.

Virtuelle Aufrufe macht das System ca. 70 Mio./Sekunde. Das ist ein sehr hoher Wert und jeder sollte für sich entscheiden, wie relevant das dann noch ist.

Die Ergebnisse hängen natürlich stark vom Compiler und der CPU ab.

Und jetzt seid ihr dran. Es wäre schön, wenn ihr euren Compiler mal laufen lasst und die Ergebnisse hier veröffentlicht.

Tntnet

Danke tntnet für Deine Mühe!

Mein System:
AMD-64 - 3200+, Gentoo mit 2.6.17
g++ (GCC) 3.4.3 20041125 (Gentoo 3.4.3-r1, ssp-3.4.3-0, pie-8.7.7)

Meine Ergbnisse:
Ohne Optimierungen:

virtual via ref: 100000000 1.10772
static via ref : 100000000 0.79737
inline via ref : 100000000 0.796589
virtual via ptr: 100000000 1.10443
static via ptr : 100000000 0.79685
inline via ptr : 100000000 0.819845

Mit O2:

virtual via ref: 100000000 0.340091
static via ref : 100000000 0.400305
inline via ref : 100000000 0.127082
virtual via ptr: 100000000 0.38924
static via ptr : 100000000 0.352535
inline via ptr : 100000000 0.129175

Mit O3:

virtual via ref: 100000000 0.335925
static via ref : 100000000 0.335889
inline via ref : 100000000 0.122384
virtual via ptr: 100000000 0.332823
static via ptr : 100000000 0.33279
inline via ptr : 100000000 0.12128

Simon2

Hi,

danke für die Arbeit !!
Es bringt in meinem Fall nicht viel, selbst Ergebnisse zu liefern, weil ich auch den xLC unter AIX habe....

Aber es sind einige sehr interessante Sachen dabei !!

z.B: hätte ich Folgendes spontan nicht erwartet (bin allerdings auch kein "Optimierer"):

tntnet schrieb:

..
ohne Optimierung:
static via ref : 100000000 1.29718
inline via ref : 100000000 1.82919

Inline 50% langsamer als static

tntnet schrieb:

..
ohne Optimierung:
static via ref : 100000000 1.29718
static via ptr : 100000000 1.83586

Pointer 50% langsamer als Referenz

tntnet schrieb:

..
mit -O5:
static via ref : 100000000 1.19209e-06

Da wird doch wohl auch ein inline hinterstecken, oder ?

Danke,

Simon2.

CStoll

@tntnet: Zum Vergleich könntest du auch noch die selben Aufrufe für ein Stack-Objekt A ob; durchführen Da dürfte der Compiler auch eine Chance haben, die virtuellen Aufrufe zu optimieren.

Konrad Rudolph

Simon2 schrieb:

tntnet schrieb:

..
ohne Optimierung:
static via ref : 100000000 1.29718
inline via ref : 100000000 1.82919

Inline 50% langsamer als static

Halte ich z.B. für unrealistisch. Sind solche Benchmark-Ergebnisse signifikant? Handelt es sich da vll. um reine Zufallsergebnisse weil die Unterschiede zu klein sind? Wie sieht der Assember-Code davon aus?