Polymorphie und moderne Compiler

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

hab einen test unter win32 gemacht.

os: WinXP SP2
prozessor: Pentium D (3.4 GHz)
ram: 2 GB
compiler: g++ 3.4.5

Habe mal wegen Konrad Rudolphs Einwand bzgl. der kleinen Zeiten den max Wert auf 1e9 gestellt:

ohne optimierung, mit debug-info (-g):

virtual via ref: 1000000000 6.27763
static via ref : 1000000000 5.82477
inline via ref : 1000000000 5.73107
virtual via ptr: 1000000000 6.30886
static via ptr : 1000000000 5.65299
inline via ptr : 1000000000 5.66861

mit optimierung (-O2)

virtual via ref: 1000000000 5.88723
static via ref : 1000000000 3.76346
inline via ref : 1000000000 0.062464
virtual via ptr: 1000000000 5.91846
static via ptr : 1000000000 3.84154
inline via ptr : 1000000000 0.593408

mit optimierung (-O3)

virtual via ref: 1000000000 6.04339
static via ref : 1000000000 1.93638
inline via ref : 1000000000 1.93638
virtual via ptr: 1000000000 6.09024
static via ptr : 1000000000 1.93638
inline via ptr : 1000000000 1.93638

Wie tntnet schon sagte im Normalfall, reicht die Performance von virtual (1 Milliarde Aufrufe in ca. 6 Sekunden).

Würde mich mal interessieren wie lange Java/.NET für 1e9 einfache, virtuelle Aufrufe brauchen.

Wieder_zu_Faul schrieb:

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.

Wenn ich die Möglichkeit habe unter verschiedenen Schwänzen zu wählen, vergleiche ich sie auch

Artchi

Wenn ich die Möglichkeit habe unter verschiedenen Schwänzen zu wählen, vergleiche ich sie auch

Aber bitte nicht hier im C++ Forum. *brrr* Danke.

Im ernst, nicht schon wieder einen Java vs. C++ Thread. Nicht im ISO-C++-Forum!!!

hustbaer

Compilerbauer schrieb:

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.

Ich meinte "virtual inheritance", nur falls da jetzt ein Misverständnis besteht. Also nicht rein abstrakte Basisklassen.
Sowas halt:

class base {};
class derived : public virtual base {};

DDR-RAM

Bin mal an VC++ 2k5 rangekommen. (x86)
Mit PGO drüber gefahren ergab:

virtual via ref: 1000000000 1.7403
static via ref : 1000000000 1.07885
inline via ref : 1000000000 1.07864
virtual via ptr: 1000000000 1.80288
static via ptr : 1000000000 1.08437
inline via ptr : 1000000000 1.07547

also auch jeweils 10^9 Aufrufe. (Profiled wurde für 10^8)
Musste allerdings bisschen den Code modifizieren. ^^

Poste mal asm output noch dazu:
virtual via ref/ptr:

mov	ecx, DWORD PTR ?theA@A@@0V1@A
	mov	edi, eax
	mov	esi, 1000000000				; 3b9aca00H
	npad	6
$LL18@main:
	mov	eax, DWORD PTR [ecx]
	cmp	eax, OFFSET ?inc_v@A@@UAEXXZ		; A::inc_v
	jne	$LN22@main
;		taken 0(0%), not-taken 100000000(100%)
	add	DWORD PTR ?theA@A@@0V1@A+4, 1
$LN17@main:
	sub	esi, 1
	jne	SHORT $LL18@main
;		taken 99999999(99%), not-taken 1(0%)

zusätzlich noch weiter weg:

; Scenario dead code below
$LN22@main:

; 26   :   T("virtual via ref", a.inc_v(), a.get()); 

	mov	ecx, OFFSET ?theA@A@@0V1@A		; A::theA
	call	eax
	mov	ecx, DWORD PTR ?theA@A@@0V1@A
	jmp	$LN17@main

Das mit den Heuristiken ist damit für den MS VC++ belegt.
static/inline via ref/ptr:

mov	ecx, DWORD PTR ?theA@A@@0V1@A+4
	mov	edx, 1000000000				; 3b9aca00H
	npad	7
$LL15@main:
	add	ecx, 1
	sub	edx, 1
	jne	SHORT $LL15@main
;		taken 99999999(99%), not-taken 1(0%)
	mov	DWORD PTR ?theA@A@@0V1@A+4, ecx

Inline wird bei beiden durchgeführt, allerdings ist die Schleife lächerlich. Ob das auf real-existierenden Code auswirkungen hat kann ich nicht sagen. Können einige Compiler diese schleife komplett wegoptimieren und durch eine einzige mov instruction ersetzen?`

MfG
DDR-RAM

tntnet

Ich habe hier noch ein paar Ergebnisse. Diesmal auf Linux (Kubuntu 6.10, AMD64-3000, gcc 4.1.2):

ohne Optimierung:

virtual via ref  : 100000000 1.17056
static via ref   : 200000000 0.918881
inline via ref   : 300000000 0.864239
virtual via ptr  : 400000000 1.26863
static via ptr   : 500000000 0.863478
inline via ptr   : 600000000 0.942093
virtual auf stack: 100000000 0.863628
static auf stack : 200000000 0.864764
inline auf stack : 300000000 0.863548

mit -O2:

virtual via ref  : 100000000 0.361489
static via ref   : 200000000 0.358389
inline via ref   : 300000000 1.19209e-06
virtual via ptr  : 400000000 0.362769
static via ptr   : 500000000 0.358353
inline via ptr   : 600000000 9.53674e-07
virtual auf stack: 100000000 0.359503
static auf stack : 200000000 0.36071
inline auf stack : 300000000 0

und mit -O3:

virtual via ref  : 100000000 0.435069
static via ref   : 200000000 0.359825
inline via ref   : 300000000 0
virtual via ptr  : 400000000 0.358871
static via ptr   : 500000000 0.359128
inline via ptr   : 600000000 0
virtual auf stack: 100000000 0.365479
static auf stack : 200000000 0.358852
inline auf stack : 300000000 0

hier zeigt sich kaum ein Unterschied zwischen virtuellen und statischen Aufrufen. Inline-Aufrufe werden weg optimiert.

Ich bin bei 1e8 Aufrufen geblieben. Die Ergebnisse sind auch so gut reproduzierbar.

Die bisherigen Ergebnisse finde ich sehr Interessant und aufschlußreich. Ich wundere mich ein wenig, daß die beiden Compiler, die mir zur Verfügung stehen, die inline-Aufrufe vollständig weg optimieren können, aber die bisherigen Ergebnisse für VC++ darauf hindeuten, daß dieser es nicht kann. Beim Gcc sieht man doch deutlich eine Verbesserung von 3.x auf 4.1.x.

(ich bin übrigens auch dafür, daß wir hier nicht über andere Programmiersprachen her ziehen. Das tun wir oft genug. Und noch was an die Moderatoren: wie wäre es mit einem Flamewar-Forum?)

Tntnet