Daten in Struct langsamer? C++

[R.A (Gast)]

Hallo,

ich frage mich gerade ob Daten wie int bool double oder auch stl 
container wie map, vector, usw in einem struct langsamere Zugriffszeiten 
haben als wenn sie nicht Teil einer struct sind? Structs sind eben 
praktsich um ein Haufen Variablen als eine in eine Funktion zu 
schleusen.

Zum Zugriff brauche ich ohne struct einfach nur den variablenname.
Mit struct habe ich die struct-variable plus die entsprechende variable 
im struct als Angabe also eine info mehr ist nötig.

Daher wollte ich mal wissen ob dadurch der Zugriff "langsamer" ist oder 
ob das keine Rolle spielt?

Gruß

[Ausprobieren? (Gast)]

Wie wäre es mal konkret auszuprobieren und die Zeit zu messen?

[Dr. Sommer (Gast)]

Das lässt sich pauschal überhaupt nicht sagen. Das hängt vom Compiler, 
dessen Einstellungen, vom Programm drumherum, und dem Speicherort des 
structs ab. Am besten kannst du das durch Testen oder Betrachten der 
Disassembly herausfinden.
Bei Architekturen mit Offsetaddressierung (ARM, x86), dürfte der Zugriff 
auf ein struct-Element über einen Pointer auf das struct gleich sein zum 
Zugriff auf einen Pointer direkt auf ein Element, wenn das struct nicht 
gerade riesig ist. Wenn die struct-Elemente viel in einer Funktion 
genutzt werden, werden die Zugriffe onehin wegoptimiert. Wenn das struct 
als lokale Variable definiert wird, verschwindet das sowieso (solange 
man keinen Pointer darauf definiert).

Ein struct aus Performance-Gründen nicht zu nutzen dürfte in 99,9% der 
Fälle falsch sein. Da gibt es meistens eine Unmenge an anderen 
Maßnahmen, die man zur Beschleunigung zuerst probieren sollte...

Bei Standard Library Containern sieht das schon anders aus. Die 
Zugriffszeiten unterscheiden sich je nach Container (deswegen gibt es 
ja überhaupt auch verschiedene davon!), und in der Spezifikation steht 
wie die aussehen ( siehe z.B. http://en.cppreference.com/w/cpp/container 
). Meistens werden aber ein paar Takte dazukommen aufgrund zusätzlicher 
Indirektion. Aber auch hier gilt, dass das so wenig ist, dass das nur 
einen geringen Einfluss hat, zumal es ohnehin kaum bessere Alternativen 
gibt, denn die Standard Container sind von Experten hochoptimiert.

Im Allgemeinen sollte man erstmal seine eigenen Algorithmen und 
Datenstrukturen optimieren, bevor man mit solchen Details herumbastelt. 
Ein sauber strukturiertes Programm (mit structs und Containern) ist 
leichter zu durchblicken und zu optimieren...

[squierrel (Gast)]

Spielt in der Regel keine Rolle.
Der Offset im Struct ist ja zur Compilezeit bekannt ->
Es wird einfach die Struct Basisadresse + dem Offset verwendet statt 
einer "einfachen" Basisadresse.

[Fritz (Gast)]

Dr. Sommer schrieb:
> Das lässt sich pauschal überhaupt nicht sagen. Das hängt vom Compiler,
> dessen Einstellungen, vom Programm drumherum, und dem Speicherort des
> structs ab. Am besten kannst du das durch Testen oder Betrachten der
> Disassembly herausfinden.

Blödsinn. Das kann man völlig pauschal sagen: Zugriff auf struct-Member 
kostet nichts.

(und für die language lawyer: es sei denn es ist eine C++-Klasse mit 
virtueller Funktionstabelle)

Da hilft auch das "hängt von X, Y und Z ab" nichts. Denn natürlich 
könnte ein bösartiger Mensch einen Compiler schreiben, der sinnlos und 
künstlich Zugriffe auf struct-Member verlangsamt, nur damit jemand im 
Internet versuchen kann, Korinthen zu kacken, aber nachdem das (a) dem 
Compilerbauer nichts erleichtert, sondern (b) sogar Mehraufwand wäre, 
wirst du keinen einzigen C-Compiler in Existenz finden, bei dem das so 
ist.

[R.A (Gast)]

Ok super wenn es gar nichts kostet dann umso besser. Es ist eben einfach 
unglaublich praktisch zur Übergabe von vielen Daten an Funktionen.

[Dr. Sommer (Gast)]

Fritz schrieb:
> wirst du keinen einzigen C-Compiler in Existenz finden, bei dem das so
> ist.

Ich hab einen gefunden: GCC

