Moderne Compiler und Optimierung virtueller Member-Funktionen

[Finnegan]

Hi!

Ich frage mich gerade wie pfiffig aktuelle Compiler dabei sind herauszufinden, ob sie auf Virtual Dispatch verzichten können.
Angenommen ich habe eine baumförmige Vererbungshierarchie mit virtuellen Funktionen:

struct Basis
{
    virtual void f() { ... };
};

struct A : Basis
{
   ...
};

struct B : A
{
   ...
};

struct Blatt1 : B
{
   void f() override { ... };
};

struct Blatt2 : Basis
{
   void f() override { ... };
};

... wenn ich nun z.B. über Blatt* die funktion f() aufrufe, kann ich dann im Allgemeinen davon ausgehen,
dass der Compiler im generierten Code auf einen vtable-Lookup verzichtet und die Blatt::f() sogar für Inlining heranzieht?
Schließlich sind die Blätter ja bereits "most derived" (gibts dafür eigentlich nen deutschen Audruck?),
und somit müssen statischer und dynamischer Typ zwangsläufig übereinstimmen.

Ich frage das gerade ohne konkretes Problem, lediglich aus allgemeinen Designüberlegungen heraus.
Bei grafischen Sachen hat man oft mit schlanken Operationen auf vielen solcher Objekte zu tun,
wo der virtual-Overhead durchaus einen Unterschied machen kann. Gleichzeitig wäre es jedoch praktisch,
an anderer Stelle, jenseits des "heißen Pfades", von der Polymorphie profitieren zu können (z.B. via Base* ).
Ich habe mich bisher etwas schwer getan etwas definitives zu recherchieren und wollte mal eure Meinung dazu hören :).

Gruss,
Finnegan

[Ruvi]

Ich meine irgendwo gelesen zu haben, dass ein VTABLE lookup aus einer assembler instruction besteht, falls dem so ist wuerde ich mich wundern, wenn man auf Compiler Seite Aufwaende betreiben wuerde um den noch einzusparen.

P.S.: Guck mal in deine Mails oder schau mal wieder im TS vorbei.

[Onkki]

Genau diese Frage hatte ich mir letztens auch einmal gestellt.

Sehr guter Link!
http://hacksoflife.blogspot.de/2007/04/c-objects-part-8-cost-of-virtual.html

Benjamin Supnik schrieb:

[...]
So a virtual method is more expensive than a function pointer, by one memory indirection. If you wanted to optimize this out, you'd put function pointers into the object itself, and pay for the decreased memory chaining with larger object size. The vtable is a layer of indirection.
[...]

Generelle Informationen. Fand ich hilfreich.
http://stackoverflow.com/questions/18404988/performance-hit-of-vtable-lookup-in-c

[Mechanics]

Das beantwortet alles nicht die ursprüngliche Frage. Und ja, virtuelle Funktionsaufrufe zu optimieren könnte sich schon lohnen, je nachdem, wieviel die Funktion macht könnte der Aufruf teurer sein, als die Funktion.

Ich denke, in den meisten (sinnvollen) Fällen ist es unmöglich, virtuelle Funktionsaufrufe durch statische zu ersetzen.

Base * b;
if (userInput)
b = new A();
else
b = new B();
b->foo();

Hier kann der Compiler nicht wissen, ob b A oder B sein wird.

[hustbaer]

Leider kann ich die Frage ob bzw. wie gut aktuelle C++ Compiler "devirtualization" können auch nicht beantworten.

Allerdings...
Virtuelle Aufrufe möchte man deswegen loswerden, weil man im non-virtual Fall Inlining machen kann. Und durch Inlining kann es sein dass ein grösserer Haufen Code zu nichts oder fast nichts zusammenfällt. z.B. weil beim Aufruf bestimmte Argumente konstant sind.

Bzw. auch der Aufruf von leeren virtuellen Funktionen - der dann mit devirtualization dann ganz entfernt werden kann.

Oder ... manche Compiler brauchen auch noch ein wenig "Bookkeeping" Code in Funktionen die Exceptions werfen können (bzw. wo Unterfunktionen aufgerufen werden die Exceptions werfen können). Mit Inlining kann der Compiler dann oft sehen dass die aufgerufene Funktion eh keine Exceptions werfen kann, und den entsprechenden Bookkeeping-Code weglassen.

In Summe kann das schätze ich schon ein bisschen was ausmachen. Auf jeden Fall mehr als nur "1 load weniger".

@Mechanics
Mit Profile guided Optimization kann der Compiler u.U. sehen dass ein virtueller Aufruf an einer bestimmten Stelle zu 70% in Klasse A landet und zu 25% Funktion in Klasse B - und nur zu 5% woanders. Der Compiler könnte dann folgenden Code generieren:

