Unterschied in der Rechenzeit zwischen C++ und Delphi

st3fan85

Hallo,
ich habe begonnen Simulationen zu schreiben und dazu verschiedene Programmiersprachen angeguckt und sie im Bereich Geschwindigkeit verglichen. Am Ende sind C++ und Delphi übergeblieben.
In einer Simulation wurden mehrere Differentialgleichungen numerisch von den Programmen gelöst und C++ hatte dabei die geringste Rechenzeit benötigt. Meistens war der C++ Code 2-3 mal so schnell. Natürlich habe ich, soweit es ging, sehr ähnliche Quellcodes verwendet.
Bei einem zweiten Vergleich wurde eine Monte-Carlo-Simulation gemacht. In dieser Simulation lag die Hauptaufgabe Elemente aus Listen/Arrays zu suchen und diese zu löschen bzw. zu verändern. Hier konnte Delphi C++ tatsächlich abhängen. C++ hatte meistens eine 10 mal längere Rechenzeit als Delphi.
Die zu suchenden Elemente bestehen aus einer Struct und gesucht wurden immer nach x-y-Koordinaten.
In C++ wurden Vectoren verwendet, da Listen mit variablen Längen gebraucht wurden. Als Such-Algorithmus wurde die find_if Anweisung verwendet und dann mit vec.erase(iterator) das Element gelöscht. Das Problem bei find_if ist, dass nur eine unäre prädikaten-Funktion übergeben werden kann, es aber immer zwei Werte gab nach den gesucht werden musste. Daher wurden zwei globale x- und y-Variablen angelegt, worauf die Prädikaten-Funktion dann zugreifen konnte. Für Konstanten und Zufallszahlen wurde die GSL-Bibliothek verwendet.

In Delphi war es ein wenig komplizierter, dort wurde das Suchen mit dem Vergleich jedes einzelnen Elements aus dem Array mit dem gesuchten Wert realisiert. Zum Löschen haben wir dazu immer das zu löschende Element mit dem letzten Element überschrieben und dann das Array verkürzt. Die Reihenfolge der Elemente spielt dabei keine Rolle.

In C++ haben wir auch einmal versucht denselben Suchalgorithmus zu verwenden aber ohne großen Zeitunterschied. Ist es normal, dass Delphi so viel schneller ist als C++, wenn es um das Suchen in Listen/Arrays geht oder haben wir uns ungeschickt angestellt?

Mechanics

@st3fan85 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

Ist es normal, dass Delphi so viel schneller ist als C++, wenn es um das Suchen in Listen/Arrays geht oder haben wir uns ungeschickt angestellt?

Wahrscheinlich letzteres.
Das musst du mal profilen, ist in den letzten Jahren immer einfacher geworden. Und dann findet man meist auch einen Ansatz, etwas zu verbessern. Wenn Delphi schneller ist, wird das einen Grund haben, und das wirst du dann auch in C++ sehr sehr sicher genauso oder besser umsetzen können.

Abgesehen von offensichtlichen Fragen, ob mit Optimierungen kompiliert usw.

SeppJ

Deine Beschreibung mit den globalen Variablen klingt schon wild und ist ein typischer Performancekiller.

Was genau hattest du vor? Alle Elemente aus einem Vektor löschen, die gleich einem von zwei möglichen Werten sind? Erstens ist find_X falsch, wenn man Dinge löschen möchte, sondern nimm remove_X, genauer auch zu lesen unter Stichwort "erase-remove idiom". Zweitens braucht es natürlich keiner globalen Variablen. Die Vergleichsfunktionen die man in die Algorithmen rein gibt, dürfen durchaus auch komplexe Objekte mit eigenem State sein. Schau dir lambda-Ausdrücke an.

st3fan85

Vielen Dank für die schnellen Antworten.
Ich möchte genau ein Element aus dem Vector mit den gesuchten x,y-Koordinaten löschen. Es wird auch nur ein Element mit diesen x,y-Koordinaten im Vector sich befinden.