typedef struct {
  int a [32];
  int b;
} X;
int test1 (X* x) {
  return x->b;
}
int test2 (int* b) {
  return *b;
}

kompiliert für ATmega8, ergibt:

00000000 <test1>:
   0:  fc 01         movw  r30, r24
   2:  e0 5c         subi  r30, 0xC0  ; 192
   4:  ff 4f         sbci  r31, 0xFF  ; 255
   6:  80 81         ld  r24, Z
   8:  91 81         ldd  r25, Z+1  ; 0x01
   a:  08 95         ret

0000000c <test2>:
   c:  fc 01         movw  r30, r24
   e:  80 81         ld  r24, Z
  10:  91 81         ldd  r25, Z+1  ; 0x01
  12:  08 95         ret

Hingegen für ARM Cortex-M3:

00000000 <test1>:
   0:  f8d0 0080   ldr.w  r0, [r0, #128]  ; 0x80
   4:  4770        bx  lr

00000006 <test2>:
   6:  6800        ldr  r0, [r0, #0]
   8:  4770        bx  lr

Und für AMD64:

0000000000000000 <test1>:
   0:  8b 87 80 00 00 00      mov    0x80(%rdi),%eax
   6:  c3                     retq   

0000000000000007 <test2>:
   7:  8b 07                  mov    (%rdi),%eax
   9:  c3                     retq

Bei test1 wird per Pointer auf struct auf "b" zugegriffen, bei test2 
direkt via Pointer.
Beim AVR ist test2 schneller, weil der AVR kein so großes Offset bei 
"LDD" erlaubt, und die manuelle Rechnung ist länger.
Beim Cortex-M3 ist die "direkte" Laufzeit identisch, aufgrund des 
größeren Offsets. Es wird aber mehr Programmspeicher genutzt, was je 
nach Pipeline/Cache-Situation langsamer sein kann.
Beim AMD64 ist dieser Unterschied noch deutlicher.

[Dr. Sommer (Gast)]

R.A schrieb:
> Ok super wenn es gar nichts kostet dann umso besser. Es ist eben
> einfach
> unglaublich praktisch zur Übergabe von vielen Daten an Funktionen.
Besser, mit struct, bzw. "class" in C++ was darauf basiert, kann man 
Objekt-Orientiert programmieren, was noch viel bessere Strukturierung 
der Programme ermöglicht...

[R.A (Gast)]

Ok dann also doch langsamer :-)
Ich schreibe gerade eine Simulation die "schnell" sein soll daher die 
Gedanken zur premature optimization ich weiß der Wurzel des Bösen ;-)
Aber wie gesagt hatte mich einfach auch theoretisch interessiert und 
wenn der Unterschied nur sehr minimal ist dann ist das ok und ich 
verzichte nicht auf die Vorteile der Strukturierung.

[Carl D. (jcw2)]

R.A schrieb:
> Ok dann also doch langsamer :-)
> Ich schreibe gerade eine Simulation die "schnell" sein soll

und deshalb sicher nicht auf einer Kiste läuft, die mit indizierter 
Adressierung Probleme hat.
AVR???!

Bring das Ding erst mal zum Laufen.
Dann messen.
Und zuallerletzt Struktur-Arrays in Array-Strukturen umbauen, wenn klar 
ist wo das (ohne funktionierende Software gar nicht existierende) 
Problem zu finden ist. Es gibt einen C++-Vortrag, wo bei FB polymorphe 
Klassen zerlegt werden, weil die VTables dann nach Methoden und nicht 
nach Klassen gruppiert werden konnten, was wegen besserem Cache-Layout 
einen niedrigen einstelligen prozentuellen Performancevorteil brachte, 
aber massive Lessbarkeitsnachteile. Nur waren 1% Energie gespart in 
allen Rechenzentren den Ärger für die Programmierer wert.
Für einen Prototyp ist das aber genau anders rum.

[Da D. (dieter)]

Fritz schrieb:
> Blödsinn

Tipp fürs nächste Mal: Wenn man seine Argumentation so anfängt, wird 
nahezu jeder Leser erwarten, dass im Rest des Textes kein besseres 
Argument mehr folgt. Was sich auch hier wieder zu bestätigen scheint.

[Tom (Gast)]

Structs/Klassen können in manchen Situationen einen 
Geschwindigkeitsnachteil haben.

Aus der Spiele-Welt kommt der Begriff data oriented programming. Das 
Ziel dabei ist es, sehr große Zahlen an Objekten, über die häufig 
iteriert wird, so anzuordnen, dass die Elemente aller Objekte, die dabei 
relevant sind, direkt hintereinander im Speicher liegen. Das führt zu 
massiv weniger Cache-Misses.

