structs, classes, vtable

Wenn mehrere Variablen zusammengefasst einem gewissen Zweck dienen, bilden sie eine Informationseinheit. Eine Informationseinheit kann in C mittels des struct-Typs gebildet werden, welcher mehrere verschieden geartete Variablen zusammenfasst und sie dem Programmierer mittels Symbolen zugänglich macht. Im umgangssprachlichen Gebrauch wird dieses Konstrukt Struct genannt. Innerhalb eines Structs werden die zusammengeclusterten Variablen Felder genannt.

Bei C++ wurden Structs zu Klassen erweitert. Eine Klasse speichert zusätzlich zu den Feldern dazugehörige Funktionen, die sogenannten Methoden. Wenn Klassen ineinander verschachtelt werden, werden Methoden von übergeordneten an untergeordnete Klassen vererbt. Untergeordnete Klassen können dabei sogenannt virtuelle Methoden überschreiben und mit ihrer eigenen Implementation belegen. Damit für Instanzen mit virtuellen Methoden während der Laufzeit des Programmes die korrekten Methoden aufgerufen werden können, benötigt jede solche Instanz eine sogenannte vtable (virtuals table), welche speichert, welche Methoden zum dynamischen Typ gehören.

Details

Grundsätzlich gilt: Ein Struct sowie eine Klasse fasst mehrere verschiedenartige Variablen zusammen. Eine Variable, welche mit einem struct- oder class-Typ definiert wurde, zeigt somit an einen Speicherblock, wo mehrere Werte verpackt sind. Beim Ansprechen eines Feldes fügt der Compiler der Start-Adresse des Blockes einen Offset hinzu und ermittelt somit die Speicheradresse des gesuchten Feldes.

Wie genau die Felder jedoch tatsächlich im Speicher angeordnet sind, darüber herrscht (zumindest beim Autor) eine gewisse Unsicherheit und ist vermutlich zumindest teilweise abhängig vom verwendeten System und Compiler.

Nach Wissen des Autors werden Structs und Klassen stets als zusammengehöriger Block betrachtet. Somit spielt es keine Rolle, wo ein Struct alloziiert wird (Heap oder Stack), die Anordnung der Felder innerhalb des Speicherblockes bleibt immer gleich. Des weiteren werden die einzelnen Felder (nach Wissen des Autors) stets in der Reihenfolge innerhalb des Speicherblockes angeordnet, wie sie vom Programmierer in den Programmcode geschrieben wurden. Dadurch wird dem Programmierer die Möglichkeit gegeben, die Speicher-Anordnung selbst zu steuern und gewisse Eigenheiten der Platzierung der Variablen durch kleine Schwindeleien zu seinem Vorteil zu nutzen. Solche Spielereien werden heutzutags jedoch kaum mehr gemacht und gelten zudem als gefährlich, weswegen hier nicht weiter darauf eingegangen wird.

Die Offsets der einzelnen Felder werden von einem Compiler (nach Vermutung des Autors) stets aligniert. Dies bedeutet, dass jeder Multi-Byte-Wert an einer Adresse beginnen muss, welche durch die Anzahl Bytes des Wertes ohne Rest teilbar ist. Ein 4-Byte-Wert muss somit beispielsweise an einer 4er-Adresse liegen. Dadurch kann es sein, dass bei Hintereinanderreihung zweier unterschiedlich grosser Typen zwischen den Werten zusätzliche Bytes eingefügt werden müssen, um das Alignment zu garantieren. Dieses Hinzufügen von Füll-Bytes wird Padding genannt. Padding-Bytes sind als unbenutzt zu betrachten, der Inhalt ist nicht definiert.

short  a: 2 Bytes
double b: 8 Bytes
char   c: 1 Byte
float  d: 4 Bytes
char   e: 1 Byte
short  f: 2 Bytes
double g: 8 Bytes

|aaaa|aaaa|----|----|----|----|----|----|
|bbbb|bbbb|bbbb|bbbb|bbbb|bbbb|bbbb|bbbb|
|cccc|----|----|----|dddd|dddd|dddd|dddd|
|eeee|----|ffff|ffff|----|----|----|----|
|gggg|gggg|gggg|gggg|gggg|gggg|gggg|gggg|