if (p->vtable == A::vtable)
{
    // Inline Version von A::Foo
}
else if (p->vtable == B::vtable)
{
    // Inline Version von B::Foo
}
else
    p->Foo(args);

[Mechanics]

hustbaer schrieb:

@Mechanics
Mit Profile guided Optimization kann der Compiler u.U. sehen dass ein virtueller Aufruf an einer bestimmten Stelle zu 70% in Klasse A landet und zu 25% Funktion in Klasse B - und nur zu 5% woanders. Der Compiler könnte dann folgenden Code generieren:

if (p->vtable == A::vtable)
{
    // Inline Version von A::Foo
}
else if (p->vtable == B::vtable)
{
    // Inline Version von B::Foo
}
else
    p->Foo(args);

Das wäre interessant... Schon mal ausprobiert, macht der Compiler (VS) sowas tatsächlich? Hab mich noch nie getraut, das mit unserer Software auszuprobieren. Unsere Software ist halt relativ groß... So groß, dass viele Tools oft eh schon aussteigen, z.B. Debugger oder Profiler. Aber für einzelne Dlls und Usecases könnte man das vielleicht tatsächlich mal probieren.

[hustbaer]

Zu GCC 5 hab ich folgendes gefunden: https://gcc.gnu.org/gcc-5/changes.html

The devirtualization pass was significantly improved by adding better support for speculative devirtualization and dynamic type detection. About 50% of virtual calls in Firefox are now speculatively devirtualized during link-time optimization.

Zu Visual Studio hab ich folgenden Bug-Report (*g*) gefunden: https://connect.microsoft.com/VisualStudio/feedback/details/812124/code-gen-bug-incorrect-devirtualization-and-inlining-when-building-with-ltcg

As discussed in http://www.youtube.com/watch?feature=player_detailpage&v=3MRxucTXPdw#t=2215 the VS 2013 compiler will speculatively devirtualize and inline function calls. (...)

VS scheint also Devirtualization zu machen. Wie gut ist wieder ne andere Frage

[Finnegan]

hustbaer schrieb:

Zu GCC 5 hab ich folgendes gefunden: https://gcc.gnu.org/gcc-5/changes.html
...
VS scheint also Devirtualization zu machen. Wie gut ist wieder ne andere Frage

Das klingt auf eden Fall vielversprechend. Wenn das sogar "spekulativ" gemacht wird, sollten besonders offensichtliche Fälle ja gut erkannt werden.
Allerdings bin ich gerade mit meiner ursprünglichen Annahme ans Zweifeln gekommen, dass es bei stärksten abgeleiteten (kann man das so nennen?) Typen eigentlich immer möglich sein sollte, dass der Compiler schon den dynamischen Typen bestimmen kann:
So wie ich das sehe kann der Compiler gar nicht allen Code kennen, in denen die Basisklasse abgeleitet werden könnte. Ich glaube ich habe irgendwann sogar schonmal einer Funktion einer dynamischen Bibliothek einen Basisklassen-Pointer auf eine im Client-Programm abgeleitete Klasse übergeben (bin mir nicht mehr ganz sicher, aber es ist denke ich machbar). In so einem Fall wäre von einem "most derived"-Typen beim kompilieren der Bibliothek auszugehen natürlich keine todsichere Wahl.

Danke jedenfalls bisher für die erhellenden Antworten

Finnegan

[hustbaer]

Dass das ganze wesentlich schlechter funktioniert als z.B. in Java, wo der (JIT-)Compiler es einfach zur Laufzeit machen kann, mit den konkreten Typen die halt wirklich vorkommen, ist klar.
Aber es geht ein bisschen was.
Je nach Programm mehr oder weniger viel.

[Nathan]

Bezüglich deiner Orginalfrage, ob virtuelle Memberfunktionen devirtualized werden, wenn Aufruf über Blattklassen stattfindet:
Folgender Code:

struct base
{
  virtual int foo() = 0;
};

struct derived : base
{
	int foo() override {return 1;}
};

int func(derived *ptr)
{
	return ptr->foo();
}

Ohne Optimierungen:

func(derived*):
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	movq	(%rax), %rax
	movq	(%rax), %rax
	movq	-8(%rbp), %rdx
	movq	%rdx, %rdi
	call	*%rax
	leave
	ret

Ich bin kein Assembler Experte, aber das ganze movq Zeugs sieht doch stark nach VTable aus. Quelle: http://goo.gl/IX6EBX
Machen wir mal O3 draus:

