Forum: PC-Programmierung Alternative "Sprungtabelle" für Strukturen (C++)


von cppcoder (Gast)


Lesenswert?

Hallo,

ich möchte in einem std::vector eine Art Sprungtabelle mit Zeigern auf 
verschiedene Objekte machen und beim iterieren die enthaltene Funktion 
aufrufen. Ich könnte die Sache mit virtuellen Methoden machen aber 
wollte aus Interesse mal fragen, welche Alternativen es noch gäbe die 
beispielsweise mehr "low-level" und/oder performanter sind. Ich weiß 
"Premature Optimization Is the Root of All Evil" darum geht es mir auch 
gar nicht sondern mich würde einfach interessieren wie eine Alternative 
aussehen könnte. Ob diese schneller ist müsste man dann sowieso messen.

Ziel:
- Es gibt unterschiedliche structs die aber alle eine funktion mit 
gleichem Funktionsrumpf haben
- Es gibt Objekte dieser structs
- Es gibt ein vector welcher Zeiger auf diese Objekte speichern soll
- Der vector soll dann möglichst performant iteriert werden und die 
funktion des entsprechenden Objektes soll dabei aufgerufen werden

Ich habe auf Anhieb keine funktionierende Sache hinbekommen.
Anbei mal den ganz einfach gehaltenen und nicht funktionierenden 
Beispielcode (C++):
1
struct struct_test1
2
{
3
    double test;
4
    void aufruf(double &a)
5
    {
6
        test += a;
7
    }
8
};
9
10
struct struct_test2
11
{
12
    double test;
13
    void aufruf(double &a)
14
    {
15
        test = test + 2.222 / a;
16
    }
17
};
18
19
int main()
20
{
21
    struct_test1 t1;
22
    struct_test2 t2;
23
24
    std::vector<void*> voidvector;
25
    voidvector.emplace_back(&t1);
26
    voidvector.emplace_back(&t2);
27
28
    for(int i = 0; i != voidvector.size(); ++i)
29
    {
30
        voidvector[i].aufruf(i+5);
31
    }
32
}

Beim Aufruf der Funktion aufruf() wirft der compiler einen Fehler.
Ist es möglich die Sache so in der Art hinzubekommen, dass es 
funktioniert?
Vielleicht gibt es auch eine ganz andere Alternative? Ich hatte auch 
std::any probiert aber das hat auch nicht funktioniert. Ich glaube 
std::variant oder std::optional passt nicht zum Thema kann mich aber 
irren.

Wäre prima wenn jemand einen Tipp geben kann wie ich obigen Code zum 
laufen bekomme oder ob es vielleicht noch bessere Alternativen gibt.

Grüße

von nfet (Gast)


Lesenswert?

Warum speicherst du nicht einfach die Methoden?

von cppcoder (Gast)


Lesenswert?

Die Methode soll auf jeden Fall mit den Daten seines Objektes arbeiten, 
ich habe es mal versucht ein Zeiger direkt auf die Methode zu erstellen 
aber das habe ich nicht hinbekommen, bekomme da eine lvalue 
Fehlermeldung bei emplace_back.
1
struct_test1 t1;
2
struct_test2 t2;
3
4
std::vector<void(*)(double)> voidvector;
5
voidvector.emplace_back(&t1.aufruf());
6
voidvector.emplace_back(&t2.aufruf());
7
8
for(int i = 0; i != voidvector.size(); ++i)
9
{
10
   voidvector[i].aufruf();
11
}

von poly (Gast)


Lesenswert?

Erstell für die Klassen eine gemeinsame Basisklasse, die die virtuelle 
Methode "aufruf" enthält. Die abgleiteten Klassen überschreiben dann 
diese Methode. Der Vector ist vom Typ "Zeiger auf Basisklasse", sodass 
die Methode "aufruf" für alle Elemente aufgerufen werden kann.

Das Zauberwort für weiter Recherchen heißt "Polymorphie".

Viele Grüße