Bei einem Sparc-Prozessor beispielsweise ist diese Alignierung zwingend notwendig, ansonsten entsteht ein Laufzeitfehler. Bei einem Intel-Prozessor müsste dies nicht zwingend der Fall sein, allerdings sind bei einem Misalignment zwei Speicherzugriffe für ein Feld notwendig. Der Autor vermutet, dass C-Compiler generell (egal für welchen Prozessor) Felder stets alignieren.

Ein Programmierer mag nun versucht sein, seine Variablen so anzuordnen, dass möglichst wenig Padding notwendig ist. Allerdings sind die Effekte bei modernen Computern und Compilern vernachlässigbar und führen nur in den seltensten Fällen zu einer Performance-Steigerung.

Methoden und vtable

In C++ können Methoden über Klassen hinweg vererbt werden, jede erbende Klasse kann somit auf die als protected oder public deklarierten Methoden der Eltern-Klasse zugreifen. Eine Elternklasse kann zudem mittels des virtual-Keywords einzelne Methoden als virtuell deklarieren. Eine virtuelle Methode erlaubt es den erbenden Klassen, bei Bedarf die Methode unter gleichem Namen neu auszuprogrammieren. Das Runtime-System sorgt sodann dafür, dass während der Laufzeit die überschriebene Methode aufgerufen wird, je nach dynamischem Typ der Variablen. Dieser Mechanismus wird Polymorphismus genannt.

Damit virtuelle Methoden aufgerufen werden können, wird für jede Klasse mit virtuellen Methoden eine sogenannte vtable (virtuals table) erstellt. Die vtable ist eine (dem Programmierer nicht zugängliche) Liste von Funktionspointern. Jedes Objekt einer solchen Klasse speichert einen Pointer auf diese Liste.

Die vtable speichert je einen Eintrag für sämtliche virtuellen Methoden der Klasse sowie deren Eltern-Klassen. Die Funktionspointer der vtable sind so angeordnet, dass eine gewünschte Methode mittels eines zur Compile-Zeit festgelegten Offsets angesprochen werden kann. Wenn eine Klasse eine virtuelle Methode nicht überschreibt, steht an der entsprechenden Stelle einfach ein Funktionspointer auf die Methode derjenigen Elternklasse, welche als nächste die Methode implementiert.

Die vtable wird für jede Instanz gespeichert, somit benötigt jedes Objekt mit virtuellen Methoden ein paar Bytes mehr. Der Compiler erweitert implizit jeden Konstruktor, so dass die vtable bei der Instantiierung korrekt gesetzt wird. Somit ist bei einer Klasse mit virtuellen Methoden selbst der Standard-Konstruktor nicht leer, sondern benötigt stets ein wenig Zeit, um die vtable zu setzen. Dies setzt zudem voraus, dass Objekte auch tatsächlich als Objekte instantiiert werden. Die Variablendefinitionen und new-Operatoren von C++ gewährleisten dies. Die malloc-Funktion sollte somit nicht verwendet werden, da die vtable nicht gesetzt wird, was zu fehlerhaftem Verhalten führt.

Der zusätzliche Platz- und Zeitverbrauch kann gerade bei relativ kleinen Klassen (wie beispielsweise Vektoren), welche in grossen Mengen instantiiert werden, stark ins Gewicht fallen. Der Pointer auf die vtable ist auf 32-Bit Systemen 4 Byte gross, bei 64-Bit Systemen dementsprechend 8 Byte. Wenn vom Compiler zudem noch einige Bytes Padding eingebaut werden, kann ein Vektor-Objekt mit 3 floats schon mal 24 Bytes belegen.

(Running 64-Bit)








24

#include <cstdio>

class Vector3{
  float x, y, z;
public:
  virtual void dosomething(){printf("Vector\n");}
  virtual ~Vector3(){}
};

int main(){
  printf("%d\n", (int)sizeof(Vector3));
  return 0;
}

Ist eine Methode nicht virtualisiert, weiss der Compiler stets aufgrund des statischen Typs, welche Methode aufzurufen ist. Somit benötigt ein Objekt KEINE vtable, wenn deren Klasse keinerlei virtuelle Methoden besitzt (inklusive aller Eltern-Klassen).