Polymorphie und moderne Compiler

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?

tntnet

CStoll schrieb:

@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.

Ok. Ich hatte das weggelassen, da ich das nicht für relevant halte, aber Du hast schon recht, daß man das natürlich auch verifizieren könnte. Also habe ich folgende Änderungen gemacht:

[] in a.h den Konstruktor public gemacht
[] eine Zusätliche Deklaration "A s;"
[*] folgende neue Tests:

T("virtual auf stack", s.inc_v(), s.get());
  T("static auf stack", s.inc_s(), s.get());
  T("inline auf stack", s.inc_i(), s.get());

Die Resultate:

ohne Optimierung:
virtual auf stack: 100000000 1.04899
static auf stack: 200000000 1.84272
inline auf stack: 300000000 3.08779

mit -O2:
virtual auf stack: 100000000 0.685513
static auf stack: 200000000 0.689291
inline auf stack: 300000000 9.53674e-07

und mit -O5:
virtual auf stack: 100000000 1.19209e-06
static auf stack: 200000000 9.53674e-07
inline auf stack: 300000000 1.19209e-06

An der Stelle fällt mir auf, daß der reset-Aufruf falsch ist. Aber das ist ja egal. Merkwürdig ist, daß ohne Optimierung die Geschwindigkeit genau verdreht ist. Ansonsten wird der virtuelle Aufruf durch eine statischen Aufruf ersetzt.

Konrad Rudolph schrieb:

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?

Unrealistisch? Das geht aus der Konsole direkt über die Zwischenablage in den Browser. Mehrfache Wiederholungen bringen sehr ähnliche Ergebnisse.

Ein Resümee für mich (und Bestätigung meiner bisherigen Vorgehensweise): Programmiere so, wie es richtig ist und überlasse dem Compiler die Optimierung (zumindest auf dieser Ebene). Algorithmen sind Aufgabe des Entwicklers, die einzelnen Bits und Bytes an die richtige Stelle zu schieben, macht der Compiler.

Höhere Optimierungslevel verlängern aber die Compilezeit beträchtlich, so daß man beim Entwickeln sparsam damit umgehen sollte.

Tntnet

Konrad Rudolph

tntnet schrieb:

Konrad Rudolph schrieb:

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?

Unrealistisch? Das geht aus der Konsole direkt über die Zwischenablage in den Browser. Mehrfache Wiederholungen bringen sehr ähnliche Ergebnisse.

Na ja, ich wollte nicht behaupten, dass Du die Ergebnisse fälschst sondern dass der Compiler entweder Deine Inline-Anweisung missachtet oder dass die Ergebnisse einfach so gering unterschiedlich sind, dass die angezeigten Unterschiede durch andere Faktoren zustande kommen.

In jedem Fall halte ich solche Ergebnisse für unzuverlässig solange man nicht das tatsächliche Ergebnis des Compilers anschaut --> als den Assemblercode. Die Zahlen weisen hier z.B. deutlich darauf hin, dass inc_i eben *nicht* ge-inlined wird. Wie kann man diese Ergebnisse sonst erklären?

Wie Konrad schon sagt, solche Ergebnisse als signifikante Benchmark-Ergebnisse zu sehen wäre falsch.
Jedoch finde ich zeigen sie sehr gut das Compiler nicht spezifiziert sind wie was zu Optimieren ist bzw wie sie vorgehen, rein sprachlich bedingt.
Das fängt an das sie Übergabewerte in der Reinfolge von links nach rechts oder von rechts nach links erstellen können, das sie Rechnungen mit Konstanten zur Kompilezeit ausrechen oder nicht usw... Auch das inline Schlüsselwort ist leider nicht "zuverlässig" da es nur als eventuelle Optimierung gedacht ist, der Compiler jedoch nicht verplichtet ist es umzusetzten. Im Gegenzug kann er aber jede Funktion als inline erstellen auch wenn diese nicht als solche gekennzeichent ist.

Ganz im Gegensatz zum Java(Sun) Standart, dort steht genau beschrieben wie alles zu geschehen hat. Ob sich da alle Compiler und VM Hersteller dran halten ist wieder eine andere Sache.

Auch muss ich Tntnet zustimmen, programmiere so wie es (für das Team/Dich) richtig ist und überlass dem Compiler den Rest (Bitoptimierung).

Falls man wirklich Optimieren muss/will sollte man sich ohnehin nur auf den Code beschrenken der Performance relevant ist. Was Erfahrungsgemäß höchstens 1/4 ist, den Rest kann man getrost so lassen wie er ist.

Natürlich kosten virtuelle Aufrufe mehr Zeit als statische oder inline Derivate , jedoch würde ich als letztes anfangen diese zu Optimieren. Was die virtuellen Basisklassen betrifft sollte man normalerweise schon eine Menge Performance sparen wenn man sie als reines Interface deklariert. (Schon komisch das Java genau das macht )

Zum Schluß möchte ich noch loswerden das ich sowas schon als "Schwanzvergleichen" betrachte wenn man Java und C++ Performance mäßig gegenüberstellt. Java ist nicht die schnellste Sprache doch dafür wurde sie auch nicht konzepiert. Wie dem auch sei, ich zieh mich hier auch besser zurück bevor mich hinreißen lasse.

Baracke

PS: Das mit den Optimierungen bezüglich Compilern beruht nur auf sogenannten erlesem Wissen weniger auf überprüften