Ok, globale Variablen sind Performancekiller, dann ist es wohl auch sehr schlecht, wenn ich die Vectoren auch im Bereich der globale Vectoren definiert habe? Ich habe mehrere Funktionen in denen die Vectoren verwendet werden, ist es dann besser die Vectoren immer an die Funktionen zu übergeben?

wob

Kannst du nicht mal konkret den Code zeigen, den du zum Testen benutzt hast?

SeppJ

@st3fan85 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

Ok, globale Variablen sind Performancekiller, dann ist es wohl auch sehr schlecht, wenn ich die Vectoren auch im Bereich der globale Vectoren definiert habe? Ich habe mehrere Funktionen in denen die Vectoren verwendet werden, ist es dann besser die Vectoren immer an die Funktionen zu übergeben?

Ja! Nutz' keine globalen Variablen! Aus zig guten Gründen, Performance als Begründung ist da höchstens auf Platz fünf der guten Gründe gegen globale Variablen. Du solltest auch ernsthaft das Lehrbuch oder den Mentor in Frage stellen, der dich überhaupt auf die Idee gebracht hat.

Außerdem wäre ich sehr an deinen Datenstrukturen interessiert. Deine Beschreibung von den zwei Werten, und dass sie einen Punkt darstellen sollen, klingt ebenfalls verdächtig. So als ob du da kein 2-Elemente Array für Punkte genommen hättest. Merke: Durch saubere Programmierung und Datenmodellierung bekommt man schon von ganz alleine sehr gute Performance.

PS: Das gilt alles auch für Delphi und jede andere Sprache!

st3fan85

Das ist alles auf meinem Mist gewachsen. Meine letzte Programmiererfahrung sind schon ein paar Jahre her. Das einzige was ich gemacht habe ist mal ein Arduino programmiert oder ein paar Daten ausgewertet und da kam es nicht auf Performance an.
Es geht im Grunde um einen Diffusionsprozess auf einer Oberfläche. Für die Oberfläche wird ein 2D-Array verwendet. Jede x,y-Koordinate ist ein Platz für ein Atom. Diese Atome können sich bewegen und wenn sich zwei treffen, bilden sie einen Tropfen. Dementsprechend existieren zwei Vectoren, einer für Atome und einer für Tropfen, die die Position auf der Oberfläche beschreiben. Atome haben nur x,y-Koordinaten und Tropfen zusätzlich Parameter wie die Größe. Bei Tropfenbildung müssen zwei Atome aus dem Vector gefunden und gelöscht werden und ein Tropfen erzeugt. Trifft ein Atom auf einen Tropfen muss ein Atom gelöscht werden und der Tropfen in seiner Größe aktualisiert werden.
Ich versuch den Such- und Löschprozess für die Atome mal grob hier einzugeben.

#include <iostream>
#include <vector>
#include <algorithm>
...
using namespace std;
const int SimSize = 200;                          
int SimField[SimSize][SimSize] = { 0 };  //Oberfläche
int gl_x, gl_y;    //Globale x,y-Koordinaten für die Prädikaten-Funktion

struct monoStr         // Sturktur für Atome/Monomere
{
    int x;
    int y;
};

struct dropStr          //Struktur für Tropfen
{
    int x;
    int y;
    int V;
    double r;
    double RE;
};

vector<monoStr> Monomers;   //Vector für die Atome/Monomere
vector<dropStr> Droplets;    // Vector für die Tropfen

bool find_monomer(const monoStr &monomer)      //Prädikat-Funktion für find_if Anweisung
{
  return monomer.x==gl_x && monomer.y==gl_y;
}

void newMono(int x, int y)   //Funktion für die Erstellung eines neuen Atoms
{
    SimField[x][y]++;
    monoStr nMono = {x, y};
    Monomers.push_back(nMono);
}

void delMonomer(int x, int y)    //Funktion für das Löschen eines Atoms von der Oberfläche
{
    SimField[x][y]--;
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    Monomers.erase(iter);
}

void Diffusion(int Index, int Richtung)
{
//Hier findes der Bewegungsprozess statt und bei einer Anlagerung an einem Tropfen muss jetzt ein Atom gelöscht werden:
delMonomer(Monomers[index].x, Monomers[index].y)
}

