mikrocontroller.net

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


Autor: cppcoder (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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++):
struct struct_test1
{
    double test;
    void aufruf(double &a)
    {
        test += a;
    }
};

struct struct_test2
{
    double test;
    void aufruf(double &a)
    {
        test = test + 2.222 / a;
    }
};

int main()
{
    struct_test1 t1;
    struct_test2 t2;

    std::vector<void*> voidvector;
    voidvector.emplace_back(&t1);
    voidvector.emplace_back(&t2);

    for(int i = 0; i != voidvector.size(); ++i)
    {
        voidvector[i].aufruf(i+5);
    }
}

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

Autor: nfet (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum speicherst du nicht einfach die Methoden?

Autor: cppcoder (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.
struct_test1 t1;
struct_test2 t2;

std::vector<void(*)(double)> voidvector;
voidvector.emplace_back(&t1.aufruf());
voidvector.emplace_back(&t2.aufruf());

for(int i = 0; i != voidvector.size(); ++i)
{
   voidvector[i].aufruf();
}

Autor: poly (Gast)
Datum:

Bewertung
2 lesenswert
nicht 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.

Autor: cppcoder (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Ntldr -. (ntldr)
Datum:

Bewertung
0 lesenswert
nicht 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.
>
> 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.

Autor: cppcoder (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 ;-)

Autor: Ntldr -. (ntldr)
Datum:

Bewertung
0 lesenswert
nicht 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:
struct A
{
    virtual void a();
    void b();
};
// Anmerkung: rbx enthält einen Pointer auf ein A.
// Aufruf von a
  mov rbx, rdi             // Objekt in rbx verschieben
  mov rax, qword ptr [rdi] // rax = *rdi (-> erstes Feld aus A holen. Hier vtable
  call qword ptr [rax]     // Aufruf von *rax (-> erstes Feld der Vtable, also a())
// Aufruf von b
  mov rdi, rbx             // Objekt in rbx verschieben
  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
Autor: Mark B. (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht 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
Autor: nfet (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Bernd K. (prof7bit)
Datum:

Bewertung
1 lesenswert
nicht 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.

Autor: Dirk K. (merciless)
Datum:

Bewertung
1 lesenswert
nicht 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
Autor: Oliver S. (oliverso)
Datum:

Bewertung
1 lesenswert
nicht 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

Autor: cppcoder (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Oliver S. (oliverso)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Vincent H. (vinci)
Datum:

Bewertung
0 lesenswert
nicht 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
Autor: Oliver S. (oliverso)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Arc N. (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eine andere Möglichkeit wären Lambdas...
typedef std::function<void(double a)> func_t;

struct struct_test1 {
  double test;

  func_t aufruf = [this](double a) {
    test += a;
  };

    struct_test1() : test(1234.5) { }
};

struct struct_test2 {
  double test;

  func_t aufruf = [this](double a) {
    test = test + 2.222 / a;
  };

    struct_test2() : test(2345.6) { }
};

int main(int argc, char* argv[]) {
  struct_test1 t1;
  struct_test2 t2;
  std::vector<func_t> vec;
  vec.emplace_back(t1.call);
  vec.emplace_back(t2.call);

  for (auto i = 0; i < vec.size(); i++) {
    vec[i](i + 5);
  }
}

Autor: cppcoder (Gast)
Datum:

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

Autor: Mark B. (markbrandis)
Datum:

Bewertung
1 lesenswert
nicht 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?

Autor: Oliver S. (oliverso)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: cppcoder (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.