BTW: Enthält die Basisklasse nur „pure virtual“ Methoden, dann wird dies 
auch als Interface bezeichnet.

von cppcoder (Gast)


Lesenswert?

Hallo, das Konzept ist mir bekannt, auch das dies wohl der standard Weg 
ist. Was mich interessiert welche weitere Alternativen es für die Sache 
noch gäbe die beispielsweise mehr "low-level" und/oder performanter sind

von Ntldr -. (ntldr)


Lesenswert?

cppcoder schrieb:
> Die Methode soll auf jeden Fall mit den Daten seines Objektes arbeiten,
> ich habe es mal versucht ein Zeiger direkt auf die Methode zu erstellen
> aber das habe ich nicht hinbekommen, bekomme da eine lvalue
> Fehlermeldung bei emplace_back.
>
1
> voidvector.emplace_back(&t2.aufruf());

Kein Wunder. Du versuchst da ja auch die Adresse des Rückgabewertes von 
aufruf() in den vector zu emplacen. Das wird so nichts.

Du benötigst in deinem Vektor mindestens Objekt und Methode. Folgendes 
würde z.B. funktionieren: https://gcc.godbolt.org/z/EEcWmR

Den Umweg über die statische Methode könnte man je nach System noch 
umgehen, aber das ist dann schon längst nicht mehr Standardkonform.

von cppcoder (Gast)


Lesenswert?

Respekt danke! das hätte ich nicht ohne weiteres so hinbekommen.

Könnte man sagen das diese Lösung dann bei einer längeren iteration (und 
ggf auch mehrfachem aufruf der gleichen methode) performanter wäre als 
bei der klassischen Polymorphie? Oder läuft das auf das selbe hinaus was 
den "overhead" angeht?
Ich hatte mal aufgeschnappt, dass Polymorphie etwa 25% teurer ist als 
ein klassischer Funktionsaufruf.
Performancedisskusionen sind natürlich immer ein bisschen gefährlich, 
würde mich aber trotzdem interessieren ;-)

von Ntldr -. (ntldr)


Lesenswert?

Bei virtuellen Methoden hast du zwei weitere Indirektion im Aufruf, da 
zunächst die Adresse der Funktion aus der vtable geladen werden muss.

Konkrete Zahlen habe ich nicht. Die 25% hören sich für mich aber stimmig 
an. Die 25% Overhead hören sich im ersten Moment viel an, aber das würde 
mich nicht beunruhigen. Funktionsaufrufe sind sehr stark in Hardware 
optimiert. Das was du innerhalb einer Funktion machst, braucht 
höchstwahrscheinlich eh deutlich länger als der Aufruf selbst.

Im Disassembly kann man ganz gut sehen was die CPU bei virtuellen 
Funktionen extra leisten muss:
1
struct A
2
{
3
    virtual void a();
4
    void b();
5
};
1
// Anmerkung: rbx enthält einen Pointer auf ein A.
2
// Aufruf von a
3
  mov rbx, rdi             // Objekt in rbx verschieben
4
  mov rax, qword ptr [rdi] // rax = *rdi (-> erstes Feld aus A holen. Hier vtable
5
  call qword ptr [rax]     // Aufruf von *rax (-> erstes Feld der Vtable, also a())
6
// Aufruf von b
7
  mov rdi, rbx             // Objekt in rbx verschieben
8
  call A::b()              // b() Aufrufen
Wie du siehst ist für a zunächst notwendig auf das Objekt zuzugreifen 
(um die Adresse der vtable zu erhalten). Danach muss dann noch die 
vtable geladen werden.

: Bearbeitet durch User
von Mark B. (markbrandis)


Lesenswert?

cppcoder schrieb:
> Was mich interessiert welche weitere Alternativen es für die Sache noch
> gäbe die beispielsweise mehr "low-level" und/oder performanter sind

Haben wir hier etwa einen klassischen Fall von "premature optimization"? 
:-)