int main()
{
do
{
//Hier wird jetzt ein Prozess ausgewählt und welches Atom davon betroffen ist. 
//Beim Diffusionsprozess wird ein Index ausgewählt und die Richtung in die Das Atom laufen soll.

Diffusion(Index, Richtung);

...
}while(t>= t_stop);
return 0;
}

Ich hoffe, dass man die Struktur des Programms einigermaßen verstehen kann. Zusätzlich zur Diffusion existieren noch mehrere Prozesse, für die es auch separate Funktionen gibt.
Ist es dann sinnvoller die Vectoren immer mit in die Funktionen zu geben?
Oder ist hier der Punkt gekommen an den die Zeiger von C++ ins Spiel kommen und nur die Adressen des Speicherbereicht an die Funktion übergeben werden? Das Zeiger-Konzept ist für mich auch ganz neu.

Schönen Gruß
Stefan

TGGC

Es gibt spezielle Datenstrukturen, die dafür gedacht sind Werte zu finden und zu entfernen und ab bestimmten Datenmengen immer schneller sind als eine "bessere" Programmiersprache. Die Perfomance von dem was du beschreibst ist dann durch die Menge der zu lesenden Daten beschränkt und nicht der Sprache.

Bashar

@st3fan85 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

vector<monoStr> Monomers;   //Vector für die Atome/Monomere
vector<dropStr> Droplets;    // Vector für die Tropfen

bool find_monomer(const monoStr &monomer)      //Prädikat-Funktion für find_if Anweisung
{
  return monomer.x==gl_x && monomer.y==gl_y;
}

void delMonomer(int x, int y)    //Funktion für das Löschen eines Atoms von der Oberfläche
{
    SimField[x][y]--;
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    Monomers.erase(iter);
}

Der find_if-Aufruf lässt sich mit Lambdas deutlich verbessern:

auto iter = find_if(Monomers.begin(), Monomers.end(), [x, y](const monoStr& m) { return m.x == x && m.y == y; });

Dann erübrigen sich auch die globalen gl_x und gl_y.

Das Löschen aus einem Vektor ist aber natürlich nicht gerade effizient, weil alle Element nach dem Iterator nach vorne geschoben werden. Ich denke, da verlierst du eher Performance. Wie hast du das denn in Delphi umgesetzt? Das kocht ja auch nur mit Wasser und kann bei einer äquivalenten array-basierten Umsetzung sicher nicht wesentlich schneller sein.

Quiche Lorraine

@Bashar
Auch das find hat eine Komplexität von O(n).

Evtuell sollte man wie TGGC schon andeutete ein std::map ausprobieren.

SeppJ

Wie schon befürchtet:

Konsequent monoStr überall benutzen, wo Koordinatenpaare gefragt sind.
Globale Variablen komplett weg, siehe Bashar
erase-remove idiom benutzen. Das macht das gleiche, was du für deinen Delphi-Code beschreibst, nämlich etwas von hinten an die Löschposition tauschen und dann hinten abschneiden. Das bringt das Löschen (minus das Suchen) von O(N) auf O(1).

Nach 1-3 bist du dann auch garantiert flotter als dein vergleichbarer Delphi Code.

Aber für beide Codes gilt:
4. Was TGGC gesagt hat: Über ganz andere Datenstrukturen nachdenken. Für Simulationen dieser Art gibt es optimierte Arten und Weisen, die Daten zu organisieren, so dass man beispielsweise nicht einen ganzen Vector nach einem bestimmten Element durchsuchen braucht, weil man schon weiß, wo man ungefähr gucken muss. Die passenden Vorgehensweisen hängen natürlich von deinen genauen Anforderungen ab, aber in Büchern über Computersimulationen stehen allerlei gängige Tipps und Tricks, die du mal studieren solltest.

Standardfrage: wurde der Compiler mit eingeschaltetem Optimizer ausgeführt? (Release oder -O3)

Bashar

@Quiche-Lorraine sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