Bastelbeispiel 1.cpp ist eher klassisch objekt-orientiert. Wenn in Zeile 
39 auf ein Element des Array zugegriffen wird, landet ein ganzer Block 
des Speichers im Cache. Da ein Dings-Objekt zum größten Teil aus "name" 
besteht, wird der Großteil der gecacheten Speicherstellen nicht benutzt 
und der nächste Cache-Miss kommt bald.

In Beispiel 2.cpp ist die Position x,y, die beim Iterieren relevant ist, 
von dem name, der meistens nicht interessiert, getrennt. Die Schleife in 
Zeile 46f operiert so auf einem kontinuierlichen Speicherbereich und 
kann die Wirkung des Cache voll ausnutzen.

Auf meinem PC ist mit -O2 die zweite Version um den Faktor ~7 schneller.

R.A schrieb:
> Ich schreibe gerade eine Simulation die "schnell" sein soll

Dabei kann das beschriebene Prinzip relevant sein. Aber wie immer: 
nichts glauben, nichts annehmen, alles selbst messen.

[Dr. Sommer (Gast)]

Erst schön elegant mit unique_ptr, size_t und initializer lists 
gearbeitet... aber dann strcpy, nackte char-Arrays und #define für 
Konstanten... pfui! ;-) Aber ansonsten stimmt es schon. Bevor man solche 
Optimierungen macht sollte man natürlich schauen ob die überhaupt 
nötig/sinnvoll sind.

[(prx) A. K. (prx)]

R.A schrieb:
> Ok super wenn es gar nichts kostet dann umso besser. Es ist eben einfach
> unglaublich praktisch zur Übergabe von vielen Daten an Funktionen.

Aha, jetzt kommt der eigentlich interessante Teil. Es handelt sich also 
nicht um die Frage, ob eine struct extra kostet. Sondern ob die 
Übergabe von Parameters als struct mehr kostet als jeweils einzeln. Und 
das ist eine völlig andere Frage.

In diesem Fall kann eine struct mehr kosten. Variablen werden oft in 
Registern übergeben, sofern genug vorhanden. Bei einer struct, die 
diverse Parameter zusammenfasst, wird hingegen meist die Adresse der 
struct übergeben. Die Parameter sind dann im Speicher und müssen erst 
dort hineingesteckt und in der Funktion wieder rausgeholt werden.

Besser wärs allerdings, du brächtest ein Beispiel. Ist sonst etwas zu 
abstrakt, für wirklich hilfeiche Tipps.

[Chris F. (chfreund)]

squierrel schrieb:
> Spielt in der Regel keine Rolle.
> Der Offset im Struct ist ja zur Compilezeit bekannt ->
> Es wird einfach die Struct Basisadresse + dem Offset verwendet statt
> einer "einfachen" Basisadresse.

So ist es. Natürlich erhöht das addieren des Offsets die Laufzeit, das 
wäre aber genauso wenn es einzelne Parameter wären. Das man im Stack nur 
einen Zeiger übergibt ist am Ende der größere Vorteil.

[(prx) A. K. (prx)]

Dr. Sommer schrieb:
> Beim AVR ist test2 schneller, weil der AVR kein so großes Offset bei
> "LDD" erlaubt, und die manuelle Rechnung ist länger.

Generell kann man sagen, dass die Adressierung einer struct über einen 
Pointer stark von der CPU abhängig ist. Bei manchen 8-Bittern ist das 
recht umständlich, weil sie nur indirekte Adressierung unterstützen. 
8051 beispielsweise.

Umgekehrt kann es einem ergehen, wenn man statische Adressierung von 
Daten einer Zusammenfassung von Daten in einer struct mit relativer 
Adressierung über Pointer gegenüberstellt. Je nach CPU ist mal die 
statische und mal die relative Adressierung im Vorteil. ARMs 
beispielsweise haben es lieber relativ.

[(prx) A. K. (prx)]

Chris F. schrieb:
> Natürlich erhöht das addieren des Offsets die Laufzeit,

Nicht bei statischer Adressierung und auch bei Adressierung relativ zu 
einem Pointer oft nicht. Sofern Offset-Adressierung vorhanden ist und 
dessen Code-Länge nicht in die Laufzeit eingeht.

[Daniel (Gast)]

Daten in einem Struct abzulegen verhindert auch, dass der Compiler sie 
umsortiert oder sogar mehrere Elemente an der gleichen Stelle ablegt 
(bei disjunkter Lebenszeit). Theoretisch könnte er es doch noch machen, 
solange er sämtlichen Code kennt, der von dem Struct erfahren kann, aber 
ich bin da pessimistisch.

