Forum: Compiler & IDEs Overhead Funktionsaufruf über Pointer


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Walter T. (nicolas)


Bewertung
-1 lesenswert
nicht lesenswert
Hallo zusammen,

ich habe eine Funktionalität, die sich am einfachsten über einen virtual 
function table, also ein struct mit Funktionszeigern realisieren ließ. 
(Die Alternative wäre eine switch-case-Orgie gewesen.)

Das struct ist natürlich nicht konstant, da die Funktionszeiger zur 
Laufzeit ausgetauscht werden.

Jetzt stelle ich mir die Frage: Welchen Overhead bezahle ich für diesen 
Komfort? Aus den kurzen Abschnitten des Assembler-Listings, die mir der 
Debugger zur Verfügung stellt, werde ich nicht schlau. Ich schätze auch, 
dass die Haupt-Nachteile erst in der Link-Time-Optimization zum Tragen 
kommen.

Gibt es da Daumenregeln für den Overhead auf den ARM Cortex M3/M4 ?

Viele Grüße
W.T.

von Frank M. (ukw) (Moderator) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
Walter T. schrieb:
> Welchen Overhead bezahle ich für diesen Komfort?

Rufe doch mal eine Funktion 1.000.000.000 mal direkt auf, dann nochmal 
über ihren Pointer und miss die Zeit.