func(derived*):
	movq	(%rdi), %rax
	movq	(%rax), %rax
	cmpq	derived::foo(), %rax
	jne	.L5
	movl	$1, %eax
	ret
.L5:
	jmp	*%rax

Wird devirtualized, aber nicht geinlined.
Glücklicherweise gibt es seit C++11 das Keyword final, was dem Compiler mitteilt, dass eine Funktion nicht weiter überschrieben wird, bzw. eine Klasse nicht Basisklasse ist.
Wenden wir das doch mal an, ohne Optimierungen:

func(derived*):
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	movq	%rax, %rdi
	call	derived::foo()
	leave
	ret

Der Aufruf selber ist ohne VTable und identisch zu der O3 Version, auch ohne Optimierungen (!).
Aktiviert man nun auch noch Optimierungen:

func(derived*):
	movl	$1, %eax
	ret

Wird geinlined: http://goo.gl/ukAsll

TL;DR: Nutz final und der Compiler kriegts auf jeden Fall hin.

[hustbaer]

Nathan schrieb:

Machen wir mal O3 draus:

func(derived*):
	movq	(%rdi), %rax
	movq	(%rax), %rax
	cmpq	derived::foo(), %rax
	jne	.L5
	movl	$1, %eax
	ret
.L5:
	jmp	*%rax

Wird devirtualized, aber nicht geinlined.

Und wie das geinlined wurde.
Wo siehst du denn einen call?
Ich sehe da nur

jne    .L5                     Jump if Not Equal -> bei L5 geht's weiter wenn doch andere Klasse
                                   Ansonsten:
    movl   $1, %eax                1 nach eax (=Returnwert) kopieren
    ret                            Return

[Finnegan]

Nathan schrieb:

TL;DR: Nutz final und der Compiler kriegts auf jeden Fall hin.

Hey cool das final hatte ich ja gar nicht mehr auf dem Radar. Hätte geglaubt dass es dafür nur wenige sinnvolle Anwendungen gibt, aber wenn ich das so sehe kann ich mir sogar vorstellen dass diese Optimierung einer der Hauptgründe dafür war.
Alle Versionen von Clang und GCC, die C++11 unterstützen scheinen das zu inlinen. Wirklich nett. Der Vollständigkeit halber habe ich es hier auch grad nochmal mit Visual C++ (2013) getestet:

cl.exe Version 18.00.31101, Full Optimization (/Ox), Inlining: Any Suitable (/Ob2)

int func(derived *ptr)
{
    return ptr->foo();
00007FF66FFF1040 B8 01 00 00 00       mov         eax,1  
}
00007FF66FFF1045 C3                   ret

Nett ;). Wenn man also final richtig einsetzt, kann man also auch an performancekritischen Stellen virtuelle Funktionen aufrufen (meine Gedanken gehen da z.B. in Richtung massenhafte Kollisions-/Physik-/Partikelobjekte in einem Spieleprojekt), ohne auf Polymorphie-Abstraktion verzichten zu müssen (bzw. umständlich drumherum zu arbeiten). Einziger Overhead ist in dem Fall der Speicher für den vtable-Pointer.

Danke,
Finnegan

[Finnegan]

hustbaer schrieb:

jne    .L5                     Jump if Not Equal -> bei L5 geht's weiter wenn doch andere Klasse
                                   Ansonsten:
    movl   $1, %eax                1 nach eax (=Returnwert) kopieren
    ret                            Return

Ah... ich sehe, da scheinst du ja mit deinem vorherigen Post den richtigen riecher gehabt zu haben:

hustbaer schrieb:

if (p->vtable == A::vtable)
{
    // Inline Version von A::Foo
}
else if (p->vtable == B::vtable)
{
    // Inline Version von B::Foo
}
else
    p->Foo(args);

Sieht so aus als würden die Compiler tatsächlich auch dann versuchen zu inlinen, wenn der dynamische Typ unbekannt ist. Tippe mal das ist stark von der Komplexität der Vererbungshierarchie abhängig.
Praktisch dass die Compiler so ehrgeizig sind, da kann man sich mehr aufs Programmieren konzentrieren anstatt sich wegen solcher Mikro-Optimierungen nen Kopf zu machen ;).

Finnegan

[hustbaer]

ps: "wenn doch andere Klasse" in meinem Beitrag ist falsch. Er checkt ja direkt den vtable Slot (nicht den vtable Pointer). Er checkt also wirklich die Funktion, nicht die Klasse. Geht also auch mit abgeleiteten Klassen die bloss foo() nicht nochmal überschreiben.
Ein indirekter Load mehr, dafür höhere Trefferwahrscheinlichkeit in vielen Fällen.