Andererseits signalisiert die Übergabe mehrerer Werte über einen Pointer 
auf ein Struct, dass die Werte garantiert nicht an der gleichen Stelle 
abgelegt sind und sich deshalb durch Ändern eines Wertes die anderen 
nicht verändern. Übergibt man Pointer auf die Elemente einzeln, muss man 
mit "restrict" arbeiten um dem Compiler den gleichen Hinweis zu geben.

[Wilhelm M. (wimalopaan)]

Tom schrieb:
>
> Auf meinem PC ist mit -O2 die zweite Version um den Faktor ~7 schneller.

Und wenn Du diese Version nimmst, ist es bei genauso schnell wie Version 
2. Trotz oder wegen std::string!

#include <string>
#include <memory>

const auto SIMULATION_STEPS = 1000;
const auto NUM = (1000UL*1000);

struct Dings
{
    float x = 0.0f;
    float y = 0.0f;
    std::string name;

    void move(float dx, float dy)
    {
        x += dx;
        y += dy;
    }

    void set_name(const std::string& n)
    {
        name = n;
    }
    void set_name(std::string&& n)
    {
        name = std::move(n);
    }
};

int main()
{
    auto data = std::make_unique<Dings[]>(NUM);
    for (size_t i = 0; i < NUM; ++i)
        data[i].set_name("default name");

    for (size_t st = 0; st < SIMULATION_STEPS; ++st)
    {
        for (size_t i = 0; i < NUM; ++i)
            data[i].move(0.01, -0.02);
    }
    return 0;
}

Also nicht zu früh irgendetwas optimieren, was man sich so denkt ...

[Chris F. (chfreund)]

A. K. schrieb:
> Nicht bei statischer Adressierung und auch bei Adressierung relativ zu
> einem Pointer oft nicht.

Ja super, wenn es ein statischer, globaler struct ist, dann nicht. Das 
stimmt natürlich, weil es der Compiler direkt erledigt.

Es ging aber eigentlich doch gerade um Übergabe eines Zeigers auf ein 
Struct an eine Funktion.

[R.A (Gast)]

Ich komme nicht drumherum das zu messen. Noch zum Usecase, der Zugriff 
in der Funktion auf die Daten selbst findet deutlich häufiger statt als 
der Aufruf der Funktion selbst. Die Übergabe natürlich als Referenz.

[R.A (Gast)]

ps: da von bit usw gesprochen wurde, ich kompiliere mit QT C++ mvsc 
64bit auf windows

[(prx) A. K. (prx)]

Chris F. schrieb:
> Es ging aber eigentlich doch gerade um Übergabe eines Zeigers auf ein
> Struct an eine Funktion.

Die Addition des Offset kostet heute bei CPUs oft keine zusätzliche 
Zeit. Bei x86 ist sie ab 486 in der Pipeline unvermeidlich enthalten, ob 
man sie braucht oder nicht. Bei ARM und diversen anderen 32-Bit RISC war 
sie schon immer Teil der Pipeline.

Teurer wird es bei CPUs mit ausschliesslich indirekter Adressierung für 
Pointer (z.B. 8051, AMD 29000), und bei diversen eher kleinen 
Mikrocontrollern und alten CPUs mit einer Befehlslaufzeit von etlichen 
Takten (z.B. 68HCxx, STM8, MSP430).

[Sven S. (boldie)]

Ich hatte mal ein sehr ähnliches Problem, auch bei einer Simulation zu 
lösen, Ich habe es dann so modelliert, dass ich für den Aufbau der 
Objekte usw. alles objektorientiert gemacht habe. Darauf habe ich dann 
auch die Referenzimplementierung und eine optimierte Implementierung 
erstellt. Diese konnte dann gut getestet werden, die Ergebnisse dieser 
Referenzimplementierung waren im weiteren Verlauf auch für die Tests 
hilfreich. Die eigentliche Simulation habe ich dann auf speziellen 
Objekten durchgeführt, bei denen die Anordnung anders war oder Dinge die 
man nicht braucht nicht mit dabei waren. Das hat bei diesem Problem 
schon einiges gebracht, die Erzeugung der speziellen Objekte übernahm 
vor der Simulation eine Art von Übersetzer.
Für mich hatte dies 2 Vorteile:
* Einfach zu durchschauender und verstehbarer Code in den 
Originalobjekten
* Eine Implementierung als Referenz
* Die Übersetzerschicht war sehr spezifisch, aber konnte auch gut durch 
Tests beschrieben und getestet werden.
* Vektorisierung war dann auch möglich durch die neue Datenanordnung.

Bei mir waren die Eingangsdaten relativ wenige, so dass sie am Ende 
perfekt in den Cache passten, die Ergebnisdaten waren sehr viele. Es 
passt zwar nicht auf jedes Problem, aber hier hat es gut funktioniert.