von Nop (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Walter T. schrieb:

> Jetzt stelle ich mir die Frage: Welchen Overhead bezahle ich für diesen
> Komfort?

Je nachdem, wie der switch vom Compiler gerade umgesetzt wird, sogar 
weniger. Mit Glück macht der Compiler auch eine Lookup-Tabelle draus, 
aber das ist nicht garantiert. Im schlimmsten Fall änderst Du eine 
irrelevante Kleinigkeit, und auf einmal macht er stattdessen eine 
if-then-else-Kette.

Der Tabellenindex muß in ein Register R_a geladen werden. Außerdem muß 
die Adresse der Tabelle in ein anderes Register R_b geladen werden.

Danach lädt man das, was in der Tabelle steht, in ein Register. Der 
LDR-Befehl kann bereits selber den Shift, den man braucht, weil Pointer 
ja 4 Byte haben. Also etwas wie R_c = R_b[Ra << 2].

Dann der normale Funktionsaufruf via BLX, zusätzlich evtl. noch Register 
sichern.

Der Overhead ist hierbei klein, denn das Laden der Tabellenadresse aus 
dem Flash ist genauso schnell wie direkte Laden einer Funktionsadresse 
bei einem direkten Funktionsaufruf. Das BLX und Registersichern hätte 
man auch so.

Man hat also einmal den case-Eintrag in ein Register zu laden und 
außerdem einen LDR in der Tabelle, was allerdings kein Flash-Zugriff 
ist, sondern RAM und somit ohne Waitstates.

von Nop (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Nop schrieb:
> das Laden der Tabellenadresse aus
> dem Flash ist genauso schnell wie direkte Laden einer Funktionsadresse
> bei einem direkten Funktionsaufruf.

Ergänzung: Beides kann, je nach Compiler, ohne Wartezeit für den 
Flashzugriff gehen, weil es Konstanten sind, die zur Linktime bekannt 
sind. Damit würde ich erwarten, daß das über den ICache abgefackelt 
wird, also effektiv ohne Waitstates.

Allerdings kann der Compiler u.U. den Funktionsaufruf auch inlinen, und 
dann springt er nicht unter Verlust des Icache im Flash herum. Beim 
Branch über die Tabelle geht das nicht, so daß u.U. ein paar Wartezyklen 
zusätzlich anfallen.

von Jim M. (turboj)


Bewertung
1 lesenswert
nicht lesenswert
Nop schrieb:
> dann springt er nicht unter Verlust des Icache im Flash herum.

Ähm:

Walter T. schrieb:
> auf den ARM Cortex M3/M4 ?

Die haben keinen eigenen I-Cache.

Das scheinbar simple Testen über..

Frank M. schrieb:
> Rufe doch mal eine Funktion 1.000.000.000 mal direkt auf, dann nochmal
> über ihren Pointer und miss die Zeit.

..kann auch schief gehen, denn ein optimierender Compiler zieht IMO das 
Laden des Pointers in ein Register als Invariante aus der Schleife raus.

Aber normalerweise ist der Unterschied nur einmal Register aus Speicher 
laden, also höchstens eine Handvoll Takte zusätzlich.

Probleme gäbe es nur wenn der Optimizer keine freien Register mehr hatte 
und nun zuätzlichen Code erzeugt um eins frei zu räumen.

von A. S. (achs)


Bewertung
-1 lesenswert
nicht lesenswert
Walter T. schrieb:
> Die Alternative wäre eine switch-case-Orgie gewesen.)

die Funktionszeiger selber haben praktisch 0 Overhead. Statt Jump to 
Adresse 0xyz ein Jump to (Inhalt von 0xyz)

von Joerg W. (joergwolfram)


Bewertung
-1 lesenswert
nicht lesenswert
Ich habe das mal an einem aktuellen Prokejkt ausprobiert, das verwendet 
"heftig" Funktionszeiger-Arrays im RAM. Die Tabellen sind zwar fix und 
"verschwenden" RAM,die Zugriffe auf das RAM sind aber schneller. Das 
Projekt ist ein Emulator, bei der Geschwindigkeitsmessung habe ich auf 
der emulierten Maschine einen Benchmark laufen lassen. Dabei habe ich 
verschiedene Varianten getestet und Folgendes festgestellt (GCC 4.9.2):

- M3 (STM32F107) und M4 (STM32F411) sind bei gleicher Taktfrequenz
   praktisch gleich schnell
- Das Geschwindigkeits-Optimum liegt bei -O2 ohne -flto
- Die Geschwindigkeit liegt mit -flto nur bei ca. 90% des Wertes
   ohne LTO
- LTO macht den Code teilweise um bis zu 25% größer
- -O3 macht gegenüber -O2 den Code größer, meist ohne
   Geschwindigkeitsvorteil

Das ist jetzt sicher nicht allgemeingültig, bildet aber schon mal einen 
Anhaltspunkt. Nach meiner Erfahrung lassen sich die Assembler-Listings 
bei -O2 noch am besten nachvollziehen, bei -Os ist von der 
ursprünglichen "Struktur" oft nicht mehr viel übrig.


Wesentlich mehr hat es gebracht, bestimmte Variablen (z.B. den 
emulierten PC) in Registern zu halten und Inlinen, solange noch genügend 
Flash verfügbar ist. Allein durch die Register-Variablen konnte ich bis 
zu 15% mehr Geschwindigkeit bekommen bei ca. 95% Codegröße.


Übrigens, ein e200z4 (PowerPC VLE, GCC 4.8.0) ist bei gleicher 
Taktfrequenz ca. 1,6x so schnell (bei 1,75-facher Codegröße).

Jörg

: Bearbeitet durch User
Beitrag #5344812 wurde vom Autor gelöscht.
von Nop (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Jim M. schrieb:

> Die haben keinen eigenen I-Cache.

Doch, haben sie, und man stellt den ebenso wie den Dcache über das 
Register FLASH_ACR ein und aus. Freilich ist das nur 128 bit und kein 
Riesen-Teil.

von Joerg W. (joergwolfram)


Bewertung
-1 lesenswert
nicht lesenswert
Gut zu wissen, insbesondere ist auch der Prefetch beim STM32F4 im 
Gegensatz zum F1 per default ausgeschaltet. Das hatte ich übersehen. 
Vielleicht komme ich am WE dazu, noch einige Messungen zu machen...

von Joerg W. (joergwolfram)


Bewertung
1 lesenswert
nicht lesenswert
Es ist schon erstaunlich, bei zugeschaltetem Prefetch, I-Cache und 
D-Cache kann man beim M4 nochmal über 40% mehr Geschwindigkeit 
rausholen. Zumindest in meinem Anwendungsfall, wobei jetzt -O3 minimal 
bessere Ergebnisse liefert.

Jörg

von Markus F. (mfro)


Bewertung
-1 lesenswert
nicht lesenswert
Joerg W. schrieb:
> - Die Geschwindigkeit liegt mit -flto nur bei ca. 90% des Wertes
>    ohne LTO
> - LTO macht den Code teilweise um bis zu 25% größer

Einleuchten will mir das nicht so recht.

Alles was -flto zusätzlich bringt, ist die Möglichkeit zu aggresiverem 
Inlining.

Wenn's langsamer wird, würde das doch bedeuten, dass Funktionen 
ge-inlined werden, die keinen Geschwindigkeitsvorteil bringen, dafür 
aber "Bottleneck-Code" ineffizienter machen? Passieren kann das m.E. 
eigentlich nur aus zwei Gründen: Du hast einen Bug gefunden oder gcc 
kennt deine Cache-Grössen nicht (oder eben falsch).

Schon mal mit l1-cache-size=xxx gespielt?

von Joerg W. (joergwolfram)


Bewertung
1 lesenswert
nicht lesenswert
Man müsste dafür wahrscheinlich nicht schon "vor-optimierten" Code 
verwenden, denn die Dinge, die ich für zeitkritisch halte, sind bereits 
"static inline". Das ist z.B. der Zugriff des emulierten Prozessors auf 
"sein" RAM/IO incl. Code-fetching. Ob das der Compiler auch weiß?

Jörg

von Nop (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Markus F. schrieb:

> Schon mal mit l1-cache-size=xxx gespielt?

Die wird in Kilobytes angegeben. Der D/Icache beim Cortex-M ist 128 Bit.

von (prx) A. K. (prx)


Bewertung
1 lesenswert
nicht lesenswert
Nop schrieb:
> Der D/Icache beim Cortex-M ist 128 Bit.

Es gibt nicht nur einen einzigen Cortex M Core.

von Joerg W. (joergwolfram)


Bewertung
1 lesenswert
nicht lesenswert
Cache gibt es lt. ARM erst ab dem M7. Beim STM32F4xx ist der Cache 
Bestandteil des Flashes. Beim I-Cache sind es 64 Cache-lines a 128 Bits 
(32 Bytes), also 2 KBytes. Der D-Cache ist kleiner und "nur" 256 Bytes 
groß (8 Cache-lines a 128 Bits).

Der Prefetch kann nur dann Waitstates verhindern, wenn ein Programm 
linear abgearbeitet wird. Wobei gerade die (häufigen) LDR-Befehle beim 
Laden von Konstanten zusätzliche Flash-Zugriffe bedeuten, die außerdem 
Vorrang vor den I-Zugriffen haben. Hier kann dann der D-Cache nützen.

Bei CPU-Emulatoren sind die eigentlichen Funktionen meist recht kurz, 
dafür wird viel gesprungen. Bei Sprungtabellen kann die eingebaute 
Srungvorhersage nicht viel ausrichten und die Pipeline muss neu gefüllt 
werden. Beim e200z4, der eine ähnliche Cache-Struktur hat (128 
Cache-lines a 128 Bits), habe ich Teilfunktionen alternativ in ASM 
geschrieben und folgende Erfahrungen gemacht:

Am schnellsten ist es, wenn man auf eine Sprungtabelle verzichtet und 
die Funktionen selbst in eine Tabelle schreibt. Dazu nehme ich den 
Code-Bedarf der aufwändigsten Funktion. Wenn dieser z.B. 50 Bytes ist, 
setze ich vor alle Funktionen in der Tabelle ein .balign 64 und 
verschiebe meinen Offset um 6 Bits nach links. Funktionen, die <= 32 
Bytes groß sind, passen damit komplett in eine Cache-line, die anderen 
in maximal zwei. Man "verliert" dabei etwas Flash, dafür gibt es aber 
mehr Geschwindigkeit. Denn auch der Prefetch lädt immer eine komplette 
Flash-Zeile (32 Bytes).


Wenn komplexere Funktionen dabei sind, die die Tabelle unnötig aufblähen 
würden, springe ich halt aus der Tabelle raus und mache woanders weiter. 
Da der Code für diese Funktionen sowieso meist mehr Takte braucht, kommt 
es auf den zusätzlichen Sprung auch nicht mehr an.

von Walter T. (nicolas)


Bewertung
-1 lesenswert
nicht lesenswert
Danke für die Diskussion!

Frank M. schrieb:
> Rufe doch mal eine Funktion 1.000.000.000 mal direkt auf, dann nochmal
> über ihren Pointer und miss die Zeit.

Von naivem Benchmarking in Verbindung mit einem optimierenden Compiler 
halte ich nicht so viel. Naja, immerhin habe ich hier zumindest keine 
Cache- und Pipelining-Effekte.


Achim S. schrieb:
> die Funktionszeiger selber haben praktisch 0 Overhead.

Ein gewisser Overhead wird vorhanden sein (schon allein für die Prüfung 
auf Nullzeiger) und ist auch vertretbar.


Cache brauche ich an den STM32F1xx und STM32F4xx nicht zu 
berücksichtigen: Haben sie nicht (auch wenn ich die Ausführungen über 
den Emulator nicht uninteressant finde). Es gibt eine Flash-Pipeline. 
Diese dürfte durch einen bedingten Sprung (wegen Prüfung auf Nullzeiger) 
oder unbedingten Sprung (normaler Funktionsaufruf) unterschiedlich 
Effektiv sein - aber diese drei Takte sind kein Faktor, der mich 
interessiert.


Im wesentlichen ziehe ich jetzt einfach mal aus der Länge der Diskussion 
den Schluss, dass diese Sprünge keine besonders großen Effekte haben 
können.

Damit kann ich leben.

von Christopher J. (christopher_j23)


Bewertung
-1 lesenswert
nicht lesenswert
Walter T. schrieb:
> Es gibt eine Flash-Pipeline.
> Diese dürfte durch einen bedingten Sprung (wegen Prüfung auf Nullzeiger)
> oder unbedingten Sprung (normaler Funktionsaufruf) unterschiedlich
> Effektiv sein - aber diese drei Takte sind kein Faktor, der mich
> interessiert.

Die Frage ist, wie oft du dir diese Pause genehmigst. Hast du eine große 
Funktion, welche aus vielen kleinen Unterfunktionen besteht, die 
wiederum sehr kurz sind, wird ein GCC bei -O2 oder -Os einfach alles 
inlinen und dank Prefetch läuft das dann durch wie Butter. Muss er jetzt 
wegen Funktionszeigern jede der kleinen Funktionen einzeln anspringen 
und jedes mal die Waitstates abwarten kann das im Extremfall durchaus 
Faktor 2-4 langsamer laufen. Bei Funktionszeigern auf größere 
Funktionen, die für sich selbst schon mehrere hundert Takte brauchen, 
sollte das aber tatsächlich relativ egal sein.

von Sheeva P. (sheevaplug)


Bewertung
1 lesenswert
nicht lesenswert
Walter T. schrieb:
> Gibt es da Daumenregeln für den Overhead auf den ARM Cortex M3/M4 ?

Es gibt nur zwei Daumenregeln für die Optimierung, und die gelten 
gänzlich unabhängig von Sprache oder Architektur:

1. "Premature optimization is the root of all evil." (Douglas E. Knuth)

2. "Measure, don't guess." (Kirk Pepperdine)

Erklärung: im Zweifelsfall machen Compiler oder Interpreter aus Deinem 
Code etwas ganz anderes, als Du Dir vorstellst. Deswegen helfen 
Faustregeln genau so viel wie Versuche, Erkenntnisse anhand von 
Beispielcode zu gewinnen. Aus diesem Grund ist schon Deine Frage, mit 
Verlaub, unsinnig, und Dein Versuch, ein Programm mit irgendwelchen 
Faustregeln zu optimieren, zwangsläufig zum Scheitern verurteilt.

Die richtige (iSv: einzige zielführende) Vorgehensweise und Reihenfolge 
ist wieder so eine gleichermaßen alte wie allgemeingültige Regel:

1. make it work,
2. make it right,
3. make it fast.

Anders gesagt: bring' Dein Programm zum Laufen, dann debugge es, und 
erst, wenn es fehlerfrei läuft, kannst Du Dir Gedanken darüber machen, 
wie Du es schneller (oder, im Embedded-Kontext, kleiner) machen kannst. 
Meist wirst Du allerdings feststellen, daß der letzte Schritt gar nicht 
notwendig ist, weil das Programm schon ausreichend schnell oder klein 
genug ist.

von S. R. (svenska)


Bewertung
-2 lesenswert
nicht lesenswert
Ein Funktionsaufruf über einen Zeiger kostet ziemlich genau das gleiche 
wie ein direkter Funktionsaufruf auch.

Allerdings kann ein direkter Funktionsaufruf vom Compiler besser 
optimiert werden (z.B. indem bestimmte Register nicht gesichert werden 
oder dank Inlining kein Aufruf stattfindet).

Versuch macht kluch, und heutzutage sollte die Wahl zwischen "wenig mehr 
Komfort" und "wenig mehr Performance" eher auf Komfort gelegt werden. 
(Gilt aber nur eingeschränkt für die Auswüchse, die sonst so getrieben 
werden...)

von Rolf M. (rmagnus)


Bewertung
0 lesenswert
nicht lesenswert
Walter T. schrieb:
> Cache brauche ich an den STM32F1xx und STM32F4xx nicht zu
> berücksichtigen: Haben sie nicht

Doch, laut Datenblatt hat zumindest der F4xx auch einen Cache. Hat Jörg 
ja schon geschrieben:

Joerg W. schrieb:
> Beim STM32F4xx ist der Cache Bestandteil des Flashes. Beim I-Cache sind es
> 64 Cache-lines a 128 Bits (32 Bytes), also 2 KBytes. Der D-Cache ist
> kleiner und "nur" 256 Bytes groß (8 Cache-lines a 128 Bits).

Nur mit dem Fehler, dass 128 Bits nicht 32, sondern nur 16 Bytes sind 
und damit der I-Cache nur 1k und der D-Cache nur 128 Bytes groß ist.

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]
  • [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.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

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