Tag-Archiv für 'Programmierung'

Bei der Nutzung der Programmiersprache C ist der Softwareentwickler neben den gängigen Optimierungen durch den Compiler zum Großteil selbst für die Optimierung des Laufzeitverhaltens eines Programms und des Speicherbedarfs der Datenstrukturen zuständig. Im folgenden Artikel wird zur Unterstützung bei der Speicheroptimierung das Linux-Tool pahole vorgestellt.

Werden bei der Programmierung in C zusammengesetzten Datentypen wie struct verwendet ist es möglich, dass aus Gründen des Alignments zwischen den Teilelementen der Struktur nicht genutzte Füllbytes eingefügt werden. Zurückzuführen ist das Einfügen dieser Füllbytes auf die Rechnerarchitektur und die Art und Weise wie ein Prozessor auf den Hauptspeicher zugreift. Wenn ein Prozessor Daten aus dem Hauptspeicher liest, dann erfolgt der Zugriff mit der Verarbeitungsbreite des Prozessors. Ist der Prozessor ein 32-bit Prozessor, dann werden in einem Schritt 4 Byte gelesen. Diese Annahme gilt für alle weiteren Beispiele.

Ein Datenelement ist dann richtig im Speicher angeordnet, wenn seine Speicheradresse einem ganzzahligen Vielfachen seiner Größe entspricht. Für diesen Fall kann der Prozessor das Datenelement optimal einlesen (ohne Überlappung und notwendige Verschiebung) und das Datenelement wird als aligned bezeichnet. Werden nun Elemente mit unterschiedlichen Speichergrößen wie unsigned short (2 Byte), unsigned char (1 Byte) oder unsigned int (4 Byte) in einem Verbunddatentyp gemischt verwendet ist es möglich, dass Füllbytes eingefügt werden um das Alignment zu gewährleisten.

Zur weiteren Erklärung soll nun folgende Datenstruktur betrachtet werden:

struct test_data {
        unsigned short alpha;
        unsigned char beta;
        unsigned int gamma;
        unsigned char delta;
};

In dieser Datenstruktur wird zwischen den Elementen beta und gamma ein Füllbyte eingefügt um gamma entsprechend den Alignment-Anforderungen auszurichten. Das Füllbyte ist notwendig, da alpha und beta zusammen 3 Byte, also beispielhaft die Adressen 0 bis 2 belegenen und gamma als Datentyp mit 4 Byte Speicherbedarf auf Adresse 4 ausgerichtet wird. Die Adresse 3 bleibt dann ungenutzt und geht als verfügbarer Speicher verloren. Diese Löcher in den Strukturen sind nicht optimal und können teilweise durch Umordnen der Elemente entfernt werden. Das manuelle Berechnen dieser Löcher ist zwar möglich, durch geeignete Werkzeuge allerdings auch automatisierbar.

Das Linux-Werkzeug pahole (Poke-a-Hole) ist ein Hilfsmittel um Datenstrukturen zu analysieren, Alignement-Löcher zu identifizieren und Umordnungsvorschläge anzugeben. Ziel ist die Reduzierung von Strukturgrößen im Speicher und dadurch die Reduzierung des Speicherbedarfs von Programmen während der Laufzeit. Ein wichtiger Effekt ist außerdem die bessere Ausnutzung von Caches und dadurch eine Beschleunigung des Programms bei Speicheroperationen. Durch die Entfernung der Füllbytes entsteht eine geringere Belastung des Speicherbusses.

Da pahole kein Tool zur statischen Quellcodeanalyse ist, sondern den mit Debug-Informationen ausgestatteten Object-Code untersucht, sind neben dem Build-Werkzeug cmake zum Kompilieren noch weitere Bibliotheken zur Unterstützung des DWARF2-Debug-Formates notwendig. Die Installation erfolgt unter Ubuntu mit:

sudo aptitude install libdw-dev libelf-dev cmake

Der Programmcode von pahole ist aufgrund des Ursprungs in der Linux-Kernel-Entwicklergemeinde im Kernel-Git-Repository verfügbar, man erhält den Quellcode mit folgendem Befehl:

git clone git://git.kernel.org/pub/scm/linux/kernel/git/acme/pahole.git

Unter Ubuntu 9.10 Karmic Koala ist unter Umständen wie in diesem Bugreport beschrieben vor dem Kompilieren noch ein Patch notwendig. Dabei ist der find_library Ausdruck für EBL_LIBRARY in cmake/modules/FindDWARF.cmake durch set (EBL_LIBRARY -ldw) zu ersetzen.

Das Kompilieren und die Installation erfolgt dann im Verzeichnis pahole mit den Befehlen:

mkdir build
cd build
cmake -DCMAKE_INSTALL_PREFIX=/usr ..
make
sudo make install

Das zu untersuchende Programm hello oder Object-File hello.o ist dann mit dem Compiler im Debug-Modus, also gcc -g zu kompilieren. Der Befehl

pahole hello

beziehungsweise

pahole hello.o

gibt dann einen Bericht in folgender Art für alle verwendeten, nicht-anonymen Strukturen aus:

struct test_data {
	short unsigned int         alpha;        /*     0     2 */
	unsigned char              beta;         /*     2     1 */
 
	/* XXX 1 byte hole, try to pack */
 
	unsigned int               gamma;        /*     4     4 */
	unsigned char              delta;        /*     8     1 */
 
	/* size: 12, cachelines: 1, members: 4 */
	/* sum members: 8, holes: 1, sum holes: 1 */
	/* padding: 3 */
	/* last cacheline: 12 bytes */
};

Der hinzugefügte Kommentar enthält für jedes Element die Adresse in Bezug auf den Anfang der Struktur und die Größe des Elementes. Zusätzlich werden Löcher in den Strukturen und die Gesamtgröße der Struktur angegeben.

Neben der Identifikation der ungenutzten Speicherbereiche kann mit dem Befehl

pahole -RC test_data hello

auch ein Hinweis für die Reorganisation der Elemente ausgegeben werden. Im vorhandenen Beispiel wäre dies die Anordnung des Elementes delta nach beta und vor gamma um das Loch von einem Byte zu füllen.

Abschließend bleibt anzumerken, dass die Relevanz dieser Optimierungen auf modernen 64-bit Architekturen höher ist, da durch die größere Verarbeitungsbreite Löcher in den Strukturen häufiger auftreten und diese auch größer sind.