Im Ernst: Wenn es auf die klassische Art allemal schnell genug 
ausgeführt wird, warum dann nach einer Alternative suchen? Für nicht 
genutzte Rechenzeit gibt es kein Geld zurück.

: Bearbeitet durch User
von nfet (Gast)


Lesenswert?

Ntldr -. schrieb:
> cppcoder schrieb:
> Die Methode soll auf jeden Fall mit den Daten seines Objektes arbeiten,
> ich habe es mal versucht ein Zeiger direkt auf die Methode zu erstellen
> aber das habe ich nicht hinbekommen, bekomme da eine lvalue
> Fehlermeldung bei emplace_back.
>
>> voidvector.emplace_back(&t2.aufruf());
>
> Kein Wunder. Du versuchst da ja auch die Adresse des Rückgabewertes von
> aufruf() in den vector zu emplacen. Das wird so nichts.
> Du benötigst in deinem Vektor mindestens Objekt und Methode. Folgendes
> würde z.B. funktionieren: https://gcc.godbolt.org/z/EEcWmR
>
> Den Umweg über die statische Methode könnte man je nach System noch
> umgehen, aber das ist dann schon längst nicht mehr Standardkonform.

Noch eine Anmerkung: std::function statt std::pair kannst du dir auch 
mal ansehen.

von Bernd K. (prof7bit)


Lesenswert?

cppcoder schrieb:
> Hallo, das Konzept ist mir bekannt, auch das dies wohl der standard Weg
> ist. Was mich interessiert welche weitere Alternativen es für die Sache
> noch gäbe die beispielsweise mehr "low-level" und/oder performanter sind

Der Compiler wird rausholen was rauszuholen geht. Viel mehr ist 
wahrscheinlich kaum drin und wahrscheinlich auch der Mühe nicht wert 
oder wird zu Code führen der beim Leser WTF??-Reaktionen hervorruft.

von Dirk K. (merciless)


Lesenswert?

Schau dir mal das Command-Pattern an. Funktoren ist das
2. Stichwort, dass mir einfällt.

Und ich würde erstmal eine saubere Lösung implementieren
und mir erst dann Gedanken um die Performance machen,
wenn dies wirklich notwendig ist.

merciless

: Bearbeitet durch User
von Oliver S. (oliverso)


Lesenswert?

Ntldr -. schrieb:
> Wie du siehst ist für a zunächst notwendig auf das Objekt zuzugreifen
> (um die Adresse der vtable zu erhalten). Danach muss dann noch die
> vtable geladen werden.

Wenn der Compiler allerdings zur Compilezeit ermitteln kann, welche 
Funktion da letztdendlich aufgerufen wird, kann der das alles weglassen, 
und die gewünschte Funktion direkt aufrufen, oder im Idealfall sogar 
inlinen.

Oliver

von cppcoder (Gast)


Lesenswert?

Danke die ganannten Sachen werde ich mir auch nochmal angucken.
Was ich noch gefunden hatte ist CRTP (curiously recurring template 
pattern), dies scheint die "schnelle" Alternative zu Polymorphie zu sein 
ohne virtual functions und pointer tables.

https://eli.thegreenplace.net/2013/12/05/the-cost-of-dynamic-virtual-calls-vs-static-crtp-dispatch-in-c

https://stackoverflow.com/questions/4173254/what-is-the-curiously-recurring-template-pattern-crtp

von Oliver S. (oliverso)


Lesenswert?

Wie gesagt, wenn zur Compilezeit schon feststeht, welche Funktion 
aufgerufen wird, optimiert der Compiler auch virtuelle Funktionsaufrufe 
weg. Zur Laufzeit macht das in dem Fall wenig aus.

CRTP ist halt ein anders Programmierparadigma. Da hat C++ ja inzwischen 
einige im Angebot.

Oliver

von Vincent H. (vinci)


Lesenswert?

Je nach Anwendung könnte man das ganze auch etwas funktionaler gestalten 
und die Objekte etwa in eine Tuple packen:
https://gcc.godbolt.org/z/aBfwcM

