C++ grosser Code vs. Geschwindigkeit

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo OO-Freaks !

Um einen Algorithmus über einen Graphen zu realisieren, erzeuge mir eine Liste von Knoten (mehr als 100.000 Stück), die jeweils wiederum Listen von Kanten enthalten. Je Kante sind weitere Informationen gespeichert.

Wenn ich den Knoten Methoden verpasse, um mit ihren Kanten zu operieren, werden die einzelnen Objekte größer und es passen nicht mehr allzuviele in den Hauptspecher. Andererseits liegt der Code dann jeweils in der Nähe der Daten, auf die er zugreift.

Wenn ich Knoten ohne Methoden baue, und die Funktionalität in das Hauptprogramm einbaue, liegt der Code dichter zusammen und ist klein, die Daten sind aber stets weit weg.

Was ist denn günstiger ?
Hat ein Pentium getrennte Caches für Code und Daten ? Dann wäre wohl Nummer 2 die Wahl, oder spielt das keine Rolle ?

Oder kann es eventuell sogar sein, dass der Compiler das eh optimiert, dass selbst wenn der Code in den Objekten steckt trotzdem nur einmal Speicher für alle Methoden benötigt wird.
(benutze Borland Compiler)

Ich weiss, das sind ganzschön viele Fragen, aber sie laufen letztendlich alle auf die selbe Antwort hinaus:

Was ist günstiger:

vielmals den gleichen Code und den jeweils bei den Daten oder
wenig Code dafür aber Daten weit weg

Vieleicht hat jemand sowas schon mal programmiert und Erfahrungen gemacht.

Ich bin jedenfalls für Hinweise sehr dankbar.

ciao, Christian

#2

Moin,

Ich bin jedenfalls für Hinweise sehr dankbar.

Mehr als einen Hinweis kann ich auch nicht geben: Im ‚Design Patterns‘ war IIRC ein Muster, das dieses Problem addressiert. Kauf das Buch, es lohnt sich auf jeden Fall, wenn Du Dich mit OO-Entwicklung auseinandersetzen willst.

Thorsten

#3

Einen ganz generellen Hinweis zu den OOP-Rules kann ich dir geben:

Der Code wird bei mehreren Instanzen eines Objekts immer gemeinsam genutzt, also nur einmal geladen. Von den Datenfelder hingegeben, bekommt jeder seine eigene Kopie.

#4

Hallo Christian

vielmals den gleichen Code und den jeweils bei den Daten oder
wenig Code dafür aber Daten weit weg

  1. Der Pentium hat 2 L1 Cache’s einen für Daten und einen für den Code,
  2. Der L2 Cache wird in veschiedene Pages aufgeteilt, also es werden nicht nur Daten eingelagert welche hintereinander liegen. Wenn die CPU auf eine Adresse zugreift, werden die nächsten paar Bytes automatisch in den Cache geladen, in der Hoffnung, dass die nächsten Zugriffe auch dort stattfinden werden.
  3. Für die CPU macht es keinen unterschied, in der Geschwindigkeit, ob der Code bei Adresse 0 liegt und die Daten erst bei 2 Megabyte abgelegt werden oder schon bei 1 KByte.
  4. Wenn das Betriebs-System gezwungen wird Daten auszulagern (weil du den Code jedem Datenelement zugeordnet hast) wird’s auf jeden Fall langsamer als wenn alles im Speicher abgelegt werden kann. Die Festplatte ist mindestens 1 Million mal langsamer als der Hautspeicher.

MfG Peter(TOO)

#5

Hi,

Wenn ich den Knoten Methoden verpasse, um mit ihren Kanten zu
operieren, werden die einzelnen Objekte größer und es passen
nicht mehr allzuviele in den Hauptspecher. Andererseits liegt
der Code dann jeweils in der Nähe der Daten, auf die er
zugreift.

Wie schon gesagt, ist es voellig wurscht, wo Daten im Speicher liegen naja, nicht gan, es ist wichtig, in welcher Art Speicher sie liegen (unter anderem zu steuern mit dem „register“ keyword), aber da optimiert der Compiler eh dran rum.
Bei normal (compile-time-)gelinkten Funktionen gibt es fuer jedes Objekt, das Du von einer Klasse erzeugst, nur einen Satz Funktionen - es wird nicht mehr Speicher fuer Funktionen benoetigt wenn Du mehr Objekte der Klasse erzeugst (ein Objekt hat aber eine Mindestgroesse von ein ein Byte, auch wenn es keine Member-Variablen oder Funktionen enthaelt - sonst gaeb es Probleme mit Arrays). Der Kompiler uebergibt den Member-Funktionen bei der Kompilierung die Adresse des Objekts, und wandelt Deine Variabelnamen in objectadresse->variabelname um, ohne dass Du es merkst - so funktioniert das. Wenn Du aber Inline-Funktionen Definition der Funktion im Klassen-Body, oder im selben Header-File mit inline-keyword, wird der Funktionscode an der Stelle des Aufrufs eingesetzt wie bei C-Makros - das kann zu starkem Code-Bloat (das von Dir beschriebene Problem) fuehren! Wenn Du virtuelle Funktionen verwendest (keyword virtual), bekommt jedes Object zusaetzlich eine Liste mit Funktionsadressen, um das gewuenschte Verhalten (Polymorphismus) zu erreichen - auch das macht Objekte natuerlich groesser.
Zur Kompilierung wuerde ich gcc (gpp, g++ djgpp u.a.) empfehlen, da er den Code am besten optimiert. Die Optimierung laesst sich auch sehr gut ueber Optionen steuern.
Um optimal effektiven Code zu erhalten, musst Du in Assembler programmieren - das wuerde ich mir aber ersparen, wenn es sich vermeiden laesst!

Gruss

Thorsten

P.S.:
Alles was ich gesagt habe und vieles mehr) laesst sich in dem hervorragenden Buch von Bruce Eckels „Thinking in C++“ nachlesen, frei downloadbar unter http://www.bruceeckel.com/

#6

Und ich auch noch:

Wenn ich den Knoten Methoden verpasse, um mit ihren Kanten zu
operieren, werden die einzelnen Objekte größer

Wenn Du keine virtuellen Methoden hast, werden die Datenstrukturen "uberhaupt nicht gr"osser, ansonsten kommt pro Datensatz noch ein Pointer zu einer Funktionstabelle dazu. Die Verkn"upfung macht der Compiler (der C+±Preprozessor)

Oder kann es eventuell sogar sein, dass der Compiler das eh
optimiert, dass selbst wenn der Code in den Objekten steckt
trotzdem nur einmal Speicher für alle Methoden benötigt wird.
(benutze Borland Compiler)

richtig.

Was ist günstiger:

Bei deinen Gr"ossenordnungen solltest Du Dir "uber Speichermanagement Gedanken machen, ansonsten haben sich schon etliche Leute zu Graphalgorithmen Gedanken gemacht, auch bzgl. Geschwindigkeit,
s. http://www.fz-juelich.de/zam/cxx/extmain.html

Ciao Lutz

#7

Danke euch allen ! (ohne Text)
einen Text