@Bashar
Auch das find hat eine Komplexität von O(n).

Mir gehts hier erstmal darum herauszufinden, wieso das in C++ langsamer als in Delphi ist.

SeppJ

@Quiche-Lorraine sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

Evtuell sollte man wie TGGC schon andeutete ein std::map ausprobieren.

Ich bezweifle dass TGGC das gemeint hat
Er denkt gewiss an Nachbarschaftslisten, zellbasierte Datenstrukturen, und ähnliches.

@SeppJ sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

erase-remove idiom benutzen. Das macht das gleiche, was du für deinen Delphi-Code beschreibst, nämlich etwas von hinten an die Löschposition tauschen und dann hinten abschneiden. Das bringt das Löschen (minus das Suchen) von O(N) auf O(1).

Das stimmt so nicht. std::remove behält die Reihenfolge bei.

Th69

@st3fan85: Und noch ein Tipp; du solltest Str aus dem Namen deiner Strukturen entfernen (bei Strdenkt man eher an einen String).

Und du könntest dir überlegen eine Klasse für deine Daten und Funktionen anzulegen (so wären die globalen Variablen eliminiert).

SeppJ

@manni66 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

@SeppJ sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:

erase-remove idiom benutzen. Das macht das gleiche, was du für deinen Delphi-Code beschreibst, nämlich etwas von hinten an die Löschposition tauschen und dann hinten abschneiden. Das bringt das Löschen (minus das Suchen) von O(N) auf O(1).

Das stimmt so nicht. std::remove behält die Reihenfolge bei.

Argh, stimmt. Bin schon lange nicht mehr auf die Idee gekommen, aus der Mitte von Vectoren zu löschen und verwechsele wie ich es machen würde mit was tatsächlich gemacht wird

hustbaer

Hat jetzt auch nix mit Delphi vs. C++ zu tun, aber das

void delMonomer(int x, int y)    //Funktion für das Löschen eines Atoms von der Oberfläche
{
    SimField[x][y]--;
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    Monomers.erase(iter);
}

void Diffusion(int Index, int Richtung)
{
//Hier findes der Bewegungsprozess statt und bei einer Anlagerung an einem Tropfen muss jetzt ein Atom gelöscht werden:
delMonomer(Monomers[index].x, Monomers[index].y)
}

ist doch verschenkte Rechenzeit.
Erst holst du in Diffusion über den Index die X und Y Koordinaten des Monomers, rufst dann damit delMonomer auf, dann sucht delMonomer wieder den Index anhand der X und Y Koordinaten und löscht dann den Eintrag. Wäre effizienter gleich den Eintrag über den Index zu löschen:

void delMonomer(vector<monoStr>::iterator iter)
{
    SimField[iter->x][iter->y]--;
    Monomers.erase(iter);
}

void delMonomer(int x, int y)
{
    gl_x = x;
    gl_y = y;
    vector<monoStr>::iterator iter = find_if(Monomers.begin(), Monomers.end(), find_monomer);
    delMonomer(iter);
}

void Diffusion(int Index, int Richtung)
{
    // ...
    delMonomer(Monomers.begin() + Index);
}

hustbaer

@st3fan85 sagte in Unterschied in der Rechenzeit zwischen C++ und Delphi:
Wie andere schon erwähnt haben wird wohl das

Zum Löschen haben wir dazu immer das zu löschende Element mit dem letzten Element überschrieben und dann das Array verkürzt. Die Reihenfolge der Elemente spielt dabei keine Rolle.

der Grund für die unterschiedliche Performance gewesen sein.

st3fan85

Hallo,
vielen Dank für die vielen Antworten. Ich muss sie mir erstmal in Ruhe durchlesen und dann meinen Code verändern, oder besser neu schreiben. Eine Frage habe ich schon. Ich habe mehrere Konstanten die in verschiedenen Funktionen verwendet werden. Ist es besser diese in den einzelnen Funktionen neu zu definieren oder kann man eine globale erstellen und diese dann an eine lokale Variable in der Funktion übergeben?

Schöne Grüße
Stefan