Auf Devirtualisierung würde ich mich im Ernstfall nicht verlassen. 
Natürlich muss man das ursprüngliche Probleme aber erstmal messen bevor 
man irgendwas anderes tut. In 99% aller Fälle wird ein virtueller Aufruf 
wohl kein Bottleneck darstellen...

/edit
ups falscher link

: Bearbeitet durch User
von Oliver S. (oliverso)


Lesenswert?

Vincent H. schrieb:
> In 99% aller Fälle wird ein virtueller Aufruf
> wohl kein Bottleneck darstellen...

Sieht so aus...

https://gcc.godbolt.org/z/rq0zei

Oliver

von Arc N. (arc)


Lesenswert?

Eine andere Möglichkeit wären Lambdas...
1
typedef std::function<void(double a)> func_t;
2
3
struct struct_test1 {
4
  double test;
5
6
  func_t aufruf = [this](double a) {
7
    test += a;
8
  };
9
10
    struct_test1() : test(1234.5) { }
11
};
12
13
struct struct_test2 {
14
  double test;
15
16
  func_t aufruf = [this](double a) {
17
    test = test + 2.222 / a;
18
  };
19
20
    struct_test2() : test(2345.6) { }
21
};
22
23
int main(int argc, char* argv[]) {
24
  struct_test1 t1;
25
  struct_test2 t2;
26
  std::vector<func_t> vec;
27
  vec.emplace_back(t1.call);
28
  vec.emplace_back(t2.call);
29
30
  for (auto i = 0; i < vec.size(); i++) {
31
    vec[i](i + 5);
32
  }
33
}

von cppcoder (Gast)


Lesenswert?

Danke, die sieht schick aus die Lösung.
Lambdas haben auch den Ruf den Overhead zu verringern ;)

von Mark B. (markbrandis)


Lesenswert?

cppcoder schrieb:
> Overhead zu verringern

Ich bezweifle nach wie vor, dass das überhaupt ein Problem darstellt.

Von welcher Hardware/Zielplattform reden wir hier denn eigentlich? 
Wurden Messungen der Performance durchgeführt? Oder wie kommt man auf 
die Idee, dass man an der Stelle etwas optimieren müsste?

von Oliver S. (oliverso)


Lesenswert?

cppcoder schrieb:
> Lambdas haben auch den Ruf den Overhead zu verringern ;)

Keine Ahnung, woher du deine urban legends alle herbekommst, aber wie 
schon mehrfach gesagt wurde, sind alle deine Vorstellungen zu dem Thema 
irgendwie seltsam.

Oliver

von cppcoder (Gast)


Lesenswert?

Ihr habt natürlich recht zu 99% der Fälle sind solche Umwege nicht nötig 
und man nutzt einfach die Polymorphie. Trotzdem sind die anderen Wege 
total interessant. Ich fand es ursprünglich einfach spannend wieso 
Pointer die nur auf Funktionen zeigen leichter in so eine Vectorliste zu 
packen sind als wenn zu der Funktion noch individuelle Daten gehören. Am 
Ende ist es aber schon logisch, denn Strukturen mit Daten sowie 
Funktionen können sich vom Aufbau weit mehr unterscheiden als wenn es 
nur um Funktionen geht, da bei einer Struktur zum Scope der Funktion 
immer noch Daten gehören. Eine gewisse Indirektion ist also gar nicht zu 
vermeiden. Vermutlich spielt auch eine Rolle wie die Funktion/Methode 
angesprochen wird, man kann bei unterschiedlichen Strukturen 
beispielsweise nicht davon ausgehen, dass die Einsprungadressen der 
Funktionen vergleichbar sind, da die Strukturen ganz unterschiedlich 
viele Daten besitzen können, dort also Bytes und ggf padding alleine 
schon große Unterschieden macht, was dazu führt, dass man es nicht mit 
dem Zeiger auf eine "nur Funktion" vergleichen kann.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.